School of Engineering and Applied Science Department of Computer Science CSci 133 -- Algorithms and Data Structures I http://www.seas.gwu.edu/~csci133/spring03 Prof. Michael B. Feldman mfeldman@gwu.edu

Insertion and Deletion with Ordered Linked Lists

A linked list is often used as an implementation for an ordered sequence of elements, which appear in order according to some key, that is, a field that is used to compare objects. This can be thought of as a linked-list analogy to a sorted array. It is therefore important to understand how to insert a new object into a linked list that is already sorted, in such a way that the sorted condition is preserved. Similarly, it is important to understand how to delete a node from such a list.

For this example, the objects consists of just strings; in general, each object will have several data fields of differing types, with one field designated as the key.

(In Java we might implement the objects as a class that implements Java's Comparable interface, and provide a compareTo method that selects and compares the keys. This is a Java-dependent implementation detail; the fundamental process of ordered insertion in a linked list is independent of any language-specific details.)

Insertion: Building an Ordered Linked List

Let's start with a list L1, represented by a header that contains a reference to the first node (front) and a reference to the last node (rear). Initially, the list is empty; the two references are null:

The insertion process has four distinct cases:

• Case 1. An inserted node is the first one to be added to an empty list.
• Case 2. The inserted node’s key is less than those of all others in the list; thus, the node goes at the beginning of a nonempty list.
• Case 3. The key is greater than all the others; thus, the node goes at the end of the list.
• Case 4. The key lies between two others; thus, the node goes in the middle of the list somewhere.

Case 1. When the list is initially empty, inserting a new node is very easy. We just set the list header's front and rear references to point to the new arrival. Our updated list is

Case 2. If the key of the new arrival is less than the key of the first node, we have a two-step subalgorithm:

1. copy the list header's front reference into the link field of the new node
2. make the list header's front reference point to the new node.
Our updated list is

Case 3. If the key of the new arrival is less than the key of the first node, again we have a two-step subalgorithm:

1. copy the list's rear reference into the link field of the last node in the list
2. make the list's rear reference point to the new node.
Our updated list is now

Case 4. Since we've covered the simple conditions in Cases 1, 2, and 3, Case 4 leaves only one condition: the newly-arriving node has a key that lies between the keys of two adjacent existing nodes, and thus must be inserted between those two nodes. We must make the new node point to the next one in the list, but also we must make the new node's predecessor node point to it.

The subalgorithm requires a search through the list, to find the proper position of the new arrival. We will need two reference variables, current and previous, for this search, to keep track of the new node's possible predecessor and its possible successor. These two pointers move together through the list. They are initialized like this:

We know the list has at least two nodes in it already, and that the new node's key is known to be greater than that of the first node (how do we know these facts?), so the first possible position for the new arrival is between the first and second nodes.

1. initialize previous to point to the first node in the list, and current to point to the second node in the list
2. while the new node's key is greater than the key of the node current points to

3. {
move previous ahead one node
move current ahead one node
}
4. make the new node's next field point to current
5. make the previous node's next field point to the new node
Inserting Label gives this updated list; previous and current are shown in their final state.

To make sure you understand the entire algorithm, try inserting Aunt, Baby, King, Queen, and Uncle, by following the algorithm precisely, step by step.

What Should We Do with Duplicate Keys?

Suppose an object arrives whose key matches the key of an object that's already in the list? The two most common strategies for handling this are
1. the "duplicate key" is treated as an error and reported in some way (boolean success flag, exception) to the calling program;
2. the second object is inserted in the list, generally after the first object
A third, less common, approach is to combine the data from the first and second objects -- the second object might be supplying additional information, for example.

There's no one best strategy -- the software designer must choose one that best suits the intended application(s).

Deletion from an Ordered Linked List

Deletion is similar to insertion in many ways. Here a key is specified, and the deletion algorithm deletes the node that contains that key. If there is no such node in the list, this fact is reported in some way to the calling program. There are two cases:
• Case 1. The arriving key matches the one in the first node.
• Case 2. The arriving key is greater than the one in the first node.
Case 1. If the arriving key matches the one in the first node, the first node is deleted by copying the first node's next field into the list header's front reference. If the front reference becomes null, this means the only node in the list was deleted and the rear reference must be made null as well.

Case 2. As in the insertion case, the algorithm uses a pair of reference variables, current to indicate the node whose key is compared to the arriving one, and previous to point to that node's predecessor node. Since the keys in the list are in ascending order, the search proceeds as long as the arriving key is greater than the keys already in the list. Once a node is found whose key is equal to or greater than the arriving one, the search is over. There are two possibilities:

• The keys are equal, in which case the node is deleted.
• The keys are not equal, in which case there is no node in the list with the desired key; inform the calling program.
Make sure you understand the deletion algorithm by deleting the first, the last, and some intermediate node frm the list L1 above.

(end of article)