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:
-
copy the list header's front reference into the link field of the new node
-
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:
-
copy the list's rear reference into the link field of the last node in
the list
-
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.
-
initialize previous to point to the first node in the list, and
current
to point to the second node in the list
-
while the new node's key is greater than the key of the node current
points to
{
move previous ahead one node
move current ahead one node
}
-
make the new node's next field point to current
-
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
-
the "duplicate key" is treated as an error and reported in some way (boolean
success flag, exception) to the calling program;
-
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)
