Java Reference
In-Depth Information
The final linked list variation is called a
doubly linked list
. The idea is that instead of
storing links in a single direction, we store them in both directions. That means that our
node class has fields for both
next
and
prev
and that we maintain the links in both
directions. For example, the three-element list [3, 7, 12] would be stored as follows:
prev
/
data
3
next
prev data
7
next
prev data
12
next
front
/
Notice that each node now has two different links pointing in different directions.
The list also has two
null
links. The final node has a
next
field that is
null
and the
first node has a
prev
field that is
null
to indicate in each case that there are no other
nodes in that direction.
In practice, programmers use some combination of these techniques. For example,
Sun uses all three techniques in its implementation of
LinkedList<E>
. It has a dou-
bly linked, circular list with a single dummy node to avoid having special cases for
an empty list.
In our implementation, we will use two of these techniques. Our list will be dou-
bly linked and will have two dummy nodes, one for the front of the list and one for
the back of the list. We will also introduce an extra field to keep track of the back of
the list. Thus, in our version, an empty list will look like this:
front
back
prev
/
data
0
next
prev data
0
next
/
This list doesn't look very empty, but that's the idea. Even when it is empty, our
list will have two dummy header nodes. That way, the fields
front
and
back
will
always point to exactly the same dummy node and we won't have to write any spe-
cial case code for changing their values. Instead, all insertions will occur between the
two dummy nodes. For example, if we insert the values
18
and
73
, our list will look
like this:
front
back
prev
/
data
0
next
prev data
18
next
prev data
73
next
prev data
0
next
/
You can think of the dummy nodes as bookends that appear on either side of the
actual nodes.
Search WWH ::
Custom Search