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 as we traverse it we end up in the following state when the loop exits:
Here is what the code to traverse the list with two pointers looks like:
while(current != null && current.key < key) {
previous = current;
current = current.link;
}
(We would have to declare previous earlier in the method.)
Now we are ready to insert the new node.
Which lines of code inserted immediately after the while
loop will properly insert the new node.
Click here to go to the next step.
Previous | Home