Linked List

Concept

A linked list is a linear data structure where each element (node) contains a value and a pointer to the next node. Unlike arrays, elements are not stored contiguously in memory. Insertion and deletion at any position take O(1) if you have the pointer, but random access takes O(n) since you must traverse from the head.

When to Use

▸When you need frequent insertions/deletions at arbitrary positions
▸Implementing stacks, queues, or deques from scratch
▸Problems involving merging, reversing, or detecting cycles in sequences
▸When you don't need random access by index

Intuition

Think of a chain where each link knows only the next link. To find the 5th link, you must start at the first and follow 4 connections. To insert a new link in the middle, just redirect two pointers — no shifting needed. The tradeoff is clear: fast insert/delete, slow search. In contests, you rarely implement linked lists (use vector/deque instead), but understanding them helps with pointer-based problems.

Complexity

Time

O(1) insert/delete at known position, O(n) search

Space

O(n)

Template Code

cpp

#include<bits/stdc++.h>
using namespace std;

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

void insertFront(Node*& head, int val){
    Node* newNode = new Node(val);
    newNode->next = head;
    head = newNode;
}

void insertAfter(Node* prev, int val){
    if(!prev) return;
    Node* newNode = new Node(val);
    newNode->next = prev->next;
    prev->next = newNode;
}

void deleteNode(Node*& head, int val){
    if(!head) return;
    if(head->val == val){
        Node* tmp = head;
        head = head->next;
        delete tmp;
        return;
    }
    Node* cur = head;
    while(cur->next && cur->next->val != val){
        cur = cur->next;
    }
    if(cur->next){
        Node* tmp = cur->next;
        cur->next = tmp->next;
        delete tmp;
    }
}

void printList(Node* head){
    Node* cur = head;
    while(cur){
        cout << cur->val;
        if(cur->next) cout << " -> ";
        cur = cur->next;
    }
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    Node* head = nullptr;

    insertFront(head, 3);
    insertFront(head, 2);
    insertFront(head, 1);
    printList(head);  // 1 -> 2 -> 3

    insertAfter(head->next, 5);
    printList(head);  // 1 -> 2 -> 5 -> 3

    deleteNode(head, 5);
    printList(head);  // 1 -> 2 -> 3

    return 0;
}

// Output:
// 1 -> 2 -> 3
// 1 -> 2 -> 5 -> 3
// 1 -> 2 -> 3