Linked lists

In short

A linked list stores a sequence as separate nodes, each holding data and the address of the next node, so the elements need not be adjacent in memory. It trades the array's constant-time random access for constant-time insertion and deletion once you hold a pointer to the place, and for growth without reallocation. It is the first data structure examined after arrays in every Indian university syllabus (AICTE/CBCS "Data Structures" paper) and in GATE CS, where pointer-manipulation code-reading questions appear regularly. In placement rounds — TCS NQT, Infosys HackWithInfy, Wipro NTH, Cognizant, and product interviews at Amazon, Flipkart, Microsoft IDC, Zoho, Adobe and Oracle — reversal, cycle detection, middle-node and merge problems are among the most asked coding questions.

Explained

Node, representation and the basic vocabulary

• A node is a self-referential structure: an information (data) field and one or more link (pointer) fields. In C: struct Node { int data; struct Node *next; };
• The list is accessed only through an external head pointer. head == NULL means an empty list; the last node's next is NULL (the terminator).
• Dynamic allocation: nodes are created with malloc/new from the heap at run time and released with free/delete; the list size is limited only by available heap, not by a declared bound.
• Linked (dynamic) vs sequential (array) allocation: an array element's address is computed as base + i × size, so access is O(1); a list has no address arithmetic — the i-th node is reached only by walking i links, so access is O(n).
• Static / cursor implementation: a list can also be simulated inside an array of records with an integer "next" index and an AVAIL (free) list of unused slots. Used in languages without pointers, in embedded code with no heap, and in file structures.
• Dummy (header/sentinel) node: a permanent first node carrying no data; it removes every "is this the first node?" special case and is the standard trick in exam answers and in library code.
• Garbage, dangling pointer, memory leak: freeing a node while another pointer still refers to it leaves a dangling pointer; losing the only pointer to a node leaks it. Always free *after* re-linking, and set the freed pointer to NULL.

Types of linked lists

1. Singly linked list (SLL): one next link; traversal in one direction only. Deleting a node needs its predecessor, so deletion by value is O(n).
2. Doubly linked list (DLL): prev and next; traversal both ways, and deletion of a node whose pointer you already hold is O(1). Costs one extra pointer per node and four pointer writes per insertion.
3. Circular singly linked list (CSLL): the last node points back to the first; there is no NULL terminator, so every traversal loop must stop on returning to the start. Keeping a tail pointer makes insertion at both front and rear O(1) — the standard queue implementation.
4. Circular doubly linked list (CDLL): head->prev = tail, tail->next = head. Any node can reach any other; this is the structure behind std::list and the Linux kernel's list_head (Java's LinkedList is doubly linked but not circular).
5. Multiply linked / multi-list: several independent link chains through the same nodes (for example a student record linked both by roll number and by branch) — used for sparse matrices and in multilist file organisation.
6. Unrolled linked list: each node holds a small array of elements, cutting pointer overhead and improving cache behaviour.
7. XOR (memory-efficient doubly) linked list: stores prev XOR next in one field — examinable as a trick, unsafe in practice (breaks with address translation and garbage collection).
8. Skip list: a layered, randomised set of linked lists giving expected O(log n) search — a probabilistic alternative to balanced trees, used in Redis sorted sets.

Core operations, step by step

Traversal: for (p = head; p != NULL; p = p->next) visit(p); — O(n), one pass; a circular list uses do { … } while (p != head);

Insertion (SLL)

• *At front:* allocate; new->next = head; head = new; — O(1).
• *After a given node q:* new->next = q->next; q->next = new; — O(1). The order is critical; reversing the two lines loses the rest of the list.
• *At end:* walk to the node with next == NULL, then link — O(n) with only a head pointer, O(1) if a tail pointer is maintained.
• *At position k (1-based):* walk to node k−1, then insert after — O(k).
• *In a sorted list:* walk while p->next->data < x, then insert after — O(n).

Deletion (SLL)

• *First node:* t = head; head = head->next; free(t); — O(1).
• *By key / by position:* keep prev while searching; prev->next = cur->next; free(cur); — O(n). Handle three cases: empty list, first node, node not found.
• *Last node:* O(n) even in a DLL unless a tail pointer exists.
• *Given only a pointer to the node (SLL):* copy the successor's data into it and delete the successor — O(1), but impossible for the last node.
• *Given a pointer to the node (DLL):* p->prev->next = p->next; if (p->next) p->next->prev = p->prev; — O(1).

Search: sequential only — O(n); binary search is not applicable, because reaching the midpoint itself costs O(n).

Sorting: merge sort is the method of choice — O(n log n), no element movement (only links change), and no extra array; split with the slow/fast pointer. Quicksort on lists suffers from the lack of random access; insertion sort on a list is O(n²) but does no shifting.

Standard problems and techniques (the interview core)

• Iterative reversal with three pointers prev, cur, next — O(n) time, O(1) space. Recursive reversal uses O(n) stack.
• Reverse in groups of k, and palindrome check (find middle, reverse second half, compare, restore).
• Two-pointer / slow-fast (tortoise and hare):
  • *Middle node:* slow moves 1, fast moves 2; when fast reaches the end slow is at the middle.
  • *n-th node from the end:* advance one pointer n nodes, then move both — single pass.
  • *Cycle detection (Floyd):* if they meet, a cycle exists; detection is O(n) time, O(1) space. Marking visited nodes with a hash set also works but costs O(n) space. Brent's algorithm is an alternative.
  • *Start of the cycle:* after the meeting, reset one pointer to the head and advance both one step; they meet at the loop's first node.
  • *Length of the cycle:* keep one pointer fixed at the meeting point and walk the other until it returns.
• Intersection (Y-shaped merge) of two lists: compute both lengths, skip the difference in the longer list, then advance together.
• Merge two sorted lists / add two numbers represented as lists — use a dummy head and carry.
• Remove duplicates — O(n) if sorted, O(n) with a hash set otherwise.
• Flatten a multilevel list, rotate by k, odd-even split, clone a list with random pointers.
• Josephus elimination — the textbook application of a circular list.

Complexity, memory and when to prefer a list

• Time: access/search O(n); insert/delete at a known position O(1); insert/delete at the front O(1); insert at the rear O(1) with a tail pointer; delete at the rear O(1) only in a DLL with a tail pointer.
• Space overhead is the real cost: one pointer (8 bytes on a 64-bit build, 4 bytes on 32-bit) per link, plus structure padding, plus the allocator's per-block header (typically 8–16 bytes with glibc malloc).
• Cache behaviour: array traversal is contiguous and prefetched; list nodes are scattered, so a list traversal can be several times slower in wall-clock terms even though both are O(n). This is why std::vector beats std::list for most real workloads.
• Prefer a linked list when: the size is unpredictable, insertions/deletions in the middle are frequent and you already hold the position, no reallocation or element copying is acceptable (large objects), or several lists must be spliced/merged in O(1).
• Prefer an array when: random access or binary search is needed, memory is tight, or traversal speed matters.

Library and system implementations

• C++: std::list (circular doubly linked), std::forward_list (singly). std::list::splice moves a whole list in O(1).
• Java: java.util.LinkedList implements both List and Deque (doubly linked); LinkedHashMap/LinkedHashSet keep insertion order with a doubly linked chain through the hash entries.
• Python: collections.deque is a doubly linked list of fixed-size blocks; plain list is a dynamic array, not a linked list.
• Systems: the Linux kernel's intrusive list_head, FAT file-system cluster chains, free-block lists in memory allocators, and hash-table separate chaining buckets are all linked lists.

Key points

• Node - data field plus link field(s); allocated on the heap, reached only through the head pointer.
• No address arithmetic - the i-th element costs O(n) because links must be followed; binary search is therefore unusable.
• Insert/delete at a known position - O(1) in a list against O(n) element shifting in an array; this is the whole advantage.
• Singly vs doubly - a DLL deletes a given node in O(1) and traverses backwards, at the cost of one extra pointer per node.
• Circular list with a tail pointer - enqueue and dequeue both O(1); the natural queue structure.
• Dummy/sentinel node - removes empty-list and first-node special cases from insert and delete code.
• Order of pointer assignment - always link the new node to the rest *before* changing the old link, or the list is lost.
• Three deletion cases - empty list, first node, key absent; exam marks are lost for ignoring them.
• Delete given a pointer in an SLL - copy the next node's data over it and delete the next; fails for the last node.
• Slow-fast pointers - middle node, n-th from the end, and cycle detection in one pass with O(1) space.
• Floyd's algorithm - meeting proves a cycle; resetting one pointer to the head then stepping both locates the cycle's start.
• Merge sort is the standard list sort - O(n log n), relinks only, no element copying.
• Memory overhead - a list of 4-byte integers typically occupies 4-6 times the memory of an equivalent array.
• Cache locality - lists lose badly to arrays on sequential scans despite equal asymptotic cost.
• Dangling pointer / memory leak - free only after re-linking, and never lose the last reference to a node.
• Static (cursor) implementation - lists inside an array with an AVAIL free list, for environments with no dynamic memory.
• Applications - stacks and queues, hash-table chaining, LRU caches, polynomial and big-integer arithmetic, sparse matrices, undo chains, free-space management.
• Not a substitute for an array when indexing, searching or memory efficiency is the priority.

Formulas and examples

**Example 1 — memory overhead (64-bit Linux, int data). Singly: 4 B data + 8 B pointer = 12 B, padded to a multiple of 8 → 16 B. Doubly: 4 + 8 + 8 = 20 B → padded to 24 B. For n = 10,000 nodes: array = 10,000 × 4 = 40,000 B ≈ 39.1 KB; SLL = 10,000 × 16 = 160,000 B ≈ 156.3 KB (4.0×); DLL = 10,000 × 24 = 240,000 B ≈ 234.4 KB** (6.0×). Adding a 16 B malloc header per node, the SLL becomes 10,000 × 32 = 320,000 B ≈ 312.5 KB, i.e. 8× the array.

Example 2 — insertion at the front, array vs list. An array holds 1,00,000 integers. Each front insertion shifts all 1,00,000 elements. For 1,000 such insertions: 1,000 × 1,00,000 = 10⁸ element moves (seconds of work). A linked list does 2 pointer writes each → 1,000 × 2 = 2,000 writes (microseconds). But to *read* the 50,000th element, the array needs 1 operation and the list needs ~50,000 link hops.

Example 3 — Floyd's cycle detection, traced. Ten nodes N1…N10; N10 points back to N7, so μ = 6 (N1…N6 lie before the cycle) and λ = 4 (N7, N8, N9, N10). Formula: s = λ⌈μ/λ⌉ = 4 × ⌈6/4⌉ = 4 × 2 = 8 steps to meet. Trace (position index, 0-based, N1 = 0):

They meet at N9 after 8 steps, as predicted. Now reset one pointer to N1 and move both one step: after 6 steps the first is at N7 and the second has gone N9→N10→N7→N8→N9→N10→N7 — both at N7, the start of the cycle. Total nodes = μ + λ = 6 + 4 = 10. ✓

Example 4 — Josephus with a circular list, n = 7, k = 3. Recurrence: J(1)=0; J(2)=(0+3) mod 2=1; J(3)=(1+3) mod 3=1; J(4)=(1+3) mod 4=0; J(5)=(0+3) mod 5=3; J(6)=(3+3) mod 6=0; J(7)=(0+3) mod 7=3 → survivor = 3 + 1 = position 4. Simulation on a circular list confirms the elimination order 3, 6, 2, 7, 5, 1 → survivor 4. Each elimination is one O(1) unlink after walking k−1 nodes, so the whole run is O(nk).

Example 5 — polynomial addition with sorted lists. P1 = 5x⁴ + 3x² + 7 (3 nodes), P2 = 4x³ + 3x² + 2x (3 nodes). Walk both in decreasing exponent, copying the larger exponent and adding on a tie: x⁴: 5 → x³: 4 → x²: 3+3 = 6 → x¹: 2 → x⁰: 7. Sum = 5x⁴ + 4x³ + 6x² + 2x + 7, 5 nodes, at most m + n = 6 comparisons — O(m+n), with no wasted storage for the missing powers (an array of coefficients would need 5 slots here and 101 for degree 100 with three terms).

struct Node { int data; struct Node *next; };

void push(struct Node **head, int x) {            /* insert at front, O(1) */
    struct Node *p = malloc(sizeof *p);
    p->data = x; p->next = *head; *head = p;
}

void insertAfter(struct Node *q, int x) {         /* O(1); order of the 2 lines matters */
    struct Node *p = malloc(sizeof *p);
    p->data = x; p->next = q->next; q->next = p;
}

void delKey(struct Node **head, int key) {        /* O(n), handles all 3 cases */
    struct Node *cur = *head, *prev = NULL;
    while (cur && cur->data != key) { prev = cur; cur = cur->next; }
    if (!cur) return;                             /* key absent */
    if (!prev) *head = cur->next;                 /* first node */
    else       prev->next = cur->next;
    free(cur);
}

struct Node *reverse(struct Node *head) {         /* O(n) time, O(1) space */
    struct Node *prev = NULL, *cur = head, *nxt;
    while (cur) { nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; }
    return prev;                                  /* new head */
}

struct Node *loopStart(struct Node *head) {       /* Floyd: detect + locate */
    struct Node *s = head, *f = head;
    while (f && f->next) {
        s = s->next; f = f->next->next;
        if (s == f) { s = head;
            while (s != f) { s = s->next; f = f->next; }
            return s; }
    }
    return NULL;                                  /* no cycle */
}

Reversal trace on 1→2→3→4: after iteration 1, prev=1 (1→NULL), cur=2; after 2, prev=2 (2→1→NULL); after 3, prev=3; after 4, prev=4 and the list is 4→3→2→1→NULL — 4 iterations, 4 pointer writes.

Where it is used

• Operating systems and systems programming: process and task lists, free-memory block lists in malloc and buddy allocators, the Linux kernel's intrusive list_head — core work at Qualcomm India, Intel India, Samsung R&D Bengaluru and Nvidia.
• Caching and databases: LRU/LFU caches built from a doubly linked list plus a hash map (browser caches, Redis, MySQL buffer pool); Redis sorted sets use skip lists — relevant to backend roles at Flipkart, Swiggy, Zomato, PhonePe and Razorpay.
• File systems and storage: FAT cluster chains, inode indirect block chains, journal/log records; blockchain blocks are a hash-linked chain, the model behind ledger systems and India's CBDC pilots.
• Application features: undo-redo stacks in editors and CAD tools, playlist "next/previous" (a circular doubly linked list), browser history, railway and IRCTC-style waitlist/queue structures, print and message queues.
• Compilers and symbol tables, sparse matrices, polynomial and arbitrary-precision arithmetic, hash-table separate chaining, adjacency lists for graphs.
• Hiring and exams: GATE CS (pointer code-reading and complexity questions), ISRO/BARC/NIELIT and PSU recruitment papers, TCS NQT and Infosys/Wipro coding rounds, and the first-round DSA screens of almost every Indian product company.

Interview questions

• Q: Why is insertion O(1) in a linked list but O(n) in an array? A: A list only rewrites two pointers once you hold the position, while an array must shift every later element to keep the elements contiguous; finding the position in a list is still O(n).
• Q: Can binary search be applied to a sorted linked list? A: No — reaching the middle element itself takes O(n) link traversals, so there is no gain; use a skip list or a balanced tree instead.
• Q: How do you find the middle node in one pass? A: Move one pointer by one node and another by two; when the fast pointer reaches the end, the slow pointer is at the middle.
• Q: How do you detect a loop with O(1) extra space, and find where it begins? A: Floyd's slow/fast pointers meet inside the loop; then reset one pointer to the head and advance both one step at a time — they meet at the loop's first node.
• Q: Delete a node when you are given only a pointer to it in a singly linked list. A: Copy the next node's data into this node and delete the next node — O(1); it cannot be done for the last node.
• Q: Which operations become O(1) in a doubly linked list that are O(n) in a singly linked list? A: Deleting a given node and inserting before a given node, because the predecessor is directly available; backward traversal also becomes possible.
• Q: Why is merge sort preferred over quicksort for linked lists? A: Merge sort needs only sequential access and relinks nodes without extra arrays, while quicksort depends on random access for partitioning and degrades badly.
• Q: What is a sentinel or dummy node and why use it? A: A data-less node kept permanently at the head (and sometimes the tail); it makes insertion and deletion uniform by eliminating empty-list and first-node special cases.
• Q: Where would you keep a tail pointer, and why? A: In a queue or any list with frequent rear insertion — it turns the O(n) walk to the end into O(1); a circular list with only a tail pointer gives O(1) access to both ends.
• Q: Arrays and linked lists are both O(n) to traverse, so why are arrays usually faster in practice? A: Array elements are contiguous, so cache lines and hardware prefetching serve many elements per memory fetch, whereas scattered list nodes cause a cache miss per node.
• Q: How do you find where two singly linked lists merge? A: Compute both lengths, advance the longer list by the difference, then move both one step at a time; the first common node is the intersection.
• Q: Is std::list or std::vector the better default in C++? A: std::vector for almost all cases, because of contiguity and cache behaviour; std::list only when O(1) splicing or stable node addresses under insertion are required.

Common mistakes

• Writing q->next = new; new->next = q->next; — the link order is reversed and the rest of the list is lost (it now points to itself).
• Not handling the empty list, the single-node list and the "key not found" case in deletion; and forgetting to update head when the first node goes.
• free(cur) before re-linking, then dereferencing cur->next — undefined behaviour from a dangling pointer; equally, losing the only pointer to a node and leaking it.
• Updating only next and not prev in a doubly linked list, and missing the NULL check if (p->next) when deleting the last node.
• Writing while (p != NULL) for a circular list — it never terminates; the test must be the return to the starting node.
• Passing head by value in C and expecting the caller's head to change — the function needs struct Node ** (or must return the new head).
• Claiming "linked list insertion is O(1)" without stating that the position must already be known, and claiming lists save memory when each node adds 8–24 bytes of pointer, padding and allocator overhead.

Related topics

• Arrays and strings · Stacks and queues · Trees and binary search trees · Hashing and hash tables · Graphs and their representation · Heaps and priority queues