3.1 : A Singly-Linked List

An (singly-linked list) is a sequence of s. Each node stores a data value and a reference to the next node in the sequence. For the last node in the sequence,

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

For efficiency, an uses variables and to keep track of the first and last node in the sequence, as well as an integer to keep track of the length of the sequence:

Node *head; Node *tail; int n;A sequence of and operations on an is illustrated in Figure 3.1.

An can efficiently implement the operations and by adding and removing elements at the head of the sequence. The operation simply creates a new node with data value , sets to the old head of the list and makes the new head of the list. Finally, it increments since the size of the 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 operation, after checking that the is not empty, removes the head by setting and decrementing . A special case occurs when the last element is being removed, in which case is set to :

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 and operations run in time.

An can also implement the FIFO queue operations and in constant time. Removals are done from the head of the list, and are identical to the 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 , where is the newly created node that contains . However, a special case occurs when , in which case . In this case, both and are set to .

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 and take constant time.

The following theorem summarizes the performance of an :

An nearly implements the full set of operations. The only missing operation is removing from the tail of an . Removing from the tail of an is difficult because it requires updating the value of so that it points to the node that precedes in the ; this is the node such that . Unfortunately, the only way to get to is by traversing the starting at and taking steps.

opendatastructures.org