An Introduction to Linked Lists
Learning web development in 2021 can be overwhelming. With so many abstractions to grapple with — from front-end declarative frameworks to object-relational mapping and cloud computing — it’s possible to build great products without understanding what’s going on under the hood. Changing focus to a lower level of abstraction can be refreshing and offers insight into how computers work step-by-step.
Today we’re going to look at linked lists, an uncommon type of ordered collection, and compare them to arrays. Both data structures can be used to tackle many of the same problems, but they can have significant differences in time complexity and memory allocation depending on the implementation.
What are arrays anyways?
An array is an ordered collection of items stored at consecutive locations in memory. Traditionally, these items are of the same data type and therefore all of the same fixed size (# of bytes). In many languages (e.g. Java) arrays are initialized with a set capacity (max length), beyond which a new item might bump into another piece of data.
Time complexity is a way of measuring how the running time for an algorithm scales when its data input increases in size. If an algorithm takes the same amount of time regardless of how much data it uses, we say that it proceeds in constant time (O(1) in Big O Notation). If the running time scales in a 1:1 ratio with the input size, we say that an algrotihm takes linear time (O(n) in Big O Notation).
Because an array’s items are all the same size, the computer can actually look up an index in constant time. For example, the 101st item in an array of 8 byte items can be found by taking the array’s base address (the location of the first item, pointed to by the variable that references it) and moving forward 8 * 100 bytes. With this approach, looking up the billionth item is no slower than looking up the second.
What about changing the array? Adding or removing from the end of an array can be accomplished quickly in constant time. Use the array’s length property to find the last item in the array as noted above and perform the insertion or deletion at that place in memory. Adding to the beginning or middle of an array takes linear time because the items after the insertion have to be pushed forward one-by-one to make room. Deleting from these places also takes linear time, because items have to be moved back to fill the gap. Arrays are slow at these operations because a base address must always point to the same location in memory, and each item that follows must be at consecutive addresses after it, without gaps (i.e. they are all neighbours). If your application involves many operations at the beginning or middle of a collection, there might be a better way…
Linked Lists!
Linked lists are stored very differently in memory. Each item is composed of a value and a pointer to the next item in the list, with the last item pointing to null. This means that the items don’t need to be next to each other in memory, in fact they almost certainly won’t be! Unlike arrays, linked lists don’t have a set capacity, so new items can be added without worrying about memory allocation.
To find an item by its index, you need to step through each previous item in the list, so lookups take linear time.
Linked lists really shine with insertions and deletions — these can take constant time. To add a new item at the beginning, point the reference to a new first element (called the head) and then point that item to the previous head.
If you keep a reference to a linked list’s tail (its last item) in addition to its head, operations on the end also take constant time. Make the new item, point it to null, and then point the previous tail to it, easy.
Likewise, operations at the middle of the list take constant time. However, it will take linear time to get to that location if you’re not there already.
A Case Study with Queues
Imagine you’re building a new app that keeps track of customer complaints. You want to respond to them in the order that they come in (first-in-first-out), so you decide to use a queue data structure. Queues can be implemented with arrays, but you opt for a linked list because you know many of your operations will be at the beginning of the collection. You decide to keep track of the list’s head and tail so that items can be added to the end and removed from the beginning in constant time. If you don’t need to perform index lookups often, a linked list could be much faster than an array.
Summary
If you have a collection of ordered data and are wondering how to structure it, think about your use cases. Will you be making a lot of lookups, and primarily pushing data to the end? Use an array. Does your application require quick insertions/deletions at multiple areas in the collection? Consider a linked list. Memory allocation is also important to consider. Filled arrays take up less memory than linked lists, but they can be sub-optimal if you don’t know how long the array will be. For more specialized approaches, there are doubly linked lists (which point backwards as well as forwards) and circular linked lists (where the tail points to the head).
Learning about data structures can be a nice way to shift gears from abstract web frameworks and look at systems with a new perspective. While some optimization comes from new tools, you might get some insights by rethinking the problem at a lower level.
References and Further Reading
- Linked Lists, Computerphile (YouTube)
- Linked List, Wikipedia
- The basics of the array data structure, Emory College
- When to use a linked list over an array/array list?, Stack Overflow
- Initial size for the ArrayList, Stack Overflow