An SLList (singly-linked list) is a sequence of Nodes. 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 { T x; Node next; }
For efficiency, an SLList 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 Stack and Queue operations on an SLList is illustrated in Figure 3.1.
An SLList can efficiently implement the Stack 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 SLList has increased by one:
T push(T x) { Node u = new Node(); u.x = x; u.next = head; head = u; if (n == 0) tail = u; n++; return x; }
The operation, after checking that the SLList 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; head = head.next; if (--n == 0) tail = null; return x; }
Clearly, both the and operations run in time.
An SLList can also efficiently implement the FIFO queue operations and . 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; head = head.next; 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 .
boolean add(T x) { Node u = new Node(); u.x = 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 SLList:
An SLList comes very close to implementing the full set of Deque operations. The only missing operation is removal from the tail of an SLList. Removing from the tail of an SLList is difficult because it requires updating the value of so that it points to the node that precedes in the SLList; this is the node such that . Unfortunately, the only way to get to is by traversing the SLList starting at and taking steps.
opendatastructures.org