SFTPK: Linked List
This post is one in a series about stuff formally trained programmers know—the rest of the series can be found here. #Linked List
In the previous post on Array, we saw that all read operations are Θ(1), which is awesome. An important reality of programming is that everything is a trade-off, so when you get fast reads with an array, adding items when you don’t know the collection size is expensive.
Array Growth Issue Example
Let’s say you create an array of ints, named X, and set the length to 5 (currently, that is using 20 bytes). Now we want to add a 6th item, so the solution is to create a second array, named Y, with a larger length. If we just want to handle one more item, it means Y is now taking up 24 bytes of memory. Then we need to do a bunch of copy operations as we copy items from X to Y, which is really slow. By the end of the process, just adding one item was really expensive.
Linked List to the Rescue
The solution is to change the way we store the data structure in memory. With a linked list, each value is wrapped with metadata and stored separately in memory (compared to an array, which stores all values in a single continuous block of memory). The reason each item is wrapped is that it then gets a pointer to the next item in the collection, so that you can still navigate through the collection.
Pros and Cons
The big advantage of a linked list is that since the values can go anywhere in memory, the collection can be expanded indefinitely until you run out of memory for very little cost, either Θ(n) or Θ(1). The difference is whether the collection implementation keeps a pointer to the final item or not: if it does not, then it needs to navigate through each item (Θ(n)), and if it knows the location of the last item, it just needs to go directly to it and set its pointer to the next item.
Removing and reordering items is also much faster than with an array, since you just need to find the items before/after and change where their pointers point to.
What is the downside then? Navigation through the collection is slower than with an array. For example, if we create an integer array and want to access the fifth item, we can do it with simple math: (start of array in memory) + (int size in memory * offset)—that will give us the location of the integer value we want to read, basically an Θ(1) operation. With a linked list, however, I need to ask the first item where the second is; then ask the second where the third is; then ask the third where the fourth is; then ask the fourth where the fifth is. So it’s a Θ(n) operation for reading.
Linked lists also use more memory since you aren’t just storing values; you are storing the values and one or two pointers with each value. This is marginal when storing types without a constant size (like a class), since an array then needs to store the pointers to the values—but it’s worth remembering.
Structures
The interesting thing about linked lists compared to arrays is that they are very flexible in their implementation. The simplest version is to just have a pointer to the first item, and each item in the collection needs to point to the next item. This is known as a singly linked list, as each item is linked to one other.
The linked list may also store a pointer to the last item to make adding faster.
Doubly Linked
Most common implementations, however, use a doubly linked list, where each item in the collection not only points to the next item in the collection but also points to the previous item in the collection. At the trade-off of memory (for the extra pointer) and potentially more expensive operations (like an insert now impacting two items and not just one), you gain the ability to navigate forward and in reverse.
Implementations
Java has a doubly linked list implementation with LinkedList, and .NET also has a doubly linked list implementation with LinkedList. JavaScript has no native implementation of it, but there are plenty of articles on how to implement it.