1.5.6 Keeping a List Sorted1.5.5 Deleting List Elements1.5 Dynamic Data Structures1.6 Abstract Data Types

1.5.6 Keeping a List Sorted

Suppose we want to keep a list sorted, i.e., we want to insert new elements not at the head of the list but at those positions that correspond to the order of their values. The following diagram illustrates the case where a node with value 3 is inserted into the list [1,2,5] should result in the list [1,2,3,5].


Inserting

Inserting into a Sorted List
 


The insertion process is similar to the deletion process explained in the previous section. We have to maintain a reference to the node which is currently investigated. If we find out that the new node has to be inserted before the current node, we have to update the link in the predecessor node. The corresponding Java method is the following:

  // ---------------------------------------------------------
  // list = insertSorted(value)
  // 'list' is the result of inserting 'value' into
  // the sorted 'this' list.
  //
  // Input
  //   'this' is sorted.
  // Output
  //   'list == this' and 'this' is sorted.
  //   'this' is the same as the old 'this' except that
  //     a new node with 'value' has been inserted.
  // ---------------------------------------------------------
  List insertSorted(int value)
  {
    Node prev = null; // previous node
    Node node = head; // current node
    while (node != null && node.value < value)
    {
      prev = node;
      node = node.next;
    }
    Node n = new Node(value, node);
    if (prev == null)
      head = n;
    else
      prev.next = n;
    return this;
  }

When we have found the node before which the new node is to be inserted, we allocate a new node n which holds value and link it to node. Then we update either the head reference (if the new node becomes the first node of the list) or the link in the predecessor node prev.

If a list is sorted, we can optimize the method search a bit by terminating the search when a node has been found that holds a value greater than the value looked for. The corresponding method becomes

  // ---------------------------------------------------------
  // node = search(value)
  // 'node' is the result of searching 'value' in 'this' list
  //
  // Output:
  //   all nodes referenced via 'this' remain unchanged.
  //   if 'node == null', then 'value' does not occur in 'this'
  //   if 'node != null', then 'node.value == value' and 'node'
  //     is the first node in 'this' for which this holds.
  // ---------------------------------------------------------
  Node search(int value)
  {
    for (Node node = head; node != null; node = node.next)
    {	
      if (node.value == value) return node;
      if (node.value > value) return null;
    }
    return null;
  }

In the unsorted case, always the whole list has to be traversed to find out that an element is not in the list. But also in the sorted case, in average half of the list has to be traversed; therefore the performance improvement is only moderate. Sorted lists are therefore used only, if we want for other reasons to process the elements in some order.


© Wolfgang Schreiner; February 3, 2005

1.5.6 Keeping a List Sorted1.5.5 Deleting List Elements1.5 Dynamic Data Structures1.6 Abstract Data Types