An Introduction to Linked Lists

Matt Davis

Posted in:

DSA

Algorithms

Studying

Learning

You typed into Google, “What is a linked list” and you have found this article among a multitude of others. Hopefully, I can make you laugh and provide some useful information along the way. Here, the goal is to explain the Singly Linked List with basic and clear language.

The following contains basic OOP programming principles and assumes you have some level of understanding of a language. I am early in my career in technology and have chosen to focus on JavaScript. The following code examples will be written in. I drew all the images in draw.io and wrote my basic code myself while referencing Cracking the Coding Interview 6th Edition (great book by the way)

While the code is JavaScript, remember that arrays are objects in JavaScript and therefore stored in memory as such. In this article I will refer to arrays in the general sense, that they are fixed in memory as a type and continuous. YMMV

Just take me to the code… GitHub

What is a Linked List?

In simple terms, a Linked List is a data structure. What is a data structure? Well, it is exactly that, a structured way to organize and store data that allows for updating and efficiently accessing that data.

A Linked List contains “nodes”. Each node is made up of “data” and a “pointer” (next). For myself, there was no real way to understand this without looking at a visual. The concept is too abstract.

A simple Linked List node

Let's take a minute here. There are multiple versions of a Linked List. Singly, doubly, and circular among others. If you want more information about these I recommend, as always, looking at Wikipedia. I am going to focus on the Singly Linked List for now. Each node in a Singly Linked List will have one reference to another node or in the case of a list with one node, the reference or “next” will be null.

A Singly Linked List with two nodes

At this point, we need to define some other commonly used terms. The “head” and the “tail” pointers. And for the sake of the visuals…

A Singly Linked List with head and tail indicating first and last nodes respectively

So the “head” is the first node and the “tail” is the last. Keep in mind this list only has two nodes. So at this point, you might be thinking what’s the big deal? Isn’t this just like an array? Well you are not entirely wrong they can both be thought of as “linear” but there are major differences.

Linked List vs. Array

An array is stored in continuous memory allocation (typically fixed at the time of initialization), whereas a Linked List is not continuous. They have a pointer to reference other data points, rather than using an “indexed” value. This is both good and bad, as with everything in life.

Note: Some Big O considerations

Accessing an indexed value is fast, O(1) constant time (hmm so smooth). This is not possible with a Linked List, we need to traverse the entire list to find a given value. There is no index, as the memory locations of a Linked List are not continuous.

The insertion at the beginning or end of a Linked List is O(1) constant. However inserting or deleting in another location is O(n), linear time. As the list must be traversed. Remember that fixed initialization of array size? A Linked List insert or delete does not require reorganizing the entire array structure. So that is awesome…. but wait there’s more!

Ok, ok, wait you said this was going to be simple? Well, let’s review.

Differences Between Array and Linked List

A Singly Linked List:

Contains nodes
each node contains data and a pointer to the next node
memory location is not continuous

An Array:

contains fixed memory allocation, continuous
each element contains data at an index

Alright, so a quick look at the differences between continuous and non-continuous storage seems in order:

Continuous:

possibly wasted memory
faster execution
external and internal fragmentation can occur (fragmentation refers to the inability to resize an allocated section of memory when processes are removed from memory)

Non-continuous:

no wasted memory
slower
only external fragmentation occurs

Applications of Linked Lists:

Forward and back in the browser
Forward and back within an Image Viewer
Polynomial representation and manipulation
Forward and back on your favourite Spotify playlist

Great, that’s just great. Let us look at some simple code so we can start to understand how to work with a Singly Linked List.

Note to keep in mind: I know I said Linked Lists are “linear” but they are recursive…oops!

1const exampleLinkedList = {
2  head: {
3    data: 1,
4    next: {
5      data: 2,
6      next: {
7        data: 3,
8        next: {
9          data: 4,
10          next: {
11            data: 5,
12            next: null,
13          },
14        },
15      },
16    },
17  },
18};

I Create a node.

So, remember, this is my interpretation and my simple understanding brought into code, there are many ways to do things, for example, we could’ve used a default parameter in the constructor for next, and set this.next = next. I encourage you to experiment with your implementation.

Let's create a node.

1class LinkedNode {
2  constructor(data) {
3    this.data = data;
4    this.next = null;
5  }
6}
7

Now let’s create a Linked List.

1class LinkedList {
2  constructor(head) {
3    this.head = null;
4    this.tail = null;
5    this.size = 0;
6  }

Alright, are you following? So far I have null, great, and easy. A representation of my current wallet I suppose… I have also added a property size, I need this to know what size of a Linked List I have (uh huh). I also need a tail pointer, as this way I know when the list ends, as the node that contains the next value of null is the tail.

So let’s add some simple methods to add data…wait? Where am I adding data and what is it linked to… ok so maybe not so simple. I suppose I need a method to add data at the beginning and then another to add at the end. Great. Just to be confusing and seem intelligent, let’s call them prepend (begin) and append (end).

1  prepend(data) {
2    const node = new LinkedNode(data);
3    if (this.size === 0) {
4      this.head = node;
5      this.tail = node;
6    } else {
7      node.next = this.head;
8      this.head = node;
9    }
10    this.size++;
11  }
12
13  append(data) {
14    const node = new LinkedNode(data);
15    if (this.size === 0) {
16      this.head = node;
17      this.tail = node;
18    } else {
19      const temp = this.tail;
20      this.tail = node;
21      temp.next = this.tail;
22    }
23    this.size++;
24  }

I first need to see if the list is empty. If there is nothing, great, I just set the head and tail to point to the same spot and add one to the size. If the list isn’t empty then depending on the method, we need to insert the data and move the pointers around to their proper reference points. If we add at the head, we move the head, if we add at the tail we move the tail. However, the append method requires a temp step as a placeholder.

Diagram showcasing steps involved in appending a new node.

Whew, that was more than I wanted to draw, if you have been following along at this point it is pretty clear that working with Linked Lists you must keep in mind the data and the pointers, each node pointer “next” as well as the overall list pointers “head” and “tail”. Let’s continue this mind-power experiment.

I would like to get a console printout of all of our data, as well as the size and the first and last data values. Hence why keeping track of size is a good idea, calculating the size can be done by iteration as well, but who has time for that? It can be useful to reset the entire list as well, maybe someone can invent a method like this for real life?

1  getSize() {
2    return this.size;
3  }
4
5  last() {
6    return this.tail.data;
7  }
8
9  first() {
10    return this.head.data;
11  }
12  clearList() {
13    this.head = null;
14    this.tail = null;
15    this.size = 0;
16  }
17
18  printList() {
19    let output = "";
20    let current = this.head;
21    while (current !== null) {
22      output += current.data + " ";
23      current = current.next;
24    }
25    console.log(output);
26  }
27

I probably will want to, at some point, remove the first node or remove the last node.

1  removeFirstNode() {
2    if (this.size === 0) {
3      return null;
4    }
5    const first = this.head;
6    if (this.size === 1) {
7      this.head = null;
8      this.tail = null;
9    } else {
10      this.head = this.head.next;
11      this.size--;
12      return first.data;
13    }
14  }
15
16  removeLastNode() {
17    if (this.size === 0) {
18      return null;
19    }
20    const last = this.tail;
21    if (this.size === 1) {
22      this.head = null;
23      this.tail = null;
24    } else {
25      let current = this.head;
26      while (current.next.next !== null) {
27        // stop at the second to last node
28        current = current.next;
29      }
30      current.next = null;
31      this.tail = current;
32    }
33    this.size--;
34    return last.data;
35  }
36

JavaScript has garbage collection, which I have been told is a form of automatic memory allocation. So all that means is I don’t have to worry when the reference to a node is moved resulting in a node with no reference, and I don’t need to specify de-allocation of memory. You know what, if I had a Doubly Linked List with each node containing a pointer to the next node and the previous node, this removal of the last node wouldn’t be so tedious…hmm.

Well, I am getting somewhere I suppose. I can add data at the beginning or end of our list, get the size, see all the data in the console, and remove the first and last nodes.

What about inserting data at a given index value, deleting a data value, or finding a given data value and its index? Bear with me. This code snippet will be dramatically long (for the obvious effect of seeming like I know precisely what is happening).

1 deleteByData(data) {
2    if (this.size === 0) {
3      console.log("List is empty");
4      return null;
5    }
6    let current = this.head;
7    let last = this.tail;
8    let previous = null;
9    while (current !== null) {
10      if (current.data === data) {
11        if (previous === null) {
12          // this means that the data to be deleted was the first element
13          return this.removeFirstNode();
14        } else if (last.data === data) {
15          // this means that the data to be deleted was the last element
16          return this.removeLastNode();
17        } else {
18          // set the previous value of next to the current.next value
19          previous.next = current.next;
20          current.next = null;
21          this.size--;
22          return current.data;
23        }
24      }
25      // if the value is not found we set the previous value to the current, and current is moved to the next
26      previous = current;
27      current = current.next;
28    }
29    // if the loop ends and nothing is found, then we return null
30    console.log("Data not found");
31    return null;
32  }
33
34  insertAt(data, index) {
35    if (index < 0 || index >= this.size) {
36      return;
37    }
38    if (index === 0) {
39      return this.prepend(data);
40    } else if (index === this.size) {
41      return this.append(data);
42    } else {
43      const node = new LinkedNode(data);
44      let current = this.head;
45      let previous = null;
46      let counter = 0;
47      // while the counter does not equal the index we move the pointers forward
48      while (counter < index) {
49        previous = current;
50        current = current.next;
51        counter++;
52      }
53      // we break out of the loop when the counter equals the index, we then sent the new data to link the current node and set the previous.next pointer to point at the new node
54      node.next = current;
55      previous.next = node;
56      this.size++;
57    }
58  }
59
60  // different than arrays, as we cannot look up by the index, there is no reference to index in LinkedList
61  findByData(data) {
62    let current = this.head;
63    let counter = 0;
64    while (current.next !== null) {
65      if (current.data === data) {
66        return `Your data, ${current.data}, was found at index ${counter}`;
67      }
68      current = current.next;
69      counter++;
70    }
71    return "Not found!";
72  }
73
74  findByIndex(index) {
75    if (index === 0) {
76      return `The data at index ${index} is ${this.head.data}`;
77    }
78    if (index === this.getSize()) {
79      return `the data at index ${index} is ${this.tail.data}`;
80    }
81    if (index > this.getSize() || index < 0) {
82      return `the data at index ${index} is not available`;
83    }
84
85    let current = this.head;
86    let counter = 0;
87    let previous = null;
88
89    while (counter < index) {
90      current = current.next;
91      previous = current;
92      counter++;
93    }
94    return `The data at index ${index} is ${current.data}`;
95  }
96}

Wow, look at that! If you are an advanced programmer I am sure you are laughing, and if you are like me, you are thinking what is going on? I ensure you with all seriousness, I am serious now. This code is not that bad, if you follow along with the steps you can figure it out. If I can do it, anyone can.

It’s nice to know that I can accomplish some basic data manipulation. arguably this is much simpler with arrays and the built-in array methods of JavaScript.

So I had a thought (surprisingly), let’s time the different actions between my basic code and array methods. Using a Node.js runtime we have access to the Performance Hooks ( Node Docs). The issues surrounding executing performance tests are out of the scope here, so I am keeping it simple and as flawed as possible. I will leave the results in the linked repository and spare them from this article but if you want to debunk my code and/or see what I came up with, here is the GitHub.

Please let me know of any flaws or errors. Although it may seem contrary, I am truly hoping to deepen my understanding of data structures by writing this article, and hopefully, it made you think.

Summary

Data structures need to be chosen based on your application. I would discourage anyone from thinking that a certain structure is better than another, everything has ups and downs.

A Singly Linked List is similar to an array however, the main difference is the array is stored in continuous memory locations, whereas the Linked List is not. The implications of this difference require us to carefully weigh the pros and cons of the Linked List to other data structures.