3.1 SLList: A Singly-Linked List

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,

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:

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:

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 :

Clearly, both the and operations run in time.

An SLList 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:

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 .

Clearly, both and take constant time.

The following theorem summarizes the performance of an SLList:

An SLList nearly implements the full set of Deque operations. The only missing operation is removing 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