3.2 $\mathtt{DLList}$: A Doubly-Linked List

A $\mathtt{DLList}$ (doubly-linked list) is very similar to an $\mathtt{SLList}$ except that each node $\mathtt{u}$ in a $\mathtt{DLList}$ has references to both the node $\mathtt{u.next}$ that follows it and the node $\mathtt{u.prev}$ that precedes it.

  struct Node {
    T x;
    Node *prev, *next;
  };

When implementing an $\mathtt{SLList}$, we saw that there were always some special cases to worry about. For example, removing the last element from an $\mathtt{SLList}$ or adding an element to an empty $\mathtt{SLList}$ requires special care so that $\mathtt{head}$ and $\mathtt{tail}$ are correctly updated. In a $\mathtt{DLList}$, the number of these special cases increases considerably. Perhaps the cleanest way to take care of all these special cases in a $\mathtt{DLList}$ is to introduce a $\mathtt{dummy}$ 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 $\mathtt{next}$ and a $\mathtt{prev}$, with $\mathtt{dummy}$ 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.

Figure 3.2: A $\mathtt{DLList}$ containing a,b,c,d,e.

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

Finding the node with a particular index in a $\mathtt{DLList}$ is easy; we can either start at the head of the list ( $\mathtt{dummy.next}$) and work forward, or start at the tail of the list ( $\mathtt{dummy.prev}$) and work backward. This allows us to reach the $\mathtt{i}$th node in $O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$ time:

  Node* getNode(int i) {
    Node* p;
    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 $\mathtt{get(i)}$ and $\mathtt{set(i,x)}$ operations are now also easy. We first find the $\mathtt{i}$th node and then get or set its $\mathtt{x}$ value:

  T get(int i) {
      return getNode(i)->x;
  }
  T set(int i, T x) {
    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 $\mathtt{i}$th node, and is therefore $O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$.

3.2.1 Adding and Removing

If we have a reference to a node $\mathtt{w}$ in a $\mathtt{DLList}$ and we want to insert a node $\mathtt{u}$ before $\mathtt{w}$, then this is just a matter of setting $\ensuremath{\mathtt{u.next}}=\ensuremath{\mathtt{w}}$, $\ensuremath{\mathtt{u.prev}}=\ensuremath{\mathtt{w.prev}}$, and then adjusting $\mathtt{u.prev.next}$ and $\mathtt{u.next.prev}$. Thanks to the dummy node, there is no need to worry about $\mathtt{w.prev}$ or $\mathtt{w.next}$ 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 $\mathtt{add(i,x)}$ is trivial to implement. We find the $\mathtt{i}$th node in the $\mathtt{DLList}$ and insert a new node $\mathtt{u}$ that contains $\mathtt{x}$ just before it.

  void add(int i, T x) {
      addBefore(getNode(i), x);
  }

The only non-constant part of the running time of $\mathtt{add(i,x)}$ is the time it takes to find the $\mathtt{i}$th node (using $\mathtt{getNode(i)}$). Thus, $\mathtt{add(i,x)}$ runs in $O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$ time.

Removing a node $\mathtt{w}$ from a $\mathtt{DLList}$ is easy. We need only adjust pointers at $\mathtt{w.next}$ and $\mathtt{w.prev}$ so that they skip over $\mathtt{w}$. 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;
    delete w;
    n--;
  }

Now the $\mathtt{remove(i)}$ operation is trivial. We find the node with index $\mathtt{i}$ and remove it:

  T remove(int i) {
    Node *w = getNode(i);
    T x = w->x;
    remove(w);
    return x;
  }

Again, the only expensive part of this operation is finding the $\mathtt{i}$th node using $\mathtt{getNode(i)}$, so $\mathtt{remove(i)}$ runs in $O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$ time.

3.2.2 Summary

The following theorem summarizes the performance of a $\mathtt{DLList}$:

Theorem 3..2   A $\mathtt{DLList}$ implements the $\mathtt{List}$ interface. The $\mathtt{get(i)}$, $\mathtt{set(i,x)}$, $\mathtt{add(i,x)}$ and $\mathtt{remove(i)}$ operations run in $O(1+\min\{\ensuremath{\mathtt{i}},\ensuremath{\mathtt{n}}-\ensuremath{\mathtt{i}}\})$ time per operation.

It is worth noting that, if we ignore the cost of the $\mathtt{getNode(i)}$ operation, then all operations on a $\mathtt{DLList}$ take constant time. Thus, the only expensive part of operations on a $\mathtt{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 $\mathtt{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. For example, pointers to the nodes of a linked list could be stored in a $\mathtt{USet}$. Then, to remove an item $\mathtt{x}$ from the linked list, the node that contains $\mathtt{x}$ can be found quickly using the $\mathtt{Uset}$ and the node can be removed from the list in constant time.