Java Reference
In-Depth Information
15.4
Variations on a Linked List
I have called this principle, by which each slight variation, if useful, is preserved,
by the term Natural Selection.
CHARLES DARWIN,
The Origin of Species
In this section, we discuss some variations on linked lists, including the two data
structures known as stacks and queues. Stacks and queues need not involve linked lists,
but one common way to implement a stack or a queue is to use a linked list.
Doubly Linked List
An ordinary linked list allows you to move down the list in one direction only
(following the links). A
doubly linked list
has one link that has a reference to the next
node and one that has a reference to the previous node. In some cases, the link to the
previous node can simplify our code. For example, we will no longer need to have a
previous
instance variable to remember the node that links to the current position.
Diagrammatically, a doubly linked list looks like the sample list in Display 15.21.
The node class for a doubly linked list can begin as follows:
doubly
linked list
private class
TwoWayNode
{
private
String item;
private
TwoWayNode previous;
private
TwoWayNode next;
...
The constructors and some of the methods in the doubly linked list class will require
changes (from the singly linked case) in their definitions to accommodate the extra link.
The major changes are to the methods that add and delete nodes. To make our code a
little cleaner, we can add a new constructor that sets the previous and next nodes:
public
TwoWayNode(String newItem, TwoWayNode previousNode,
TwoWayNode nextNode)
{
item = newItem;
next = nextNode;
previous = previousNode;
}
To add a new
TwoWayNode
to the front of the list requires setting links on two nodes
instead of one. The general process is shown in Display 15.22. In the
addToStart
method, we first create a new
TwoWayNode
. Because the new node will go on the front
of the list, we set the previous link to
null
and the
next
link to the current head:
TwoWayNode newHead =
new
TwoWayNode(itemName, null, head);
