3.1 $\mathtt{SLList}$: A Singly-Linked List

An $\mathtt{SLList}$ (singly-linked list) is a sequence of $\mathtt{Node}$s. Each node $\mathtt{u}$ stores a data value $\mathtt{u.x}$ and a reference $\mathtt{u.next}$ to the next node in the sequence. For the last node $\mathtt{w}$ in the sequence, $\ensuremath{\mathtt{w.next}} = \ensuremath{\mathtt{null}}$

  class Node {
  public:
    T x;
    Node *next;
    Node(T x0) {
      x = 0;
      next = NULL;
    }
  };

For efficiency, an $\mathtt{SLList}$ uses variables $\mathtt{head}$ and $\mathtt{tail}$ to keep track of the first and last node in the sequence, as well as an integer $\mathtt{n}$ to keep track of the length of the sequence:

  Node *head;
  Node *tail;
  int n;

A sequence of $\mathtt{Stack}$ and $\mathtt{Queue}$ operations on an $\mathtt{SLList}$ is illustrated in Figure 3.1.

Figure 3.1: A sequence of $\mathtt{Queue}$ ( $\mathtt{add(x)}$ and $\mathtt{remove()}$) and $\mathtt{Stack}$ ( $\mathtt{push(x)}$ and $\mathtt{pop()}$) operations on an $\mathtt{SLList}$.

An $\mathtt{SLList}$ can efficiently implement the $\mathtt{Stack}$ operations $\mathtt{push()}$ and $\mathtt{pop()}$ by adding and removing elements at the head of the sequence. The $\mathtt{push()}$ operation simply creates a new node $\mathtt{u}$ with data value $\mathtt{x}$, sets $\mathtt{u.next}$ to the old head of the list and makes $\mathtt{u}$ the new head of the list. Finally, it increments $\mathtt{n}$ since the size of the $\mathtt{SLList}$ has increased by one:

  T push(T x) {
    Node *u = new Node(x);
    u->next = head;
    head = u;
    if (n == 0)
      tail = u;
    n++;
    return x;
  }

The $\mathtt{pop()}$ operation, after checking that the $\mathtt{SLList}$ is not empty, removes the head by setting $\ensuremath{\mathtt{head=head.next}}$ and decrementing $\mathtt{n}$. A special case occurs when the last element is being removed, in which case $\mathtt{tail}$ is set to $\mathtt{null}$:

  T pop() {
    if (n == 0)  return null;
    T x = head->x;
    Node *u = head;
    head = head->next;
    delete u;
    if (--n == 0) tail = NULL;
    return x;
  }

Clearly, both the $\mathtt{push(x)}$ and $\mathtt{pop()}$ operations run in $O(1)$ time.

3.1.1 Queue Operations

An $\mathtt{SLList}$ can also implement the FIFO queue operations $\mathtt{add(x)}$ and $\mathtt{remove()}$ in constant time. Removals are done from the head of the list, and are identical to the $\mathtt{pop()}$ operation:

  T remove() {
    if (n == 0)  return null;
    T x = head->x;
    Node *u = head;
    head = head->next;
    delete u;
    if (--n == 0) tail = NULL;
    return x;
  }

Additions, on the other hand, are done at the tail of the list. In most cases, this is done by setting $\ensuremath{\mathtt{tail.next}}=\ensuremath{\mathtt{u}}$, where $\mathtt{u}$ is the newly created node that contains $\mathtt{x}$. However, a special case occurs when $\ensuremath{\mathtt{n}}=0$, in which case $\ensuremath{\mathtt{tail}}=\ensuremath{\mathtt{head}}=\ensuremath{\mathtt{null}}$. In this case, both $\mathtt{tail}$ and $\mathtt{head}$ are set to $\mathtt{u}$.

  bool add(T x) {
    Node *u = new Node(x);
    if (n == 0) {
      head = u;
    } else {
      tail->next = u;
    }
    tail = u;
    n++;
    return true;
  }

Clearly, both $\mathtt{add(x)}$ and $\mathtt{remove()}$ take constant time.

3.1.2 Summary

The following theorem summarizes the performance of an $\mathtt{SLList}$:

Theorem 3..1   An $\mathtt{SLList}$ implements the $\mathtt{Stack}$ and (FIFO) $\mathtt{Queue}$ interfaces. The $\mathtt{push(x)}$, $\mathtt{pop()}$, $\mathtt{add(x)}$ and $\mathtt{remove()}$ operations run in $O(1)$ time per operation.

An $\mathtt{SLList}$ nearly implements the full set of $\mathtt{Deque}$ operations. The only missing operation is removing from the tail of an $\mathtt{SLList}$. Removing from the tail of an $\mathtt{SLList}$ is difficult because it requires updating the value of $\mathtt{tail}$ so that it points to the node $\mathtt{w}$ that precedes $\mathtt{tail}$ in the $\mathtt{SLList}$; this is the node $\mathtt{w}$ such that $\ensuremath{\mathtt{w.next}}=\ensuremath{\mathtt{tail}}$. Unfortunately, the only way to get to $\mathtt{w}$ is by traversing the $\mathtt{SLList}$ starting at $\mathtt{head}$ and taking $\ensuremath{\mathtt{n}}-2$ steps.