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}$ ...