Linked Lists - Building Java Programs: A Back to Basics Approach - page 934

2 3

1

data
2

next data

4

next
/

p

5 6

4

data
3

next data

9

next
/ q

Having the variables numbered makes it easier to discuss the task at hand. Which
of these variables has to change in value to get from the before picture to the after
picture? The boxes numbered 3, 4, and 5 have to change. If we change them appro-
priately, we'll be done.
We have to be careful about how we change the links. The order can be important.
For example, suppose we start by changing box 4 (the variable q ). In the final situa-
tion, it's supposed to point at the node with 9 in it. We can accomplish this by
leapfrogging over the current node to which it is pointing:

q = q.next;

But if we start with this change, what happens to the node that contains 3 ? We lose
track of it, as the following picture indicates:

2 3

1

data
2

next data

4

next
/

p

5 6

4

data
3

next data

9

next
/ q

Once we have lost track of the node containing 3 , we have no way to get back to
it. It's like a helium balloon that has floated away because we let go of the string.
This is a common problem in linked list programming that you have to consider
carefully. One solution is to introduce a temporary variable that would keep track of
the node to which the variable q used to point (the node containing 3 ). Often, though,
we can instead solve the problem by carefully choosing the order of the changes that
we make.
Of the three values we have to change to solve this problem, the one that is safe to
change is box 3 because it's currently null . We begin by setting it to point to the
node containing 3 :

p.next.next = q;