Open in app

Sign in

Write

Sign in

A Mini Deep Dive into Linked Lists in Javascript for Beginners

Autumn Potts
7 min readAug 26, 2023

--

Today, I wanted to share a little bit about a topic important to computer science, the linked list.

You have probably heard it mentioned before, the infamous linked list. The data structure that all comp sci undergrads fear. Well, let’s talk about that. I’d like to think that linked lists are built up, the idea of them seems daunting and convoluted. In reality, it’s fairly simple, and it is probably related to things you have done before. In this article, we will only cover singly linked lists, if you would like to learn more about the types of linked lists and how they work I encourage you to research that after reading this! Let’s walk through it together!

What is a linked list anyway?

So you are probably wondering, what a linked list actually is. A linked list is a data structure that consists of a sequence of nodes, where each node stores a reference to an object and a reference to the next node. We can picture people in a line-up, each person is given a number and the name of the person behind them in the line-up. The number represents the data or object being referenced, and the name of the person behind them is the reference (or address) of the next data point in the list.

Fig 1. A image representation of a linked list — image from codeacademy (https://www.freecodecamp.org/news/how-linked-lists-work/)

Why are linked lists used?

In Javascript, linked lists are used in a number of other data structures, such as queues, stacks and hashtables.

One of the reasons that they are used in these data structures is that they are very efficient for dealing with dynamic memory allocation. Unlike arrays, where you typically allocate a fixed block of memory upfront, linked lists have the ability to grow and shrink as needed.

Another reason linked lists are used so prevalently is that they excel at insertion and deletion operations. Let’s compare to arrays again, removing an element from the middle of an array can be very inefficient, in some cases requiring you to loop through every item in an array to find the exact element you want to remove in the first place. A linked list uses pointers to reference its nodes, adding and removing pointers is all that needs to be done, and it’s all done in constant time. This is not true for singly linked lists, however, but it is a feature of some of the other types and worth mentioning.

How do I actually use a linked list?

So, earlier in this article, I mentioned that a linked list is comprised of nodes, and a node in more technical terms, is a class that has two variables in its constructor. The data being stored by the node and the reference to the next node in the list. The example code below shows what that might look like in code.

// Define a Node class to represent each element in the linked list.
class Node {
  constructor(data) {
    this.data = data; // The data stored in this node.
    this.next = null; // Reference to the next node in the list (initialized to null).
  }
}

To manage the nodes, we construct the linked list class. This class simply manages all the nodes within it. If you are familiar with the tree structure you might recognize this pattern, the node and the actual list as different classes that work together to form the data structure. In a linked list we have the head and the tail nodes, the head is the first node in the list, and the tail is the last node in the list.

// Define a LinkedList class to manage the linked list
Class LinkedList {
 constructor() {
  This.head = null; // The first node in the list (initialized to null)
  }
}

This is the basic structure of a linked list in Javascript. Naturally, you might think this looks a little bare, and you would be correct. This linked list is missing methods!

Let’s consider what actions you might want to take with a linked list. The first thing that may come to mind is adding nodes to our list. The most basic form of doing this is appending, or adding the node to the end of the list. Wait, but what if I want to add a node to the start of the list? Or remove a node with a specific value, or maybe add a node after a specific node that already exists?

Well, you probably already guessed it, but bum-da-da-da, this is where the methods come in. We can add methods of all these actions and more. I will show you some basics in code below.

class LinkedList {
  constructor() {
    this.head = null; // The first node in the list (initialized to null).
  }

  // Add a new node to the end of the list.
  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
  }

  // Insert a new node at the beginning of the list.
  prepend(data) {
    const newNode = new Node(data);
    newNode.next = this.head;
    this.head = newNode;
  }

  // Insert after a specific node that already exists
  insertAfter(existingNode, dataToInsert) {
    const newNode = new Node(dataToInsert);
    newNode.next = existingNode.next;
    existingNode.next = newNode;
  }

  // Delete a node with a specific value from the list.
  delete(data) {
    if (!this.head) return;

    if (this.head.data === data) {
      this.head = this.head.next;
      return;
    }

    let current = this.head;
    while (current.next) {
      if (current.next.data === data) {
        current.next = current.next.next;
        return;
      }
      current = current.next;
    }
  }

  // Search for a node with a specific value and return it.
  search(data) {
    let current = this.head;
    while (current) {
      if (current.data === data) {
        return current;
      }
      current = current.next;
    }
    return null; // Not found.
  }

  // Print the linked list.
  print() {
    let current = this.head;
    const result = [];
    while (current) {
      result.push(current.data);
      current = current.next;
    }
    console.log(result.join(" -> "));
  }
}

// Example usage:
const myList = new LinkedList();
myList.append(1);
myList.append(2);
myList.append(3);
myList.prepend(0);
myList.print(); // Output: 0 -> 1 -> 2 -> 3
myList.delete(2);
myList.print(); // Output: 0 -> 1 -> 3

const nodeToInsertAfter = myList.search(1); // Find the node with data 1
myList.insertAfter(nodeToInsertAfter, 3);
myList.print(); // Output: 1 -> 3 -> 2

Now, let’s walk through adding a node to the end list. This is the append method in the linked list. We start by creating our new node, then we check if the list is currently empty by checking if the head is currently null. If it is empty then we place our new node at the head. Otherwise, we find the last node of the current list (the node whose next property is currently null). We do this by setting a variable called current to this.head, the first node in the list and then we iterate through the list by using a while loop to find the node whose next property is null. Once that node is found, its next property is then set to a reference of the new node.

Thinking about the first few steps of appending a node to the list, we can see that the code for setting a new head and prepending to our list is already there too.

Understanding how we are moving through our linked list

Let’s switch gears here a little bit and discuss briefly how we are moving through our linked list. This is important to consider when actually applying your new knowledge.

Traversing a linked list requires that we visit each node in the list, starting from the head and moving backwards. Typically this is done using a while loop, looping through until the current nodes next property is set to null or the data stored in that node is the data being searched for. Let’s take a look at another quick example to illustrate how this is all happening.

Consider the following code,

class LinkedList {
  // ...

  // Method to traverse and perform an operation on each node.
  traverseAndProcess(callback) {
    let current = this.head; // Start from the head

    while (current) {
      // Process the current node using the provided callback
      callback(current.data);

      // Move to the next node
      current = current.next;
    }
  }
}

// Example usage:
const myList = new LinkedList();
myList.append(1);
myList.append(2);
myList.append(3);

// Traversing and printing each node's data.
myList.traverseAndProcess((data) => {
  console.log(data);
});

This linked list has a method called traverseAndProcess, it accepts a callback as an argument. Inside this method we do exactly as we described above, we set a variable called current to the head of the list (this.head). The loop through each node using a while loop. Inside that while loop we call our callback, which in this case is simply logging the data for us. We can see that we move through each item in our list.

Is that it?

Yep! That really is it. I hope by now you can see that linked lists are not evil mythical data structures out to tourment comp sci undergrads. They are simple, delicate data structures that do their jobs very well.

These are the absolute basics, there is so much more that can be done with this data structure. The floor is now yours, get creative, try out some linked lists, and use them to make awesome things! Happy hacking my dudes!

References

Computer Science
Programming
Linked Lists
Education
Technology

--

--

Autumn Potts

Written by Autumn Potts

1 Follower

Help

Status

About

Careers

Press

Blog

Privacy

Terms

Text to speech

Teams