Java Reference
In-Depth Information
Suppose that the node to be inserted into the chain contains the integer 6. We need to locate
where in the chain the new node belongs. Since we have a reference,
firsNode
, to the first node in
the chain, we can start there. We make comparisons as we move toward the end of the chain until
we find the correct insertion point. Thus, we would compare 6 with 2, then with 3, with 5, and
finally with 8 to see that 6 belongs between 5 and 8.
To insert a node into a chain, we need a reference to the node prior to the point of insertion.
Thus, during the traversal of the chain, we save a reference to the node before the current one, as
Figure 8-10 illustrates. Note that inserting at the beginning of the chain differs somewhat from
inserting anywhere else in the chain.
FIGURE 8-10
During the traversal of a chain to locate the insertion point, save
a reference to the node before the current one
6 belongs here; it is greater than
2, 3, and 5 but less than 8
2
3
5
8
10
firstNode
previousNode
currentNode
8.17
Now imagine that we have a method
insertInOrder(nodeToInsert)
that inserts a node into its
correct sorted position within a chain, as just described. We can use this method to implement an
insertion sort by adopting the same strategy that we used to sort an array: Divide the chain into two parts.
The first part is sorted, and it initially contains only the first node. The second part is unsorted and
initially is the rest of the chain. Figure 8-11 illustrates how to make this division. We first make the
variable
unsortedPart
reference the second node and then set the link portion of the first node to
null
.
FIGURE 8-11
Breaking a chain of nodes into two pieces as the first step in an
insertion sort: (a) the original chain; (b) the two pieces
(a)
5
9
4
1
2
firstNode
(b)
5
2
9
4
1
firstNode
unsortedPart
To sort the nodes, we use the method
insertInOrder
to take each node from the unsorted part and
insert it into the sorted part. Notice that our plan relinks existing nodes instead of creating new ones.
