3.2

A `DLList` (doubly-linked list) is very similar to an `SLList` except
that each node
in a `DLList` has references to both the node
that follows it and the node
that precedes it.

class Node { T x; Node prev, next; }

When implementing an `SLList`, we saw that there were always several
special cases to worry about. For example, removing the last element
from an `SLList` or adding an element to an empty `SLList` requires care
to ensure that
and
are correctly updated. In a `DLList`,
the number of these special cases increases considerably. Perhaps the
cleanest way to take care of all these special cases in a `DLList` is to
introduce a
node.
This is a node that does not contain any data,
but acts as a placeholder so that there are no special nodes; every node
has both a
and a
, with
acting as the node that
follows the last node in the list and that precedes the first node in
the list. In this way, the nodes of the list are (doubly-)linked into
a cycle, as illustrated in Figure 3.2.

int n; Node dummy; DLList() { dummy = new Node(); dummy.next = dummy; dummy.prev = dummy; n = 0; }

Finding the node with a particular index in a `DLList` is easy; we can
either start at the head of the list (
) and work forward,
or start at the tail of the list (
) and work backward.
This allows us to reach the
th node in
time:

Node getNode(int i) { Node p = null; if (i < n / 2) { p = dummy.next; for (int j = 0; j < i; j++) p = p.next; } else { p = dummy; for (int j = n; j > i; j--) p = p.prev; } return p; }

The and operations are now also easy. We first find the th node and then get or set its value:

T get(int i) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); return getNode(i).x; } T set(int i, T x) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); Node u = getNode(i); T y = u.x; u.x = x; return y; }

The running time of these operations is dominated by the time it takes to find the th node, and is therefore .

If we have a reference to a node
in a `DLList` and we want to insert a
node
before
, then this is just a matter of setting
,
, and then adjusting
and
. (See Figure 3.3.)
Thanks to the dummy node, there is no need to worry about
or
not existing.

Node addBefore(Node w, T x) { Node u = new Node(); u.x = x; u.prev = w.prev; u.next = w; u.next.prev = u; u.prev.next = u; n++; return u; }

Now, the list operation
is trivial to implement. We find the
th node in the `DLList` and insert a new node
that contains
just before it.

void add(int i, T x) { if (i < 0 || i > n) throw new IndexOutOfBoundsException(); addBefore(getNode(i), x); }

The only non-constant part of the running time of is the time it takes to find the th node (using ). Thus, runs in time.

Removing a node
from a `DLList` is easy. We only need to adjust
pointers at
and
so that they skip over
. Again, the
use of the dummy node eliminates the need to consider any special cases:

void remove(Node w) { w.prev.next = w.next; w.next.prev = w.prev; n--; }

Now the operation is trivial. We find the node with index and remove it:

T remove(int i) { if (i < 0 || i > n - 1) throw new IndexOutOfBoundsException(); Node w = getNode(i); remove(w); return w.x; }

Again, the only expensive part of this operation is finding the th node using , so runs in time.

The following theorem summarizes the performance of a `DLList`:

It is worth noting that, if we ignore the cost of the
operation, then all operations on a `DLList` take constant time.
Thus, the only expensive part of operations on a `DLList` is finding
the relevant node. Once we have the relevant node, adding, removing,
or accessing the data at that node takes only constant time.

This is in sharp contrast to the array-based `List` implementations of
Chapter 2; in those implementations, the relevant array
item can be found in constant time. However, addition or removal requires
shifting elements in the array and, in general, takes non-constant time.

For this reason, linked list structures are well-suited to applications
where references to list nodes can be obtained through external means.
An example of this is the `LinkedHashSet` data structure found in the
Java Collections Framework, in which a set of items is stored in a
doubly-linked list and the nodes of the doubly-linked list are stored
in a hash table (discussed in Chapter 5). When elements
are removed from a `LinkedHashSet`, the hash table is used to find the
relevant list node in constant time and then the list node is deleted
(also in constant time).

opendatastructures.org