Linked Lists
Channel: Jonathan Anderson
Date: 22/05/2018

Transcript:

One of the simplest data structures we'll look at this term is the linked list. We've been introduced to the idea of linked lists before when discussing iterators, but now we'll really dig into the details.

Arrays and vectors guarantee that values will be stored contiguously in memory, which makes iteration fast and allocation simple. Containers that store fixed-size data, or that only grow at the end, are ideally stored as arrays or vectors (which are basically just arrays whose memory is managed for you). Arrays are great for iteration and in-place updates, but they are not very amenable to insertion or deletion. Every time you delete an element, all of the remaining elements need to be shifted over by one to fill in the space. This is an order-N operation. The same is true of insertion: in addition to potentially allocating new memory to store the larger array, you must shift order-N elements around to make room for the new element.

Linked lists overcome these costs by breaking the assumption of contiguous storage. In a linked list, adjacent sequence elements do not have to be stored adjacent to each other in memory. Instead, elements can be allocated anywhere in the heap; to keep track of them all, each element is contained in an object (a list node) that holds the element and a pointer or two. In a singly-linked list, each node has a pointer to the next node in the list. In a doubly-linked list, each node has both a forward pointer to the next node and a back pointer to the previous node. Iterating through a list now becomes a matter of following pointers instead of incrementing an index. Iterating through a linked list is an order-N operation, just like iterating through an array, but with a higher constant factor. Each step of the iteration involves a pointer dereference and an assignment instead of just incrementing a pointer or an index. Still, 2n or 3n operations are still order-N.

The top-level object that represents a linked list will contain a pointer to the node at the head of the list and a pointer to the node at the tail. The simplest option is to have these pointers point at the first and last nodes or be null if there are no nodes in the list. A more consistent option, however, is to always point at head and tail nodes that act as bookends for the list rather than members of it. Such nodes are called sentinels, and they can help simplify the list's logic because they allow empty and non-empty lists to be treated in the same way.

An iterator over a linked list has to be more sophisticated than just a pointer. A list iterator object will keep track of the list node that it's pointing at and will implement operator methods such the dereference operator and the increment operators. The increment operators, instead of incrementing a pointer, will dereference the current node's "next" pointer and set that value to be the new "current" node. In a doubly-linked list, the decrement operators work in the same way but with the current node's "previous" pointer.

If we have an iterator that points at a specific node in the list, inserting or deleting an element at that location can be done in constant time. First, a new node is created containing the element, a "next" pointer and a "previous" pointer. Next, the pointers of the surrounding nodes are updated to incorporate the new node. This integrates the new node into the linked list. Deletion is similar: first we update the surrounding nodes' "next" and "previous" nodes to skip the node being deleted, then we free the memory. Both insertion and deletion require some pointer arithmetic and some memory allocation operations, but they do not depend on the length of the list. That is, they can be done in constant time.

So that's how linked lists are stored, iterated over and modified. We'll have a chance to explore these ideas in our practical class sessions.