Deleting a node from the list(SINGLE LINKED LIST)

Linked List

1. Deleting a node from the list(SINGLE LINKED LIST) In a linked list, an element can be deleted: A. From the 1 st location B. From the last location C. From any position in the list

2. A. Deletion- From the beginning 1. Create a pointer ptr of type struct node 2. If (head==NULL) then exit 3. Else set ptr = head 4. set head= ptr -> link 5. free( ptr )

3. B. Deletion- From the end 1.Create a pointer ptr & temp of type struct node. 2.If (head -> link ==NULL) do step 3,4,5 else goto 6 3.ptr=head 4.head=NULL 5.free( ptr ) 6.ptr=head 7.temp = head -> link 8.while(tem -> link !=NULL) do 9,10 else goto 11 9.ptr=temp 10.temp = tem -> link 11.ptr- > link =NULL 12.free (temp)

4. C. Deletion- From any position 1.Read the value key that is to be deleted 2.Create pointer ptr & temp of type struct node 3.Set ptr =head 4.if head=NULL then print underflow and exit 5.temp= ptr 6.while( ptr !=null) do step 7,8,9 7.If( ptr - >data=key) then 8. a) temp->link= ptr ->link 9. b) free( ptr ) & exit 10. temp= ptr 11. Ptr = ptr ->link

5. . Merging Merge L2 after L1 Set ptr = head1 While( ptr ->link!= NULL) do step 3 else goto step 4 ptr = ptr ->link ptr ->link=head2 Return(head2) Head=head1 Stop

6. DOUBLY LINKED LIST Single linked list= one-way list List can be traversed in one direction only Double linked list= Two-way list List can be traversed in two directions two- way list is a linear collection of data elements called nodes where each node N is divided in to three parts Data field contains the data of N LLINK field contains the pointer to the preceding Node in the list RLINK field contains the pointer to the next node in the list

7. Operations on a Double Linked List

8. Insertion- after an element key

9. DELETION OF DOUBLE LINKED LIST

10. i ) Deletion- from 1 st location

11. ii) Deletion- from last location

12. iii) Deletion- from intermediate location

13. Advantages Of DLL : Reversing the doubly linked list is very easy. It can  allocate or reallocate memory  easily during its execution. As with a singly linked list, it is the easiest data structure to implement. The traversal of this doubly linked list is bidirectional which is not possible in a singly linked list. Deletion of nodes is easy as compared to a  Singly Linked List . A singly linked list deletion requires a pointer to the node and previous node to be deleted but in the doubly linked list, it only required the pointer which is to be deleted.

14. Disadvantages Of DLL : It uses extra memory when compared to the array and singly linked list. Since elements in memory are stored randomly, therefore the elements are accessed sequentially no direct access is allowed.

15. Uses Of DLL : It is used in the navigation systems where front and back navigation is required. It is used by the browser to implement backward and forward navigation of visited web pages that is a back and forward button. It is also used to represent a classic game deck of cards. It is also used by various applications to implement undo and redo functionality. Doubly Linked List is also used in constructing  MRU / LRU   (Most/least recently used) cache. Other data structures like  stacks ,  Hash Tables ,  Binary trees  can also be constructed or programmed using a doubly-linked list. Also in many operating systems, the  thread scheduler (the thing that chooses what process needs to run at which time) maintains a doubly-linked list of all processes running at that time.

16. CIRCULAR LINKED LIST In a single linked list, the link field of the last node is null. If we utilize this link field to store the pointer of the header node, a number of advantages can be gained. A linked list, whose last node points back to the first node, instead of containing the null pointer is called a circular list

17. Advantages: 1 . Accessibility of a member node – here every member node is accessible from any node by merely chaining through the list eg : Finding of earlier occurrence or post occurrence of a data will be easy 2. Null link problem- Null value in next field may create problem during the execution of the program if proper care is not taken 3. Some easy-to-implement operations - Operations like merging, splitting, deletion, dispose of an entire list etc can be done easily with circular list

18. Advantages: 1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to stop when the first visited node is visited again. 2)  Useful for implementation of queue. Unlike  this  implementation, we don’t need to maintain two pointers for front and rear if we use circular linked list. We can maintain a pointer to the last inserted node and front can always be obtained as next of last. 3)  Circular lists are useful in applications to repeatedly go around the list. For example, when multiple applications are running on a PC, it is common for the operating system to put the running applications on a list and then to cycle through them, giving each of them a slice of time to execute, and then making them wait while the CPU is given to another application. It is convenient for the operating system to use a circular list so that when it reaches the end of the list it can cycle around to the front of the list. 4)  Circular Doubly Linked Lists are used for implementation of advanced data structures like  Fibonacci Heap .

19. Disadvantages: If not cared, system may get trap into in infinite loop It occurs when we are unable to detect the end of the list while moving from one node to the next

20. Circular Linked List (Traversal) In a circular linked list, we stop traversal when we reach the first node again . /* Function to traverse a given Circular linked list and print nodes */ void printList ( struct Node *first) { struct Node *temp = first; // If linked list is not empty if (first != NULL) { // Keep printing nodes till we reach the first node again do { printf ("%d ", temp->data); temp = temp->next; } while (temp != first); } }

21. Implementation   To implement a circular singly linked list, we take an external pointer that points to the last node of the list. If we have a pointer last pointing to the last node, then last -> next will point to the first node. The pointer  last  points to node Z and last -> next points to node P.  

22. Insertion   A node can be added in three ways:  Insertion in an empty list Insertion at the beginning of the list Insertion at the end of the list Insertion in between the nodes

23. Insertion in an empty List   Initially, when the list is empty, the  last  pointer will be NULL.    

24. After inserting node T,  After insertion, T is the last node, so the pointer  last  points to node T. And Node T is the first and the last node, so T points to itself. 

25. Function to insert a node into an empty list,  struct Node * addToEmpty ( struct Node *last, int data) {      // This function is only for empty list      if (last != NULL)        return last;        // Creating a node dynamically.      struct Node *temp =            ( struct Node*) malloc ( sizeof ( struct Node));        // Assigning the data.      temp -> data = data;      last = temp;      // Note : list was empty. We link single node      // to itself.      temp -> next = last;        return last; }

26. Insertion at the beginning of the list   To insert a node at the beginning of the list, follow these steps:  1. Create a node, say T.  2. Make T -> next = last -> next.  3. last -> next = T. 

27. After insertion, 

28. Function to insert nodes at the beginning of the list,  struct Node * addBegin ( struct Node *last, int data) {    if (last == NULL)       return addToEmpty (last, data);      // Creating a node dynamically.    struct Node *temp          = ( struct Node *) malloc ( sizeof ( struct Node));        // Assigning the data.    temp -> data = data;      // Adjusting the links.    temp -> next = last -> next;    last -> next = temp;        return last; }

29. Insertion at the end of the list   To insert a node at the end of the list, follow these steps:  1. Create a node, say T.  2. Make T -> next = last -> next;  3. last -> next = T.  4. last = T. 

30. After insertion, 

31. Function to insert a node at the end of the List  struct Node * addEnd ( struct Node *last, int data) {    if (last == NULL)       return addToEmpty (last, data);      // Creating a node dynamically.    struct Node *temp =          ( struct Node *) malloc ( sizeof ( struct Node));        // Assigning the data.    temp -> data = data;      // Adjusting the links.    temp -> next = last -> next;    last -> next = temp;    last = temp;        return last; }

32. Insertion in between the nodes   To insert a node in between the two nodes, follow these steps:  1. Create a node, say T.  2. Search for the node after which T needs to be inserted, say that node is P.  3. Make T -> next = P -> next;  4. P -> next = T.

33. Suppose 12 needs to be inserted before the node has the value 10,

34. After searching and insertion, 

35. Function to insert a node at the end of the List, struct Node * addAfter ( struct Node *last, int data, int item) {      if (last == NULL)         return NULL;        struct Node *temp, *p;      p = last -> next;        // Searching the item.      do      {          if (p ->data == item)          {              // Creating a node dynamically.              temp = ( struct Node *) malloc ( sizeof ( struct Node));                // Assigning the data.              temp -> data = data;                // Adjusting the links.              temp -> next = p -> next;                                 

36.   // Adding newly allocated node after p.              p -> next = temp; // Checking for the last node.              if (p == last)                  last = temp;                return last;          }          p = p -> next;      } while (p != last -> next );   printf ( “%d not present in the list”,item ) ;      return last; }

37. Deletion at different positions in a Circular Linked List Given a Circular Linked List. The task is to write programs to delete nodes from this list present at:  First position. Last Position. At any given position    .

38. Deleting first node from Singly Circular Linked List

39. Approach :  1. Take two pointers current and previous and traverse the list. 2. Keep the pointer current fixed pointing to the first node and move previous until it reaches the last node. 3. Once , the pointer previous reaches the last node, do the following:  previous->next = current-> next head = previous -> next;

40. Function to delete first node from singly circular linked list :   // Function to delete First node of // Circular Linked List void DeleteFirst ( struct Node** head) {      struct Node *previous = *head, * firstNode = *head;        // check if list doesn't have any node      // if not then return      if (*head == NULL) {          printf ( "\ nList is empty\n" );          return ;      }        // check if list have single node      // if yes then delete it and return      if (previous->next == previous) {          *head = NULL;          return ;      }       

41. // traverse second node to first      while (previous->next != *head) {            previous = previous->next;      }        // now previous is last node and      // first node( firstNode ) link address      // put in last node(previous) link      previous->next = firstNode ->next;        // make second node as head node      *head = previous->next;      free ( firstNode );      return ; }

42. Deleting the last node of the Circular Linked List

43. Approach :  1.Take two pointers current and previous and traverse the list. 2. Move both pointers such that next of previous is always pointing to current. Keep moving the pointers current fand previous until current reaches the last node and previous is at the second last node. 3. Once , the pointer current reaches the last node, do the following:  previous->next = current-> next head = previous -> next;

44. Function to delete last node from the list :  // Function delete last node of // Circular Linked List void DeleteLast ( struct Node** head) {      struct Node *current = *head, *temp = *head, *previous;        // check if list doesn't have any node      // if not then return      if (*head == NULL) {          printf ( "\ nList is empty\n" );          return ;      }        // check if list have single node      // if yes then delete it and return      if (current->next == current) {          *head = NULL;          return ;      }  

45.      // move first node to last      // previous      while (current->next != *head) {          previous = current;          current = current->next;      }        previous->next = current->next;      *head = previous->next;      free (current);      return ; }

46. Deleting nodes at given index in the Circular linked list

47. Approach :  1. First , find the length of the list. That is, the number of nodes in the list. 2.Take two pointers previous and current to traverse the list. Such that previous is one position behind the current node. 3. Take a variable count initialized to 0 to keep track of the number of nodes traversed. 4.Traverse the list until the given index is reached. 5.Once the given index is reached, do  previous->next = current->next .

48. Function to delete a node at given index or location from singly circular linked list :  // Function to delete node at given index // of Circular Linked List void DeleteAtPosition ( struct Node** head, int index) {      // find length of list      int len = Length(*head);      int count = 1;      struct Node *previous = *head, *next = *head;        // check if list doesn't have any node      // if not then return      if (*head == NULL) {          printf ( "\ nDelete Last List is empty\n" );          return ;      }        // given index is in list or not      if (index >= len || index < 0) {          printf ( "\ nIndex is not Found\n" );          return ;      }       

49. // delete first node      if (index == 0) {          DeleteFirst (head);          return ;      }        // traverse first to last node      while ( len > 0) {            // if index found delete that node          if (index == count) {              previous->next = next->next;              free (next);              return ;          }          previous = previous->next;          next = previous->next;          len --;          count++;      }        return ; }