SLList: A Singly-Linked List
Explore the structure and functionality of the SLList, a singly-linked list that efficiently supports stack and FIFO queue operations in constant time. Understand how nodes link in sequence, manage head and tail references, and perform add and remove operations, highlighting both advantages and limitations compared to arrays.
We'll cover the following...
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 ...