Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Notes › DSA

Linked List

A linked list stores elements in nodes. Each node holds a value and a pointer to the next node. Unlike an array, the nodes are not next to each other in memory, so you cannot jump to the i-th element — you have to walk there.

head → [10 | •] → [20 | •] → [30 | •] → null

Types

Type Each node points to Use
Singly next Simple lists, stacks
Doubly next and prev Browser history, LRU cache, deque
Circular last node → head Round-robin scheduling, music playlists

Node and basic operations (C++)

struct Node {
    int val;
    Node* next;
    Node(int v) : val(v), next(nullptr) {}
};

// insert at the front — O(1)
Node* pushFront(Node* head, int v) {
    Node* n = new Node(v);
    n->next = head;
    return n;                 // new head
}

// insert after position k (0-based) — O(k)
void insertAfter(Node* head, int k, int v) {
    Node* cur = head;
    for (int i = 0; i < k && cur; i++) cur = cur->next;
    if (!cur) return;
    Node* n = new Node(v);
    n->next = cur->next;      // 1. new node points to the rest
    cur->next = n;            // 2. then link it in (order matters!)
}

// delete the first node with value v — O(n)
Node* removeValue(Node* head, int v) {
    Node dummy(0);
    dummy.next = head;
    Node* prev = &dummy;
    while (prev->next && prev->next->val != v) prev = prev->next;
    if (prev->next) {
        Node* del = prev->next;
        prev->next = del->next;
        delete del;
    }
    return dummy.next;
}

Dummy (sentinel) node trick: put a fake node before the head. Then deleting or inserting at the head needs no special case.

Complexity

Operation Array Linked list
Access i-th element O(1) O(n)
Insert / delete at front O(n) O(1)
Insert / delete in the middle (pointer known) O(n) O(1)
Search O(n) O(n)
Extra memory none one pointer per node
Cache friendly yes no

Must-know patterns

1. Reverse a list (iterative)

Three pointers: prev, curr, next. Save next before you change curr->next.

Node* reverse(Node* head) {
    Node *prev = nullptr, *curr = head;
    while (curr) {
        Node* nxt = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nxt;
    }
    return prev;              // new head
}

Watch it step by step in the linked list visualizer.

2. Fast and slow pointers

slow moves 1 step, fast moves 2 steps.

bool hasCycle(Node* head) {
    Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

3. Merge two sorted lists

Use a dummy node and attach the smaller head each time — O(n + m).

4. k-th node from the end

Move a first pointer k steps ahead, then move both until the first reaches the end.

5. Remove duplicates from a sorted list

If cur->val == cur->next->val, skip the next node; else move on.

Classic problems

Problem Idea
Reverse linked list 3 pointers
Middle of linked list fast/slow
Linked list cycle I & II Floyd's algorithm
Merge two sorted lists dummy node
Remove N-th node from end gap of N between two pointers
Palindrome linked list find middle, reverse second half, compare
Intersection of two lists switch heads when a pointer reaches the end
Add two numbers digit by digit with a carry
LRU cache hash map + doubly linked list

Practise them in the Linked List section of the DSA sheet.

Interview one-liners

More DSA notes