Understanding Linked Lists in JavaScript

#javascript #datastructures #linkedlist #beginners

Hey friends 👋

It’s another Tutorial Wednesday, and today we’re stepping up a bit in our DSA journey with Linked Lists.

What is a Linked List?

A linked list is a series of items connected in a sequence. Imagine a treasure hunt where each clue is on a separate piece of paper. The first clue is easy to find, but every other clue is hidden at a different location and points to the next one. A linked list works exactly like this:

Each Node is a piece of paper. It holds a piece of data (the treasure's location) and a pointer to the next clue.
The head is the very first clue, the starting point of the hunt.
The tail is a special note you keep in your pocket that always tells you where the last clue is.

This structure allows us to add or remove items very efficiently, as we'll see below.

Implementing a Linked List

The code for a linked list is broken down into two parts: a Node class and a LinkedList class.

i. The Node Class

This is our blueprint for each individual item in the list. It's very simple.

class Node {
  constructor(value) {
    this.value = value; // The data for this node
    this.next = null;   // A pointer to the next node in the list
  }
}

ii. The LinkedList Class

This class manages the entire list. It keeps track of the head (the first node) and the tail (the last node). The tail is the key to making our operations fast.

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null; // We add a tail pointer here
  }

The `append` Method: The Magic of O(1)

The append method adds a new node to the end of our list. This is where the tail pointer shines, making the process incredibly fast.

Without a tail pointer: To add a new clue, you would have to follow every single clue from the beginning of the hunt to find the last one. If your hunt has 100 clues, you have to do 100 steps. This is slow and we call it O(n).
With a tail pointer: You just look at your "last clue" note (this.tail), link your new clue to it, and then update your note to point to the new clue. It's always a quick, two-step process, no matter how long the list is. We call this O(1).

  // Add node at the end in O(1) time
  append(value) {
    const newNode = new Node(value);

    // If the list is empty, the new node is both the first and last
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      return;
    }

    // Otherwise, link the current tail to the new node
    this.tail.next = newNode;
    // Then, make the new node the new tail
    this.tail = newNode;
  }

The `print` Method

This method lets us see all the nodes in our list by traversing from the head.

  // Print all nodes 
  print() {
    const values = [];
    let current = this.head;
    while (current) {
      values.push(current.value);
      current = current.next;
    }
    return values.join(" -> ");
  }
}

Example Usage
Here's how we'd use our new, efficient linked list.

const list = new LinkedList();
list.append("First Clue");
list.append("Second Clue");
list.append("Third Clue");
console.log(list.print()); // First Clue -> Second Clue -> Third Clue