Linked Lists

A Linked List is a linear data structure where each element (called a node) contains two things: the data it stores and a pointer (or reference) to the next node in the sequence.

Unlike arrays, linked list elements are not stored in contiguous memory. Each node can be anywhere in memory — the pointers connect them together like links in a chain.

Key Terms:

• Node — A single element containing data + a pointer
• Data — The value stored in the node
• Next Pointer — Reference to the following node
• Head — The first node in the list
• Tail — The last node in the list
• null — The tail's next pointer points to null (end of list)

In a Singly Linked List, each node points only to the next node. You can traverse the list in one direction: from head to tail.

Use the controls below to insert nodes and watch the list update in real time.

Operation Code:

// Click an insert button to see the code for that operation

Now let's delete nodes and search through the list. Deletion requires updating pointers, and searching requires traversal from head to tail.

Operation Code:

// Click an operation button to see the code

A Doubly Linked List extends the singly linked list by adding a prev pointer in each node. This allows traversal in both directions — forward and backward.

Each node now has: prev | data | next

Doubly Linked List Code:

// Each node in a Doubly Linked List:
class Node {
    constructor(data) {
        this.data = data;
        this.prev = null;  // pointer to previous node
        this.next = null;  // pointer to next node
    }
}

Arrays and Linked Lists have different performance characteristics. Understanding when to use each is crucial.

* Amortized   ** With tail pointer   *** O(1) for doubly linked list

1. What is the time complexity of inserting a node at the head of a singly linked list?

2. What additional pointer does a doubly linked list node have compared to a singly linked list node?

3. Which operation is faster in an array than in a linked list?