Deleting a Node from a Singly Linked List

This article is part of article series - "Datastructures"

Previous Article: Implementation of Singly Linked List.
Next Article: Reversing a Singly Linked List

Deletion of a Node from a Singly Linked List
Similar to insertion we have three cases for deleting a Node from a Singly Linked List.

• Deleting First Node in Singly Linked List
  
  To complete deletion of firstNode in the list we have to change Head pointing to Next of firstNode.
  
  Pseudocode:

  firstNode = Head
  
  Head = firstNode->Next
  
  free firstNode

  Complexity:
  Time Complexity: O(1)
  Space Complexity: O(1)
  
  Sourcecode:

   int delNodeData(int num)
   {
      struct Node *prev_ptr, *cur_ptr;
  
      cur_ptr=Head;
  
      while(cur_ptr != NULL)
      {
         if(cur_ptr->Data == num)
         {
            if(cur_ptr==Head)
            {
               Head=cur_ptr->Next;
               free(cur_ptr);
               return 0;
            }
            else
            {
               prev_ptr->Next=cur_ptr->Next;
               free(cur_ptr);
               return 0;
            }
         }
         else
         {
            prev_ptr=cur_ptr;
            cur_ptr=cur_ptr->Next;
         }
      }
  
      printf("\nElement %d is not found in the List", num);
      return 1;
   }

• Deleting Last Node in the Singly Linked List
  
  Traverse to Last Node in the List using two pointers namely prevNode and curNode. Once curNode reaches the last Node in the list point Next in prevNode to NULL and free the curNode.
  
  Pseudocode:

  curNode = head
  
  forever:
  
   if curNode->Next == NULL
   break
  
   prevNode = curNode
   curNode = curNode->Next
  
  prevNode->Next = NULL
  
  free curNode

  Complexity:
  Time Complexity: O(n)
  Space Complexity: O(1)
  
  
• Deleting Node from position 'p' in the List
  
  To delete a Node at the position 'p' we have to first traverse the list until we reach the position 'p'. For this case have to maintain two pointers namely prevNode and curNode. Since Singly Linked Lists are uni-directional we have to maintain the information about previous Node in prevNode. Once we reach the position 'p' we have to modify prevNode Next pointing to curNode Next and free curNode.
  
  Pseudocode:
  

  curNode = head
  curPos = 1
  
  forever:
  
   if curPos == P || curNode == NULL
   break
  
   prevNode = curNode
   curNode = curNode->Next
   curPos++
  
  if curNode != NULL:
   
   prevNode->Next = curNode->Next
   free curNode

  Complexity:
  Time Complexity: O(n) worst case
  Space Complexity: O(3)
  
  Sourcecode:

  int delNodeLoc(int loc)
   {
      struct Node *prev_ptr, *cur_ptr;
      int i;
  
      cur_ptr=Head;
  
      if(loc > (length()) || loc <= 0)
      {
          printf("\nDeletion of Node at given location is not possible\n ");
      }
      else
      {
          // If the location is starting of the list
          if (loc == 1)
          {
              Head=cur_ptr->Next;
              free(cur_ptr);
              return 0;
          }
          else
          {
              for(i=1;i<loc;i++)
              {
                  prev_ptr=cur_ptr;
                  cur_ptr=cur_ptr->Next;
              }
  
              prev_ptr->Next=cur_ptr->Next;
              free(cur_ptr);
          }
      }
      return 1;
   }

Previous Article: Implementation of Singly Linked List.
Next Article: Reversing a Singly Linked List