2.1 Introduction to linked list | Need of linked list | data structures

see this is what this is a snapshot of memory memory is what I have told you already in many videos that it's a long tape of bytes and each byte see these are bytes and each by it is having its own address suppose I am taking this segment of memory memories or this side all extended in this side in this side also extended so I'm taking open-ended and I'm taking the address started from hundred so the next byte address is 1 0 man 1/4 next byte it is 1 0 2 like this see this memory is very crucial data source in our system we don't have unlimited memory in a computer system fine so it is a responsibility of a memory manager to manage this resource to manage the memory to which process memory is to be located how much memory is to be allocated to which memory is free which memory is allocated now like this fine so memory manager is going to take care of this thing fine now suppose a programmer want some memory in this case a programmer is writing a program and he is going to declare a variable like this in suppose variable name is X fine now when after declaring this variable what happens the memory manager will look at how many bytes four bytes for this integer in typical compilers fine so let us suppose memory manager are located 4 bytes to this X and started from which location started from let us suppose this location from 1 1 to these 4 bytes these four bytes has been allocated to this X and memory manager will tell the programmer that I have allocated to the memory which has started from one one two one two three four bytes fine and suppose he has entered sum here is initialized at runtime this X and he can enter some integer value like 7 so now the programmer suppose we want to store three integers fine so we we have we have read the concept of airings so how he will declare int suppose array name is a and size is 3 so see array is what action of data items which are of same data-type fine so for three integers for three venues the memory manager will allocate how many bytes 3 into 4 that is 2 any bytes fine and then that 12 bytes would be in consecutive continuous location that integer the values of the areas are always stored in continuous locations so let us suppose one complete block of 12 bytes has been allocated suppose from 102 from hundred to this one one one this is free and memory manager has allocated the hello has allocated this block to this a so now programmer has entered three values here now the programmer wants to store one extra integer value an extra value and he wants to extend this array size now he will last through the many memory manager that I want to store one extra value can I extend can you extend the size and I want to extend the same block I want to extend the size of there I am NOT going to declare another variable I am going to extend the size of that I want size of array for now now what the memory manager will do see because in advance the programmer told that I want size for only three integers so he has allocated 12 bytes now what a memory manager will say he'll say I cannot extend the size of your area because I have already allocated that that consecutive block to some other variable because at starting I didn't know that you are going to extend your array size so now programmers will ask what can I do now I won't add a size 4 so now memory manager will say I can allocate you a fresh block of 16 bytes because for for size of the array how many bytes would be required 4 into 4 that is 16 but I cannot extend this block now what programmer will think programmer will think that maybe in future I need to store 10 values fine so it's starting only I asked the memory manager to allocate me the size 450 values for 50 elements that I want my array size 50 now hint en 50 maximum limit now what memory manager will do my many - little bit locate how many bytes 15 - for that is 200 bytes a fresh block of 200 bytes of consecutive locations so these 200 bytes block is from maybe you can say from 122 this 3 109 addresses 3 1 9 these blocks would be allocated to this one but now suppose the programmer only needs to store maximum 10 elements so this space is wasted now because he is going to use only how many bytes 10 into 4 that is 40 bytes he is going to use starting 40 bytes right and remaining memory is what that memory has already been allocated to this arena so memory is not free the memory manager cannot allocate this free memory to another variable but this programmer is not using that memory so this is what the wastage of memory so this is a main drawback of n because of the fixed size because the programmer has to give fixed size of the array in advance at compile time only because of this vestige of memory is there in case of arrays fine now what is the solution of this problem so now the solution of this problem is what length list and here here see if the memory manager has allocated these fresh block then these values would be copied here only so that would be a very tedious work to do and again suppose after some time thus thus the programmer wants the size programmer wants to store 52 elements then again programmer maybe is not able to extend the memory in some cases then fresh a block of 452 452 elements how many bytes 52 into 4 so 2 0 8 bytes would be allocated a new block of to 0 8 byte would be allocated and all the that elements of this previous array would be copied there so very tedious work to ruin Harry's mind the solution is what linked lists so linked lists is also a collection of elements the arrays were also a collection of elements right it is a collection of more than one date items fine link list is also a collection of more than one date items but the only difference is what in linked lists thus this data items are not storing consecutive locations because this in area these are stored in consecutive location continuous location fine now how see if the programmer make a request for one element he wants to store one element fine now the memory manager suppose are located and for integer value for bytes so suppose memory manager has allocated these four bytes right for the request of integer variable and suppose he has stored some value that is for here after this suppose he has made another separate request for one variable that is for storing an integer value so again four bytes would be allocated but it is not compulsory that that four bytes would be allocated consecutive to to this because that is a separate request that is not a requesting form of Eric so suppose now for next request memory manager has allocated from here four bytes right one two three and four and he has stored here suppose three fine now again he has requested two more requests for until for storing integer values so now this is how for the four separate request of four integer values the memory manager has allocated these four blocks to the programmer so see here these four values are also a collection find that is a linked list because here I'm not discussing that he has he has declared like this in text and into I into Z or in Thai something like this not variable separate variables this is also a collection file this is also a list now suppose if this these four are in a collection in array that is fine because these are consecutive locations so if you know this thing the base address of this one you can easily the compiler can easy compute this address of the next one but here we cannot say if this we are at this value in this collection we are at this and visa then we cannot say at where where the next integer is fine in that collection so some extra information has to be stored that is what if with the this thing with this thing with this value if we store address of that next value then we can easily reach to here fine and from here in the list with this second value if we store the address of the next value the next integer value then back we can easily go from here to here and here we can store with this value the address of the next value fine so this is what this is also a collection of four integer values but here the these values are not storing contiguous location we have removed that drawback fine now see so some extra space is to be located with this one for storing address of the next value and address of the next value which variable can store address of any another value that is a pointer variable can store address of some another variable fine so here four bytes would be allocated again because in typical compilers it there for storing the value for showing the address it takes four bytes so see here again four bytes would be located with this one two three and four fine for storing the address of this one right here four bytes would be located for storing address of this one here with this four bytes would be allocated first story this one so total how many bytes would be allocated eight bytes for for this value and four bytes for storing the pointer to the next well right so this is the memory representation logically how we will represent this linked list see four three four nodes one is this one this then in this in this with this for address of next would be stored see suppose address of this is 1 0 2 for three addresses we have started from one one three four eight we have started from one two three and address of this is 132 so here with this four one one three would be stored so this will point to the next node here 123 would be stored so this will point to this node and here 132 will be stored this will point to this node and suppose this is the last node in the list so here null would be stored so in the linked list this complete is known as a node so here you can say this is drawback of linked list with the with this well knew you how to store pointer also so some extra spaces to be located the pointer to the next node here pointer to next node this complete is known as a node here fine so this removes the drawback of array now suppose I want to extend the size of linked list I want to insert one extra element here I want to insert 10 in the in my linked list right now suppose I want to insert 10 here so here can we insert this 10 directly here or the memory manager will allocate space for all the five variables some fresh block would be allocated no why so because these values are not not in contiguous locations so if anywhere space is available for 8 bytes then memory manager can allocate space they are only fine and we can provide link to link into this node for that new node inserted but in array we cannot do this because in array drobik is what all the value should be in consecutive locations fine so maybe sometimes if it is not possible to extend this size in case of arrays now if you want to insert this thing so simply somewhere in memory somewhere in memory suppose address is 200 and Nord is to be allocated memory size of 8 bytes has to be allocated that is known as node and here this 200 would be stored in the link in the pointer part of this previous node fine and here the value is 10 and this is the last one so here you can store none so this is how you can see that insertion in a linked list is very easy so here we can say we have removed that fixed size drawback that was in array no need to specify the size that in the linked list I want ten elements 20 elements are like this you can insert anytime an element from in the linked list so when you write a program in linked list then how we will declare the snowed-in array if I want to declare simply you will write data type array name and size that is very easy but in case of linked list cygnus here this particular node is containing two values and type of two values so is different one is integer value and this one is what address so this is what a pointer not a simple variable this is a simple variable this is what a pointer to types in one node fine so you have to define your own data type fine so that user-defined data types you are going to use that is structure so you are going to write strap so after this struct keyword you are going to give the name of your datatype you want to three it fine here I'm taking the name node struct node so within this you will write C one type want to value the type of one is empty cell so here you will write int suppose of a name of variable is a but this is what for this I will declare this as a pointer because only pointer can store address of another variable and this point there is going to store address of this node right not address of any other variable or any other integer variable this pointer is going to store address of another node fine so here you will write what strap node pointer and name of the point that you can say next so this is how we are going to define our new data type that is struct node the name of the data type is complete this one struct no not only not only known that is struct node and these are members of this structure here you write struct keyword then tag and within this you'll write members man two members are there one is this one one is this one now why I am writing here struct node as you know if you want to declare a pointer which is going to store address of some another integer variable then how you will declare int star P this P is going to store address of integer variable fine if I write float history P it means this P is going to store address of a float variable it means it is pointer to float pointer to in so here this is data type this data type is what this data type is for the variable whose address this pointer is going to store fine now here this is the pointer the pointer is going to store address off this one this one this is what node and data type of this node is what this complete struct node name of data type see this is data type struct node so that is why here I am writing data type that in struct node this is same s Turek and this is pointer name you can write next you can write your hair link it's up to you fine now next thing is this is the linked list now another pointer is there you can say head pointer start pointer it it's up to you this pointer is going to store address of the first node in the linked list address so first node is 1 0 2 so this head is going to point to the first node in the linked list right if you know this this address 1 0 2 if you know the value of this head this pointer they can then you can easily reverse this linked list fine but here random access is not possible in air what is there you can directly if you want to access this three you can directly access this tree compiler can directly compute the address of this three if the compiler know the base address but here if you know the base address that is the address of this firstly the first node that is one zero two and if you want to access this one this node this data you want to access but you cannot directly go here compiler cannot directly compute this address fine that is drawback of this thing because here that data is not in consecutive locations it is in scattered locations fine so if you know this value of this head was 0-2 so here you can go from this node you can go where check out the link part see this is what data part and this is link part of the node fine so check out the link part here the address address of which node one one three it means address of this node so you can go to this node now check out the link part 1 2 3 here address is this one you can go to here 1 2 3 so now you can reach here fine so in link list only sequential access is possible you cannot directly access you cannot randomly access any data fine if you want to access this last data then also you have to traverse the complete list first of all this then this then this after 1 3 2 and after that you can go here fine so this is you can say drawback off this thing so this traversal need or you can say this searching will need the time complexity the time is order of n accessing of any elements need order of N in worst case if you want to access the first element then obviously it is 1 only order of 1 if last means in worst case it is and you have to traverse the unending sin the list so it is order of n but in array it was accessing of any elements will take order of 1 only constant time fine here insertion is easy and deletion is also easy why so because see if sorted air is there like this see let us take an area of size six only four elements we have in there air and I want to insert five here this is sorted area now where you can insert five here you can insert five only fine so you have to do what you have to shift this 40 here here you have to shift 30 here you have to shift 20 here you have to shift 10 and here now you can insert five right so it will take how many shifting of all the elements so order of n if you want to delete if suppose I want to believe this 10 I want to delete this 10 then also you have to shift 20 here 30 here and 40 here then also it is approximately I am going to take order of n fine what it depends the position from where you want to delete and at which position you want to insert the data right if you want to insert suppose between these elements right here one node I want to insert then what you have to update just you have to update see it suppose address this this memory location has been allocated here suppose that the 300 at 300 fine so what you have to do this 300 should be here and this 1 1 3 should be here so this link would be something like this as simple as that right so insertion and deletion is easy in this case rather than array so briefly you can say a linked list is what is it it is a linear data structure it is a collection of data elements which are stored in known consecutive locations next point is some extra space would be required to store the pointers with each value next point you can say insertion and deletion is easier then array next point you can say accessing of any element is going to take order of n time complexity and in array it is order of 1 only next point you can say binary search is not possible in linked list in this fundamental this structure of linked list because binary search in that case we are to find out middle element so here we cannot go directly to middle element so you can say binary search is not possible next point you can say it is of dynamic size so in next video I am going to discuss the basic operations of this linked list traversal insertion deletion something like this with the help of their code as well as we are going to discuss types of linked lists fine so I'll see in the next video till then bye bye

Channel: Jenny's lectures CS/IT NET&JRF

Views: 681,034

Keywords: linked list in data structure, linkedlist, linkedlist in c, data structure, algorithms, what is linked list, what is array, array, ugc net, ugc net computer science preparation, study material, gate, GATE computer science, jenny's lectures CS/IT NET&JRF, jayanti khatri, jennys lectures, engineering, c programming, computer science engineering, computer science youtube channels, it, ds notes, cse, IT, technical, avl tree, bst, coaching classes, b.tech cse, m.tech, sorting algorithms

Id: dmb1i4oN5oE

Length: 22min 10sec (1330 seconds)

Published: Wed Aug 07 2019