Implementing a Linked List Data Structure with JavaScript

As part of our goal to publish an article about every data structure listed as must-have knowledge in Gayle’s Cracking the Coding Interview, this article will explore the linked list data structure.

A linked list is made up of a series of nodes, each of which contains data and a reference to the next node in the list. The first node in the list is called the head, and the last node in the list has its next reference set to null, which indicates the end of the list. Let’s see how we can implement a linked list in JavaScript.

Creating a linked list

To create a linked list in JavaScript, we will start by defining a Node class that will represent each node in the list. Each node should have a value and a next property that points the the next node in the list.

Let’s define our Node class:

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
  }
}

As mentioned above, nodes should have two properties, value and next, of which we defined in our Node class.

Now that we have the Node class defined, we can move onto our LinkedList class, which is going to contain a head property that points to the first node in the list.

class LinkedList {
  constructor() {
    this.head = null;
  }
}

The head will be null since there are no nodes in the list. We’ll need a way to insert a new node into the list. Let’s move on.

Inserting Nodes into the linked list

The first thing we’ll implement on our linked list is the ability to insert a new node. To do this, we’ll define an insert() method, which will take a value as an argument, creating a new Node with the value, adding it to the end of the list. Let’s add it to the LinkedList class from above.

class LinkedList {
  constructor() {
    this.head = null;
  }

  insert(value) {
    const node = new Node(value);

    if (!this.head) {
      this.head = node;
    } else {
      let current = this.head;

      while (current.next) {
        current = current.next;
      }

      current.next = node;
    }
  }
}

The implementation will check if the head is null. If it is, it will set the head to the new node. If it’s not, it will traverse the list until it finds the last node, setting its next property to the new node.

Implementing traversal

The next operation we want to implement is traversing the list. Traversing the list means iterating through each node in the list and performing some operation on it. Let’s implement this on our LinkedList class.

class LinkedList {
  constructor() {
    this.head = null;
  }

  // insert() code here

  traverse() {
    let current = this.head;

    while (current) {
      console.log(current.value);
      current = current.next;
    }
  }
}

Our traverse() method starts at the head of the list and iterates through each node by following the next pointers until it reaches the end of the list. For each node, it logs the node’s value to the console.

So far, we’ve implemented insertion and traversal. Let’s look at how we can delete nodes from the list.

Deleting Nodes from the list

The final implementation we will create is deleting a node from the list. To do this, we will define a delete() method on our LinkedList class. The delete() method will take a value as an argument and remove the first node in the list that has that value.

class LinkedList {
  constructor() {
    this.head = null;
  }

  // insert() and traverse() methods implementations here

  delete(value) {
    if (!this.head) {
      return;
    }

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

    let current = this.head;

    while (current.next) {
      if (current.next.value === value) {
        current.next = current.next.next;
        return;
      }

      current = current.next;
    }
  }
}

The delete() method first checks if the head is null. If it is, it returns since there are no nodes in the list. If the head’s value is equal to the value we want to delete, it sets the head to the next node in the list, effectively removing the first node.

If the head’s value is not equal to the value we want to delete, it iterates through the list until it finds the first node with the value we want to delete and removes it by setting its next property to the next node in the list.

Using the linked list

To use the LinkedList class, we’ll create an instance of the LinkedList class and then call its methods to perform operations on the list.

Let’s try it out!

// create a new linked list
const list = new LinkedList();

// insert nodes into the list
list.insert(1);
list.insert(2);
list.insert(3);

// traverse the list and log each node's value to the console
list.traverse(); // logs: 1, 2, 3

// delete a node from the list
list.delete(2);

// traverse the list again to confirm the node was deleted
list.traverse(); // logs: 1, 3

In the code above, we create a new instance of the LinkedList class and then insert three nodes into the list with values 1, 2, and 3. We then traverse the list and log each node’s value to the console.

After that, we delete the node with the value 2 from the list using the delete() method, and then traverse the list again to confirm that the node was successfully deleted. That’s all there is to it. Pretty simple, no?

Conclusion

A linked list is a powerful data structure that can be used to store and manipulate data in a flexible and efficient way.

In this article, we implemented a linked list by using a Node class to represent each node in the list and a LinkedList class to hold the nodes. With this implementation, it is possible to insert, delete, and traverse nodes in the list, allowing for dynamic manipulation of data.

While linked lists have some disadvantages, they offer many advantages over other data structures in certain situations, making them a valuable tool for any programmer’s toolkit.

If you’d like to explore more data structures, follow the links:

• Queue Data Structure
• Graph Data Structure
• Tree Data Structure

Master the coding interview

If you want to explore data structures and algorithms via a video course, taught by an amazing instructor, Andrei Neagoi, Zero to Mastery has a great course for you: Master the Coding Interview: Data Structures + Algorithms.

In this course, you will:

• Ace coding interviews given by some of the top tech companies.
• Learn to implement and use different data structures.
• Learn the notorious Big-O notation.
• Become more confident and prepared for your next coding interview.

Get 10% off by using code FRIENDS10.

FAQ

Q: What is a linked list?

A: A linked list is a data structure that consists of a sequence of nodes, where each node contains a value and a reference to the next node in the sequence. Linked lists are used to represent linear data structures like lists, stacks, and queues.

Q: What are the advantages of linked lists?

A: Linked lists have several advantages over other data structures, including:

• Dynamic size: Linked lists can grow or shrink in size as needed.
• Ease of insertion and deletion: Nodes can be inserted or deleted from a linked list without affecting the rest of the list.
• Efficient memory utilization: Linked lists only use as much memory as needed to store the data.

Q: What are the disadvantages of linked lists?

A: Of course, linked lists also have some disadvantages, such as:

• Slower access time: Since linked lists are not stored in contiguous memory locations, accessing a specific element in the list can be slower than accessing an element in an array.
• Extra memory usage: Linked lists require extra memory to store the references to the next node in the list.
• More complex to implement: Implementing a linked list requires more code than implementing an array.

Q: What are the types of linked lists?

A: There are several types of linked lists, such as:

• Singly linked list: Each node only contains a reference to the next node in the list.
• Doubly linked list: Each node contains references to both the next and previous nodes in the list.
• Circular linked list: The last node in the list contains a reference to the first node, creating a circular structure.

Q: What is the time complexity of common linked list operations?

A: The time complexity of common linked list operations:

• Insertion at the beginning: O(1)
• Insertion at the end: O(n)
• Deletion at the beginning: O(1)
• Deletion at the end: O(n)
• Traversing the list: O(n)

Disclosure: We are affiliated with ZTM (Zero to Mastery), so if you happen to be interested in the course above and purchase it through our link, we will recieve a small commission of the sale (at no extra cost to you). Please also note that we have browsed ZTM courses and have found them to be some of the best material on the web. We don’t recommend them solely for personal gain.

Thank you for the support!