/* Ajith - Syntax Higlighter - End ----------------------------------------------- */

12.25.2012

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

No comments :

Post a Comment

Your comments are moderated