Linked List Visualization

Interactive Demonstration

Visualize common Singly Linked List operations.

Value: O(1)

Value: O(n)

Head

NULL

Target: New: O(n)

Value: O(n)

Add nodes or perform operations on the linked list.

How Linked Lists Work

A singly linked list is a linear data structure where elements are not stored at contiguous memory locations. Instead, elements are linked using pointers.

Node: Each element in a linked list is a node. A node typically contains two components:
- Data: The actual value stored in the node.
- Next Pointer: A reference (or pointer) to the next node in the sequence. The last node's pointer points to NULL.
Head: A pointer that references the very first node in the linked list. If the list is empty, the head points to NULL.
Traversal: Accessing elements involves starting from the head and following the `next` pointers sequentially until the desired node or the end of the list is reached. This results in O(n) time complexity for access, search, insertion (at arbitrary position), and deletion (at arbitrary position).
Advantages: Dynamic size (easy to grow/shrink), efficient insertions/deletions at the beginning (O(1)).
Disadvantages: Slow access/search (O(n)), requires extra memory for pointers.

Example Implementation (Conceptual)

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

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

    // Add to head - O(1)
    addHead(data) {
        const newNode = new Node(data);
        newNode.next = this.head;
        this.head = newNode;
    }

    // Add to tail - O(n)
    addTail(data) {
        const newNode = new Node(data);
        if (!this.head) {
            this.head = newNode;
            return;
        }
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    // Delete node by value - O(n)
    delete(data) {
        if (!this.head) return false;

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

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

        if (current.next) { // Found the node before the one to delete
            current.next = current.next.next;
            return true;
        }
        return false; // Not found
    }

    // Search for value - O(n)
    search(data) {
        let current = this.head;
        while (current) {
            if (current.data === data) {
                return current; // Return the node if found
            }
            current = current.next;
        }
        return null; // Not found
    }
}