Starting from the state shown in the last picture, there is no way to easily hook in the new node. We need a handle on the node before the current one, so that we can change its link.
The solution to this problem is to use a second pointer that lags one node behind current. If we move two pointers along the list when traversing it we end up in the following situation:
When the loop exits, the variables are in the following state:
Here is what the code to traverse the list with two pointers looks like (the statement Node previous; would appear earlier in the method):
while(current != null && current.key < key) {
previous = current;
current = current.link;
}
Now we are ready to insert the new node.
Which lines of code inserted immediately following the while
loop will properly insert the new node.
Click here to go to the next step.
Previous | Home