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

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the bottom.

• How is a queue built from two stacks kept in FIFO order? from Lesson 3.3.3
• In a linear array queue, why can it report full with free slots? from Lesson 3.3.1
• What does malloc(n * sizeof(int)) return, and what must you eventually do with it? from Lesson 1.7

1 · The Hook

🎣

A train is a chain of coaches. Each coach is coupled to the next; to add a pantry car in the middle you uncouple one joint and couple twice — nobody shifts the other coaches along the platform. A linked list stores data the same way: separate blocks of memory, each holding a pointer to the next.

2 · Predict First

🤔

What does this print? (Helpers newNode, build and printList are defined below.)

int main(void)
{
    struct node *head = newNode(10);
    head->next = newNode(20);
    head->next->next = newNode(30);
    printList(head);
    printf("%d %d\n", head->data, head->next->next->data);
    return 0;
}

Make a guess in your head. The answer opens Section 3.

3 · Core Concept

💡

Predict First — the answer

Output

10 20 30 
10 30

head points to the node holding 10; its next points to 20; that one’s next points to 30, whose next is NULL.

Nodes and the head pointer

A node is a self-referential structure (Lesson 1.6) holding the data and a pointer to the next node. The list is reached through a pointer to its first node, the head; the last node’s next is NULL. An empty list is head == NULL. Nodes are created with malloc (Lesson 1.7) one at a time, so the list can grow to any length, and nodes need not be next to each other in memory.

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

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

struct node *build(int a[], int k)          /* list a[0] -> a[1] -> ... */
{
    struct node *head = NULL, *tail = NULL;
    int i;
    for (i = 0; i < k; i++) {
        struct node *n = newNode(a[i]);
        if (head == NULL) head = n;
        else tail->next = n;
        tail = n;
    }
    return head;
}

void printList(struct node *p)
{
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

Traversal and search

Walk with a pointer: for (p = head; p != NULL; p = p->next). Length, printing, searching and summing all follow this pattern: O(n). There is no a[i]: reaching the i-th node takes i steps.

Insertion

• At the head: new node points to the old head; head points to the new node. O(1).
• After a node p: n->next = p->next; p->next = n; O(1) once p is known. The order matters: doing the second line first loses the rest of the list.
• At the tail: walk to the last node (O(n)), or keep a tail pointer (O(1)).

int main(void)
{
    int a[] = {1, 2, 3};
    struct node *head = build(a, 3);
    struct node *n = newNode(9);
    /* WRONG order would be: head->next = n; n->next = head->next;  (loses 2 and 3) */
    n->next = head->next;            /* first link the new node to the rest */
    head->next = n;                  /* then link the previous node to it  */
    printList(head);
    return 0;
}

Output

1 9 2 3

Deletion

To delete a node you must change its previous node’s next, so search with two pointers (prev, cur). Deleting the first node changes head itself. Free the removed node.

Functions that change the head

Because C passes by value (Lesson 1.4.2), a function that inserts at the head or deletes the first node needs struct node **head (the address of the caller’s head pointer), or must return the new head.

int length(struct node *p)
{
    int n = 0;
    for (; p != NULL; p = p->next) n++;
    return n;
}

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

void insertHead(struct node **head, int x)
{
    struct node *n = newNode(x);
    n->next = *head;
    *head = n;
}

void insertAfter(struct node *p, int x)
{
    struct node *n = newNode(x);
    n->next = p->next;
    p->next = n;
}

void deleteValue(struct node **head, int key)
{
    struct node *cur = *head, *prev = NULL;
    while (cur != NULL && cur->data != key) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return;            /* not found */
    if (prev == NULL) *head = cur->next; /* deleting the first node */
    else prev->next = cur->next;
    free(cur);
}

int main(void)
{
    int a[] = {10, 20, 30, 40};
    struct node *head = build(a, 4);
    insertHead(&head, 5);
    insertAfter(search(head, 20), 25);
    deleteValue(&head, 30);
    deleteValue(&head, 5);
    printList(head);
    printf("length %d, found 40? %d, found 99? %d\n", length(head), search(head, 40) != NULL, search(head, 99) != NULL);
    return 0;
}

Output

10 20 25 40 
length 4, found 40? 1, found 99? 0

Linked list vs array

4 · Visual

After the operations of the program above: 10 → 20 → 25 → 40 → NULL. The addresses are scattered; only the next pointers give the order.

insertAfter(p, 25) where p holds 20:

before:   [10|•]--> [20|•]--------------> [30|•]--> ...
                     p
step 1:   n = [25|•] ; n->next = p->next          [25|•]--> [30|•]
step 2:   p->next = n
after:    [10|•]--> [20|•]--> [25|•]--> [30|•]--> ...

deleteValue(30):  prev = node 20, cur = node 30
          prev->next = cur->next ;  free(cur)
          [20|•]------------------> [40|•]

Two pointer changes insert; one pointer change (plus free) deletes.

5 · Worked Examples

Example 1 Easy

What does this print?

int main(void)
{
    struct node *head = newNode(10);
    head->next = newNode(20);
    head->next->next = newNode(30);
    printList(head);
    printf("%d %d\n", head->data, head->next->next->data);
    return 0;
}

Solution

Output

10 20 30 
10 30

Example 2 Medium

What does this print?

int main(void)
{
    int a[] = {4, 8, 15, 16, 23};
    struct node *head = build(a, 5);
    struct node *p = head->next->next;
    p->next = p->next->next;
    head = head->next;
    printList(head);
    return 0;
}

Solution

p is the node 15. p->next = p->next->next skips 16 (15 → 23). Then head moves to 8, dropping 4 from the front.

Output

8 15 23

Example 3 GATE

What does this print?

int length(struct node *p)
{
    int n = 0;
    for (; p != NULL; p = p->next) n++;
    return n;
}

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

void insertHead(struct node **head, int x)
{
    struct node *n = newNode(x);
    n->next = *head;
    *head = n;
}

void insertAfter(struct node *p, int x)
{
    struct node *n = newNode(x);
    n->next = p->next;
    p->next = n;
}

void deleteValue(struct node **head, int key)
{
    struct node *cur = *head, *prev = NULL;
    while (cur != NULL && cur->data != key) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return;            /* not found */
    if (prev == NULL) *head = cur->next; /* deleting the first node */
    else prev->next = cur->next;
    free(cur);
}

int main(void)
{
    int a[] = {10, 20, 30, 40};
    struct node *head = build(a, 4);
    insertHead(&head, 5);
    insertAfter(search(head, 20), 25);
    deleteValue(&head, 30);
    deleteValue(&head, 5);
    printList(head);
    printf("length %d, found 40? %d, found 99? %d\n", length(head), search(head, 40) != NULL, search(head, 99) != NULL);
    return 0;
}

Solution

Start 10 20 30 40. insertHead(5): 5 10 20 30 40. insertAfter(node 20, 25): 5 10 20 25 30 40. deleteValue(30): 5 10 20 25 40. deleteValue(5) removes the first node, changing head: 10 20 25 40.

Output

10 20 25 40 
length 4, found 40? 1, found 99? 0

6 · GATE Traps

⚠️

• When inserting after p, set n->next before p->next, or the rest of the list is lost.
• Deleting needs the previous node; deleting the first node changes head.
• A function that changes head must receive struct node ** (or return the new head).
• Always test p != NULL before using p->next.
• Accessing the i-th node is O(i): no indexing, no binary search.
• Free removed nodes, or memory leaks.

8 · Memory Hook

🧠

“Couple, then uncouple.” Hook the new coach to the train behind it first, then attach it to the coach in front — never let go of the rear part of the train.

9 · Connect the Dots

Lesson 1.6 linked three records by hand; now lists are built and changed by functions. Some list tasks need clever pointer moves: turning the whole list around, finding the middle in one pass, detecting a list that loops back on itself. Next lesson answers: how are these done with two or three pointers walking together?

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1MCQ1 markCosts

In a singly linked list with only a head pointer, which operation is O(1)?

• (A) insert at the end
• (B) search for a value
• (C) access the 5th node
• (D) insert at the front

Q2MCQ2 marksOutput

What does this print?

int main(void)
{
    int a[] = {4, 8, 15, 16, 23};
    struct node *head = build(a, 5);
    struct node *p = head->next->next;
    p->next = p->next->next;
    head = head->next;
    printList(head);
    return 0;
}

• (A) 8 15 23
• (B) 4 8 15 23
• (C) 8 15 16 23
• (D) 8 16 23

Q3MCQ1 markOrder of links

To insert node n after node p, which order is correct?

• (A) n->next = p; p->next = n;
• (B) n->next = p->next; p->next = n;
• (C) p = n; n->next = p;
• (D) p->next = n; n->next = p->next;

Q4MSQ1 markFacts

Which are true about singly linked lists?

• (A) Nodes are usually created with malloc.
• (B) Binary search can be done in O(log n).
• (C) Deleting a node needs access to its previous node.
• (D) The last node’s next is NULL.

Q5NAT2 marksOutput

What does this print? (enter the length printed)

int length(struct node *p)
{
    int n = 0;
    for (; p != NULL; p = p->next) n++;
    return n;
}

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

void insertHead(struct node **head, int x)
{
    struct node *n = newNode(x);
    n->next = *head;
    *head = n;
}

void insertAfter(struct node *p, int x)
{
    struct node *n = newNode(x);
    n->next = p->next;
    p->next = n;
}

void deleteValue(struct node **head, int key)
{
    struct node *cur = *head, *prev = NULL;
    while (cur != NULL && cur->data != key) {
        prev = cur;
        cur = cur->next;
    }
    if (cur == NULL) return;            /* not found */
    if (prev == NULL) *head = cur->next; /* deleting the first node */
    else prev->next = cur->next;
    free(cur);
}

int main(void)
{
    int a[] = {10, 20, 30, 40};
    struct node *head = build(a, 4);
    insertHead(&head, 5);
    insertAfter(search(head, 20), 25);
    deleteValue(&head, 30);
    deleteValue(&head, 5);
    printList(head);
    printf("length %d, found 40? %d, found 99? %d\n", length(head), search(head, 40) != NULL, search(head, 99) != NULL);
    return 0;
}

Numerical answer: ________

11 · Rule Card

• 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.

12 · Concept Ledger

Unlocked in this lesson. From here on, these terms may be used.

nodelinked listsingly linked listhead pointertraversalinsert at head / after / at taildelete with previous pointertail pointer

13 · Answer Vault