Linked Lists in C

Concept

A singly linked list is a chain of heap-allocated nodes, each holding data and a pointer to the next node.

Insertion at the head is O(1). Pass a pointer to the head pointer (Node **) when the function must change the head.

Reversing a list iteratively with three pointers (prev, curr, next) is one of the most-asked C interview questions. Always free every node.

Code (C17)

#include <stdio.h>
#include <stdlib.h>

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

void push(Node **head, int v) {
    Node *n = malloc(sizeof *n);
    n->data = v; n->next = *head; *head = n;
}

Node *reverse(Node *head) {
    Node *prev = NULL, *next;
    while (head) { next = head->next; head->next = prev; prev = head; head = next; }
    return prev;
}

void free_list(Node *h) { while (h) { Node *t = h->next; free(h); h = t; } }

int main(void) {
    Node *h = NULL;
    for (int i = 1; i <= 4; i++) push(&h, i);   // 4 3 2 1
    h = reverse(h);                              // 1 2 3 4
    for (Node *p = h; p; p = p->next) printf("%d ", p->data);
    free_list(h);
    return 0;
}

Remember

• Use Node ** to modify the head.
• Save next before relinking.
• Free every node.

Interview questions