Linked Lists Data Structure — Complete Guide

What is a Linked List?

A Linked List is a linear data structure in which elements (called nodes) are not stored in contiguous memory locations. Instead, each node consists of two parts:

1. Data: The value stored in the node.
2. Next Pointer: A reference/pointer to the next node in the sequence.

Head → [ Data: 10 | Next ] ──→ [ Data: 20 | Next ] ──→ [ Data: 30 | Next ] ──→ Null

Linked List vs Array

Types of Linked Lists

1. Singly Linked List

Each node points only to the next node. Navigation is one-way (forward).

2. Doubly Linked List (DLL)

Each node contains two pointers: next (points to subsequent node) and prev (points to preceding node). Allows bidirectional traversal.

Null ←─ [ Prev | Data: 10 | Next ] ⇄ [ Prev | Data: 20 | Next ] ─→ Null

3. Circular Linked List

The last node's next pointer points back to the head instead of null, forming a closed loop.

Scratch Implementation (Singly Linked List)

javascript
class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

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

    // Insert at head — O(1)
    insertAtHead(val) {
        const newNode = new ListNode(val, this.head);
        this.head = newNode;
    }

    // Delete node by value — O(N)
    delete(val) {
        if (!this.head) return;
        if (this.head.val === val) {
            this.head = this.head.next;
            return;
        }

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

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

Solved Problem 1: Reverse a Linked List 🟢 Easy

Problem: Reverse a singly linked list in-place and return the new head.

javascript
function reverseList(head) {
    let prev = null;
    let curr = head;

    while (curr !== null) {
        let nextTemp = curr.next; // Store next node
        curr.next = prev;         // Reverse current pointer
        prev = curr;              // Move prev forward
        curr = nextTemp;          // Move curr forward
    }

    return prev; // New head
}

Time: O(N) | Space: O(1)

Solved Problem 2: Linked List Cycle Detection (Floyd's Cycle Finding) 🟢 Easy

Problem: Determine if a linked list contains a cycle.

Floyd's Tortoise and Hare Algorithm: Use two pointers moving at different speeds (slow moves 1 step, fast moves 2 steps). If a cycle exists, the fast pointer will eventually catch up to the slow pointer inside the cycle!

javascript
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; // Fast pointer caught slow pointer → Cycle detected!
        }
    }

    return false;
}

Time: O(N) | Space: O(1)

Solved Problem 3: LRU Cache Design 🔴 Hard

Problem: Design a Least Recently Used (LRU) Cache data structure supporting get and put in O(1) average time.

Solution Architecture: Use a Doubly Linked List combined with a Hash Map.

• Hash Map: Provides O(1) key → node lookup.
• Doubly Linked List: Maintains usage order. Most recently used at head, least recently used at tail. Moving or evicting nodes takes O(1) pointer updates.

javascript
class Node {
    constructor(key, val) {
        this.key = key;
        this.val = val;
        this.prev = null;
        this.next = null;
    }
}

class LRUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.map = new Map();
        
        // Dummy head and tail nodes
        this.head = new Node(0, 0);
        this.tail = new Node(0, 0);
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    _remove(node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    _insertAtHead(node) {
        node.next = this.head.next;
        node.next.prev = node;
        this.head.next = node;
        node.prev = this.head;
    }

    get(key) {
        if (!this.map.has(key)) return -1;
        const node = this.map.get(key);
        this._remove(node);
        this._insertAtHead(node); // Move to most recent
        return node.val;
    }

    put(key, value) {
        if (this.map.has(key)) {
            this._remove(this.map.get(key));
        }

        const newNode = new Node(key, value);
        this._insertAtHead(newNode);
        this.map.set(key, newNode);

        if (this.map.size > this.capacity) {
            // Evict LRU item (before dummy tail)
            const lru = this.tail.prev;
            this._remove(lru);
            this.map.delete(lru.key);
        }
    }
}

Frequently Asked Questions

Q: Why use Dummy / Sentinel Nodes in Linked List problems?
A: Dummy nodes eliminate tedious edge case handling for operations at the head of the list (such as deleting the head node or inserting into an empty list).

Q: How to find the middle of a Linked List in a single pass?
A: Use fast and slow pointers. Move slow by 1 step and fast by 2 steps. When fast reaches the end of the list, slow will be pointing directly to the middle node.