Linked List Data Structure | Insert, Traverse and Delete Nodes in a Linked List | DSA-One Course #36
Linked List Data Structure | Insert, Traverse and Delete Nodes in a Linked List | DSA-One Course #36
Hey guys, In this video, we’re going to learn about a new Data Structure called Linked List. We’ll learn how Linked List is different from Arrays. How we create a Linked List, How to Traverse in a Linked List. How to Insert and Delete Nodes from a Linked List.
🥳 Join our Telegram Community:
Telegram channel: https://telegram.me/realanujbhaiya
Telegram group: https://telegram.me/dsa_one
🚀 Follow me on:
Instagram: https://www.instagram.com/Anuj.Kumar…
Linkedin: https://www.linkedin.com/in/sharma-ku…
Twitter: https://twitter.com/realanujbhaiya
💸 Use coupon code ANUJBHAIYA on GeeksforGeeks to avail discounts on courses!
📚 Complete DSA Playlist: • DSA-One Course - The Complete Data St…
Complete Android Development Playlist: • Android Development Tutorial for Begi…
Hashtags:
#anujbhaiya #dsaone
Ignore these tags:
linked list in data structure
linked list
data structures
linked lists
data structure
singly linked list
doubly linked list
linked list data structure
what is linked list
singly linked list in data structure
linked list in data structures
data structures linked lists
circular linked list in data structure
singly linked list data structure
what is linked list in data structure
linked list in data structure using c
linked list operations in data structure
linked list
singly linked list
insert
doubly linked list
linked lists
insertion in linked list
single linked list
insert node at a specific position in a linked list
circular linked list
insert node
linked list insert a new node as the first node
insert in a sorted linked list
linked list c++ insert node
linked list type
insert a node into linked list
insert beginning linked list
insert node in linked list c++
شرح linked list in c++ - insert node
linked list
how to traverse a linked list
linked list traversal
traverse linked list
singly linked list
program to traverse a doubly linked list
traverse
code to traverse a linked list
traverse linked list iterativery
linked list operations: traverse
algorithm to traverse header linked list
linked list traversal algorithm
algorithm to traverse circular header linked list
traversing linked list
linked lists traversal
linked list reverse traversal
linked lists
linked list
delete a node from linked list
delete
singly linked list
delete node in a linked list
linked lists
single linked list
linked list delete
delete a linked list
linked list delete node
delete in linked list
singly linked list deleting the node
doubly linked list delete node
doubly linked list delete at end
delete a loop in a linked list
delete last node of linked list
doubly linked list delete last node
linked list delete last node in java
Content
0 -> Hey what's up guys Anuj here and welcome to the DSA course
2.362 -> And in today's video we gonna talk about liked list
4.174 -> Before this we have seen multiple data structures in this course
6.773 -> And today we gonna see a new topic which is one of the favorite topics of interviewer in an interview
11.254 -> Multiple type of questions are asked on it.
13.352 -> We will see all those in coming videos
15.006 -> Today we gonna see basics of link list
16.981 -> Because in link list if you have a good hold on basic knowledge , then questions are solved very intuitively inside it
22.126 -> So today we gonna study very basics that how you implement linked list, what is linked list
27.434 -> How you insert inside it, how you traverse inside it, how to do delete operations inside it
31.531 -> So we gonna see all these things in one video
34.213 -> And in coming videos we will be solving questions
36.77 -> So firstly what is linked list
40.145 -> lets talk about this
40.912 -> So linked list is also a data structure that stores data in linear form
44.314 -> So array also does the same work. Array also stores data in linear form
49.552 -> So what is the difference between array and linked list?
51.343 -> So lets talk about what is the difference between array and linked list
54.749 -> After that we will dive deep more inside linked list
57.479 -> So can you see here also in liked list eighteen, sixteen ten, like this you are storing data linearly
63.938 -> How the data is stored non linearly?
66.451 -> So non linear like if you go inside tree, you see inside tree non linear
69.671 -> One node two children
70.729 -> This node two children like that
71.972 -> Similarly graph is non linear
74.581 -> But here your data is stored non linearly
76.887 -> So what is the difference between array and linked list. Lets talk about this
82.402 -> So how implementation is done inside array?
84.104 -> That you first tell the array what is its size going to be
86.68 -> When you initialize the array you tell what is its size going to be
90.888 -> So that memory can be preallocated
93.489 -> Suppose I want to make an array
95.357 -> So you will tell
96.004 -> Like what is the size of this array four plus four eight
98.275 -> So you will first tell it that initialize an array of size eight and pre allocate memory for that
106.265 -> So in this way an array of name a will be created
109.437 -> Now in what way this array of name a will be created?
112.138 -> A will get a location inside memory
115.385 -> Suppose a get location twenty forty inside the array.
118.653 -> After that we will see which type of array is creating
121.219 -> The array is of int type
122.229 -> In inside integer it will be seen
124.047 -> Eight , eight
125.133 -> So what is the size of an integer
126.606 -> The size of one integer is four bites
128.018 -> So four multiply by eight
129.691 -> The memory of thirty two bites will be pre allocated
134.113 -> And your elements will be stored in such a way
137.01 -> First element will be at twenty forty position
139.062 -> Then next one will be here after leaving four bites
140.815 -> Next one will be here after leaving four bites
142.175 -> Next one will be here after leaving four bites
143.368 -> In this way they are stored in continuous manner inside the memory
146.932 -> But in linked list you do not tell in starting that what is the size of linked list going to be.
151.019 -> You do not need to tell
152.184 -> You can store elements dynamically inside the array
154.948 -> You can dynamically add as many elements as you want inside it later.
157.749 -> You cannot do this work here
159.438 -> Here if you want to add more elements you will have to make a new array
163.148 -> You will have to give that array anew size and copy the elements of this array inside the new array
168.213 -> After that you will have to put more elements from behind
170.479 -> There it will work in this way
171.426 -> But in linked list you do not need to do anything like this
174.024 -> Because in starting you do not tell what is the size going to be
175.8 -> You come and put a new element
177.376 -> You put that element anywhere inside the memory
179.367 -> Suppose you had to put element eighteen
181.048 -> What you did you made a node. This whole thing inside it is a node
189.028 -> Three nodes are here
190.137 -> So this is a node
191.349 -> In this concept of node is there
192.446 -> Node carries two things inside it one is data part and other is reference of next node
198.537 -> This requires the reference of next node so that it can traverse further inside the linked list
203.111 -> So suppose we created a node
205.066 -> And we had to store data eighteen
207.343 -> We made a node and said the data of of this node would be eighteen
211.678 -> And next reference of this node will be null for now
214.641 -> So a node is created inside memory at this four two six location
220.654 -> So this us our head
222.348 -> Now if you want to add a new element inside it, new data inside it
225.353 -> So you will say that okay I have to put sixteen
227.013 -> So in what way you will move inside it
228.909 -> First you will go to last
230.424 -> You will come to this two four two six location
232.293 -> And after that you will check if an element is added or not after this.
235.007 -> Yes no element is there after it because its next is null
236.97 -> So you will create a new node
238.492 -> This time a new node will be created in which data will be sixteen
241.647 -> And the address of this new node will come to the next pointer of this current node
248.09 -> So you gave any location to new node
250.293 -> You put the new node at this two four two six location
252.875 -> So in this node we will say the next of this node will be two six two four
256.937 -> So in this way a link is created inside memory
260.771 -> Even if they are not stored together
262.565 -> They are stored at different different places inside memory. You will also be seeing many holes inside the array
265.983 -> Where some other thing may be storing
269.284 -> But it does not matter
270.121 -> Even now we can access elements in continuous manner one by one
274.342 -> How can we do this? Because this element has reference of next node as well
278.06 -> See here it has data eighteen
279.817 -> But of I ask which is the next node after you. It knows that it is two six two four
283.915 -> So I can jump directly to two six two four
285.548 -> So this becomes two six two four
287.06 -> And the data inside this two six two four is sixteen
289.468 -> Which next node does it have?
291.039 -> Which is at next of it?
292.785 -> So two inside two thousand thirty
294.466 -> So if we wanted to insert ten
296.479 -> Suppose ten was here
297.651 -> So if node were present before also
299.452 -> Even then it would not be affected
300.785 -> Node can be anywhere
303.825 -> So we put this node
305.532 -> The dat part inside this node is ten
307.528 -> The address of this node is two thousand thirty
309.278 -> So we did two thousand thirty to its next
311.258 -> And we put null in its next
313.144 -> Because no element is there inside its next
314.483 -> S in this way can you see you have a link so that you can reference the next node
318.763 -> And you need not to tell in the starting
321.01 -> That what is the size going to be
322.676 -> So if you want to add a new node, new data after ten
326.092 -> Then make a new node after ten
328.913 -> And put the reference of that node inside the next of ten
332.2 -> That where that node is present inside the memory
334.016 -> It can be anywhere inside the memory . It doe not matter
335.922 -> In this ay you can traverse inside the element
338.223 -> So this is the funda of implementation inside the linked list
341.026 -> What is the benefit of this?
342.503 -> What is the need of this?
343.875 -> Why we cannot make the array? We will tell in starting what order is going to be
346.955 -> Yes you can do
348.159 -> But array has one disadvantage
350.271 -> What is that?
351.07 -> That if you want to insert a new element inside the array in middle, how will you do it?
355.224 -> Suppose I want to insert element twenty after sixteen
358.574 -> I want to insert twenty here so how can I insert twenty
361.792 -> I cannot directly put twenty here because if I do this, our ten will be lost from here
365.867 -> So I will have to right shift ten first
368.764 -> Then If I right shift ten , then twenty will lost. So I will have to right shift twenty also
372.179 -> I will have to right shift sixteen also
373.316 -> That means you will have to right shift all the elements one by one after the element that you want to insert inside the array
379.712 -> So here the operation becomes O of n
382.859 -> Similarly If I want to delete any element inside this array
386 -> Suppose I want to delete fifteen
387.565 -> I want to delete this element
389.133 -> So how will I delete? I cannot directly delete fifteen
391.397 -> Because I want to store elements in continuous fashion so holes cannot be there inside the array
395.823 -> So what will happen
396.523 -> All the elements will left shift one by one
398.482 -> Eighteen will come in place of fifteen
399.783 -> Sixteen will come here, ten will come here, twenty will come here
402.269 -> So again n operation are taking place here
404.468 -> So can you understand that it has a disadvantage that if you want to insert or delete in middle you have to do shifting
412.441 -> Here you need not to do this
414.978 -> Suppose you want to insert an element in middle
417.234 -> Suppose I want to insert a new element after sixteen
419.703 -> And suppose a big linked list is there after this.
422.11 -> Lets insert hundred after sixteen in middle
425.305 -> So what will I do I will make a new node
427.614 -> inside the memory
429.617 -> In that I will put data hundred
430.785 -> Now I don't mind where this new nod is present. Suppose this is present at memory allocation five thousand forty
435.525 -> It is at this place
436.876 -> No problem. What will I do
438.32 -> I will put reference of this new node inside the next of sixteen
442.058 -> So next of sixteen will be five zero four zero
444.113 -> So I will say five zero four zero will be here
447.149 -> So it means this link will break from here automatically
449.667 -> And this node will be connected with this
451.855 -> And ten was at its next
454.989 -> And I know ten was at two thousand thirty
457.201 -> So I will say next of hundred will be two thousand thirty
459.847 -> And then in this way this link will be created
463.395 -> Because I put its reference here
465.341 -> This put this node's reference
467.259 -> In this way this link is created
468.214 -> So can you see how easily the element is inserted in middle
470.835 -> Similarly if you want to delete any element from middle
473.198 -> Then you just have to change the next reference
474.982 -> Your element will be deleted easily
476.696 -> So no need to do any shifting
478.628 -> In case of linked list it is very easy to insert and delete any element in middle.
481.962 -> So this is the benefit of making a linked list over an array
484.665 -> You must have seen two benefits
485.906 -> First benefit is you need not to tell in starting the size of data structure and linked list
492.58 -> You need not to tell in advance
494.197 -> You can dynamically insert elements inside it when you want
496.901 -> And second benefit is you can insert and delete elements inside it without any shifting
501.546 -> So we have two benefits for which we choose linked lists sometimes over arrays
505.386 -> Now lets move further and see how can you implement linked lists
509.059 -> We will be seeing in Java how linked list is implemented
511.511 -> And how can you do multiple things inside it programmatically
514.839 -> Lets see that.
515.939 -> So lets discuss the basic building block node of linked list
518.959 -> That how node works
520.262 -> Because you connect multiple nodes that make a list
524.085 -> That we call linked list
525.276 -> So basically everything is hidden inside this node
527.967 -> Node has two parts. One part is data and second part is next
532.231 -> You can data type make of any type . You can store any type of data inside it
535.517 -> Either you store integers or characters or strings or any other type of data
541.193 -> Like in array you can store any type of data
543.589 -> But in next you tell the reference of next node
547.801 -> So lets see how you implement this
550.554 -> So we have created class named node
552.645 -> This structure remains saved always
554.878 -> You just change here that at some time int, then at some time character or string or anything
558.634 -> If you want you can make it generic
560.327 -> How will you make it generic
561.583 -> So lets see it first it is like this
563.857 -> Int data, node next, next node will be here because you have to store the reference of next node here.
568.798 -> So that next will be of next type
571.19 -> And when you will have to make a new node, you will be making in this way
574.504 -> You will be calling this constructor
576.349 -> And in that constructor you will tell what data you want to add at this time
579.143 -> And when you will call a new constructor , a new node will be created at some place inside the memory
584.526 -> So this is that node
586.615 -> And the data inside it is equal to this data for now
589.027 -> The data that you are telling here
590.308 -> If you do not want to keep it as int type, you want to do it of any other type in future
593.869 -> Or you want to make it generic
596.452 -> Like we saw in collection framework you tell the array list of integers. Like that
599.772 -> In this way your generic works
602.18 -> Here you tell that it is your integer type array list
605.229 -> If you want to do the same thing inside your node also
607.697 -> It is very easy
609.014 -> While making the node you will tell that this class supports the generic
613.541 -> So here you will put a type t
615.774 -> You can put anything here. I just put t
618.863 -> After that you can remove int from here and say this a T type data
622.463 -> And similarly you will also remove from here
624.977 -> That it is T type data
626.331 -> Now you will not initialize this node in this way
630.513 -> Now you will initialize the node in this way that
632.455 -> Node of type suppose it is integer
635.366 -> You will tell node of type integer like this
637.645 -> Now you will pass int inside this because here T has been of integer type
643.756 -> If you want to make it of string type so you will do node of type string
647.205 -> Then you will pass string here because now this T has type string
651.531 -> So in this way node class is created
654.543 -> And in this way multiple elements run
656.586 -> Lets see that
657.69 -> So this is my main function
658.646 -> I have tried building a linked list here. Lets see how I did this
661.765 -> So first I created tree nodes
663.835 -> I had to put three nodes inside linked list
665.827 -> I have created three nodes. This is n1, this is n2, this is n3
668.721 -> I have created n1 as new node ten
671.151 -> I have created n2 as new node twenty
672.59 -> I have created n3 as new node thirty
674.037 -> Now what will happen after doing this
676.289 -> That inside big memory, at some place n1 will be there, then at sone place n2 will be there, then in between at some place n3 will be there
683.534 -> For now they are not connected in any way
686.097 -> For now these are three nodes present inside the memory
689.607 -> We want to make a chain, linked list of these three
692.143 -> So how will we make it?
692.979 -> So we say it is an convention inside linked list
695.736 -> That we call first node as head
697.622 -> We call first node of linked list as head
700.338 -> So we created a head
701.946 -> We created a reference named head. We have made a node of name head
705.582 -> That we call this is equal to n1
707.861 -> What will happen after doing this
709.17 -> That I will call this n1 node as this is our head
713.464 -> So basically head will be pointing this node
715.663 -> Either you can say point or reference
718.771 -> That head is referencing this node
720.562 -> After that I want to connect n2 with this node
724.525 -> So what I will do n1 dot next
726.205 -> Because in n1 , a field named next is also there
728.815 -> n1 dot next
730.355 -> I can say n1 dot next is equal to n2
732.631 -> After doing this , it will connect with this
735.27 -> n1 and n2 will be connected
736.968 -> Because I said the next of n1 is n2
739.549 -> So if I want to jump from n1 to ne, I can easily do that
742.993 -> If I know n1
743.907 -> I will just do n1 dot next and I will directly jump to m2
748.167 -> Similarly I will do n2 dot next equal to n3
751.301 -> What will happen? The next of n2 will be n3
754.142 -> Now they are connected. n2 is connected to n1 and n2 is connected to n3
758.728 -> Even though they are present at any place inside the memory
760.534 -> In this way these three nodes have been connected
762.99 -> Head and n1 are pointing to this node
765.771 -> n2 is pointing this even now, n3 is pointing this even now
768.191 -> But it does not matter
769.177 -> If n1, n2, n3 are lost inside the memory
772.39 -> And you have only reference of head only
774.278 -> Even then you can go to n3
777.42 -> By iterating
778.546 -> Suppose the references of n1, n2, n3 are lost at any time
782.613 -> We do not know where they are
784.147 -> And you want to find out which element was there at n3 position. Which element was present at third position
788.515 -> Come to head and traverse three times
791.687 -> Come here, then here, then here
793.262 -> Traverse two times. First time here, second time here
795.472 -> So you will reach at third. Because these are not different now inside the memory
798.87 -> A link has made between these
801.134 -> That is why we call them linked list
802.205 -> So in this way linked list is implemented
805.018 -> And inside memory , the work goes on like this
806.832 -> So this is your creation
809.202 -> Now lets see how you traverse inside a link list
811.65 -> So now lets see how can we traverse inside our linked list
814.229 -> Howe can we access every element one by one
816.443 -> So I made a new function
818.344 -> In which I have called the function named traverse
820.212 -> In this traverse function I am accepting a node
823.638 -> Which is head
824.868 -> Because I just nee a pointer of linked list
826.535 -> Even If I get a head pointer for linked list, I will be able to travel inside complete linked list
830.261 -> Suppose this is my linked list ten, five, fifteen
833.181 -> In this first node which is head
834.864 -> I have its pointer
836.168 -> So I can travel inside complete linked list
838.553 -> Lets see how we can
839.737 -> For that I have created a temporary node which is current
842.494 -> And I have assigned that equal to head
844.27 -> So for now I have made it named current
846.658 -> So for now current is pointing this.
848.955 -> Node current is equals to head means current node is pointing ten
852.534 -> Current is pointing this node
853.875 -> And I ran a while loop. While current is not null
856.906 -> Until When current is not equal to null, till then print the data of current
860.988 -> So data of current is ten
862.037 -> So I will print ten
863.577 -> Suppose my output is coming here
865.548 -> So I printed ten
866.832 -> After that current equals to current dot next
869.315 -> Si what is current dot next. Current is this. Current's next is this node
873.13 -> So I am saying current is not current now . It is equal to current dot next
876.558 -> Current dot next is this node. So now current will not point this instead it will point this node
880.761 -> So current is pointing this now
883.134 -> Now we will again come inside the while loop
884.875 -> So if the current is equal to null. So no current is not equal to null for now
887.643 -> Current is pointing this node at this time
888.982 -> So print the data of current
891.367 -> Current's data is five
893.947 -> So we printed five
896.038 -> After that what we did current equals to current dot next
898.558 -> So for now current is at this node
899.866 -> The next of current is this node
901.565 -> So now current is pointing its next
903.64 -> So now current will not point this
905.543 -> Now current will come here
907.104 -> Before current was at this position . Now we wrote current equals to current dot next
911.714 -> So current's next is this so the next of current will become this now.
913.492 -> After that we will again go in while loop
915.411 -> Is current equals to null?
916.322 -> So current is not equal to null . Current is pointing this node
918.797 -> So okay! Come inside the while loop
919.618 -> Print data of current
921 -> So current is fifteen. So we printed fifteen
923.68 -> It is not necessary that you want to print. It can happen that you want to perform an operation
926.976 -> It can happen that you want to find if any element is present or not
929.39 -> So for that you will have to traverse the elements one by one
932.518 -> So in this way you can traverse there
934.159 -> After that we printed. After that current equals to current dot next
938.564 -> So the next of current is null
940.308 -> So current will start pointing null
942.622 -> So now current will come here
944.498 -> And now current is pointing null
946.936 -> Now we will come here again and check if the current is equals to null or not
950.456 -> Yes so we will see current is equal to null
952.54 -> So this condition will become false
954.341 -> Because we will go into it only when the current is not null
956.312 -> But now current has been null
957.859 -> We have found that we have travelled the complete list
961.291 -> And we will come out of this while loop and we have traversed completely
963.912 -> Can you see ten, five, fifteen has printed
966.477 -> Ten, five and fifteen has been like this now
968.065 -> So in this way if you are given a linked list and you have to traverse in it
971.953 -> So if you got the pointer of head, you can traverse the complete list
975.86 -> So we have seen how traverse works
978.603 -> Now lets see if you want to insert any element inside linked list, how do you do that
982.631 -> So now lets see how can you insert an element inside a linked list
986.094 -> Suppose you are given a linked list like this
988.754 -> Five, ten, fifteen, twenty four, forty
990.503 -> And you have to insert the element in somewhere between
992.604 -> So you have told which element do you want to insert
994.848 -> You have told linked list. Because you gave head, so you have got the complete linked list
998.802 -> And you have told on which position do you want to insert that element
1001.92 -> So you want to insert it at third position
1003.529 -> We are taking zero based indexing
1005.605 -> So third position means you have to insert the element at this place
1008.487 -> You have to insert an element in between at this place
1010.659 -> So twenty four and forty will move further a little bit
1012.897 -> And in between a new element thirty will be inserted
1016.353 -> A new element will be inserted in between
1018.31 -> In which data is thirty
1020.032 -> So lets see how can you achieve this
1022.507 -> If you were inside an array what would you do . You would go to this position and right shift all the elements after this
1030.391 -> And put thirty at this position
1032.849 -> Our work would be done
1033.758 -> But you had to do shift operations many times there
1036.094 -> Here you will have to do nothing like this
1037.44 -> But here you will have to first reach at that position
1039.643 -> You will have to first reach at that position where you want to insert this element
1043.314 -> Because it does not have a direct pointer
1044.96 -> To reach at that place
1046.356 -> Because all the elements inside array remains in continuous fashion, so you apply a formula and you can easily jump at that position easily
1052.756 -> Because you know all the elements are inside
1056.135 -> And all of them are taking some specific number of bytes
1059.725 -> So if you want to reach at this place
1061.552 -> Multiply the position with the size of this byte
1064.929 -> Then you can reach at this place. You can access the reference of this place
1068.448 -> Same case is not in linked list because in linked list elements are not stored at same place
1074.016 -> If one is stored here, other is stored here, other one is stored at some different place
1076.356 -> So you cannot reach at that place by directly applying the formula
1079.251 -> But you have reference
1081.013 -> Its reference is here, its reference is here
1082.85 -> So if you want to reach here, you can reach here by traversing
1085.737 -> So first we will do the same
1087.166 -> First we will reach at this place
1088.861 -> We will reach at this middle link
1091.057 -> How can we reach there?
1091.953 -> So firstly this dat. Because we want to insert this data, so this data will not be inserted directly
1096.811 -> First a node of this will be created
1098.265 -> So I have made a node. Node to add
1100.466 -> For simplicity I have taken the data of integer type here
1103.046 -> And I am not typing integer inside node
1105.265 -> If you want you can achieve the same thing by using generic
1108.407 -> Node of type integer
1109.824 -> Equals to new node and in that I passed the data
1112.831 -> So what will happen with it. A new node will be created
1114.484 -> In this way a new node will be created
1115.792 -> It will present inside memory randomly at any place
1118.337 -> For now it is a orphan node
1120.527 -> Now lets see how are we inserting
1122.663 -> So here we will have to handle a special case
1125.564 -> That if the position is zero, then we will have to upgrade the head
1130.983 -> We will have to upgrade the pointer of head
1132.645 -> So for now its head is pointing here
1134.803 -> If you are told that insert thirty at zero position only
1137.987 -> So how will you do that?
1138.89 -> This is your thirty
1140.158 -> You will say the next of this thirty is null at this time
1143.573 -> I make its next as head
1145.17 -> So its next will be head
1146.713 -> So its next will start pointing head
1149.282 -> And then I will say head will start pointing this
1151.67 -> So now instead of pointing this zero, head is pointing this
1155.168 -> So in this way it has become a linked list
1157.146 -> Thirty has come before it
1158.074 -> Thirty, then five, then ten, then fifteen like this
1160.432 -> So in this way thirty has come to zeroth index
1162.591 -> So in this way if the position is zero then you have to do this work
1165.011 -> Then return because you have inserted thirty at zeroth position
1168.072 -> But if you do not have to insert at zeroth position
1170.539 -> So how will you work
1171.941 -> Now lets see that
1172.774 -> So if you want to insert any element, then you will have to find the reference of node just before it
1178.572 -> Why you will you have yo find
1180.215 -> Because you will be doing all the changes at the node which is before it
1183.024 -> Suppose we are inserting the element at this third position
1185.007 -> So I will have to find which node is present at second position
1188.164 -> So I will need the reference of this node
1189.93 -> Why will I need?
1191.205 -> Because what will I do
1192.19 -> Let me remove this from here
1193.522 -> What will I do
1194.915 -> That I will bring a thirty node
1197.032 -> And the next of this thirty will start pointing this
1201.584 -> And the node of this, instead of pointing this, will start pointing this
1207.3 -> In this way your insert will work
1210.025 -> So basically I need reference of this node
1212.512 -> I need reference of this node as well as this node
1214.949 -> Lets see how can we get it
1216.332 -> The important thing is I should get the reference of the position at this node which is just before the position where I have to insert.
1222.608 -> Lets see how can we achieve that
1224.753 -> So I have made a pointer named previous
1227.016 -> That we will be moving further
1228.52 -> For now I have initialized this with head
1230.748 -> So previous will be pointing this
1232.446 -> Because head will also be pointing this
1233.879 -> For now previous will also pointing this
1235.739 -> And I have to take this previous further till here
1238.752 -> I have to deliver this previous node to this node
1241.103 -> So I will have to see how many times I have to run this loop
1243.595 -> How many times I have to iterate this previous to deliver it here
1246.095 -> So if I have to insert my element at this third place
1248.919 -> So how many times I will have to do previous equals to previous dot next
1252.08 -> Means how many times I will have to take this previous further
1254.719 -> So I will take the previous further once
1255.965 -> Then again I will take this further
1257.036 -> So you must be seeing this that if I want to insert my element at any position, then I will have to iterate this previous loop position minus one times
1265.321 -> I have done the same here. I ran a loop that is running position minus one times
1269.073 -> This is running from zero to position minus one times
1271.493 -> And what does it doing , previous equals to previous dot next
1273.547 -> So because here position is three
1276.346 -> So it will run for zero and one
1279.049 -> This will run for i equals to zero and one
1280.045 -> When i will equals to zero, it will be previous
1281.704 -> Previous dot next so previous will happen here
1283.931 -> And in next iteration previous will happen here
1286.765 -> So now previous is pointing this
1288.884 -> It is pointing this and we will come out of this loop
1291.114 -> So we got the reference of this loop that we required also
1294.126 -> Now what will we do
1295.213 -> This is our two add node
1296.705 -> That we created in starting
1299.068 -> The next of two add will be this node
1301.361 -> Twenty four
1302.685 -> And next of previous will be two add
1304.637 -> So the next of two add will be this node
1306.508 -> And next of previous will be two add
1308.587 -> And in this way the link, which was in middle will break , and a new node will be inserted in between
1312.829 -> You will need not to right shift the further elements because they are nit affected by the change that which element came and which went
1318.091 -> So now at third position, this element will come
1320.526 -> This will be at fourth position and this will be at fifth position
1323.326 -> So in this way insert is working
1325.769 -> One more thing . There is one more caviart that we need to understand
1329.613 -> That you cannot alternate these two lines
1331.79 -> That you cannot do the next of previous this
1335.158 -> And then next of to add previous dot next
1338.699 -> Because if you do this
1340.061 -> Like lets travel these two lines in opposite order
1343.995 -> Because we have to do this
1345.331 -> Its next this, its next this
1346.545 -> So lets first do its next this and then we will try doing its next this
1350.167 -> If you do this, you will lost that link and pointer of this node
1354.064 -> If you reverse these two
1355.688 -> So if you do previous dot next as to add
1358.289 -> So the next of previous will be to add
1360.321 -> This link has been made
1362.235 -> Buy you lost this node now
1364.664 -> Now you cannot access this node
1366.879 -> Now you will do to dot next equals to previous dot next
1369.897 -> So previous is this, next of previous is this
1372.549 -> To add is this , so to add dot next
1374.541 -> Means the next of it will start pointing it only
1379.019 -> Now this link will no longer available
1381.156 -> This link will lost
1382.697 -> That is why you will have to be careful. You do not have to loose the pointer of node inside the linked list
1388.581 -> Even though if you want, store them at some place
1391.501 -> Move with a temporary
1393.316 -> Create a new reference
1394.85 -> Store there
1396.816 -> But you do not have to loose the references of your node
1399.513 -> We have to keep this in mind because we stuck many times here
1402.993 -> So whenever you are adding a new link or you are doing reference anywhere, keep this in mind that you do not miss any reference while adding a new link
1413.999 -> You do not loose anything
1415.498 -> So in this way our insert works
1417.622 -> You can run it at any other example
1419.681 -> You see if I have to insert in last
1422.127 -> Means if I have to insert element at sixth position
1424.773 -> So how will that work
1426.307 -> Try checking if the code is blasting or not
1428.535 -> This code will work
1429.873 -> But lets suppose you said that insert the element at tenth position
1433.23 -> position equals to ten
1434.498 -> Your list is of size five
1436.978 -> But you said insert the element at tenth position
1438.624 -> So that is not possible. Here you will do
1440.608 -> So you will not get the reference here
1442.546 -> Here null contraception will come
1443.958 -> We have to see those things
1445.241 -> That if we are not going beyond the linked list
1447.343 -> See these types of things
1448.656 -> So this is our insert working
1450.915 -> Now lets see if we want to delete an element from middle. How that code works
1454.814 -> So I have written the delete code as well
1456.818 -> And it is similar to insert code
1459.45 -> Here also you will be required the pointer of previous node
1462.463 -> You will require the pointer of the node that is just before the node that you want to delete
1465.498 -> Lets see how the logic is working
1467.329 -> So I have made function named delete in which first you pass a linked list
1470.82 -> So to pass linked list, only head is required
1472.37 -> And also tell the position of element that you want to delete
1475.714 -> So suppose you passed head here and you want to delete third element
1480.45 -> This is your linked list. Suppose you want to remove this twelve from here
1482.655 -> So if you remove twelve , so this will be the next of fifteen fourteen
1486.17 -> Basically we want that next of fifteen should be fourteen
1488.478 -> So as soon as next of fifteen will be fourteen will happen
1490.737 -> So the next of fifteen will not be twelve
1492.066 -> So this reference will be removed
1494.031 -> Now if this reference will be removed
1495.415 -> So then when you will travel, traverse inside linked list, you will come to fifteen
1498.564 -> From fifteen's next go to fourteen
1500.373 -> From fourteen's next you will keep moving ahead
1502.082 -> So in this way twelve will be removed from here
1504.194 -> So how will it work. Lets see
1506.008 -> So can you see we will be required the reference of the element that is just before the element that you want to remove
1510.397 -> Because we can say its next that the next of this element will be equal to the next of this element's next
1516.466 -> Are you understanding
1517.567 -> That its next will be equal to the next of its next
1522.024 -> That is what I have written that previous dot next equals to previous dot next dot next
1525.456 -> How is it working . Lets see
1526.742 -> So firstly if our position is zero
1528.893 -> Means if we want to remove head
1530.179 -> We want to remove head element so how can we remove
1532.414 -> You cannot remove head
1534.14 -> If you will say head equals to null
1536.329 -> Then the linked list will end
1537.863 -> You cannot do like this
1538.996 -> So here you will write head equals to head dot next
1541.535 -> So we handled this separately
1542.874 -> That suppose this is head
1544.245 -> And we have to remove zeroth position. So how can we remove
1547.798 -> We will say head equals to head dot next
1549.874 -> So head dot next is this element
1551.242 -> So now instead of pointing this, head will start pointing this
1554.685 -> So head will point this. So if you will traverse inside the linked list , then you will start traversing from here five will go by itself
1560.716 -> There exist a garbage collector inside java
1562.219 -> What is its work
1562.965 -> That if any position, any variable does not have an active reference
1568.1 -> So that keep removing from memory by itself
1570.073 -> So this five has no active reference now , so this will automatically be removed from the memory
1575.059 -> You need not to worry about this where, what will it work
1577.785 -> So this node will stay here but this node will be removed from memory after sometime because no one is referencing this node
1583.714 -> So in this way garbage collector works in Java
1588.212 -> So if the position will be zero then we can move further like this and return
1591.464 -> Our work will end there
1592.751 -> But if we do not want to delete zeroth position
1595.394 -> Suppose we have to delete third position . So how will that work
1597.5 -> So we need pointer of second position
1599.63 -> How are we finding
1600.588 -> Again same manner. I didn't changed this code
1602.599 -> See previous is equal to head
1604.797 -> Then we are iterating position minus one inside it
1606.988 -> And we are doing previous dot next
1608.872 -> So suppose we wanted to remove third element
1610.434 -> Our previous was here
1611.904 -> Suppose our head was here
1613.345 -> And we created previous equals to head
1616.104 -> So from here we will travel two times
1618.239 -> Because the position is third so we will travel two times
1620.016 -> First time we will come here and in second time we will come here
1621.522 -> So our previous will start pointing this
1624.339 -> This will be previous
1625.571 -> Now we just have to write only one line
1627.643 -> That the next of previous will be previous dot next dot next
1631.624 -> So this is previous dot next dot next
1633.838 -> So now it will start pointing this
1635.624 -> And this link will be removed from here
1638.377 -> And now this twelve node will be automatically removed because it will present randomly inside the memory and it does not have an active reference
1644.927 -> Nothing is pointing twelve so twelve will be automatically removed from memory
1648.608 -> So in this way you can delete any element
1651.562 -> Here if you want to check
1653.687 -> Suppose I wanted to delete third element instead of three
1657.32 -> So how will you delete that?
1658.345 -> You have to delete fourth element, so first you will come to this position
1661.267 -> So your previous will be this
1662.441 -> This will be your previous
1664.334 -> What we are doing previous dot next equals to previous dot next dot next
1667.898 -> So previous dot next dot next is null
1669.985 -> So next of previous will start pointing null
1672.66 -> So this fourteen will go from the memory automatically
1674.932 -> Its next will now point this null instead of pointing fourteen
1679.481 -> So in this way you can delete any element from this
1681.675 -> In this way your delete works
1683.082 -> So these were your operations that are always present inside any data structure
1686.864 -> To insert, To delete, To find , to traverse
1690.121 -> So we have seen all these
1691.999 -> How you build them
1693.082 -> We have seen all these things. This is your basics of linked list
1695.204 -> If this is solid clear to you, then after that all the multiple questions that will be coming
1699.517 -> You will play in pointers only
1701.395 -> If you have understood the approach of pointers, after that no question is hard inside it
1707.789 -> You will play all in pointer
1709.761 -> That we will also be seeing in coming videos how multiple questions of pointers work
1713.321 -> We will be doing a lot of questions. Other than that if you need questions for practice, you will get them in the link in description
1719.177 -> With that I am going. If you liked this video, then do like and subscribe the channel . I will meet you in next video. Bye bye.
Source: https://www.youtube.com/watch?v=4tU7d0TTiZQ