Linked list

Easy way to understand: a treasure huntAasan tareeka: treasure hunt

Imagine a treasure hunt. Each clue card has two things written on it: a prize (the data) and where the next clue is hidden (the pointer). You only know where the FIRST card is. To reach the 4th card you must visit cards 1, 2 and 3 first, because each card tells you where the next one is. The last card says "no more clues" — that is NULL. That is exactly how a linked list works.Ek treasure hunt socho. Har clue card pe do cheezein likhi hain: ek prize (data) aur agla clue kahan chhupa hai (pointer). Tumhe sirf PEHLE card ka pata hai. 4th card tak pahunchne ke liye pehle 1, 2 aur 3 card dekhne padenge, kyunki har card hi batata hai ki agla kahan hai. Aakhri card pe likha hai "aur clue nahi" — wahi NULL hai. Linked list bilkul aise hi kaam karti hai.

• Node = one clue card (data + address of the next card).
• head = the address of the first card. Lose it and you lose the whole list.
• NULL = "no more cards". It marks the end of the list.
• Cards can be hidden anywhere — that's why nodes don't need to sit next to each other in memory.

• Node = ek clue card (data + agle card ka address).
• head = pehle card ka address. Ye kho diya toh poori list kho gayi.
• NULL = "aur cards nahi". Ye list ka end mark karta hai.
• Cards kahin bhi chhupe ho sakte hain — isliye nodes ko memory mein ek ke baad ek baithna zaroori nahi.

What is a linked list?Linked list kya hai?

A linked list is a linear data structure made of nodes. Each node stores some data and a pointer (link) to the next node. Unlike an array, the nodes are not stored next to each other in memory — they can be anywhere, and the links hold the list together. The list is accessed through a pointer to the first node, called head. The last node's next pointer is NULL.Linked list ek linear data structure hai jo nodes se bani hoti hai. Har node kuch data aur agle node ka pointer (link) store karta hai. Array ki tarah nodes memory mein saath-saath nahi hote — kahin bhi ho sakte hain, aur links hi list ko jod ke rakhte hain. List ko pehle node ke pointer se access karte hain, jise head kehte hain. Aakhri node ka next pointer NULL hota hai.

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

struct Node *head = NULL;   // empty list

// head → [10 | •] → [20 | •] → [30 | NULL]

Why use a linked list?Linked list kyun use karein?

• Dynamic size: memory is allocated one node at a time with malloc, so the list grows and shrinks as needed — no fixed capacity, no overflow until memory runs out.
• Cheap insert/delete: adding or removing a node only changes a couple of pointers; nothing is shifted.
• No wasted reserved space, unlike an array declared with a large fixed size.

• Dynamic size: malloc se ek-ek node ki memory milti hai, toh list zarurat ke hisaab se badhti-ghatti hai — koi fixed capacity nahi, memory khatam hone tak overflow nahi.
• Sasta insert/delete: node add ya remove karne mein bas do-teen pointers badalte hain; kuch shift nahi hota.
• Bada fixed-size array declare karne jaisi reserved jagah waste nahi hoti.

Common mistakeCommon galtiThe price: no random access (reaching the i-th node takes O(i) steps), extra memory for every pointer, and poor cache performance because nodes are scattered.Keemat: random access nahi (i-th node tak pahunchne mein O(i) steps), har pointer ke liye extra memory, aur nodes bikhre hone ki wajah se cache performance kharab.

Array vs linked listArray vs linked list

Types of linked listsLinked lists ke types

Creating a nodeNode banana

struct Node *newNode(int x) {
    struct Node *n = malloc(sizeof(struct Node));
    n->data = x;
    n->next = NULL;
    return n;
}

Traversal, length and searchTraversal, length aur search

Every list algorithm starts with walking the list: start at head and follow next until NULL. Never move head itself — use a temporary pointer, or you lose the list.Har list algorithm list ko walk karne se shuru hota hai: head se shuru karo aur NULL tak next follow karo. head ko khud kabhi move mat karo — temporary pointer use karo, warna list kho jaayegi.

void print(struct Node *head) {
    for (struct Node *p = head; p != NULL; p = p->next)
        printf("%d -> ", p->data);
    printf("NULL\n");
}

int length(struct Node *head) {
    int count = 0;
    while (head) { count++; head = head->next; }
    return count;
}

struct Node *search(struct Node *head, int key) {
    while (head && head->data != key) head = head->next;
    return head;   // NULL if not found
}

TipAll three are O(n) time and O(1) extra space.Teeno O(n) time aur O(1) extra space lete hain.

InsertionInsertion

// At beginning
struct Node *insertFront(struct Node *head, int x) {
    struct Node *n = newNode(x);
    n->next = head;
    return n;                       // n is the new head
}

// At end
struct Node *insertEnd(struct Node *head, int x) {
    struct Node *n = newNode(x);
    if (head == NULL) return n;
    struct Node *p = head;
    while (p->next) p = p->next;    // stop at the last node
    p->next = n;
    return head;
}

// After node p
void insertAfter(struct Node *p, int x) {
    struct Node *n = newNode(x);
    n->next = p->next;              // 1. link new node forward
    p->next = n;                    // 2. then link p to it
}

Common mistakeCommon galtiOrder matters in insertAfter: if you set p->next = n first, you lose the rest of the list.insertAfter mein order zaroori hai: agar pehle p->next = n kar diya toh baaki list kho jaayegi.

DeletionDeletion

struct Node *deleteFront(struct Node *head) {
    if (!head) return NULL;
    struct Node *t = head;
    head = head->next;
    free(t);
    return head;
}

struct Node *deleteKey(struct Node *head, int key) {
    if (!head) return NULL;
    if (head->data == key) return deleteFront(head);
    struct Node *prev = head;
    while (prev->next && prev->next->data != key) prev = prev->next;
    if (prev->next) {
        struct Node *t = prev->next;
        prev->next = t->next;       // unlink
        free(t);                    // then free
    }
    return head;
}

Common mistakeCommon galtiFreeing a node before saving its next pointer is undefined behaviour. Always unlink/save first, free last.Node ka next pointer save kiye bina use free karna undefined behaviour hai. Hamesha pehle unlink/save, free sabse last.

Reversing a listList reverse karna

Walk the list once and flip every next pointer to point backwards. Three pointers are needed: prev (already-reversed part), curr (node being flipped) and next (saved so we don't lose the rest).List ko ek baar walk karo aur har next pointer ko ulta (peeche ki taraf) kar do. Teen pointers chahiye: prev (jo part reverse ho chuka), curr (jo node abhi palat rahe hain) aur next (save kiya hua, taaki baaki list na khoye).

struct Node *reverse(struct Node *head) {
    struct Node *prev = NULL, *curr = head, *next;
    while (curr) {
        next = curr->next;   // 1. save the rest
        curr->next = prev;   // 2. flip the link
        prev = curr;         // 3. move prev forward
        curr = next;         // 4. move curr forward
    }
    return prev;             // new head
}

// Recursive version: O(n) time, O(n) stack space
struct Node *reverseRec(struct Node *head) {
    if (!head || !head->next) return head;
    struct Node *rest = reverseRec(head->next);
    head->next->next = head;
    head->next = NULL;
    return rest;
}

Fast and slow pointersFast aur slow pointers

Two pointers moving at different speeds solve many list problems in one pass with O(1) extra space.Alag speed se chalne wale do pointers kai list problems ek hi pass mein O(1) extra space se solve kar dete hain.

• Cycle start: after slow and fast meet, move one pointer back to head and advance both one step at a time — they meet at the first node of the cycle.
• k-th node from the end: move a pointer k steps ahead, then move both together until the leading one hits NULL.
• Palindrome check: find the middle, reverse the second half, compare both halves.

• Cycle start: slow aur fast milne ke baad ek pointer ko wapas head pe le jao aur dono ko ek-ek step chalao — wo cycle ke pehle node pe milenge.
• End se k-th node: ek pointer ko k steps aage le jao, phir dono ko saath chalao jab tak aage wala NULL na ho.
• Palindrome check: middle dhoondo, second half reverse karo, dono halves compare karo.

// Middle node (for even length, returns the second middle)
struct Node *middle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }
    return slow;
}

// Floyd's cycle detection
int hasCycle(struct Node *head) {
    struct Node *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return 1;
    }
    return 0;
}

Merging two sorted listsDo sorted lists merge karna

struct Node *merge(struct Node *a, struct Node *b) {
    struct Node dummy, *tail = &dummy;
    dummy.next = NULL;
    while (a && b) {
        if (a->data <= b->data) { tail->next = a; a = a->next; }
        else                    { tail->next = b; b = b->next; }
        tail = tail->next;
    }
    tail->next = a ? a : b;   // attach the leftover part
    return dummy.next;
}

TipO(m + n) time, O(1) extra space. This is the merge step of merge sort, which is the preferred way to sort a linked list (O(n log n), no random access needed).O(m + n) time, O(1) extra space. Ye merge sort ka merge step hai — linked list sort karne ka best tareeka (O(n log n), random access ki zarurat nahi).

Doubly linked listDoubly linked list

Each node has prev and next pointers. You can walk in both directions, and given a pointer to a node you can delete it in O(1) because its predecessor is directly available.Har node mein prev aur next pointers hote hain. Dono direction mein walk kar sakte ho, aur kisi node ka pointer diya ho toh use O(1) mein delete kar sakte ho kyunki uska predecessor seedha available hai.

struct DNode {
    int data;
    struct DNode *prev, *next;
};

// Delete node p in O(1)
void deleteNode(struct DNode **head, struct DNode *p) {
    if (p->prev) p->prev->next = p->next;
    else         *head = p->next;          // p was the head
    if (p->next) p->next->prev = p->prev;
    free(p);
}

// Insert n after p: four pointer updates
void insertAfterD(struct DNode *p, struct DNode *n) {
    n->prev = p;
    n->next = p->next;
    if (p->next) p->next->prev = n;
    p->next = n;
}

Common mistakeCommon galtiInserting into a doubly list needs 4 pointer changes (2 in the new node, 2 in its neighbours); deleting needs 2. GATE often asks which line in such code is wrong — check the NULL cases at the head and tail.Doubly list mein insert ke liye 4 pointer changes chahiye (2 naye node mein, 2 neighbours mein); delete ke liye 2. GATE aksar poochta hai ki aise code mein kaunsi line galat hai — head aur tail pe NULL cases check karo.

Circular linked listCircular linked list

The last node points back to the first, so there is no NULL. Loops must stop when they come back to the starting node.Aakhri node wapas pehle ko point karta hai, isliye koi NULL nahi hota. Loops ko tab rukna chahiye jab wo starting node pe wapas aa jaayein.

• Keep a pointer to the LAST node instead of the first: then both the first (last->next) and the last node are reachable in O(1), so insert at front and at end are both O(1).
• Used for round-robin scheduling and circular buffers.
• Josephus problem is a classic circular-list application.

• Pehle node ki jagah LAST node ka pointer rakho: tab first (last->next) aur last dono O(1) mein milte hain, toh front aur end dono pe insert O(1).
• Round-robin scheduling aur circular buffers mein use hota hai.
• Josephus problem circular list ki classic application hai.

void printCircular(struct Node *head) {
    if (!head) return;
    struct Node *p = head;
    do {
        printf("%d ", p->data);
        p = p->next;
    } while (p != head);
}

Complexity summaryComplexity summary

Common mistakeCommon galtiDeleting the last node of a singly or circular list is O(n) even with a tail pointer, because you need the second-last node.Singly ya circular list ka last node delete karna tail pointer ke saath bhi O(n) hai, kyunki second-last node chahiye.

GATE-style practiceGATE-style practice

• Q1. In a singly linked list with only a head pointer, which needs O(n): insert at front, delete front, or insert at end? → Insert at end.
• Q2. A circular list is accessed by a pointer to the last node. Cost of inserting at the front and at the end? → Both O(1).
• Q3. Best sorting algorithm for a linked list? → Merge sort, O(n log n).
• Q4. Can binary search run in O(log n) on a sorted linked list? → No; finding the middle takes O(n) each time.
• Q5. Given only a pointer p to a node (not the last) in a singly list, delete it in O(1)? → Copy p->next's data into p, then delete p->next.
• Q6. Minimum extra pointers to reverse a singly list iteratively? → Three (prev, curr, next).

• Q1. Sirf head pointer wali singly linked list mein kya O(n) leta hai: front pe insert, front delete, ya end pe insert? → End pe insert.
• Q2. Circular list last node ke pointer se access hoti hai. Front aur end pe insert ki cost? → Dono O(1).
• Q3. Linked list ke liye best sorting algorithm? → Merge sort, O(n log n).
• Q4. Sorted linked list pe binary search O(log n) mein chal sakta hai? → Nahi; har baar middle dhoondhne mein O(n) lagta hai.
• Q5. Singly list mein sirf ek node ka pointer p diya hai (last nahi), use O(1) mein delete karo? → p->next ka data p mein copy karo, phir p->next delete kar do.
• Q6. Singly list ko iteratively reverse karne ke liye minimum extra pointers? → Teen (prev, curr, next).

Practice MCQsPractice MCQs

Previous-year GATE questions on this chapter, plus similar practice questions. Pick an option to see the answer.Is chapter ke GATE previous-year questions, aur unke jaise practice questions. Option choose karo, answer aur explanation turant dikhega.