SLList: A Singly-Linked List

Linked list overview

Here, we study implementations of the List interface using pointer-based data structures. These structures are made up of nodes that contain the list items. Using references (pointers), the nodes are linked together into a sequence. We first study singly-linked lists, which can implement Stack and (FIFO) Queue operations in constant time per operation and then move on to doubly-linked lists, which can implement Deque operations in constant time.

Linked lists have advantages and disadvantages when compared to array-based implementations of the List interface. The primary disadvantage is that we lose the ability to access any element using get(i) or set(i, x) in constant time. Instead, we have to walk through the list, one element at a time, until we reach the $i^{th}$ element. The primary advantage is that they are more dynamic: Given a reference to any list node u, we can delete u or insert a node adjacent to u in constant time. This is true no matter where u is in the list.

SLList: A singly-linked list

An SLList (singly-linked list) is 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.