JavaScript Data Structures - 14 - Linked List Class

Introduction

In this tutorial, we will explore how to implement a Linked List class in JavaScript. Linked lists are fundamental data structures that allow for efficient insertion and removal of elements. Understanding linked lists is essential for mastering data structures and algorithms, and this guide will walk you through creating a simple linked list from scratch.

Step 1: Create the Node Class

To begin, we need a class to represent each node in our linked list. The node will hold data and a reference to the next node.

1. Define the Node class.
2. Include a constructor that initializes the data and next properties.

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

Step 2: Create the Linked List Class

Next, we will create the Linked List class which will manage the nodes.

1. Define the LinkedList class.
2. Initialize head and tail properties in the constructor.

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

Step 3: Add a Method to Append Nodes

We will add a method to append new nodes to the end of the list.

1. Create a method called append.
2. Check if the head is null. If it is, set both head and tail to the new node.
3. If the head exists, set the current tail's next to the new node and update the tail reference.

append(data) {
    const newNode = new Node(data);
    if (!this.head) {
        this.head = newNode;
        this.tail = newNode;
    } else {
        this.tail.next = newNode;
        this.tail = newNode;
    }
}

Step 4: Add a Method to Display the List

To visualize the linked list, we will add a method to display its contents.

1. Create a method called display.
2. Traverse the list starting from the head.
3. Collect node data and print it.

display() {
    let current = this.head;
    let result = '';
    while (current) {
        result += current.data + ' -> ';
        current = current.next;
    }
    console.log(result + 'null');
}

Step 5: Add a Method to Remove a Node

This step involves creating a method to remove a node by its value.

1. Create a method called remove.
2. Check if the list is empty or if the head node is the one to be removed.
3. Traverse the list and update the next references to bypass the node to be removed.

remove(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;
    }
}

Conclusion

In this tutorial, we covered the implementation of a simple Linked List class in JavaScript. We created a Node class, built the Linked List class, and added methods for appending nodes, displaying the list, and removing nodes.

Next steps could include exploring more complex operations like inserting nodes at specific positions, reversing the list, or implementing a doubly linked list. Understanding these operations will deepen your grasp of linked lists and data structures in general.