Understanding Data Structures: Linked Lists

Rylan Bauermeister
Jul 11 · 12 min read

What This Guide Is

This guide is intended as a primer and refresher on the linked list data structure. It will cover the structure itself, its computational timings, its common algorithms, and how to code up its various permutations.

The examples contained herein are in Javascript by sheer preference by the author, but are written specifically to be accessible to other programming languages.

What Is a Linked List?

Linked lists are considered by many to be the most basic data structure, and it’s easy to see why. A linked list comprises a series of nodes, each of which contains a pointer to the next node in the series. This typically culminates in a node which points to , signifying the end of the list. Visually, it’s something like this:

Fig 1: Basic illustration of a linked list

The first mistake that many people make when looking at a linked list is to assume it’s a weird implementation of an array. While the two structure have many superficial similarities, those similarities are just that: superficial. The two are distinct ways of storing related data.

Let’s examine what makes a linked list different from an array, namely the method of storage in memory.

An array consumes a block of memory. In strict languages, such as Java or Rust, this size must be specified beforehand, and as such they take up a designated chunk of memory equal to the number of items times the size of the data type. In dynamic languages, such as Javascript, arrays can be grown or shrunk to meet the need of the programmer. In both cases, they are stored in memory as a lump of data. You can access the next item in an array by moving forward N bytes, where N is the size of the item being stored. You can therefore reach index X by moving forward NX bytes.

Linked lists, on the other hand, can be spread about in memory. While this makes accessing a specific node harder, it makes creating new nodes and removing old ones much faster, as they can be created anywhere in memory. The attribute of a linked list node contains a pointer to the memory wherein the next node is stored.

Operation Timings

Fig 2: Linked list timings compared to a common array

If you were having trouble differentiating linked lists from arrays, this should help. You’ll notice right off the bat that arrays and linked lists are polar opposites in terms of timing. The reasoning is simple: because linked lists are not fixed to a single location in memory, they can very easily insert new content at the front (or head) of the list. However, appending to the end of the list requires traversing the entire list, as a basic linked list does not store how many elements it contains.

NOTE: other types of linked list do store this information. See Linked List With Tail and Size toward the end of this guide for more information.

The same is true of reading: accessing the Nth element in a linked list requires traversing N elements.

With an array it is easy to access the end of the list, but manipulating the middle or the beginning is complicated. Because it takes up a specific space in memory, in order to insert or remove from anywhere other than the front of the list requires shifting the entire rest of the list forward. If you insert new data at index 1, you need to move what used to be there to index 2. You then need to adjust index 2 forward to 3, and so on and so forth until the end of the array.

In linked lists, the old node can simply be removed, like so:

Fig 3: Node deletion in a linked list

The pointer from to is overwritten to point to instead. Nothing needs to move, because the data’s storage location in memory is irrelevant.

Under What Circumstances Is a Linked List Useful?

The answer is: lots of places! Linked lists being growable without significant impact to memory makes them very useful structures. A few places they shine are:

  1. Stacks and Queues: because these two data structures don’t care about data in the middle of an array, but only at the ends, linked lists can be used to make extremely efficient version of both.
  2. Any instance where only adjacent nodes are relevant: imagine a slideshow. You have a next button, and a previous button. A linked list would be a perfectly efficient way of storing this information, as when you will only every need to fetch the adjacent piece of data, which can be done very quickly. The same can be said of music players, or web browser history.
  3. You want an array, but plan to do a lot of inserting and not a lot of reading: if you have knowledge of the application of a data structure before you begin, it can allow you to make far more optimal choices. In this case, if you know you need to store data, but will be inserting items into it more often than you need to extract a single item out of it, then a linked list might suit your needs beautifully.

As with many aspect of programming, the trick to knowing when to apply a structure lies in careful consideration of the situation in which it is being utilized, followed by an analysis of how the pros and cons of each structure can be made to suit your needs. Linked lists seem like a weird little structure, but they actually have many potential applications.

Working With Linked Lists

In order to work effectively with linked lists, there’s a couple algorithms (using the term loosely) that a programmer should keep in their back pocket. Let’s go over them.

Linked List Traversal

Linked lists are most commonly iterated over by use of a loop. Since they lack indexes, loops actually aren’t tremendously useful. Instead, we move over them by checking if the current node (or its pointer) is .

Here’s a basic print function:

Fig 4: iterating over a linked list

This function moves through a linked list, and prints the value at each position. The variable is repeatedly set to its own property, moving it down the line until it is equal to (and has therefore reached the end of the list). Note that we do not use the value for head, but instead assign a new variable; if we were to reassign , we could potentially lose it and destroy the entire list. Better by far to use a secondary variable.

Removing A Value

Let’s say you want to remove the value from a linked list. You’ll need to iterate over the list, looking one node forward until you locate the node containing . Then, you’ll want to stitch the current node to the node two ahead of it (or null, as the case may be), as illustrated in Fig 3.

Fig 5: An example of a removal function for linked lists

Lines 2–8 cover edge cases. The first is checking to make sure the list contains anything. If it doesn’t we return , the sign that we didn’t find the value in question. The second check ensures the value we are trying to remove isn’t the value of the head itself. If so, we simply delete the current head by setting to .

The rest utilizes a basic traversal, as seen in Fig 4, only instead of looking at the current node, we look at the node. When we find our target, we set to , effectively skipping the node containing the value we wanted gone. We can be guaranteed that is a valid variable because our loop checks that is initialized.

Loop Detection

Another common issue that can crop up in linked lists is a loop (or cycle). Consider the following:

Fig 6: A cyclical list

This, obviously, is a problem. If we are using a check against to determine whether to stop a loop, this list would cause our previous functions to error out. While a well-made linked list won’t ever allow a coder to enter this state, it’s absolutely worth knowing how to check for.

The algorithm that is commonly employed is colloquially referred to as the tortoise and hare method of cycle detection. It checks for cycles by firing off two pointers, one of which moves at double the speed of the other. If they are ever pointing at the same thing, we know the list has a cycle. If, on the other hand, either of them ever reaches null, we know that the list terminates naturally.

Here’s an implementation:

Fig 7: Tortoise and hare cycle detection

The first thing we do for this algorithm is to check the first three positions for . Obviously, if any of them are , we know that our list terminates naturally. Then we set them off. We only check 's for null, as will be lagging behind; any value it hits will already have been checked by the . If at any point they strictly equal one another, we know that we’ve found a cycle.

NOTE: you may be wondering about duplicate values. Examine the algorithm and you’ll find that we never actually check the value contained in the nodes — rather, we only check that the nodes themselves are equal. In Javascript, this requires that the objects actually be the same, i.e. stored in the same slot in memory. In this way, we can check for cycles in lists containing duplicate values.

Programming a Linked List (& Permutations)

In this section we’ll go through three basic forms of linked list.

Singly Linked List

Every linked list starts with a node class. Here’s one:

Fig 8: the Node class

This is pretty self explanatory. It is a small data structure that contains a constructor which takes a value and stores it in val. It also allocates space for a property.

NOTE: since we’re in Javascript, some of what we’re programming here is redundant. JS does not require space allocation; you can assign additional properties to variables whenever you want. This is, however, representative of the form this will take in many other languages. While written in JS, this guide is intended to be useful for people using any language.


Now that we have our Node class, we need our Linked List. A shell for our functions would look something like this:

Fig 9: a shell for the Linked List class

All future code can be assumed to exist within this shell, in the area specified. There’s nothing remarkable here, save for the initialization of a head variable, which is currently set to (as the list is empty).


Let’s give this thing a little more grit by implementing and so we can edit the end of the list.

Fig 10: push and pop

Let’s start by discussing . There’s a basic check at the front that looks to see if the list is empty; if so, we simply assign to a new Node with value of . Otherwise, we need to find the end of the list, then assign our new Node to the of the previous final node.

is slightly more complicated. As with , we dedicate a bit of space to error checking. Lines 18–23 are all dedicated to closing out edge cases. Where it gets interesting is on line 27.

You’ll notice that this time we’re checking . This is because we want the second to last node. When , we’ll know that we’re at the second to last node in the list. Then, all we need to do is set to null, indicating that we’ve snipped off the last item of the list.

There’s a little additional logic here surrounding a return value, here called . This is simply to mirror the behavior of an array. When a node is popped, we return its value. This behavior will exist in similar functions, and future iterations of this one, so don’t be alarmed.


and are much more succinct:

Fig 11: shift and unshift

Because we already have access to , we know exactly where we’re putting the new node. In we do a quick error check to make sure we aren’t shifting an empty list, then just set to .

isn’t much more complex. We make a new node with its value set to . Then, we redeclare to be equal to our new node. Easy!


The function utilized in Fig 5 can be used here, as well as the function. The final function to write out is a simple . This function is very basic, and can be presented without further ado:

Fig 12: contains

We use our basic while-loop-iteration, compare the value of each node to the value we received as an argument. If we find it, return true. Else, return false.

Linked List With Tail & Size

By this point you’re getting pretty familiar with the structure, and even have one of your own programmed out. You might be starting to wonder things like: why is accessing the end of the list so difficult? Why aren’t we tracking the size of the list?

The answer is simple: we weren’t because it was simpler. However, you can, and many people do! Very little in programming is set in stone. Making use-case modifications is often a useful, or even expected talent. So let’s take a look at what some of those functions look like if we try to implement a head and tail.


For starters, our constructor needs to change.

Fig 13: constructor for linked list with head and tail.

There. Now we initialize a linked list to have a size of zero, and a tail that’s equal to its initial head.


Updating and comes next.

Fig 15: push and pop with a tail and size

got much simpler! Aside from the edge case checking on lines 4–7, we can see that the whole operation can be done in 3 lines now, and in O(1) time. That’s a big boost! All we have to do is set to a new node containing the value passed in, then increment up the size.

on the other hand got a bit gnarly. Lines 17–23 are all error checking (if you’re interested, you can see the complete code for the helper function ). What comes next seems overly complicated, though! Weren’t we storing the tail value now? What’s all this?

Well, in order to set the new tail, we need the second to last item in the linked list. This means traversing the whole list again, as our list contains pointers going in one direction. This is an issue which could be fixed, and will be addressed in the next section, Doubly Linked Lists.

The rest of the code is pretty similar, save for incrementing and decrementing the size counter. This new version seems great, but the inability to traverse in the other direction is vexing. Let’s look into fixing that.

Doubly Linked Lists

Previously we were coding singly linked lists. What is meant by this is that the pointers flow in one direction only. Nodes have a property, but not a property. A list which flows in both directions can be said to be doubly linked.

Let’s look at the implementation.


Fig 15: a two way node

To start, we have our two way Node. It has both a and a property, allowing it to move in both directions. Let’s see what this does to our and functions.

Fig 16: doubly linked push and pop

Now this looks more like what we were hoping for. looks similar, although we now need to assign a value to the new node when we push it on. on the other hand has become tiny. All it does is set the tail to the value of the previous node, then set that node’s next to . Exactly how we wanted to do it before, and now we can manipulate the tail of the list in O(1) time.

The other functions are still pretty unchanged, although they now feature some more upkeep to make sure their values of are set properly. We can, however, now do fun things like printing the list backwards without it requiring nested loops:

Fig 17: printing a linked list backwards

Our linked list is now devilishly efficient for queues and stacks, and can be read forward and backwards. Not too shabby!

Conclusion

You should now have a very good idea of what a linked list is, and the ways you can expand upon it. If you wish to play with one that’s already written, check the sources for a link to my repository — it has a testing suite you can use in addition to the full code for all of these examples.

Sources

Rylan Bauermeister

Written by

Software engineer and writer who likes weird edge cases and talking about the world.