Java Reference
In-Depth Information
The idea of stopping one step early in processing a list isn't limited to this append-
ing operation. It is a fundamental pattern that comes up over and over in linked list
programming, as you'll see with the other examples in the chapter.
The Middle of the List
If you want your LinkedIntList to have the same capabilities as the ArrayIntList
that we developed in Chapter 15, you have to add several new methods. For example,
you will want to have a method called get that returns a value at a given index. When
the underlying structure was an array, you could simply ask for the array element at
that index. But for a linked list, you have access only to the front of the list. So, to
find a value at a particular index, you have no choice but to start at the front and
examine each value until you get to the desired location:
public int get(int index) {
ListNode current = front;
for (int i = 0; i < index; i++) {
current = current.next;
}
return current.data;
}
As we noted earlier, this means that your linked list does not have the fast random
access property that arrays and our ArrayIntList have. Instead, we say that the
linked list has sequential access, meaning that you have to go through the values in
sequence until you get to the value of interest.
Let's now consider the task of adding a value at a particular index. There is a spe-
cial case when you add at index 0, at the front of the list. For example, suppose a list
contains the values [19, 8, 42]:
data
19
next
data
8
next
data
42
next
/
front
Suppose you want to add the value 5 at the front of this list. Then you will need to
construct a new node that has the value 5 and that points to the current front of the list:
new ListNode(5, front)
Constructing this node generates the following situation:
data
5
next
data
19
next
data
8
next
data
42
next
/
front
 
Search WWH ::




Custom Search