A Singly Linked List is, in essence, a sequence of nodes. Each node, u, stores a data value, u.x, and a reference, u.next, to the next node in the sequence. For the last node, w, in the sequence, w.next = null. For efficiency, a SinglyLinkedList uses variables, head, and tail, to keep track of the first and last node in the sequence as well as an integer, n, to track the length of the sequence. A sequence of Stack and Queue operations on a SinglyLinkedList is illustrated in Fig.1.

A SinglyLinkedList can efficiently implement the Stack operations push() and pop() by adding and removing elements at the head of the sequence. The push() operation simply creates a new node, u, with a data value, x, sets u.next to the old head of the list and makes u the new head. Lastly, it increments n since the length of the sequence has increased.

The pop() operation checks the list is not empty and, if it is not, removes the head by setting head=head.next and decrementing n. An edge case occurs when the last element is being removed where tail is set to null.

Looking at the code should give a clear indication that the push(x) and pop() operations both run in O(1) time.

A Singly Linked List can also implement FIFO queue operations add(x) and remove() in constant time. Removals are done at the head of the list, and are identical to the pop() operation.

Additions, however, are applied to the tail of the list. Ordinarily, this is achieved by setting tail.next=u, where u is the newly created code that contains x. Although, an edge case exists when n=0, in this event, both tail and head are set to u.

Again, by insepecting the code we should have a clear indication that both operations run in constant time.

The following theorem summarizes the performance of a SinglyLinkedList

A SinglyLinkedList implements the Stack and FIFO Queue interfaces. The push(x), pop(), add(x) and remove() operations run in O(1) time per operation.

A SinglyLinkedList nearly implements the full set of Deque operations. However, removing the tail of a SinglyLinkedList is onerous. It requires updating the value of tail so that it points to the node, w, that precedes tail in the list (the node w.next=tail). Due to the structure of SinglyLinkedLists, unsuitably, the only way to achieve this is by iterating the list starting at head for n-2 steps.