Linked List using C | Data Structures Tutorial | Mr. Srinivas

hi everyone welcome to nourish technologies this is strain woz today we are going to discuss linkedlist concept in a data structures and algorithms linkedlist so first of all what is a linkedlist a linkedlist is a dynamic memory allocation collection type first one this is a collection type nothing but collection of elements like arrays stacks queues but this is not static right it is impossible to create a static linkedlist there is no fixed size of a linkedlist a linkedlist is always dynamic collection always a dynamic collection so what is the advantage of a linkedlist so when compared with the arrays and as well as the stacks and queues best comparison right array versus linkedlist so why when we are using okay for example if you take one array if you take one array whenever we want to insert an element into array for example here some of the elements are this 10 20 30 40 50 60 60 of course it is a linear data structure suppose I want to insert a new element here 100 I want to insert I do not want to replace remember I want to insert an element into array so then what will happen first it has to shift all the elements because directly if you insert the 20 will be replaced of course we lost the value 20 data element so first we need to shift all the elements by one location by one location and then we have to insert 60 come to here 50 40 30 20 and then hundred will be inserted here 100 so this is called insertion of an element into an array but here it is to shift the elements to insert an element in your particular position of array it will take a lot of time right accessing is very easy in arrays reason it is an index based and using some internal pointers concept right easily we can access the information in Aris right but whenever we are trying to insert an element or if you are trying to delete an element then it will take a lot of time because shifting of elements for example if you want to delete hundred then again we have to shift all the elements all the elements here it is only four five elements are there but collection is nothing but in a real time lakhs of lakhs of elements we are storing so by the time right instead of using arrays it is better to go for stacks stacks okay right instead of stacks and queues so very important one is a linkedlist concept in a linkedlist right insertions and deletions are much faster when compared with arrays stacks and queues right see here for example how do we insert elements into linkedlist how it will become much faster right see so generally if you want to store elements into linkedlist the data will be stored in the form of nodes in the form of nodes node is nothing but a memory block right how the memory block will be see how the elements will be stored in a linkedlist right for example if you want to store some of the elements like 10 10 20 all these are individual blocks so there is no a sequential order there is no near data structure concept there is no linear data structure of course processing is nothing but in the form of a linear data structure only but storing right not in a side-by-side memory locations no consecutive memory locations concept for example first element it is a block memory allocation just considered to 0 for 6 next suppose this is phi0 for 8 so there is a connection sir how you are connecting 5 0 4 8 we are collecting connecting into another field that I will show you different types of linked list we have single linkedlist W linking list circular linkedlist and all so there will discuss more briefly and here it is here it is a 5 0 4 8 we are storing and here it is supposed 9 double 0 to that we are storing here next for example 7 0 5 to that we are storing here and is linked simply this is a link part this is link part so for example if you want to insert a node in between 20 and 30 no need to disturb anyway these locations are not sequential locations random locations using any expression or using any formula you cannot access write the elements of linkedlist directly impossible you have to travel from one node to another node until write you will get the intended node for example here I want to insert an element just consider 50 50 and then you should break this one we have to connect like this and we have to connect like this then the new element will be inserted in between 20 and 30 for that no shifting of elements so easily we can insert and delete the elements from the linkedlist so this is the only advantage when compared with arrays when we go for a linkedlist instead of arrays this is only the reason ok and how the nodes we are storing right how the memory we are allocating two nodes so what is the structure of node and all we'll see so how the node structure will be so generally generally we have three types of linked lists so mostly so we are using in algorithms three types of linked lists first one is a single linkedlist single linkedlist second one is a double linkedlist double linkedlist and the third one is a circular linkedlist first one is a single linkedlist second one is a double linkedlist third one is a circular linkedlist in a single link at least how the node type will be how the node type here it is a minimum it is having two fields this is what we called node node sir what is this how you will create node in a program very simple a user-defined data type in C language that is none other than structure C struct struct node struct node and how many things two fields surface one is what first one is a data field if you take only one integer here it is a one field sir suppose I want to store employee information like employee number employee name and employee salary then three fields employee number employee name employee self but this is link field this is added field is compulsory so whatever the data no matter link field is mandatory this is pointer field link field so how the node structure will be clearly that will discuss okay so whenever we start discussing about a single linked list by the time I will explain very clearly okay next come to that part double linkedlist here here node and here it is the node is having three fields node is having three fields in single linkedlist so node is having two fields two fields one is a data field and second one is a Link field and in this double linkedlist a node is having three fields this is data and this is a right-side link our link right side no dling and this is left-side node link that is l link these two are pointer type because which is holding address not data this is double linked list and x1 circular linked list is also same just like a double linkedlist only the node is having three fields the node is having three fields data field in some of the cases they may write a left link and right link also simply they will write left and right variables any variable name you can use no matter okay but concept is important so logic is different people will write a different kinds of logic right but finally the implementation should be same okay that is what we call algorithm so these are three types of linkedlist single linkedlist double linkedlist circular linkedlist in double linkedlist and circular linkedlist the node is having three fields one is a data field to link fields and here it is in a single linkedlist node is having only one field right so that is a data field and the next field of course it is mandatory field that is a Link field so totally two fields it contains okay so this is about just a node type node structure so exactly how we are creating the node and how to allocate the memory dynamically right in a program how you will create a node all these things see how we are creating a nodes in a single linkedlist here in a single linkedlist how the structure will be first I will write node structures so this is first node this is second node this is third node and some of the nodes we are writing like this nodes at different memory locations suppose nine zero five eight seven double zero two five zero four eight two zero seven two seven two so first we have to create the structure struct name we are giving node how many fields are there two fields are there what is the first field it is a data field this is data field and this is Link field data suppose consider integer data ten I am storing here it is integer data first field is of type integer type we are storing information but see the second node it is holding the link so what is that link five zero four eight we are storing here Phi zero four eight so that it is pointing so here it is second one is a link sir here question is link is of type what sir we know that in pointers we have type of pointers and untie pointers so type of pointers means the pointer always should pointing to a specific type of data integer pointer pointing to integer data float pointer pointing to float data array pointer pointing to an array structure pointer pointing to a structure so here the pointer is pointing to structure this is another node this is the type is a user-defined data type it is a struct node type so it is a pointer pointing to user defined data type that is a struct node type so pointer link is of type word struct node type link is of type word tracked node type these are the two fields first one is a integer field and second one is a link field that is the struct node type okay so this is a structure so remaining for example twenty and seven double zero two will be stored so that it is pointing next suppose here it is a 3905 it and it is pointing and X 140 no other thing so here it is we are storing a null point no connection from the last node sir who is pointing the first node that you have to declare one pointer variable struct node star that is root variable first to root get memory allocation first of all root get memory allocations are how many bytes are root is a pointer type variable root is a pointer type variable so how many bytes memory will be allocated generally a two bytes memory or 4 bytes memory depends on the size of the compiler we are using if you are using 16-bit pointer size is a 2 bytes if you are using 32-bit the pointer size is of 4 bytes so here it will occupy either 2 bytes or 4 bytes memory 2 bytes are 4 bytes memory so here it is in the root here it is what value will be stored so how memory will be allocated to this node node creation okay node structure is okay but dynamically how the memory will be allocated to this structure that is important already we discussed how to allocate the memory to structures in dynamic memory allocation concept so what is the method we are using malloc method or ml ock we can also call write a Murloc method we are using C here it is Malik Malik and here it is what we have to pass how many bytes you have to pass occupy the memory that you have to pass we do not know because integer size we do not know and pointer size is also we do not know that is depends on the compiler directly you cannot give it 2 bytes or 4 bytes reason right that is from compiler to compiler pointer size varies so it is better to depends on a size of function so here it is size of size of a struct node directly node data type we are passing directly node data right we are passing sizeof struct node so malloc function allocates the memory is our how many bytes are it will allocate only first one right this one will be allocated that we are collecting into root sir can be so directly first time you can assign the value directly and of course with the help of some of the temporary variables and the some more logic is required to exactly assign the value to root variable that we'll discuss briefly right so whenever we are discussing about operations on a linkedlist single linkedlist this is just only a creation so as of now directly I am assigning this is not a correct way exactly root and here it is we are passing and we are converting into struct node type type casting because malloc function return type is a wide pointer we know that it is a generic pointer common pointer it is returning already we discussed very clearly in a dynamic memory allocation in C language yes or no right here it is a malloc function is returning right wide pointer that we are collecting into a variable root root is of type word struct node type so typecasting is important so we are converting typecasting so that 2:07 2 will be stored into root it start pointing to this one always we are maintaining only the first node address into the root variable all the remaining nodes connected from one node to another node that is what we call a linkedlist this is completely dynamic there is no static memory allocation for this one nothing but for the linkedlist okay and how to perform all the operations how to insert the element how to append the element how to delete the element nothing but how to deal node first node how to delete write a middle note how to delete last node how to delete how to display how to sort the elements how to swap two elements nothing but two nodes how to swap all these operations will discuss in the next session okay for more videos please subscribe to nourish id channel thank you thank you

Channel: Naresh i Technologies

Views: 770,669

Rating: 4.9000721 out of 5

Keywords: Data Structures, Naresh IT, Srinivas, Data Structures Demo, Online Data Structures Training, Data Structures Tutorial Videos, Data Structures Overview, Data Structures Interview Questions, Linked List using C, Linked List, What is a linked list, Singly Linked Lists, Linked List Program in C, linked list in c program examples, linked list in data structure, Linked List in Data Structure using C, c with data structures, ds through c, c with ds, linked list in data structure in c

Id: eGnlKPCkAFY

Length: 18min 28sec (1108 seconds)

Published: Mon Sep 26 2016