In this section, we perservere with the study of List interface implementations, using pointer-based data structures as oppose to arrays. The structures are made up of nodes that contain list items. Using references (pointers), the nodes are linked together into a sequence. We first study singly-linked lists, which can implement a 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 (See Interfaces).

Linked lists have strengths and weaknesses compared to array-based implementations of the List interface. The main weakness is that we lose the ability to access any element using get(i) or set(i,x) in constant time. Instead we have to iterate over the list until we reach the ith element. Whereas the main strength 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, regardless of where u is in the list.

• Singly Linked List
• Doubly Linked List
• Space Efficient Linked List