Understanding Linked Lists and Their Operations

Hello ji, How are you all? this is Love Babbar Welcome to the channel Code help , today we are going to talk about linked list , this is lecture no-44 Here we will discuss all topics related to linked list After this there will be one more video where will solve many questions Lets understand what is a linked list? This is a type of linear data structure Which is formed by collection of nodes We will talk in layman terms , so that you can get the clarity This is a type of linear data structure ,which is form by collection of nodes A node is a combination of , say we have red about encapsulation , there will be capsule There will be some some data members There will be some functions , by combination of both capsule will be formed In node there will be some data , and the address of next node This is a type of linear data structure ,which is form by collection of nodes There are many nodes , node displays data and also the address of next node Linked list is a data structure containing many nodes, and a node looks like this This is a node , there is 3 as data , there is one more node , there is 5, it is at 710 there will be 710 , this is a pointer basically pointing to this node In same way this will be pointing to other pointer There is 7 , here is address of other There is 9 , this is not pointing to anyone It is pointing to NULL Linked list is a data structure containing many nodes , there are many nodes One node contains data , and the address of next node Why we need linked list? There is a case in array , you made an array of size 10 Will you be able to change it on run time? You have ran the code , and now you want make it of 100 size , can you do it? bhaiya , no we have not learned that You can't do it? Before moving ahead in the video , lets talk about Coding Ninjas Coding Ninjas has supported us in this course by supporting the major chunk of the video sponsorship Thanks to them Coding Ninjas is the largest coding education platform where you can access various type of courses if you are interested in paid courses If you want course on web dev , machine learning , development ,OS ,DBMS ,DSA in java , python Then Coding Ninjas is the place for you The best thing about CN is that you get one on one doubt support All your doubts will be resolved within 1-2 hours The courses are really well structured If you will work hard , then you will definitely get the result The course makers have already cracked big tech companies So, you need not to worry about that The courses are available in both Hindi and English languages You will also get hint videos in every question So, if you want to buy any of their courses Then you can use the link in the description to get the 20% off on all of their courses Thank you You have made one vector of int of size 5 , as this will be fully filled Vector is a type of dynamic array Its size will get doubled , it will become of size 10 All these values will be copied In short a new storage is allocated , and values got copied in it Can i say ,this is a optimal case? Is i say there is a 10 sized array convert it to 100 sized array , you don't know how to do it But you know that size gets doubled up after vector get completely filled But here new memory is allocated then the values are copied Is this a optimal case? no It is not optimal , you are taking a new space ,and copying value, it is taking some time So to minimize these thing , linked list is used here 1. this is a dynamic data structure You can increase/ decrease the size at run time There is no memory wastage Here we can see that here we filled the 6th space , but other 4 are getting wasted But here I can change the size at run time , so there will be no memory wastage If I talk about insertion / deletion in linked list Deletion is easy in linked list There is no need to shift In case of array , if I need to put something here Then I have to shift these elements by one place Or I need to delete it , then I need to shift them backward by one So here I can see some benefits of linked list As we will move ahead , we will also know some disadvantages Linked list is a data structure containing many nodes , there are many nodes There is data and address of next node , lets see the example Lets make a linked list Create a node , there is 5 as data and there is address 710 Of next node which is at 710 , there is 8 as data , and 810 address of next node There is 12 , 910 address There is a node at 910 , there is 11 , there is nothing There is NULL , your linked list ends here So in this way a linked list exists Arrays are of this type , it is a continuous This is some address 710 , this is your name ,then there some indexes There use to be some values It use to be in continuous way In linked list there is no need of continuous storage I want to allocate everything in heap , this is the heap , there is one block there is 5 ,then 7, one is 11 This is pointing to this ,this to this then this to this , then this to this , and this is pointing to NULL So this is your linked list, this is your head pointer So you got to know here that there is no need of continuous memory allocation and your data will be stored in this way This is an efficient data structure , you can change its size at run time We seen this example , this pointer name is head This is pointing to this location We call this singly linked list Let me explain the types , types of linked lists The above is the example of singly linked list Then there is Doubly LL Circular LL Circular doubly LL These are some types of LL , 1st we will talk about singly LL Singly Linked list Before understanding Linked list , as I said linked list is collection of nodes So 1st see about nodes , there will be data and the address of next node Lets implement this , then you will understand it Lets say data will be int type and address will be the pointer These are the nodes This is pointing to this , this to this , there address is stored This field is a pointer , this is pointing to a node This is a pointer of node type , are you getting it ? 1st we are taking an int value as data , this address pointer of node type So I have to implement this node Then how will I do it? Lets make its class , class linked list node , we made the class There will data of int type 2nd we need a pointer of node type to store the data Linked list Node * next; Then I closed it So here we implemented a node , there is some data , there will be a pointer containing the address Lets say , we named it node , class node, this is public int data ,Node * next So here I have created a node class , I can create its object in this way Node * node1= new node (); So in this way I have created a node , and can print the data and the address of the 2nd nodelike this Its giving garbage values cout<< node1 -> next << endl; There is giving some garbage values I want that whenever I want to fill a node then I can create it , so I written its constructor Node (int data ),this->data =data ; this-> next =Null; Whenever a new node it created , then constructor will be be called There you will put data , put NULL in the next in starting Now if I run it , node data will be 10 and node next will be NULL so in this way you learn how you can use constructor in the Linked list Did you get it ? , we learned how to implement node There are two things inside node , 1. data ,2. address The data is of int type In address we are talking about the pointer This pointer is pointing to the node , so this is pointer of node type node * next; So in this way I have created node class Lets understand singly linked list Let me make some blocks There will be two things , 1. data , 2. pointer There is 5 , 10 , 12 , 9 This node is pointing to this 710 , there is 810 , here 810 is copied This node's address is 910 , this will be saved here , this is pointing to this There will be NULL because it is not pointing any node In this way when you have single next pointer and a data So this type of Linked list is called Singly Linked list So this is clear to us Lets talk about insertion , how can we insert ? Lets say , 1st I created a node , it is empty , in starting your head will point to NULL When you created a new node ,Node *node1=new Node(10); This is a node , there is 10 inside it this is pointing to NULL, we understood it I want to insert one more node I made a function , InsertAtHead(),lets say I want to make a node taking 12 as input There is 12 , and there will be NULL If I show it here , this is 12 , and this is pointing to NULL I want to connect this node with this, my head is here Now if I want to connect this node with node1 then I will remove the NULL , I have to point it here If it name it temp, temp->next =head /node1 , both are same So I pointed this in this way And I know that head always points to start We have to remove head from here , put it here head = temp, because this location is being indicating by temp So in this way you inserted it There is one new node 15 , 1st I have to create it , this is pointing to NULL Then we have to remove it , will have to point it to 12's node It's mean this statement , then we have to update the head , put it here You got the idea little bit When we will write it , you will get the clarity There is a function , void InsertAtHead() , Inside it we are sending head , from this we will know where we have connect this node Node* &head, int data , why I have taken reference , I will explain it in few minutes Whenever is any new data ,we create a new node , Node* temp=new Node(d) Then my next step is , the new node that I have created I have to point it to the NULL temp-> next=head; In 3rd step , you have to change the node to which head is pointing, head=temp; So in this way you have inserted a new node at head Bhaiya but why you have taken reference here ? Here I have taken reference , because I didn't want to create a copy , I want to make change in my original linked list So that why I have taken reference here Lets 1st write a print function , which will print our Linked list we will learn how to traverse a linked list In starting we will give the head , for printing also reference is needed? no . but I didn't want to make a copy So how we will print Assume that I have an linked list , there is a block ,this is pointing to this This is pointing to this , then this is pointing to NULL There is 3, here 5 , here 7 Head is pointing to this, we named it That's it, now I didn't want to update it , so I made a variable temp node* temp=head So you made one more pointer, and pointed to it Then you told to print this , current node -> print Then you move the temp by one in forward direction Then you are doing the same work in loop Until you reaches NULL Lets make a temp , Node * temp =head while(temp !=NULL ) , cout<< temp-> data << " " ; Then move temp by one , now temp is here I want to go here , this address is already here temp= temp-> next I want temp to go from this location to this This is already stored here , , temp =temp-> next From this I will move to next location before going there we used endl , for better visibility So here I created a new node And I pointed head there Then I said to insert , insertAtHead(head ,12) Now my state will be like this , 1st 12 then 10 Lets print it , here I inserted head , after inserting we will print it Lets run it , there is little problem Lets clear it and run it again Write temp properly, again ran it 1st it was 10, if I show you here lets comment this , lets run it again 1st there was 10 Then we inserted 12 , show it is printing 12 ,10, same thing we have seen here 1st it was 12 then 10 If now I insert 15,so 1st 15 will come , then 12 ,10 Lets see , so if I make one more call ,insertAtHead(head ,15) So then your answer will be 15 , 12 ,10 Lets run it , 15 ,12 ,10 , so in this way you are understanding that , we created a linked list but bhaiya it is happening in revere way If I say 10 , then a node of 10 is created , And it is pointing to NULL , then I insert 20 , which is pointing to 10, then it is pointing to NULL Now if I have put in this way 10 , 20 , 30 So 30 will be at 1st place , then it is pointing to 20 , then to 10 , then 10 is pointing to NULL Or if I have put data in this way 10 , 20 ,30 ,40, 1st 40's node will be created , then 30 , then 20, and 10's node I want if there is this type of input , so I want that 1st 10 will come , then 20 , then 30 , then 40 I want this We can do it , for this we have to keep a tail What do you mean by tail? The way I am using head , insert at head Now I will create a function , which is insertAtTail(0 , which will always add new node after the ending node Tail will be a pointer of node type , which will always indicate to the last node Did you get it? the way you kept head , same way you have to keep tail In starting I also created tail , Node* tail=node1 When there will be single node , then you will call same node as head and tail void insetAtTail(node*&tail, int d) In short 1st I have create a new node ,then I said Now I created a node of 12 , this is pointing to nulll You will point tail's next to this node tail->next=temp So we remove this from line no. 30, and pointed it in this way Tail will always point to last node , and this is the last node So change tail from here to here tail=tail->next Bhaiya explain it once, now this block is containing this address And I want to go to this address , so point tail to its next So in this way if any node comes , we will put it in last Lets run it , I change it to insertAtTail lets run it There is some problem It is printing 10, 12 ,15 Node* tail =node1 , and then printed it, our answer came 10, then we said to insert at tail A node is created for 12 , then tail-> next =temp then tail=tail->next Tail = temp Lets run it, still it is not working there is some little mistake here I have to pass tail, then I ran it Before it was printing 10 ,then 12 ,10 , then 15 ,12 ,10 Now it will print 10 ,12 ,15, it is working properly You have seen both the things You know insert at beginning , insert at end /tail 3rd insert in middle For this what I need to do Lets say I have this linked list , there are four blocks I gave input to insert 22 at 3rd position here a new node is created , you removed this connection from here You pointed it here , and it here Now your linked list changed to this Here you inserted a new node ,then there are the old nodes You gave the position and the data , and by this your pointer got changed , so this type of linked list is formed Linked list is like English only , simple thing Now you know the steps , 1st I pointed it here Then you removed this connection and pointed it here , you have to just to convert Hindi language into code Here I am making insertAtPosition( int position ,int data ) I cleared it, 1st I need to reach this position 1st I was here , then I moved here If I have to go to the position 'n', then I am going up to 'n-1' Lets say nodeToInsert->next=temp->next Then I have to remove this pointer , and point it here Its name is nodeToInsert ,temp->next=NodeToInsert Your work has been done by these to statements Lets write it , 1st I have to traverse node*temp=head int cnt =1 , we are at starting If I have to got to the 3rd position , then I need to move forward by one So I have to go to 'n-1' node So I ran a loop , while (cnt <position -1) temp=temp->next cnt++ So we have understood this For this 'd make a node Node* nodeToInsert =new Node(d) NodeToInsert ->next =temp->next , we have to point it here remove this connection and point it here temp->next =NodeToInsert Lets call it , run it Insert 22 between 12 and 15 insertAtPosition (head ,3 ,22), then you printed it lets run it So here you inserted 22 at 3rd position ,in short you also ran it there are some cases that we need to cover , as here I say to insert 22 at 1st position It is unable to do it ,why? Lets see , because we have started from 1st position , and to insert we always requires the previous node Here we put a case , if (position==1)insertAtHead(head,d), can I run it now ? Lets run it , now it is working There is still some problem , we need to return it, lets run it So we inserted 22 at starting Lets talk about the last node Here I have inserted 10 ,12 ,15 , three things Now if I want to insert at 4th node , we have already solved the case for middle And for starting here ran it, if I write 4 , in that case also it is working properly There is one mistake , if you inserted at 4th, then your tail should also get updated In this whole function we didn't updated the tail So you need to update the tail also head is already getting updated So you are getting it Or you know the length of linked list , if( len == position-1 ), insertAtTail(tail ,d) But you don't know the length, are you getting this? We know that there is a case where we have to insert at last How will we handle it? When you will reach the last node , you said my current linked list is of this type I have to insert at 4th position , so your temp will be pointing to this And your node will be pointing to NULL 1st you pointed it there , which is pointing it So you also pointed it to NULL Then you cut it from here , then you connect it like this And we knew it but the tail which was pointing here It is still pointing here , I want to bring it here How will it happen? So if I write a simple condition , when I am adding this temp->next=NULL, it means I am adding at last In that case update the tail if (temp->next==NULL ) Here I call ,insertAtTail( tail,d) Here you returned it So here you created a generic code where you can insert at anywhere In short here you have to pass tail also Lets run it , code is working properly To verify head and tail ,we will print it In same way I will write for tail to verify it Then I ran it So head is coming at 10 Tail is coming at 22 , so we written a code of insert , where if we want to insert at start, we can do it If at end then also ,at middle also So in this way you have learned insertion in linked list, insertion at any position You also learned to traverse it, here you have written print function, you learned this You will learn to delete As we can insert any node in same way we can also delete any node Lets talk about it, how to delete ? Lets talk about next process , deletion Lets say I have this linked list , and I have to delete a node delete Node (position) , or deleteNode( value), and comparing it with every element I will implement this , and you will implement this by your self, take it as homework Here we will compare data values Lets see by deleting this position So we created a function , void deleteNode(position ,head) Now I have to delete a position , it can be any position Tail is beneficial to us , that's why we should keep it, if we want to insert at end , then we can do it At starting head will be pointing here tail is pointing here , take tail as option Provide me the position and I will delete it , it can be from 1 to length Lets do it lets think , this is thew linked list case.1 I ma deleting middle node I want to delete this node , how I will do it? remove this connection and point it to this Now this looks like this And this is pointing to this , free its memory Now your state look like this , this 1, 2, 4, so you deleted it in 2 steps You wanted to delete this node , temp->next=current-> next So by this statement you pointed it here and cancelled out it This is for middle node Lets say i want to delete the last node , then what will happen ? This is my linked list 1,2,3,4 I want to delete this , this is my current node This is my previous node , here we are representing temp as previous previous -> next = current -> next, which is NULL In short you removed this connection and pointed to this There is no need to do extra for last node Then I will free it 3rd case ,I want to delete the 1st node There will be no previous node If this is my linkedlist 1,2,3,4 This is my head , and I want to delete it , so this is current there is no previous , so previous is NULL , As I will write previous -> next, this means NULL->next NULL pointer exception , it will give error, so this will not work for start So handle it by different method I have given position , if (position ==1) else, deleting any middle node or last node Lets understand it, if i have delete 1st node Then how we will do it? I have to bring head here , then we will free it from the memory head=head->next then I freed the memory ,Node* temp= head ,delete temp In same way , if I go in the class , then I have to write destructor ~Node () ,int value=this->data, why we are doing I will explain if(this->next!=NULL), then free it So this is the code to free the memory Memory is free for node with data , I stored it at line no.18 , so that I can tell that I have freed it Here we are freeing the memory So 1st position we deed it in this way We m oved head forward and freed the memory Lets say I want top delete the 3rd node I have to keep current pointer here , and previous pointer here At starting I am at head node I moved 2 times forward , in case of 3rd position 1wst make two pointers Node* cur=head , Node* prev=NULL int cnt=1 while(cnt<position) For 3rd it will run two times With every iteration move it forward , cur and prev If I have to moved them forward then how I will do it This is my linked list At starting cur is here , and prev will be NULL cur=cur->next So you pointed cur here Before doing this , 1st you have to point prev here So you 1st said prev=cur, so this became two step process 1st there was current , prev was NULL 1.This is the linked list , prev is pointing to this , and cur is also pointing to this prev=cur In 2nd step you will write cur=cur->next Before current was here Now it is here prev=cur, cur=cur->next cnt++, then we will write prev->next= cur->next In this way you also deed this , in this case this pointer would have come here Then I have to free it, delete cur, so I also deed this part Deletenode(1, head) , then I printed it lets run it, there is some problem 1st 22 is getting free , then for 15 , then 12 , then for 10 There is some problem Somewhere we are trying to excess NULL and there it is creating problem Whenever we are freeing the memory This 3 is still pointing to this , before deleting it , we have to remove this Because our destructor's code has been written in this way I don't want that which is not required points to another memory , which is our data , I want to remove it So I want to remove this before deleting this Here I am deleting temp, 1st temp->next=NULL Here cur->next=NULL By adding this we removed this, now this is pointing to NULL If we talk about this case , if we talk about 1st node , it will also get stopped Because this is pointing to this , so I have to remove it In short , I initialized it as NULL Now if I run it, 1st it deleted 10, 12 ,15,22 are remaining Delete only 4th node , then will it run ? There is segmentation error Lets try to understand it, it is wrong here , lets run it It ran successfully, here we have deed mistake in loop So here we deleted 22 Now if I say to delete 15, so it deleted it So now we have written a generic code for deletion, which can delete any node We have to keep in mind how to delete 1st node Whichever node you ant to delete , set the previous pointer as NULL So here you have understood how deletion works in linked list Now you have seen insertion , traversal , and deletion also And this is the generic code So here you have understood singly linked list, we will do the questions One thing keep in mind , when we written delete code , then we handled the head case But has my tail came to the right position ? Lets check it So I printed it here , run it So my tail is still at 22, it is working properly If I have deleted the 4th node So tail is pointing to some garbage value So this is your homework , when I delete last node , then how will you handle the tail Tail case is optional , so see it, when you do deletion then how will you handle tail Idea , use the previous position and how we identify last node, use them it will be solved Linked list are the steps coming in your mind I never practised linked list from any interview it is simple to do So here we understood the singly linked list Lets talk about the 2nd thing , Doubly linked list What is this? here just node's structure is getting changed There are three things in the node ,1. data , 2. previous Lets make it in abetter way , so that you can understand it in a better way This is your node , there is 1. data , lets say 5 , 2. pointer, which is pointing to next node 3.previous pointer In singly linked list you had data and pointer of next node, here you have data and pointers of next and previous node This is your doubly linked list This is next , then this is pointing to NULL This is its previous , this is its previous previous There is 3 ,5 , 7 This is data , this is next pointer , this is previous pointer Every node has two pointers previous and next, previous indicates the previous node , next indicates the next node So this is your doubly linked list Lets code it, it is simple to do There are 3 things 1. data 2. previous ,3. next So you created a node class , here you created 3 things , 1. data ,2. previous 2. next Then you made a constructor of node type, where you took a value this-> data =d this-> prev=NULL this->next=NULL in starting , so in this way you created a constructor If here you make a node , Node* node1 =new Node(10) I have to print it, void print(Node* head) ,Node* temp=head while (temp!=NULL), print the temp data , and increment it cout<<endl; So you have written this print function also I cleared it , I have made this node , now print it Node* head =node1 I ran it It printed 10 Lets say I need a function which give the length of linked list int getLength(Node* head) , written the same code which is here int len=0 at starting You have to increment it here Here you have to return it cout<< getLength(head)and ran it My length comes 1, you we saw two functions We learned to find length , traversal In same way I have written a function here , insertAtHead(head,11) Then you printed it Here we have to create it Now here I have to add it , lets understand how to do it In starting there can be a node Lets see how we used to insert in singly linked list Create a new node , put head there Then bring it to the write position , lets do it here Create a new node ,7 Your head is pointing to this node , this is NULL , and also this in starting You 1st created this In 2nd step , I will point it here Then point it to here , it means temp->next=head 3rd step , head->prev=temp, that's it Then we bring head here This is temp , head= temp, this is your 4th step in 4 steps you finished the game 1st you created a node , Node* temp=new node(d) Next step ,put temp->next= head head->prev=temp Then place head to its correct position , head =temp Lets run it Lets put space here , Lets run it , 1st it was 10 , then I put 11 In this way I have created a doubly linked list I have put every pointer to its correct position So we have understood this If I 2-3 more nodes for 13 ,8, then ran it 1st it was 10 , then 11 ,10 , then 13 ,11 ,10, then 8 ,13 ,11, 10 So I have learned to insert If I have to insert at tail , void insertAtTail(Node* & tail , int data ) Lets 1st see the code of singly LL Now if I have to understand about insert at tail, it is easy In singly LL , we had created a node , then pointed last node to new node then updated the tail , three steps For example ,This was our linked list ,this is the new node 1. create this new node 2. tail->next=new node Then we have to update the tail , tail=temp Here also we will do the same This is our Doubly linked list this is pointing to NULL , these are the prevs There are 3, 7, 9, this is the head , and this is the tail When I say this is head , I am talking this whole node , when I say tail I am talking about this node If I want to insert a node here 1.Create a node , this is pointing to NULL There is 13 2. Connect this to this , its name it tail and its temp ,tail-> next=temp temp->prev=tail 4. Tail is at wrong position , tail=temp Lets implement it , Node* temp=new Node(d) tail->next=temp temp->prev = tail tail=temp Here I am explaining you Till my linked list is of 8 ,13, 10 ,11, at end I have to insert 25 insertAtTail(head, 25), then I printed it head Here I have created a Node* tail=node1 Now I ran it, 1st it was 8 ,13 ,11, 10 , now it has become Lets run it again , clear it It was 8, 13, 11 ,10 , here I put 25 at end at line no. 76 so it is working successfully , so we have also written the tail function So now we know to insert at head , tail , in same way if I go back to singly linked list Insert at any position , can I do it? void inssertAtPosition (head ,int position, int data ) We will implement the same algorithm If position is 1 , then do insertAtHead, copy paste it If you have to insert at 1st position , then you gave head , the data In this way we have to do something, we will copy it and make the change in it There is temp pointing to head int cnt=1 , then we are moving forward The position at which we have to insert , we are moving towards it We reached the last position , here we passed tail; At last position we returned it If I have to do in middle , then we will use these three lines Lets say I have to put a node here 1st step is to create this node, which we have already done at line no.80 This is my temp, node to insert , make logic according to this My next and prev are pointing to Null We have to point this next here ,2.nodeToInsert->next=temp->next temp->next->prev=nodeToNext It is simple ,temp->next->prev=nodeToNext This is nodeToInsert 4.temp->next=nodeToInsert 5. nodeToInsert->prev=temp So you pointed four pointers to their right place There should be no confusion We brought this pointer here , temp->next Then we did temp -> next->prev=nodeToInsert temp->next=nodeToInsert ,we removed this connection , and pointed to this This is pointing to NULL , so we pointed it to temp, nodeToInsert->prev=temp Lets write it here Temp->next -> prev=nodeToInsert temp->next=nodeToInsert nodeToInsert->prev=temp Lets print it, so this is your current linked list Now I have to insert 100 at 2nd position, insertAtPosition(tail,head ,2,100) My answer should be 8, 100 ,13 , 11 ,10 ,25 I ran it , it is working properly Same thing but at 1st position, 101 Now I have to insert 102 at 8th position It is working properly , so we have written all the 3 functions Now we can insert anywhere I simply copied the code of singly linked list , and changed it little bit And in this way created doubly linked list code We seen the traversal , insertion In doubly linked list we show insertion , we can insert anywhere In starting you have created a node , I want to start from '0' Assume that we removed this node , in starting the head is NULL And tell is NULL Now what will happen , lets run it, its is giving segmentation fault There is some problem in code , we went to print the head Here we have put Null, there should be no issue In starting there is no node , so when we do insertAtHead () , then what's happen ? A new node is created , temp->next=head , head->prev=temp , here head is NULL There is problem ,if(head==NULL), then handle it differently, here the same will be implemented So we have handled this case , Node* temp=new Node(d) Now this is your head , head=temp If we want to include tail , we didn't need it that much Here I have put tail and updated it here So you handled it like this If i want to handle same thing here , If ( head==NULL ), then I will handle it differently , and esle part differently We did the same thing here Did you get it? Here You passed a tail also tail=temp Here you passed head , and updated it here So you handled two cases here So you handled empty case here ,and here also If you go here , then you can handle this , here we will also pass head Here also I have to send tail So we have handled it here , lets run it It is working properly , but here there is some problem In the last entry ,lets understand it Here , we said insert at tail Here we will print head and tail once In this tail 's data I am copying it here and here We can do it using print function also Lets run it , 1st is was 11 , then 13 ,11, head in on 13 ,Tail is on 11 It si correct , up to 101 our code is working properly At last position it gave segmentation fault , here last position is getting handled Here we will do temp->next==NULL, so we are inserting at tail esle, in this way What's wrong here , lets see Lets prints the values , cout<< "tail" << tail<, endl; We are trying to access a NULL pointer , that's why it is giving segmentation fault Lets run it again Tail is at 25 , so NULL is not there Here segmentation fault is coming , after printing tail 25 and head 101 Here there is some problem We given 8, 13 ,11 ,25 I got the issue We said to insert at 8th position , but we have to insert at 7th position Because we have deleted one node at starting , now lets run it It is working properly , in short our input parameter was wrong So we have handled this case , where there was nothing at starting of linked list Same thing we have to handle in future , in our singly LL After that ,insertatposition () , there is no need to handle , because we are putting in middle This is simple , so you have to handle this case in case of empty linked list So we have deed insertion , also handled the edge cases Then we show traversal , and print Now we want to delete If I talk about deletion Lets copy this and paste it here So we have moved to deletion , this is for deleting your starting node Lets say ,if I make a linked list here There are 3, 5, 7 . I want to delete it This is head , so to delete starting node what I need to do? 1st I have to point this pointer to NULL Then This will become the starting node , if this is my temp temp->next->prev=NULL So you made it NULL Make this pointer to also point NULL This is temp->next=NULL Now this is 3 pointing to NULL , head is here This node is pointing to this Now I have to bring head to its correct position , 3.head=temp->next so I need to do this before I have to do this here 2. temp->next ,and this becomes my 3rd step now I have to free this memory in 4th step by calling the destructor 1. Point this pointer to NULL head=temp->next temp->next=NULL In last you freed the memory by calling the destructor Lets code it, temp->next->prev = NULL Lets remove this , then head = temp->next temp->next=NULL then we have to free the memory Here I have write my own destructor ~Node (), int value=this->data if(next!=NULL) , in this case delete next next=NULL cout<<" memory free for node with data "<< value<<endl; So we have written the logic of deleting at starting Then it can be middle or last element In this way we moved ahead , now I just need to delete the current node We have reached the state , assume this is our linked list , this is prev NULL and this is next , this is its prev In same way , Lets say I want to delete this node , then I named it current and its prev What steps I need to take? lets understand it Remove this connection from here , make it NULL This is currnt->prev=NULL So ,Remove this connection from here , make it NULL Next will be prev->next=curr-> next It moved here , you corrected this pointers This is pointing to NULL , this is the next node , then you made it to point NULL This node's prev is NULL , next is also NULL In this case this was last pointer that's why it is pointing to NULL But if this was a middle node , then this would be pointing to some other node Then I have to correct this pointer also , curr->next=NULL So I marked this also as NULL Now I have to free its memory , lets write it Curr->prev=NULL, ,lets remove this from here Curr->prev=NULL prev->next=curr->next Curr-> next=NULL ,then you have to free the memory , delete curr So in this way you have written the code for deleting, lets run it Here linked list is of size 7, there is nodes Lets delete one by one Lets 1st delete the 1st node , deletenode (1, head) Then we printed this I have to delete 101 , so here we have deleted 101 , an rest are there It is working properly Now I want to delete any middle node I have to delete 25, 6th position So 25 was there , and you freed its space , so it is working properly Lets run for 1st position again , you have to delete 101 , so it is working properly then I said to delete 25 at 6th position , so we have freed it Now I want to delete at last position , 7th ,I deleted it If we see carefully ,102 has been freed but tail is at wrong position As I have seen it in singly linked list , I have gave it to you as homework As here I have handled head, in same way you have to handle tail in homework In same way here also this is for homework So we saw insertion at any position traversal, and deletion also at any node So here we have learned the concepts of doubly linked list This is simple to do We are thinking and coding it, there are only some steps So here we also completed doubly linked list Lets move to our 3rd topic , Circular linked list As we have learned singly LL few minutes ago There will be data , and the pointer , which is pointing to this We only deed some changes in it , lets say there was 3 ,5 , ,9 ,12 So singly LL was pointing to NULL like this Now the last node will point to 1st node So we called it a circular linked list , this part is same as singly linked list But your last node rather pointing to NULL ,it is pointing to 1st node If we will try to traverse it, then we will print 1st this , then this ,then this ,then this , you will move in a loop according to previous logic In same way your doubly linked list can be also change to doubly linked list This is prev , it is pointing to NULL , this is the next , there is data there is also data , in same way And this is pointing to NULL So this is our doubly linked list , if we do little changes here , rather pointing this to NULL If I point it to this , and this to here , then it will be also converted in circular doubly LL I will show you by solving 1 case , how a circular linked list will be formed The way we made doubly linked list by copying singly LL , in same way you will implement this, this is for homework Lets try to understand this case , how this works? There is a linked list , there is some data, this is pointing to next node , then this to this This is also pointing to next node , this is pointing again to 1st node So this is my circular linked list , node structure is same here There will be a data variable , then there will be Node* next This class is going to remain the same and we will try to implement it How to insert, traverse and the deletion part Before moving ahead let me shoe you the link If you go to guided path at Code studio , you will get the notes of linked list , and some good questions also Here I got some notes of linked list ,from where I can clear my concept more Here are some task also , solve them , you will also get the important questions that are asked in companies So here you can see lots of problems There are many links , let me show you Till now we have just opened 1st link , here I am getting more things Here it is written asked in Amazon , Microsoft , Adobe , etc So you can solve questions at code studio Lets move to our topic , here we are implementing circular linked list Lets create node , class Node , int data ,Node* next: Then I created a constructor data , this->data =d this->next=NULL So you deed this , in same way if I want to create destructor here ~Node(0 , int value =this->data If (this->next!=NULL) , delete next and next =NULL Here I will copy paste it So here I printed it, so here I have written the destructor Now I have to insert , one function use to insertAtHead() Then insertAtTail() insertAtPosition (0, 3 functions In circular LL it is little different We don't use head pointer , we only use tail pointer Here our list is circular , if I simply take tail pointer By using it I can add at tail , and at head also If I have reach 1st node from last node, if this is tail then I will write tail->next It is pointing to head node , so there is no need to create head, I can use head and tail by tail pointer only Lets create these functions We can't tell from where linked list is starting and from where it is ending I will give you data in input , as you get the data , then create a new node after that If this is a linked list ,there is 3 , then 5 , then 7 , then 9, then 9 is again pointing to 3 If I give 7 as input data , then you are searching for 7 , it is there Then you will create a new node for 11 , and you pointed it here ,then you removed this connection 3, 5, 7, 11, 9then circular So according to this data we will insert a new node You can do anything , but I want insert it according to this data I made a function, insertNode (Node* &tail ,int element, int d) Lets understand it, 1. It can be an empty list Where tail is NULL , in this case you will create a new node You put data in it, oit is pointing to itself 1. you created new node , pointed its next to itself, 2. tail=temp 3.temp->next=temp So we are understanding the 1st case Lets talk about 2nd case , when there is only one node , and you want to add one more There is one node , which is pointing to itself , and here I want to insert 1 more node , there is 5 , and it is pointing to NULL In input I will give data , by comparing it, insert after this , and a data from which I will create a node This is the data , and I will compare it with this So this is clear to us , then I searched , here we got 3 This is my current node , we named it temp I want to put 5 after 3 1st step , it si pointing to something curr->next is pointing to some thing Lets save it ,Forward =curr->next Now I want it to point here , so I want it to point at temp Now this temp is pointing to null , I pointed it to where curr->next was pointing , temp->next=forward , it can be optimized So by using thease 3 we made this linked list This is 3 , it is pointing to 5 , 5 is again pointing to 3, did you get it? Lets say , now I have two nodes 3, 5 Now I can put a node after 3 or I can put it after 5 Lets see the 1st case , here I want to put before 3 Lets say , this is 3 , and this is 5 , and this is pointing to this I have to insert a node here 4, it is also pointing to NULL 1.Create a node 2.Store where this is pointing , forward =curr Lets optimize it it , I want it to point here , I can call it curr->next temp-.next=curr->next In short, You cancelled this NULL , and brought it here , this is the 2nd step 3rd ,I want it to point here , curr->next=temp 1.Create a node ,2.Store where this is pointing , forward =curr,temp-.next=curr->next 3rd ,I want it to point here , curr->next=temp This is pointing to this , this to this , and again this is pointing to this So this is your 1st logic , if i try to optimize it Then we can optimize the same logic 1st create the node ,temp->next=curr->next These 3 lines can be used here 2nd case , I want to put a node before five , this is 3 , this is 5 and I have to put a node of 6, which will come before 5 And this get cancel , lets understand it quickly 1. Create a node , this is pointing to NULL 2. temp->next=curr->next In short it moved from here to here , and this moved to here 3.It is pointing here ,cancel it , and point it here , this is curr curr->next=temp Same thing we have written in above , so we have reached a generic case Lets implement this ,can we search or not? Assume that element is present in the list if(tail==NULL) It means this is an empty list Empty list logic is in this way Create a new node tail=newNode newNode->next=newNode, so you have handled the 1st case After this all things will be same esle , your list is not empty We can assume here that element is present So we created a curr pointer, we inserted it in tail Until we get this element , we will search while(curr->data !=element), curr=curr->next If we come out the loop it means element is found curr is pointing to it We created a new node temp->next=curr->next curr->next=temp So in this way we inserted in a circular linked list Lets run it, make a node * tail=NULL, call insert function Pass tail , 5, 3 This is the case for empty list We printed tail, there is no head void print (Node* tail ), how we will print it? Lets see how to traverse it , this is a node there is 3 , this is a node of 5, there is 7, then 9 My tail will be here ,lets print this Then go to this and print it , then this , then this , when you again reach here , then stop Condition will be when you reach the same tail position , then stop print it , then this , then this , when you again reach here , then stop Node* temp=tail while(tail->next!=temp) up to that print it , cout<< tail-> data <<" " tail=tail->next so in this way you printed it, but there is one problem If it was a single node , then it can't print it, according to this logic 1st I will print tail's data , and the rest part will be printed here There is do while loop It is executed one time You 1st process all these things , then you check the while condition and we repeat it lets use it, do cout<<tail->data <<" " tail=tail ->next while(tail!=temp) Lets create it here , and print it I want to insert an element , insertNode (tail ,5 ,3 ) , then printed it print(tail) Lets run it, we are able to print 3 lets run it , 3 is getting printed here insertNode (tail ,3 ,5) print(tail) ,lets run it 3,5 , in same way search 5 and put 7 after it Lets run it , it is working properly , in same find a node 7 and put 9 after it lets run it, it is working properly Lets insert in middle , my list is 3 ,5 ,7 ,9 Now put 6 after 5 put 10 after 9, we have already deed this it is working , put 4 after 3 So it is working properly , it can insert at any position Here start and tail are not logical here , because we don't know where it is starting and where it is ending But we taken tail , and by using it ,we are inserting Here we handled empty list condition, then the non empty case Here we are doing insertion ,you can also create a sorted linked list So here we learned insertion , and also the traversal We ran a do while loop , it will be executed at least once We printed the data of tail , then incremented it, till it become equal to temp Once we traversed we will stop Lets talk about deletion , void deleteNode() The deletion we saw in case of doubly linked list , we use to give a position , and it use to delete it So we have understood that properly ,this is value , delete this node So you will understand both the codes This is a circular linked list Delete the node of 5 , I have to delete this node curr will be here ,and prev here 1.prev->next=curr->next In short you pointed it from here to here This is also pointing to this , remove this and point it top null This is curr->next =NULL Then delete this , 3. free the memory Lets write the case , empty case if (tail==NULL), there is no node , print list is empty ,please check again then you returned In else part there will be non empty case for deletion you have send a value , Node* &tail ,int value , by comparing which we will find which to delete Assuming that value is present in the linked list Now we started to compare , Node curr =tail Node * prev=tail in same way a curr =prev->next while(curr->data != value) prev=curr curr=curr->next prev->next=curr->next curr->next=NULL then we have to free the memory, delete curr Lets check whether we have written a destructor or not , yes it is there All is good Clear it, lets check is it working or not So this is our linked list , I want to delete 3 deleteNode (tail, 3), print(tail) I ran it, here you free the memory but there is some segmentation fault So we went to delete 3 , so curr should be here , and prev here prev->next=curr->next curr->next=NULL Then we freed the memory Here we deed one mistake , tail is pointing to this I have to make sure that tail should be preserved Lets tail is pointing to current tail=prev lets run it All is working properly 3 ,4 ,5 ,6 ,7 ,9 ,10 then we deleted 3 Then it gave 10 , 4 ,5 .,6, 7, 9 So we corrected it, lets run kit So 3 got deleted , now if I want to delete 10 , then So we got 3, 4,5 ,6, 7, 9 Now if I want to delete a middle element , 6 It was 3, 4, 5, 6,7 ,9 ,10 now it is giving 3, 4, 5, 7, 9, 10 Let say I commented this , now there is only one node And I want to delete it , so it is giving segmentation fault Here you have a single block of memory and it is pointing to itself curr is pointing to this , prev also , tail also Then you freed this memory And when you tried to access it using tail ,then it gave segmentation fault It is easy to handle empty list Deletion is not possible here When there will be only one node , curr is pointing to it, prev also , tail also then how will we handle this case? If(curr==prev ) , then you are talking about single node , tail =NULL When there are 2 nodes or >=2 nodes This type of linked list There is one more node Curr will be always different from prev , curr!=prev if (tail==curr) , and I want to delete curr, tail =prev But 1 node case is not handled , lets write it here 1 node linked list , if (curr==prev), tail=NULL this is for >=2 nodes linked list Make sure you are checking , if(tail==NULL), list is empty then return Lets run it, we have single node 3 and we are deleting it there is problem , let run it again You freed 3 , list is empty So you deed one node like this If this is two node case, you have 3 and 5 there was 3 and 5 , you deleted 3 , so 5 left Now only 3 is left So our deletion code is also working properly, here we handled all the cases We learned to traverse , insert ,, if it is empty then I will handle it in this way , if non empty then in this way Then you moved to deletion same here also If you remove these conditions , you are deleting it, but you can't print it, make sure you have to print it So in this way in circular LL , we learned insertion , traversal, deletion also So in this whole video I have seen singly linked list , then deed all these things in it Same in doubly linked list In circular LL also In next lecture we will move to questions , for now you will go to code studio There are some documentation , and some popular questions , these are asked interviews slow and fast pointer Add one to linked list Merge two sorted linked list is a good question flatten the multi level LL These are the questions which is asked most You can explore this documentation on Code studio That's it for this video , here we have learned these things , there is homework also , this video may be of 2 hours Tell me , what you feel about the video , here we have compensated for the previous videos That's it for this video ,we will meet in the next video ,Bye bye!!

Hello ji, How are you all? this is Love Babbar Welcome to the channel Code help , today we are going to talk about linked list , this is lecture no-44 Here we will discuss all topics related to linked list After this there will be one more video where will solve many questions  Lets understand what is a linked list? This is a type of linear data structure  Which is formed by collection of nodes  We will talk in layman terms , so that you can get the clarity  This is a type of linear data structure ,which is form by collection of nodes A node is a combination of , say we have red about encapsulation , there will be capsule  There will be some some data members  There will be some functions , by combination of both capsule will be formed  In node there will be some data , and the address of next node  This is a type of linear data structure ,which is form by collection of nodes There are many nodes , node displays data and also the address of next node  Linked list is a data structure containing many nodes, and a node looks like this This is a node , there is 3 as data , there is one more node , there is 5, it is at 710 there will be 710 , this is a pointer basically pointing to this node  In same way this will be pointing to other pointer  There is 7 , here is address of other There is 9 , this is not pointing to anyone  It is pointing to NULL Linked list is a data structure containing many nodes , there are many nodes  One node contains data , and the address of next node Why we need linked list? There is a case in array , you made an array of size 10 Will you be able to change it on run time? You have ran the code , and now you want make it of 100 size , can you do it? bhaiya , no we have not learned that  You can't do it? Before moving ahead in the video , lets talk about Coding Ninjas  Coding Ninjas has supported us in this course by supporting the major chunk of the video sponsorship  Thanks to them  Coding Ninjas is the largest coding education platform where you can access various type of courses if you are interested in paid courses If you want course on web dev , machine learning , development ,OS ,DBMS ,DSA in java , python  Then Coding Ninjas is the place for you  The best thing about CN is that you get one on one doubt support All your doubts will be resolved within 1-2 hours  The courses are really well structured  If you will work hard , then you will definitely get the result The course makers have already cracked big tech companies  So, you need not to worry about that  The courses are available in both Hindi and English languages  You will also get hint videos in every question  So, if you want to buy any of their courses  Then you can use the link in the description to get the 20% off on all of their courses  Thank you You have made one vector of int of size 5 , as this will be fully filled  Vector is a type of dynamic array  Its size will get doubled , it will become of size 10  All these values will be copied  In short a new storage is allocated , and values got copied in it Can i say ,this is a optimal case? Is i say there is a 10 sized array convert it to 100 sized array , you don't know how to do it But you know that size gets doubled up after vector get completely filled  But here new memory is allocated then the values are copied  Is this a optimal case? no It is not optimal , you are taking a new space ,and copying value, it is taking some time So to minimize these thing , linked list is used here  1. this is a dynamic data structure  You can increase/ decrease the size at run time  There is no memory wastage  Here we can see that here we filled the 6th space , but other 4 are getting wasted  But here I can change the size at run time , so there will be no memory wastage  If I talk about insertion / deletion in linked list  Deletion is easy in linked list There is no need to shift  In case of array , if I need to put something here  Then I have to shift these elements by one place  Or I need to delete it , then I need to shift them backward by one  So here I can see some benefits of linked list  As we will move ahead , we will also know some disadvantages  Linked list is a data structure containing many nodes , there are many nodes  There is data and address of next node , lets see the example Lets make a linked list  Create a node , there is 5 as data and there is address 710  Of next node which is at 710 , there is 8 as data , and 810 address of next node  There is 12 , 910 address There is a node at 910 , there is 11 , there is nothing There is NULL , your linked list ends here So in this way a linked list exists  Arrays are of this type , it is a continuous  This is some address 710 , this is your name  ,then there some indexes  There use to be some values  It use to be in continuous way  In linked list there is no need of continuous storage  I want to allocate everything in heap , this is the heap , there is one block there is 5 ,then 7, one is 11 This is pointing to this ,this to this then this to this , then this to this , and this is pointing to NULL So this is your linked list, this is your head pointer  So you got to know here  that there is no need of continuous memory allocation  and your data will be stored in this way  This is an efficient data structure , you can change its size at run time  We seen this example , this pointer name is head  This is pointing to this location  We call this singly  linked list Let me explain the types , types of linked lists  The above is the example of singly linked list  Then there is Doubly LL Circular LL  Circular doubly LL  These are some types of LL , 1st we will talk about singly LL  Singly Linked list  Before understanding Linked list , as I said linked list is collection of nodes  So 1st see about nodes , there will be data and the address of next node  Lets implement  this , then you will understand it  Lets say data will be int type and address will be the pointer  These are the nodes  This is pointing to this , this to this , there address is stored  This field is a pointer , this is pointing to a node  This is a pointer of node type , are you getting it ?  1st we are taking an int value as data ,  this address pointer of node type So I have to implement this node  Then how will I do it?  Lets make its class , class linked list node , we made the class  There will data of int  type  2nd we need a pointer of node type to store the data  Linked list Node * next;  Then I closed it  So here we implemented a node , there is some data , there will be a pointer containing the address  Lets say , we named it node  , class node, this is public int data ,Node * next So here I have created a node class , I can create its object in this way  Node * node1= new node ();  So in this way I have created a node , and can print the data and the address of the 2nd nodelike this Its giving garbage values  cout<< node1 -> next << endl; There is  giving some garbage values I want that whenever I want to fill a node then I can create it , so I written its constructor  Node (int data ),this->data =data ; this-> next =Null; Whenever a new node it created , then constructor will be be called  There you will put data , put NULL in the next in starting  Now if I run it , node data will be 10 and node next will be NULL  so in this way you learn how you can use constructor in the Linked list  Did you get it ? , we learned how to implement node  There are two things inside node , 1. data ,2. address  The data is of int type  In address we are talking about the pointer  This pointer is pointing to the node , so this is pointer of node type  node * next; So in this way I have created node class  Lets understand singly linked list  Let me make some blocks  There will be two things , 1. data , 2. pointer  There is 5 , 10 , 12 , 9  This node is pointing to this 710 , there is 810 , here 810 is copied  This node's address is 910 , this will be saved here , this is pointing to this There will be NULL because it is not pointing any node In this way when you have single next pointer and a data So this type of Linked list is called Singly Linked list So this is clear to us  Lets talk about insertion , how can we insert ? Lets say , 1st I created a node , it is empty , in starting your head will point to NULL When you created a new node ,Node *node1=new Node(10); This is a node , there is 10 inside it this is pointing to NULL, we understood it I want to insert one more node I made a function , InsertAtHead(),lets say I want to make a node taking 12 as input  There is 12 , and there will be NULL If I show it here , this is 12 , and this is pointing to NULL I want to connect this node with this, my head is here  Now if I want to connect this node with node1 then I will remove the NULL , I have to point it here  If it name it temp, temp->next =head /node1 , both are same  So I pointed this in this way  And I know that head always points to start  We have to remove head from here , put it here  head = temp, because this location is being indicating by temp So in this way you inserted it  There is one new node 15 , 1st I have to create it , this is pointing to NULL  Then we have to remove it , will have to point it to 12's node  It's mean this statement , then we have to update the head , put it here  You got the idea little bit  When we will write it , you will get the clarity There is a function , void InsertAtHead() , Inside it we are sending head , from this we will know where we have connect this node Node* &head, int data , why I have taken reference , I will explain it in few minutes  Whenever is any new data ,we create a new node , Node* temp=new Node(d) Then my next step is , the new node that I have created  I have to point it to the NULL  temp-> next=head; In 3rd step , you have to change the node to which head is pointing, head=temp; So in this way you have inserted a new node at head  Bhaiya but why you have taken reference here ? Here I have taken reference , because I didn't want to create  a copy , I want to make change in my original linked list  So that why I have taken reference here  Lets 1st write a print function , which will print our Linked list   we will learn how to traverse a linked list  In starting we will give the head , for printing also reference is needed? no . but I didn't want to make a copy  So how we will print  Assume that I have an linked list , there is a block ,this is pointing to this This is pointing to this , then this is pointing to NULL  There is 3, here 5 , here 7 Head is pointing to this, we named it That's it, now I didn't want to update it , so I made a variable temp node* temp=head So you made one more pointer, and pointed to it  Then you told to print this , current node -> print Then you move the temp by one in forward direction  Then you are doing the same work in loop Until you reaches NULL Lets make a temp , Node * temp =head  while(temp !=NULL ) , cout<< temp-> data << " " ; Then move temp by one , now temp is here  I want to go here , this address is already here  temp= temp-> next  I want temp to go from this location to this  This is already stored here , , temp =temp-> next  From this I will move to next location  before going there we used endl , for better visibility  So here I created a new node  And I pointed head there  Then I said to insert , insertAtHead(head ,12) Now my state will be like this , 1st 12 then 10 Lets print it , here I inserted head , after inserting we will print it Lets run it , there is little problem  Lets clear it and run it again  Write temp properly, again ran it 1st it was 10, if I show you here  lets comment this , lets run it again  1st there was 10  Then we inserted 12 , show it is printing 12 ,10, same thing we have seen here  1st it was 12 then 10 If now I insert 15,so 1st 15 will come , then 12 ,10 Lets see , so if I make one more call ,insertAtHead(head ,15) So then your answer will be 15 , 12 ,10  Lets run it , 15 ,12 ,10 , so in this way you are understanding that , we created a linked list  but bhaiya it is happening in revere way  If I say 10 , then a node of 10 is created ,  And it is pointing to NULL , then I insert 20 , which is pointing to 10, then it is pointing to NULL Now if I have put in this way 10 , 20 , 30  So 30 will be at 1st place , then it is pointing to 20 , then to 10 , then 10 is pointing to NULL  Or if I have put data in this way 10 , 20 ,30 ,40, 1st 40's node will be created , then 30 , then 20, and 10's node  I want if there is this type of input , so I want that 1st 10 will come , then 20 , then 30 , then 40 I want this  We can do it , for this we have to keep a tail What do you mean by tail? The way I am using head , insert at head  Now I will create a function , which is insertAtTail(0 , which will always add new node after the ending node  Tail will be a pointer  of node type , which will always indicate to the last node Did you get it? the way you kept head , same way you have to keep tail In starting I also created tail , Node* tail=node1 When there will be single node , then you will call same node as head and tail  void insetAtTail(node*&tail, int d) In short 1st I have create a new node ,then I said Now I created a node of 12 , this is pointing to nulll  You will point tail's next to this node tail->next=temp   So we remove this from line no. 30, and pointed it in this way  Tail will always point to last node , and this is the last node  So change tail from here to here  tail=tail->next Bhaiya explain it once, now this block is containing this address  And I want to go to this address , so point tail to its next So in this way if any node comes , we will put it in last  Lets run it , I change it to insertAtTail lets run it There is some problem  It is printing 10, 12 ,15 Node* tail =node1 , and then printed it, our answer came 10, then we said to insert at tail A node is created for 12 , then tail-> next =temp then tail=tail->next Tail = temp Lets run it, still it is not working  there is some little mistake  here I have to pass tail, then I ran it Before it was printing 10 ,then 12 ,10 , then 15 ,12 ,10  Now it will print 10 ,12 ,15, it is working properly  You have seen both the things  You know insert at beginning , insert at end /tail 3rd insert in middle  For this what I need to do  Lets say I have this linked list , there are four blocks  I gave input to insert 22 at 3rd position  here a new node is created , you removed this connection from here  You pointed it here , and it here  Now your linked list changed to this  Here you inserted a new node ,then there are the old nodes You gave the position and the data , and by this your pointer got changed , so this type of linked list is formed  Linked list is like English only , simple thing Now you know the steps , 1st I pointed it here  Then you removed this connection and pointed it here , you have to just to convert Hindi language into code  Here I am making  insertAtPosition( int position ,int data ) I cleared it, 1st I need to reach this position 1st I was here , then I moved here  If I have to go to the position 'n', then I am going up to 'n-1'  Lets say nodeToInsert->next=temp->next Then I have to remove this pointer , and point it here  Its name is nodeToInsert ,temp->next=NodeToInsert Your work has been done by these to statements  Lets write it , 1st I have to traverse  node*temp=head int cnt =1 , we are at starting  If I have to got to the 3rd position , then I need to move forward by one So I have to go to 'n-1' node  So I ran a loop , while (cnt <position -1)  temp=temp->next cnt++ So we have understood this  For this 'd  make a node  Node* nodeToInsert =new Node(d) NodeToInsert ->next =temp->next , we have to point it here  remove this connection and point it here  temp->next =NodeToInsert Lets call it , run  it Insert 22 between 12 and 15 insertAtPosition (head ,3 ,22), then you printed it  lets run it So here you inserted 22 at 3rd position ,in short you also ran it there are some cases that we need to cover , as here I say to insert 22 at 1st position It is unable to do it ,why? Lets see , because we have started from 1st position , and to insert we always requires the previous node Here we put a case , if (position==1)insertAtHead(head,d), can I run it now ? Lets run it , now it is working  There is still some problem , we need to return it, lets run it So we inserted 22 at starting  Lets talk about the last node  Here I have inserted 10 ,12 ,15 , three things  Now if I want to insert at 4th node , we have already solved the case for middle  And for starting here  ran it, if I write 4 , in that case also it is working properly  There is one mistake , if you inserted at 4th, then your tail should also get updated  In this whole function we didn't updated the tail  So you need to update the tail also  head is already getting updated  So you are getting it  Or you know the length of linked list , if( len == position-1 ), insertAtTail(tail ,d) But you don't know the length, are you getting this? We know that there is a case where we have to insert at last  How will we handle it? When you will reach the last node , you said my current linked list is of this type I have to insert at 4th position , so your temp will be pointing to this And your node will be pointing to NULL  1st you pointed it there , which is pointing it  So you also pointed it to NULL  Then you cut it from here , then you connect it like this  And we knew it but the tail which was pointing here  It is still pointing here , I want to bring it here  How will it happen?  So if I write a simple condition , when I am adding this  temp->next=NULL, it means I am adding at last In that case update the tail  if (temp->next==NULL ) Here I call ,insertAtTail( tail,d)  Here you returned it So here you created a generic code where you can insert at anywhere  In short here you have to pass tail also  Lets run it , code is working properly  To verify head and tail ,we will print it In same way I will write for tail to verify it Then I ran it  So head is coming at 10 Tail is coming at 22 , so we written a code of insert , where if we want to insert at start, we can do it If at end then also ,at middle also  So in this way you have learned insertion in linked list, insertion at any position  You also learned to traverse it, here you have written print function, you learned this You will learn to delete  As we can insert any node in same way we can also delete any node  Lets talk about it, how to delete ? Lets talk about next process , deletion  Lets say I have this linked list , and I have to delete a node delete Node (position) , or deleteNode( value), and comparing it with every element I will implement this , and you will implement this by your self, take it as homework Here we will compare data values  Lets see by deleting this position  So we created a function , void deleteNode(position ,head)  Now I have to delete a position , it can be any position  Tail is beneficial to us , that's why we should keep it, if we want to insert at end , then we can do it At starting head will be pointing here  tail is pointing here , take tail as option  Provide me the position and I will delete it , it can be from 1 to length Lets do it lets think , this is thew linked list  case.1  I ma deleting middle node  I want to delete this node , how I will do it? remove this connection and point it to this  Now this looks like this  And this is pointing to this , free its memory  Now your state look like this , this 1, 2, 4, so you deleted it in 2 steps  You wanted to delete this node , temp->next=current-> next So by this statement you pointed it here and cancelled out it This is for middle node Lets say i want to delete the last node , then what will happen ? This is my linked list  1,2,3,4 I want to delete this , this is my current node  This is my previous node , here we are representing temp as previous previous -> next = current -> next, which is NULL In short you removed this connection and pointed to this  There is no need to do extra for last node  Then I will free it 3rd case ,I want to delete the 1st node  There will be no previous node  If this is my linkedlist  1,2,3,4 This is my head , and I want to delete it , so this is current  there is no previous , so previous is NULL ,  As I will write previous -> next, this means NULL->next NULL pointer exception , it will give error, so this will not work for start So handle it by different method I have given position , if (position ==1) else, deleting any  middle node or  last node  Lets understand it, if i have delete 1st node  Then how we will do it? I have to bring head here , then we will free it from the memory  head=head->next then I freed the memory ,Node* temp= head ,delete temp In same way , if I go in the class , then I have to write destructor  ~Node () ,int value=this->data, why we are doing I will explain if(this->next!=NULL), then free it So this is the code to free the memory  Memory is free for node with data , I stored it at line no.18 , so that I can tell that I have freed it Here we are freeing the memory  So 1st position we deed it in this way We m oved head forward and freed the memory  Lets say I want top delete the 3rd node  I have to keep current pointer here , and previous pointer here  At starting I am at head node  I moved 2 times forward , in case of 3rd position  1wst make two pointers Node* cur=head , Node* prev=NULL int cnt=1  while(cnt<position) For 3rd it will run two times  With every iteration move it forward , cur and prev If I have to moved them forward then how I will do it This is my linked list  At starting cur is here , and prev will be NULL  cur=cur->next So you pointed cur here  Before doing this , 1st you have to point prev here  So you 1st said prev=cur, so this became two step process  1st there was current , prev was NULL  1.This is the linked list , prev is pointing to this , and cur is also pointing to this  prev=cur In 2nd step you will write cur=cur->next Before current was here  Now it is here  prev=cur, cur=cur->next cnt++, then we will write prev->next= cur->next In this way you also deed this , in this case this pointer would have come here Then I have to free it, delete cur, so I also deed this part Deletenode(1, head) , then I printed it lets run it, there is some problem  1st 22 is getting free , then for 15 , then 12 , then for 10  There is some problem  Somewhere we are trying to excess NULL and there it is creating problem  Whenever we are freeing the memory  This 3 is still pointing to this , before deleting it , we have to remove this  Because our destructor's code has been written in this way I don't want that which is not required points to another memory , which is our data , I want to remove it So I want to remove this before deleting this Here I am deleting temp, 1st temp->next=NULL Here cur->next=NULL By adding this we removed this, now this is pointing to NULL  If we talk about this case , if we talk about 1st node , it will also get stopped  Because this is pointing to this , so I have to remove it In short , I initialized it as NULL Now if I run it, 1st it deleted 10, 12 ,15,22  are remaining Delete only 4th node , then will it run ? There is segmentation error  Lets try to understand it, it is wrong here , lets run it It ran successfully, here we have deed mistake in loop So here we deleted 22 Now if I say to delete 15, so it deleted it So now we have written a generic code for deletion, which can delete any node We have to keep in mind how to delete 1st node Whichever node you ant to delete , set the previous pointer as NULL So here you have understood how deletion works in linked list Now you have seen insertion , traversal , and deletion also And this is the generic code  So here you have understood singly linked list, we will do the questions  One thing keep in mind , when we written delete code , then we handled the head case  But has my tail came to the right position ? Lets check it So I printed it here , run it So my tail is still at 22, it is working properly If I have deleted the 4th node  So tail is pointing to some garbage value So this is your homework , when I delete last node , then how will you handle the tail  Tail case is optional , so see  it, when you do deletion then how will you handle tail Idea , use the previous position and how we identify last node, use them it will be solved  Linked list are the steps coming in your mind  I never practised linked list from any interview  it is simple to do  So here we understood the singly linked list  Lets talk about the 2nd thing , Doubly linked list  What is this? here just node's structure is getting changed  There are three things in the node  ,1. data , 2. previous  Lets make it in abetter way , so that you can understand it in a better way  This is your node , there is 1. data , lets say 5 , 2. pointer, which is pointing to next node 3.previous pointer  In singly linked list you had data and pointer of next node, here you have data and pointers of next and previous node  This is your doubly linked list  This is next ,  then this  is pointing to NULL  This is its previous , this is its previous previous  There is 3 ,5 , 7  This is data , this is next pointer , this is previous pointer Every node has two pointers previous and next, previous indicates the previous node , next indicates the next node So this is your doubly linked list  Lets code it, it is simple to do There are 3 things 1. data 2. previous ,3. next So you created a node class , here you created 3 things , 1. data ,2. previous 2. next Then you made a constructor of node type, where you took a value  this-> data =d  this-> prev=NULL this->next=NULL in starting , so in this way you created a constructor If here you make a node , Node* node1 =new Node(10) I have to print it, void print(Node* head) ,Node* temp=head while (temp!=NULL), print the temp data , and increment it cout<<endl; So you have written this print function also  I cleared it , I have made this node , now print it  Node* head =node1 I ran it It printed 10 Lets say I need a function which give the length of linked list int getLength(Node* head) , written the same code which is here  int len=0 at starting  You have to increment it here  Here you have to return it cout<< getLength(head)and ran it My length comes 1, you we saw two functions  We learned to find length , traversal  In same way I have written a function here , insertAtHead(head,11) Then you printed it Here we have to create it  Now here I have to add it , lets understand how to do it In starting there can be a node  Lets see how we used to insert in singly linked list Create a new node , put head there  Then bring it to the write position , lets do it here  Create a new node  ,7 Your head is pointing to this node , this is NULL , and also this in starting   You 1st created this  In 2nd step , I will point it here  Then point it to here , it means temp->next=head 3rd step , head->prev=temp, that's it Then we bring head here  This is temp , head= temp, this is your 4th step in 4 steps you finished the game  1st you created a node , Node* temp=new node(d) Next step ,put temp->next= head  head->prev=temp Then place head to its correct position , head =temp Lets run it  Lets put space here ,  Lets run it , 1st it was 10 , then I put 11  In this way I have created a doubly linked list I have put every pointer to its correct position  So we have understood this  If I 2-3 more nodes  for 13 ,8, then ran it 1st it was 10 , then 11 ,10 , then 13 ,11 ,10, then 8 ,13 ,11, 10 So I have learned to insert If I have to insert at tail , void insertAtTail(Node* & tail , int data ) Lets 1st see the code of singly LL  Now if I have to understand about insert at tail, it is easy  In singly LL , we had created a node , then pointed last node to new node  then updated the tail , three steps  For example ,This was our linked list ,this is the new node  1. create this new node  2. tail->next=new node  Then we have to update the tail , tail=temp Here also we will do the same  This is our Doubly linked list this is pointing to NULL , these are the prevs  There are 3, 7, 9, this is the head , and this is the tail  When I say this is head , I am talking this whole node , when I say tail I am talking about this node  If I want to insert a node here  1.Create a node , this is pointing to NULL  There is 13  2. Connect this to this , its name it tail and its temp ,tail-> next=temp temp->prev=tail 4. Tail is at wrong position , tail=temp Lets implement it , Node* temp=new Node(d)  tail->next=temp temp->prev = tail  tail=temp Here I am explaining  you  Till my linked list is of 8 ,13, 10 ,11, at end I have to insert 25 insertAtTail(head, 25), then I printed it head  Here I have created a Node* tail=node1 Now I ran it, 1st it was 8 ,13 ,11, 10 , now it has become  Lets run it  again , clear it It was 8, 13, 11 ,10 , here I put 25 at end at line no. 76 so it is working successfully , so we have also written the tail function So now we know to insert at head , tail , in same way if I go back to singly linked list  Insert at any position , can I do it?  void inssertAtPosition (head ,int position, int data ) We will implement the same algorithm  If position is 1 , then do insertAtHead, copy paste it If you have to insert at 1st position , then you gave head , the data  In this way we have to do something, we will copy it and make the change in it  There is temp pointing to head  int cnt=1 , then we are moving forward  The position at which we have to insert , we are moving towards it We reached the last position , here we passed tail; At last position we returned it If I have to do in middle , then we will use these three lines  Lets say I have to put a node here  1st step is to create this node, which we have already done at line no.80 This is my temp, node to insert , make logic according to this  My next and prev are pointing to Null  We have to point this next here ,2.nodeToInsert->next=temp->next temp->next->prev=nodeToNext It is simple ,temp->next->prev=nodeToNext This is nodeToInsert 4.temp->next=nodeToInsert 5. nodeToInsert->prev=temp So you pointed four pointers to their right place  There should be no confusion  We brought this pointer here , temp->next Then we did temp -> next->prev=nodeToInsert temp->next=nodeToInsert ,we removed this connection , and pointed to this  This is pointing to NULL , so we pointed it to temp, nodeToInsert->prev=temp Lets write it here  Temp->next -> prev=nodeToInsert temp->next=nodeToInsert nodeToInsert->prev=temp Lets print it, so this is your current linked list Now I have to insert 100 at 2nd position, insertAtPosition(tail,head ,2,100) My answer should be 8, 100 ,13 , 11 ,10 ,25 I ran it , it is working properly Same thing but at 1st position, 101  Now I have to insert 102 at 8th position It is working properly , so we have written all the 3 functions  Now we can insert anywhere  I simply copied the code of singly linked list , and changed it little bit And in this way created doubly linked list code  We seen the traversal , insertion  In doubly linked list we show insertion , we can insert  anywhere   In starting you have created a node , I want to start from '0' Assume that we removed this node , in starting the head is NULL  And tell is NULL  Now what will happen , lets run it, its is giving segmentation fault There is some problem in code , we went to print the head  Here we have put Null, there should be no issue  In starting there is no node , so when we do insertAtHead () , then what's happen ? A new node is created , temp->next=head , head->prev=temp , here head is NULL There is problem ,if(head==NULL), then handle it differently, here the same will be implemented   So we have handled this case , Node* temp=new Node(d) Now this is your head , head=temp If we want to include tail , we didn't need it that much Here I have put tail and updated it here  So you handled it like this  If i want to handle same thing here , If ( head==NULL ), then I will handle it differently , and esle part differently  We did the same thing here  Did you get it? Here You passed a tail also tail=temp Here you passed head , and updated it here  So you handled two cases here  So you handled empty case here ,and here also  If you go here , then you can handle this , here we will also pass head  Here also I have to send tail  So we have handled it here , lets run it  It is working properly , but here there is some problem  In the last entry ,lets understand it Here , we said insert at tail Here we will print head and tail once  In this tail 's data  I am copying it here and here  We can do it using print function also  Lets run it , 1st is was 11 , then 13 ,11, head in on 13 ,Tail is on 11 It si correct , up to 101 our code is working properly  At last position it gave segmentation fault , here last position is getting handled  Here we will do temp->next==NULL, so we are inserting at tail esle, in this way  What's wrong here , lets see  Lets prints the values , cout<< "tail" << tail<, endl; We are trying to access a NULL pointer , that's why it is giving segmentation fault Lets run it again  Tail is at 25 , so NULL is not there  Here segmentation fault is coming , after printing tail 25 and head 101  Here there is some problem  We given 8, 13 ,11 ,25 I got the issue  We said to insert at 8th position , but we have to insert at 7th position Because we have deleted one node at starting , now lets run it It is working properly , in short our input parameter was wrong  So we have handled this case , where there was nothing at starting of linked list Same thing we have to handle in future , in our singly LL  After that ,insertatposition () , there is no need to handle , because we are putting in middle  This is simple , so you have to handle this case in case of empty linked list So we have deed insertion , also handled the edge cases  Then we show traversal , and print Now we want to delete  If I talk about deletion  Lets copy this and paste it here  So we have moved to deletion , this is for deleting your starting node Lets say ,if I make a linked list here  There are 3, 5, 7 . I want to delete it  This is head , so to delete starting node what I need to do? 1st I have to point this pointer to NULL  Then This will become the starting node , if this is my temp temp->next->prev=NULL So you made it NULL  Make this pointer to also point NULL This is temp->next=NULL  Now this is 3 pointing to NULL , head is here  This node is pointing to this  Now I have to bring head to its correct position , 3.head=temp->next so I need to do this before  I have to do this here  2. temp->next ,and this becomes my 3rd step now I have to free this memory in 4th step by calling the destructor  1. Point this pointer to NULL  head=temp->next temp->next=NULL In last you freed the memory by calling the destructor  Lets code it, temp->next->prev = NULL Lets remove this , then head = temp->next  temp->next=NULL then we have to free the memory  Here I have write my own destructor  ~Node (), int value=this->data  if(next!=NULL) , in this case delete next next=NULL cout<<" memory free for node with data "<< value<<endl; So we have written the logic of deleting at starting  Then it can be middle or last element  In this way we moved ahead , now I just need to delete the current node  We have reached the state , assume this is our linked list , this is prev NULL and this is next , this is its prev In same way ,  Lets say I want to delete this node , then I named it current and its prev What steps I need to take? lets understand it Remove this connection from here , make it NULL  This is currnt->prev=NULL  So ,Remove this connection from here , make it NULL  Next will be prev->next=curr-> next It moved here , you corrected this pointers This is pointing to NULL , this is the next node , then you made it to point NULL  This node's prev is NULL , next is also NULL In this case this was last pointer that's why it is pointing to NULL  But if this was a middle node , then this would be pointing to some other node  Then I have to correct this pointer also , curr->next=NULL So I marked this also as NULL  Now I have to free its memory , lets write it Curr->prev=NULL, ,lets remove this from here  Curr->prev=NULL prev->next=curr->next Curr-> next=NULL ,then you have to free the memory , delete curr So in this way you have written the code for deleting, lets run it Here linked list is of size 7, there is nodes Lets delete one by one  Lets 1st delete the 1st node , deletenode (1, head) Then we printed this  I have to delete 101 , so here we have deleted 101 , an rest are there  It is working properly Now I want to delete any middle node  I have to delete 25, 6th position  So 25 was there , and you freed its space , so it is working properly  Lets run for 1st position again , you have to delete 101 , so it is working properly  then I said to delete 25 at 6th position , so we have freed it Now I want to delete at last position , 7th ,I deleted it  If we see carefully ,102 has been freed but tail is at wrong position As I have seen it in singly linked list , I have gave it to you as homework  As here I have handled head, in same way you have to handle tail in homework  In same way here also this is for homework  So we saw insertion at any position  traversal, and deletion also at any node  So here we have learned the concepts of doubly linked list This is simple to do We are thinking and coding it, there are only some steps  So here we also completed doubly linked list  Lets move to our 3rd topic , Circular linked list  As we have learned singly LL few minutes ago  There will be data , and the pointer , which is pointing to this  We only deed some changes in it , lets say there was 3 ,5 , ,9 ,12  So singly LL was pointing to NULL like this  Now the last node will point to 1st node So we called it a circular linked list , this part is same as singly linked list  But your last node rather pointing to NULL ,it is pointing to 1st node  If we will try to traverse it, then we will print 1st this , then this ,then this ,then this , you will move in a loop according to previous logic  In same way your doubly linked list can be also change to doubly linked list  This is prev , it is pointing to NULL , this is the next , there is data there is also data , in same way And this is pointing to NULL  So this is our doubly linked list , if we do little changes here , rather pointing this to NULL If I point it to this , and this to here , then it will be also converted in circular doubly LL I will show you by solving 1 case , how a circular linked list will be formed  The way we made doubly linked list by copying singly LL , in same way you will implement this, this is for homework  Lets try to understand this case , how this works?  There is a linked list , there is some data, this is pointing to next node , then this to this  This is also pointing to next node , this is pointing again to 1st node  So this is my circular linked list , node structure is same here  There will be a data variable , then there will be Node* next This class is going to remain the same and we will try to implement it How to insert, traverse and the deletion part Before moving ahead let me shoe you the link  If you go to guided path at Code studio , you will get the notes of linked list , and some good questions also Here I got some notes of linked list ,from where I can clear my concept more  Here are some task also , solve them , you will also get the important questions that are asked in companies  So here you can see lots of problems  There are many links , let me show you  Till now we have just opened 1st link , here I am getting more things  Here it is written asked in Amazon , Microsoft , Adobe , etc So you can solve questions at code studio Lets move to our topic , here we are implementing circular linked list  Lets create node , class Node , int data ,Node* next: Then I created a constructor  data , this->data =d this->next=NULL So you deed this , in same way if I want to create destructor here  ~Node(0 , int value =this->data  If (this->next!=NULL) , delete next and next =NULL Here I will copy paste it  So here I printed it, so here I have written the destructor Now I have to insert , one function use to insertAtHead() Then insertAtTail() insertAtPosition (0, 3 functions  In circular LL it is little different We don't use head pointer , we only use tail pointer  Here our list is circular , if I simply take tail pointer  By using it I can add at tail , and at head also  If I have reach 1st node from last node, if this is tail then I will write tail->next It is pointing to head node , so there is no need to create head, I can use head and tail by tail pointer only Lets create these functions  We can't tell from where linked list is starting and from where it is ending  I will give you data in input , as you get the data , then create a new node after that  If this is a linked list ,there is 3 , then 5 , then 7 , then 9, then 9 is again pointing to 3 If I give 7 as input data , then you are searching for 7 , it is there  Then you will create a new node for 11 , and you pointed it here ,then you removed this connection 3, 5, 7, 11, 9then circular So according to this data we will insert a new node  You can do anything , but I want insert it according to this data I made a function, insertNode (Node* &tail ,int element, int d) Lets understand it, 1. It can be an empty list  Where tail is NULL , in this case you will create a new node  You put data in it, oit is pointing to itself  1. you created new node , pointed its next to itself, 2. tail=temp 3.temp->next=temp So we are understanding the 1st case  Lets talk about 2nd case , when there is only one node , and you want to add one more There is one node , which is pointing to itself , and here I want to insert 1 more node , there is 5 , and it is pointing to NULL In input I will give data , by comparing it, insert after this , and a data from which I will create a node  This is the data , and I will compare it with this  So this is clear to us , then I searched , here we got 3 This is my current node , we named it temp I want to put 5 after 3 1st step , it si pointing to something curr->next is pointing to some thing  Lets save it ,Forward =curr->next  Now I want it to point here , so I want it to point at temp Now this temp is pointing to null , I pointed it to where curr->next was pointing , temp->next=forward , it can be optimized  So by using thease 3 we made this linked list  This is 3 , it is pointing to 5 , 5 is again pointing to 3, did you get it? Lets say , now I have two nodes 3, 5  Now I can put a node after 3 or I can put it after 5 Lets see the 1st case , here I want to put before 3  Lets say , this is 3 , and this is 5 , and this is pointing to this  I have to insert a node here 4, it is also pointing to NULL  1.Create a node  2.Store where this is pointing , forward =curr Lets optimize it it , I want it to point here , I can call it curr->next temp-.next=curr->next In short, You cancelled this NULL  , and brought it here , this is the 2nd step  3rd ,I want it to point here , curr->next=temp 1.Create a node ,2.Store where this is pointing , forward =curr,temp-.next=curr->next 3rd ,I want it to point here , curr->next=temp This is pointing to this , this to this , and again this is pointing to this  So this is your 1st logic , if i try to optimize it Then we can optimize the same logic  1st create the node ,temp->next=curr->next These 3 lines can be used here  2nd case , I want to put a node before five , this is 3 , this is 5 and I have to put a node of 6, which will come before 5 And this get cancel , lets understand it quickly 1. Create a node , this is pointing to NULL 2. temp->next=curr->next In short it moved from here to here , and this moved to here  3.It is pointing here ,cancel it , and point it here , this is curr curr->next=temp Same thing we have written in above , so we have reached a generic case  Lets implement this ,can we search or not? Assume that element is present in the list if(tail==NULL) It means this is an empty list  Empty list logic is in this way  Create a new node  tail=newNode  newNode->next=newNode, so you have handled the 1st case  After this all things will be same  esle , your list is not empty We can assume here that element is present  So we created a curr pointer, we inserted it in tail  Until we get this element , we will search while(curr->data !=element), curr=curr->next If we come out the loop it means element is found  curr is pointing to it We created a new node  temp->next=curr->next curr->next=temp So in this way we inserted in a circular linked list  Lets run it, make a node * tail=NULL, call insert function Pass tail , 5, 3 This is the case for empty list  We printed tail, there is no head void print (Node* tail ), how we will print it? Lets see how to traverse it , this is a node  there is 3 , this is a node of 5, there is 7, then 9 My tail will be here ,lets print this Then go to this and print it , then this , then this , when you again reach here , then stop Condition will be when you reach the same tail position , then stop  print it , then this , then this , when you again reach here , then stop Node* temp=tail while(tail->next!=temp) up to that print it , cout<< tail-> data <<" "  tail=tail->next  so in this way you printed it, but there is one problem  If it was a single node , then it can't print it, according to this logic 1st I will print tail's data , and the rest part will be printed here  There is do while loop It is executed one time  You 1st process all these things , then you check the while condition and we repeat it lets use it, do cout<<tail->data <<" " tail=tail ->next while(tail!=temp) Lets create it here , and print it I want to insert an element , insertNode (tail ,5 ,3 ) , then printed it print(tail) Lets run it, we are able to print 3  lets run it , 3 is getting printed here  insertNode (tail ,3 ,5) print(tail) ,lets run it 3,5 , in same way search 5 and put 7 after it  Lets run it , it is working properly , in same find a node 7 and put 9 after it  lets run it, it is working properly Lets insert in middle , my list is 3 ,5 ,7 ,9 Now put 6 after 5 put 10 after 9, we have already deed this  it is working , put 4 after 3  So it is working properly , it can insert at any position  Here start and tail are not logical here , because we don't know where it is starting and where it is ending But we taken tail , and by using it ,we are inserting  Here we handled empty list condition, then the non empty case  Here we are doing insertion ,you can also create a sorted linked list So here we learned insertion , and also the traversal  We ran a do while loop , it will be executed at least once  We printed the data of tail , then incremented it, till it become equal to temp Once we traversed we will stop Lets talk about deletion , void deleteNode() The deletion we saw in case of doubly linked list , we use to give a position , and it use to delete it So we have understood that properly ,this is value , delete this node  So you will understand both the codes  This is a circular linked list  Delete the node of 5 , I have to delete this node  curr will be here ,and prev here  1.prev->next=curr->next In short you pointed  it from here to here  This is also pointing to this , remove this and point it top null  This is curr->next =NULL Then delete this , 3. free the memory  Lets write the case , empty case  if (tail==NULL), there is no node , print  list is empty ,please check again then you returned  In else part there will be non empty case  for deletion you have send a value , Node* &tail ,int value , by comparing which we will find which to delete Assuming that value is present in the linked list  Now we started to compare , Node curr =tail Node * prev=tail in same way a curr =prev->next while(curr->data != value) prev=curr curr=curr->next prev->next=curr->next curr->next=NULL then we have to free the memory, delete curr Lets check whether we have written a destructor or not , yes it is there  All is good  Clear it, lets check is it working or not So this is our linked list , I want to delete 3 deleteNode (tail, 3), print(tail) I ran it, here you free the memory but there is some segmentation fault  So we went to delete 3 , so curr should be here , and prev here  prev->next=curr->next curr->next=NULL Then we freed the memory Here we deed one mistake , tail is pointing to this I have to make sure that tail should be preserved  Lets tail is pointing to current  tail=prev lets run it All is working properly 3 ,4 ,5 ,6 ,7 ,9 ,10 then we deleted 3  Then it gave 10 , 4 ,5 .,6, 7, 9 So we corrected it, lets run kit So 3 got deleted , now if I want to delete 10 , then  So we got 3, 4,5 ,6, 7, 9 Now if I want to delete a middle element , 6 It was 3, 4, 5, 6,7  ,9 ,10 now it is giving 3, 4, 5, 7, 9, 10 Let say I commented this , now there is only one node  And I want to delete it , so it is giving segmentation fault Here you have a single block of memory and it is pointing to itself  curr is pointing to this , prev also , tail also  Then you freed this memory  And when you tried to access it using tail ,then it gave segmentation fault It is easy to handle empty list  Deletion is not possible here  When there will be only one node , curr is pointing to it, prev also , tail also  then how will we handle this case? If(curr==prev ) , then you are talking about single node , tail =NULL When there are 2 nodes or >=2 nodes  This type of linked list There is one more node  Curr will be always different from prev , curr!=prev if (tail==curr) , and I want to delete curr, tail =prev But 1 node case is not handled , lets write it here  1 node linked list , if (curr==prev), tail=NULL this is for >=2 nodes linked list Make sure you are checking , if(tail==NULL), list is empty then return  Lets run it, we have single node 3 and we are deleting it there is problem , let run it again You freed 3 , list is empty So you deed one node like this  If this is two node case, you have 3 and 5 there was 3 and 5 , you deleted 3 , so 5 left Now only 3 is left So our deletion code is also working properly, here we handled all the cases  We learned to traverse , insert ,, if it is empty then I will handle it in this way , if non empty then in this way Then you moved to deletion same here also If you remove these conditions , you are deleting it, but you can't print it, make sure you have to print it So in this way in circular LL , we learned insertion , traversal, deletion also  So in this whole video I have seen singly linked list , then deed all these things in it Same in doubly linked list  In circular LL also  In next lecture we will move to questions , for now you will go to code studio There are some documentation , and some popular questions , these are asked interviews  slow and fast pointer  Add one to linked list  Merge two sorted linked list is a good question  flatten the multi level LL  These are the questions which is asked most You can explore this documentation on Code studio That's it for this video , here we have learned these things , there is homework also , this video may be of 2 hours  Tell me , what you feel about the video , here we have compensated for the previous videos  That's it for this video ,we will meet in the next video ,Bye bye!!

Transcript for:Understanding Linked Lists and Their Operations

Transcript for:
Understanding Linked Lists and Their Operations