Java Reference
In-Depth Information
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 lit-
tle 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);
Next we must set the
previous
link on the old head node to reference the new head.
We can do this by setting
head.previous = newHead
, but we must take care to ensure
that
head
is not
null
(i.e., the list is not empty). Finally, we can set
head
to
newHead
.
if
(head !=
null
)
{
head.previous = newHead;
}
head = newHead;
To delete a node from the doubly linked list also requires updating the references
on both sides of the node to delete. Thanks to the backward link there is no need for
an instance variable to keep track of the previous node in the list, as was required for
the singly linked list. The general process of deleting a node referenced by
position
is
shown in Display 15.23. Note that some cases must be handled separately, such as
deleting a node from the beginning or the end of the list.
The process of inserting a new node into the doubly linked list is shown in Display
15.24. In this case we will insert the new node in front of the iterator referenced by
position
. Note that there are also special cases for the insert routine when inserting to
the front or adding to the end of the list. Only the general case of inserting between
two existing nodes is shown in Display 15.24.
A complete example of a doubly linked list is shown in Display 15.25. The code in
Display 15.25 is modified from the code in Display 15.17. Use of the doubly linked
list is virtually identical to use of a singly linked list. Display 15.26 demonstrates addi-
tion, deletion, and insertion into the doubly linked list.
