Demystifying Linked Lists

When I first encountered linked lists when learning JS, I felt hopeless. As a beginner, I really struggled to understand what they are used for and why we could not just use an array! As I didn’t want to leave a big gap in my knowledge, I took some time to demystify all about linked lists. This post is the result of such a process. I learned, and I hope you will learn too:

• What linked lists are and what they are made of

• Differences between linked lists and arrays

• Common uses of linked lists

• Code example

• Is a blockchain a linked list?

What are linked lists?

Linked lists are a common data structure in computer science. To be clear, an array is also a data structure, not a data type (for example, objects or booleans, or integers). Linked lists are made up of nodes, which are individual objects that contain two elements:

• Some data

• A reference to the next node called pointer

We can imagine that in a linked list nodes are connected to each other in a chain-like structure.

An important note here. Every linked list contains a head, which is a pointer to the first node of the list. The head does not contain any data itself. At the end of the linked list, we find a tail: as opposed to the head, the tail contains data, but it has no reference to the next node - because there is no next node!

In JavaScript (and I guess in other programming languages) linked lists look like deeply nested objects (see the code snippet below).

The difference between linked lists and arrays

The main difference between linked lists and arrays is that arrays are more of a static data structure, whereas linked lists are more of a dynamic data structure. I say ‘more of a’ static data structure because as you likely know, we can indeed modify the content of an array with methods such as push(), pop(), shift(), unshift(), and many more. Still, the addition or removal of data in a linked list is much more flexible than in an array.

When inserting or deleting elements, linked lists are more efficient than arrays because they do not require any shifting or resizing of the data in the list. In an array, inserting or deleting an element at the beginning or middle of the list requires shifting all of the other elements in the array to make room for the new element or to fill the gap left by the deleted element.

Common uses of linked lists

Using an array instead of a linked list will depend on the specifics of the application we are building. Linked lists are commonly used to:

• Storing the data of a list or queue, where elements are added and removed in a particular order. If you are into NFTs, you are probably familiar with software that manage queues of users. Simply put, as one user gets to the checkout page, another one is allowed to enter the queue. The user at the checkout page will be removed from the linked list, whereas the new user will be inserted at the beginning of the linked list.

• Implementing an undo/redo system where each action performed by the user is stored in a linked list and can be undone or redone by moving backward or forward in the list. This is a feature we use every single day in text editors and so many other software. Blessed ctrl/cmd + Z (and ctrl/cmd + shift + Z)!

Curious to see what a linked list looks like? Let’s write the code for a simple one.

// Define the Node class. Each Node object has two properties:
// - data: the data stored in the node
// - next: a reference to the next node in the list
class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
  }
}

// Define the LinkedList class. Each LinkedList object has two properties:
// - head: a reference to the first node in the list
// - length: the number of nodes in the list
class LinkedList {
  constructor() {
    this.head = null;
    this.length = 0;
  }

  // Define a method for adding a new node to the end of the list
  append(data) {
    // Create a new node
    const newNode = new Node(data);

    // If the list is empty, set the new node as the head
    if (this.head === null) {
      this.head = newNode;
    } else {
      // Otherwise, find the last node in the list and set its next property
      // to point to the new node
      let current = this.head;
      while (current.next !== null) {
        current = current.next;
      }
      current.next = newNode;
    }

    // Increment the length of the list
    this.length++;
  }
}

// Create a new LinkedList instance
const list = new LinkedList();

// Add some nodes to the list
list.append('first');
list.append('second');
list.append('third');
list.append('fourth');

console.log(list)

/* 
LinkedList 
{head: {data: "first", 
     next: {data: "second", 
         next: {data: "third", 
             next: {data: "fourth", 
                next: null}
                }
            }
        }, 
    length: 4}
*/

In LinkedList, the only method is append (data), which allows appending a new node. Other methods to manage the linked list are commonly included, e.g., for inserting a node at the beginning or removing a node at a certain index of the linked list.

Is a blockchain a linked list?

If you have ever heard of a blockchain before, you most likely know that it is made up of interconnected blocks. A block stores information (for example transactions) and is linked to the previous and the next one, therefore forming a chain of blocks. While both linked lists and blockchains involve the concept of linking data together, the way that they do so is different. Linked lists are used to store and manipulate data in a linear sequence: as in the queue to buy NFTs, the linked list is dynamically updated and nodes (representing buyers) can be added or removed. On the other hand, blockchains are used to create a secure, ever-growing, and immutable record of data: blocks cannot be removed as nodes in linked lists. Do not confuse the nodes of a linked list with the nodes of a blockchain. The latter are the computers that help secure the networks.

In brief: blockchains are not linked lists, although they both involve the concept of linking some kind of data together.

That's a wrap!

Questions? Leave them below in the comments. I hope this article helped you to better understand linked lists.

If you liked it, leave a follow on Twitter - I am looking forward to connecting with fellow beginner developers!