Linked Lists for the Junior Developer
If you’re like me, a recent graduate of a web development boot camp with no prior programming experience, you might feel that you’re lacking in certain CS fundamentals that could come up in a technical interview. A quick google of “the best tech interview prep material” will inevitably lead you to a list of topics ranging from Hash Tables to BigO Notation, and likely leave you with the feeling that you’ve only scratched the surface of what it takes to be a hireable developer. This article is going to look at one of the (many) topics that could come up: the Linked List data structure. Some basic knowledge of programming fundamentals is assumed for the reader, but you don’t need to be an expert to get something out of this. I’ll walk you through what linked lists are and what they do, from the perspective of one fledgling web developer to another, with the goal being to leave you with enough of an understanding that if the topic does come up in your next TI you can feel reasonably confident discussing it.
So, what the heck are linked lists?
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions. A drawback of linked lists is that access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists.
- Obligatory Wikipedia Definition
This leaves a dry taste in my mouth, and to the recently-initiated, it might also name drop some concepts that aren’t entirely familiar to you yet. That’s ok, I got you friend; and if this definition already makes perfect sense, congratulations, you probably don’t need to read this article!
Let’s break down that Wikipedia definition into somewhat simpler terms:
a linked list is a linear collection of data elements whose order is not given by their physical placement in memory
This starts to make more sense if you take it in the context of how Arrays are stored in a computer’s memory:
Arrays are stored contiguously, meaning that the items they contain are stored next to each other inside the array, with that array being fixed in place in the computer’s memory. This is what allows us to access any item in an array by their index. Using the image above, if we wanted to access the item with a value of 68, we would do something like console.log(array[5])using the item’s index of 5. This is one of the benefits of contiguously stored data structures: accessing any item contained within it arbitrarily and quickly.
Going back to the linked list definition, we now start to understand that a linked list is primarily defined by it not being stored contiguously. In fact, each Node (a.k.a item) in a linked list can be placed anywhere within a computer’s memory where there is room for it. The cool thing about linked lists is that each node contains a piece of information alongside its data that points to the next link (or node) in the list. This gives the linked list both its name and its purpose: to move between these linked pieces of data in a sequence. Links, nodes, and items are basically a bunch of different names for the same thing: the bits of data that make up one piece (or link, or item, or node, or…) of the list.
It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains: data, and a reference (in other words, a link) to the next node in the sequence.
O.K., this is starting to make sense now! Let’s look at the next part:
What are they used for?
This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions.
There are two key takeaways here: First, that linked lists are useful for their ability to insert or remove a new link with relative ease. I say relative because there’s some more context from our dear friend the array; adding and removing items from an array can involve multiple costly operations under the hood, and operations take time, a valuable resource to manage in large-scale projects. Add on to this that in some programming languages, like C++, arrays are expected to be initialized with a set length, like a length of 5 in this example: int MyArray[5] = {0,1,2,3,4};and you’ll start to see where linked lists really shine. With linked lists, we can just move through one node to another and then break the link at the desired point, insert a new node there, and reforge the link. There are loads of videos out there like this one from HackerRank that go more in-depth into this process if you’re so inclined, but for now, you just have to know that this process is easier with linked lists than it is with arrays typically (and especially in languages like C++).
The second point to grasp is that linked lists can hold more than one link pointer, allowing more complex linked lists to do things like move backward through the list, circle back to the first when reaching the end, and even more wild stuff. Those are out of the scope for this article, but you should know that it is possible, and they do exist.
What aren’t they used for?
A drawback of linked lists is that access time is linear (and difficult to pipeline). Faster access, such as random access, is not feasible. Arrays have better cache locality compared to linked lists.
Now, this relates to BigO Notation, a fascinating and complicated subject that’s occasionally fun but more commonly migraine-inducing, so here’s the TLDR of BigO: everything your code does takes time to run, and you can calculate that amount of time fairly accurately using BigO. Above, it mentions that access time is linear. This refers to the main weakness of a linked list: you cannot access a node (or item, or link…) arbitrarily as you would with an item in an array using its index. Instead, you have to start at the first node (called the Head) and work your way sequentially through every node and link until you get to the desired piece of data. Now, in a small linked list that’s not much of a problem and it won’t cost you much of that sweet, juicy time. But imagine if you had a linked list containing ~10,000 nodes and you wanted to access the 9,826th node; you have to start at the head and move through (a.k.a ‘traverse’) 9,825 nodes until you reach the desired data. This is referred to in BigO as a Linear scaling problem, represented with the symbol O(n). Additionally, the more complex versions of linked lists take up more space in memory due to their multiple pointers. This may leave you asking:
Why would I want to use them?
This is a trick question because you likely use linked lists multiple times a day already without knowing it. Every click ‘back’ or ‘forward’ on your smartphone or browser, every CTRL+Z or CTRL+Y on your keyboard, and other state-based actions we encounter regularly when using software like Photoshop, Spotify, or Word often rely on linked lists to function as we expect them to. As a programmer who primarily works with Javascript, I deal with linked lists to give my call stack its functionality (enabling Last In First Out), and it can be used for sequential graphs, hash tables, and other advanced subject matter. They have their drawbacks, as discussed earlier, but they are still around and kicking and will be for some time.
So, that’s the quick and dirty of linked lists. This is by no means written to be a comprehensive or deep explanation of the concept, but rather a primer to get you feeling solid in the foundations in the event it comes up in a technical interview. If you’re interested in learning more on the topic, the resources I used for my own research are below.
Resources:
