Linked List Basic Functions Part 3

Linked List Basic Functions Part 3

In this tutorial, you will learn 1. Implementation of function for inserting a node at end. 2. Implementation of function for deleting first node. 3. Implementation of function for deleting last node. What is the code of function for insertion of a node at end?
  1. void InsertAtEnd(int val)
  2. {    
  3. if (checkempty())
  4. {
  5. Node *nnode=new Node;
  6. nnode->data=val;
  7. nnode->next=head;
  8. head=nnode;
  9. }
  10.  
  11. else
  12. {       Node * curr;
  13. curr=head;
  14. Node *curr1;
  15. curr1=curr->next;
  16. while(curr1!=NULL)
  17. {
  18. curr=curr->next;
  19. curr1=curr1->next;
  20. }
  21. Node *nnode=new Node;
  22. nnode->data=val;
  23. curr->next=nnode;}
  24. }
Given above is the code for inserting a node at end. First, you check if the linked list is empty. If its empty, then the code for inserting at beginning will work. If its not empty, then you make two pointers curr and curr1. curr1 will point to node next to curr. When curr1 will become null then curr will point to last node. What we do is that we simply put the address of new node in next of last node. Hence, link is made. What is the code for deleting the first node?
  1. void DeleteFirstNode()
  2. {
  3.         if(checkempty())
  4.         {
  5.                 cout<<"Already empty";
  6.         }
  7.         else
  8.         {
  9.                 Node * curr;
  10.                 curr=head;
  11.                 head=head->next;
  12.                 delete curr;
  13.         }
  14. }
Given above is the code for deleting first node. You first check whether the linked list is empty or not. If empty then it cannot delete any node. If its not empty, first you make a pointer and make it equal to head so that it points to first node. After that, make head equal to 2nd node and delete first node. Remember deleting a pointer means deleting the object it points to and as while inserting, we were making dynamic nodes ( As new operator was used ) so that memory must be deleted manually. What is code for deleting last node?
  1. void DeleteLastNode()
  2. {
  3.         if(checkempty())
  4.         {
  5.                 cout<<"Already empty";
  6.         }
  7.         else if (head->next==NULL)
  8.         {
  9.                 Node * curr;
  10.                 curr=head;
  11.                 head=head->next;
  12.                 delete curr;
  13.         }
  14.         else
  15.         {
  16.                 Node *curr;
  17.                 Node *curr1;
  18.                 curr=head;
  19.                 curr1=curr->next;
  20.                 while(curr1->next!=NULL)
  21.                 {
  22.                         curr=curr->next;
  23.                         curr1=curr1->next;
  24.                 }
  25.                 curr->next=NULL;
  26.                 delete curr1;
  27. }
  28. }
Given above is the code for deleting the last node of linked list. First we check whether the list is empty or not. If empty, you cannot delete a node. Then, we check whether the linked list has just one node. If the next of first element (head) is NULL then there is just one node. If there is one node, method of deleting a single node works. If more than one nodes, we make two pointers curr and curr1. curr1 pointing to element next to curr and we stop curr1 at last node so curr points second last. Lastly, we make the next of second last element equal to null and delete last element. Note: Basic functions of insertion, deletion, traversal, constructor and check if empty are discussed. In next tutorial, copy constructor, destructor and sorting to make the linked list will be discussed. Then after that insertion and deletion at any point will be discussed along with comparison between effiviency of different functions in arrays and linked list. Output: Output

Add new comment