Friday, November 28, 2014

Given only a pointer to a single node in a singly linked list how do you delete it

Approach

  • If we don't have the pointer to the previous node, and don't have the head pointer to be able to get to the previous node, then our approach is to copy the contents of the node that comes after the node to be deleted into the current node.
  • If the node we have to delete is the last node, then we won't be able to delete it.  Our only other option in this case is to make this node a "dummy node".
  • This takes constant time O(1) since we don't have to traverse the list to get the node previous to the node to be deleted.
      public boolean removeSpecific(Node refNode) {  
           if (refNode == null || refNode.next == null)  
                return false;  
           Node next = refNode.next;  
           refNode.data = next.data;  
           refNode.next = next.next;  
           return true;  
      }  

No comments:

Post a Comment