Linked lists - Data Structures and Problem Solving Using Java - page 632

Before describing some of the additional operations that are available, let
us consider how the insertion and removal operations change. Naturally, we
can now do both insertBefore and insertAfter . Twice as many link moves are
involved for insertAfter with doubly linked lists as with singly linked lists. If
we write each statement explicitly, we obtain

Insertion and
removal involve
twice as many link
changes as for a
singly linked list.

newNode = new DoublyLinkedListNode( x );
newNode.prev = current; // Set x's prev link
newNode.next = current.next; // Set x's next link
newNode.prev.next = newNode; // Set a's next link
newNode.next.prev = newNode; // Set b's prev link
current = newNode;

As we showed earlier, the first two link moves can be collapsed into the
DoublyLinkedListNode construction that is done by new . The changes (in
order 1 , 2 , 3 , 4 ) are illustrated in Figure 17.17.

Figure 17.17 can also be used as a guide in the removal algorithm. Unlike
the singly linked list, we can remove the current node because the previous
node is available to us automatically. Thus to remove x we have to change a 's
next link and b 's prev link. The basic moves are

The remove opera-
tion can proceed
from the current
node because
we can obtain the
previous node
instantly.

current.prev.next = current.next; // Set a's next link
current.next.prev = current.prev; // Set b's prev link
current = head; // So current is not stale

To do a complete doubly linked list implementation, we need to decide
which operations to support. We can reasonably expect twice as many opera-
tions as in the singly linked list. Each individual procedure is similar to the
linked list routines; only the dynamic operations involve additional link
moves. Moreover, for many of the routines, the code is dominated by error
checks. Although some of the checks will change (e.g., we do not test against
null ), they certainly do not become any more complex. In Section 17.5, we
use a doubly linked list to implement the Collections API linked list class,

figure 17.17
Insertion in a doubly
linked list by getting
new node and then
changing pointers in
the order indicated

... . ..

a b

3

2

1

x

4