Creating and Working with Linked Lists in JavaScript

Introduction

In JavaScript, arrays are commonly used for storing lists of elements. However, when dealing with dynamic data structures where insertions and deletions happen frequently, linked lists can be a better choice. Unlike arrays, linked lists provide efficient insertions and deletions without needing to shift elements.

In this blog, we'll cover:

• What a linked list is
• How to create a linked list in JavaScript
• How to insert, delete, and traverse nodes
• Detecting cycles in a linked list

1. What is a Linked List?

A linked list is a linear data structure where each element (node) contains:

• A value
• A reference (or pointer) to the next node

Types of Linked Lists

1. Singly Linked List – Each node points to the next node.
2. Doubly Linked List – Each node has two pointers, one to the next node and one to the previous node.
3. Circular Linked List – The last node points back to the first node.

2. Implementing a Singly Linked List in JavaScript

Since JavaScript does not have built-in linked list support, we create one using objects.

Defining a Node

function ListNode(val) {
    this.val = val;
    this.next = null;
}

• Each ListNode object holds a value (val) and a pointer to the next node.

Creating a Linked List

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

    // Insert at the end
    append(val) {
        let newNode = new ListNode(val);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Print the list
    printList() {
        let current = this.head;
        let output = "";
        while (current) {
            output += current.val + " -> ";
            current = current.next;
        }
        console.log(output + "null");
    }
}

// Example Usage
let list = new LinkedList();
list.append(1);
list.append(2);
list.append(3);
list.printList(); // Output: 1 -> 2 -> 3 -> null

3. Inserting and Deleting Nodes

Insert at the Beginning

prepend(val) {
    let newNode = new ListNode(val);
    newNode.next = this.head;
    this.head = newNode;
}

Delete a Node

delete(val) {
    if (!this.head) return;

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

    let current = this.head;
    while (current.next && current.next.val !== val) {
        current = current.next;
    }

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

4. Detecting a Cycle in a Linked List

A cycle occurs when a node's next pointer points back to a previous node, forming a loop.

Floyd’s Cycle Detection Algorithm (Tortoise and Hare)

function hasCycle(head) {
    let slow = head;
    let fast = head;

    while (fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

5. Conclusion

Linked lists are a powerful data structure that offers advantages over arrays for certain operations. JavaScript doesn’t have native linked lists, but we can implement them using objects.

Summary of Operations:

✅ Append (insert at end) – O(n)
✅ Prepend (insert at beginning) – O(1)
✅ Delete – O(n)
✅ Cycle Detection – O(n)