3.1

An `SLList` (singly-linked list) is a sequence of `Node`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 { 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

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 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; 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` 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