Linked lists

ACompressed recap

🧾

Nodes hold data and next; head reaches the first, NULL ends the list. Insert after p with n->next = p->next then p->next = n; delete with the previous node’s next; head-changing functions need struct node **. Reverse with prev/cur/next; find the middle and detect cycles with slow and fast pointers. Doubly linked lists delete a known node in O(1) at the cost of a second pointer; circular lists close the ring. Linked stacks use the head; linked queues insert at rear and delete at front. To trace pointer code, draw boxes and update one arrow per statement.

BMerged rule card

3.4.1 Singly linked list: node, head, traversal, search, insertion (head/tail/middle), deletion

• Node = data + next; head → first node; last->next = NULL; empty: head == NULL.
• Traverse: for (p = head; p; p = p->next) — O(n).
• Insert after p: n->next = p->next; p->next = n; (in this order).
• Insert at head O(1); at tail O(n) (O(1) with tail pointer).
• Delete: prev->next = cur->next; free(cur); first node changes head.
• Head-changing functions take struct node ** or return the head.

3.4.2 Reversing a list (iterative and recursive); finding the middle; detecting a cycle (fast/slow pointers)

• Reverse: while (cur) { nxt = cur->next; cur->next = prev; prev = cur; cur = nxt; } return prev;
• Recursive: rest = rrev(head->next); head->next->next = head; head->next = NULL;
• Middle: slow +1, fast +2 while fast && fast->next; even n → second middle.
• Cycle: slow == fast ⇒ cycle; fast hits NULL ⇒ none. O(n) time, O(1) space.

3.4.3 Doubly and circular linked lists; operation costs compared with arrays

• Doubly linked: prev + next; delete/insert beside a known node O(1); 4 writes to insert, 2 to delete.
• Circular: last->next = head; traverse with do-while until back at the start.
• A last pointer on a circular list gives O(1) access to both ends.
• Singly linked + tail: insert at end O(1), delete at end O(n).
• Price of doubly linked: one more pointer per node.

3.4.4 Stack and queue built on linked lists

• Linked stack: top = head; push/pop at head; empty top == NULL.
• Linked queue: front = head (delete), rear = last (insert); both O(1).
• Empty enqueue sets front = rear = n; last dequeue sets rear = NULL.
• No fixed capacity; extra pointer per item; malloc/free per operation.

3.4.5 GATE drill: tracing pointer-manipulation code on linked lists

• Draw boxes + arrows; label pointer variables; one change per statement.
• p->next = p->next->next unlinks one node.
• q one step behind p reaches the second-to-last node.
• Data swap vs link swap: same printout, different nodes.
• Recursion over a list: before-call prints forwards, after-call backwards; p->next->next skips alternate nodes.

CInterleaved GATE-style questions

Q1MCQ2 marksOutput

What does this print?

struct node *moveLastToFront(struct node *head)
{
    struct node *p = head, *q = NULL;
    if (head == NULL || head->next == NULL) return head;
    while (p->next != NULL) {
        q = p;
        p = p->next;
    }
    q->next = NULL;
    p->next = head;
    head = p;
    return head;
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6};
    printList(moveLastToFront(build(a, 6)));
    return 0;
}

• (A) 6 1 2 3 4 5
• (B) 1 2 3 4 5 6
• (C) 2 3 4 5 6 1
• (D) 6 5 4 3 2 1

Q2NAT1 markPointers

How many next pointers change when a node is inserted after a known node of a singly linked list?

Numerical answer: ________

Q3MCQ1 markMiddle

For a 9-node list, slow/fast pointers leave slow on node:

• (A) 9
• (B) 6
• (C) 5
• (D) 4

Q4MCQ1 markCosts

Which needs O(n) time in a singly linked list with head and tail pointers?

• (A) delete at front
• (B) delete at end
• (C) insert at front
• (D) insert at end

Q5MCQ2 marksOutput

What does this print?

void f(struct node *p)
{
    if (p == NULL) return;
    printf("%d ", p->data);
    if (p->next != NULL)
        f(p->next->next);
    printf("%d ", p->data);
}

int main(void)
{
    int a[] = {1, 2, 3, 4, 5, 6};
    f(build(a, 6));
    printf("\n");
    return 0;
}

• (A) 1 2 3 4 5 6
• (B) 1 3 5 5 3 1
• (C) 1 3 5
• (D) 1 3 5 6 4 2

Q6MCQ1 markCycle

In Floyd’s method, a list has a cycle exactly when:

• (A) slow reaches NULL
• (B) slow and fast meet
• (C) fast is twice slow’s index
• (D) fast reaches NULL

Q7MSQ2 marksQueue

For a linked queue with front and rear, which are correct?

• (A) enqueue links after rear
• (B) dequeue of the last item must set rear to NULL
• (C) dequeue removes front
• (D) enqueue into an empty queue only sets rear

Q8MCQ2 marksReverse

After iterative reversal of 1 → 2 → 3 → 4 with prev/cur/nxt, which node’s next is NULL?

• (A) 1
• (B) 4
• (C) 2
• (D) none

Q9NAT2 marksOutput

What does this print? (enter the number of values printed)

void deleteAlternate(struct node *p)
{
    struct node *gone;
    while (p != NULL && p->next != NULL) {
        gone = p->next;
        p->next = gone->next;
        free(gone);
        p = p->next;
    }
}

int main(void)
{
    int a[] = {10, 20, 30, 40, 50};
    struct node *h = build(a, 5);
    deleteAlternate(h);
    printList(h);
    return 0;
}

Numerical answer: ________

DAnswer Vault