Subsections


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}$.
\includegraphics{figs/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}}=\ensuremath{\mathtt{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 efficiently implement the FIFO queue operations $ \mathtt{add(x)}$ and $ \mathtt{remove()}$. 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}$ comes very close to implementing the full set of $ \mathtt{Deque}$ operations. The only missing operation is removal 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.

opendatastructures.org