1.5.5 Deleting List Elements1.5.4 Searching for List Elements1.5 Dynamic Data Structures1.5.6 Keeping a List Sorted

1.5.5 Deleting List Elements

Suppose we want to delete from a list the first node that holds a particular key value. For this purpose, we have to find the appropriate list node and update any reference to this node by a link to the successor node:

The following diagram illustrates the case where the node with value 2 is deleted from a list [3,2,1].


Deleting

Deleting a List Element
 


Please note that "deleteting" a node actually means "unlinking" the node from the list; the node itself still exists (and is unchanged) and may be still referenced from other data structures.

The key idea in the deletion process is to traverse the list looking for the node to be deleted while keeping track of the predecessor node of the currently investigated node. Once the right node is found, we have to update the link of the predecessor. The corresponding Java method is as follows:

  // ---------------------------------------------------------
  // list = delete(value)
  // 'list' is the result of deleting the first node that
  /  holds 'value' from 'this' list.
  //
  // Output
  //   'list == this'.
  //   if 'value' was not in the old 'this', 'this' equals
  //     the old 'this'.
  //   if 'value' was in the old 'this', 'this' equals the 
  //     old 'this' except that the first node with 
  //     'node.value == value' is unlinked.
  // ---------------------------------------------------------
  List delete(int value)
  {
    Node prev = null; // previous node
    Node node = head; // current node
    while (node != null && node.value != value)
    {
      prev = node;
      node = node.next;
    }
    if (node != null)
    {
      if (prev == null)
        head = node.next;
      else
        prev.next = node.next;
    }
    return this;
  }

The critical part of this method is the condition after the iteration. If node is not null, then it holds value, i.e., we have found the node to be deleted. Then, if prev is null, this is the first node in the list and head has to be updated. Otherwise, prev references the predecessor of node and its link to the next node has to be updated.

Example  Since delete has been implemented as a program function that returns the updated list as its argument, we can now write statements like
  List l = new List();
  l.insert(1).insert(2).insert(1).delete(1).delete(2).delete(2);

Which elements does l contain after these update operations?


© Wolfgang Schreiner; February 3, 2005

1.5.5 Deleting List Elements1.5.4 Searching for List Elements1.5 Dynamic Data Structures1.5.6 Keeping a List Sorted