Linked list

A linked list is a linear data structure where elements (nodes) are stored separately in memory and connected by pointers. Each node holds a piece of data plus a pointer to the next node. The list ends when a node’s next pointer is NULL.

struct node {
    int          value;
    struct node *next;
};
struct node *head;   // points to the first node

The list is accessed through a head pointer. To traverse, you start at the head and follow next pointers until you hit NULL.

Why linked lists exist

Arrays are rigid — fixed size at allocation, expensive to grow. Linked lists are dynamic: you allocate one node at a time as the list grows, and free nodes individually when removed. The trade-off is memory locality (arrays are contiguous, linked lists are scattered) and access time (arrays are O(1) indexed, linked lists are O(n)).

When you’d choose a linked list over an array:

You don’t know the maximum size up front.
You frequently insert or delete at the front (or middle, given a pointer).
You don’t need random access by index.

When an array wins:

You access elements by index repeatedly.
The size is bounded and known.
Cache performance matters (sequential array access is much faster than chasing scattered pointers).

Building a linked list

Allocate the head node with malloc, set its value, and point it to the next:

head = (struct node *) malloc(sizeof(struct node));
head->value = 14;
 
head->next = (struct node *) malloc(sizeof(struct node));
head->next->value = 92;
head->next->next = NULL;   // mark end of list

Always check that malloc succeeded:

if (head == NULL) {
    printf("failed");
    exit(1);
}

Helper: newNode

Repeating the malloc-and-initialize pattern gets tedious. A helper function:

node *newNode(int value) {
    node *tmp = (node *) malloc(sizeof(node));
    tmp->value = value;
    tmp->next  = NULL;
    return tmp;
}

Now creating a node is one call.

Operations

Traverse (print all values)

void printList(struct node *head) {
    struct node *tmp = head;
    printf("[ ");
    while (tmp != NULL) {
        printf("%d, ", tmp->value);
        tmp = tmp->next;
    }
    printf("]\n");
}

The pattern: walk a temp pointer along the list until NULL. O(n) in list length.

Insert at front (insertFirst)

void insertFirst(node **h, int data) {
    node *n = newNode(data);
    n->next = *h;
    *h = n;
}
insertFirst(&head, 14);

The double pointer **h is needed because we may modify the head (if the list was empty, head changes from NULL to the new node). O(1).

Append at end

To append, walk to the last node and link the new node:

void appendList(node **h, int data) {
    node *n = newNode(data);
    if (*h == NULL) {
        *h = n;
        return;
    }
    node *tail = *h;
    while (tail->next != NULL) {
        tail = tail->next;
    }
    tail->next = n;
}

O(n) — you walk to the end first.

Insert after a specific value

struct node *tmp = head;
while (tmp != NULL && tmp->value != 92) {
    tmp = tmp->next;
}
if (tmp != NULL) {
    node *n = newNode(42);
    n->next = tmp->next;
    tmp->next = n;
}

Walk to the matching node, splice the new node in. O(n) for the walk; O(1) for the splice itself.

Insert sorted

Maintain sort order on each insert. Three cases: empty list, insert before the first node, insert in the middle, append at the end.

void insertSorted(node **head, int value) {
    node *n = newNode(value);
    if (*head == NULL) {
        *head = n;
        return;
    }
    if ((*head)->value > value) {
        n->next = *head;
        *head = n;
        return;
    }
    node *tmp = *head;
    while (tmp->next != NULL) {
        if (tmp->next->value > value) {
            n->next = tmp->next;
            tmp->next = n;
            return;
        }
        tmp = tmp->next;
    }
    tmp->next = n;
}

O(n) — walk to find the right position.

Remove first node

int removeFirst(node **head) {
    int value = 0;
    if (*head != NULL) {
        node *tmp = *head;
        *head = (*head)->next;
        value = tmp->value;
        free(tmp);
    }
    return value;
}

Save head, advance head, free the old head. O(1).

Delete by value

void deleteValue(node **head, int val) {
    if (*head == NULL) return;
    
    if ((*head)->value == val) {
        node *tmp = *head;
        *head = (*head)->next;
        free(tmp);
        return;
    }
    
    node *prev = *head;
    while (prev->next != NULL) {
        if (prev->next->value == val) {
            node *tmp = prev->next;
            prev->next = tmp->next;
            free(tmp);
            return;
        }
        prev = prev->next;
    }
}

Use a prev pointer so you can detach a node by linking around it. O(n) for the walk.

Always free what you malloc

Every malloc should be matched by a free when the node is removed. Forgetting to free leaks memory. For freeing the entire list:

void freeList(node *head) {
    while (head != NULL) {
        node *tmp = head;
        head = head->next;
        free(tmp);
    }
}

Note: capture head->next before freeing head, or you’ve already lost the rest of the list.

Variants

Doubly linked list — each node has a prev pointer too. Allows backward traversal at the cost of one extra pointer per node.
Circular linked list — the last node’s next points back to the head. Useful for round-robin schedules, repeating playlists, etc.
Sentinel-headed list — a dummy “header” node simplifies edge cases (no special-case for empty list).

For the array-based alternative that grows dynamically, see Dynamic array.

Idriss Rami — Notes

Explorer