Bytebook Compiler

Linked Lists

Singly Linked List

Nodes joined by pointers: create, traverse, insert at the head, tail or a position, delete, and search — with every operation's cost.

5 min read1 runnable exampleInteractive4-question quiz

A linked list stores elements in separate nodes scattered around memory. Each node holds its data and a pointer to the next node. The list is reached through a pointer to the first node, called the head; the last node points to NULL.

10203040NULLhead
A singly linked list. Each box is a node: data on the left, the next pointer on the right.

Unlike an array, a linked list can grow one node at a time and insert anywhere without shifting other elements — you only rewire pointers.

The node

C
typedef struct Node {
    int data;
    struct Node *next;     // a pointer to another node of the same type
} Node;

A structure that contains a pointer to its own type is called self-referential.

Try it

Insert and delete nodes and watch the pointers change:

The complete program

Every function receives Node **head (a pointer to the head pointer) when it may need to change which node is first.

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

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

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

void insertHead(Node **head, int data) {          // O(1)
    Node *n = newNode(data);
    n->next = *head;
    *head = n;
}

void insertTail(Node **head, int data) {          // O(n): walk to the end
    Node *n = newNode(data);
    if (*head == NULL) { *head = n; return; }
    Node *p = *head;
    while (p->next != NULL) p = p->next;
    p->next = n;
}

void insertAt(Node **head, int pos, int data) {   // pos 0 = new head
    if (pos == 0) { insertHead(head, data); return; }
    Node *p = *head;
    for (int i = 0; p != NULL && i < pos - 1; i++) p = p->next;
    if (p == NULL) { printf("position %d out of range\n", pos); return; }
    Node *n = newNode(data);
    n->next = p->next;                            // 1. new node points to the rest
    p->next = n;                                  // 2. previous node points to new node
}

void deleteValue(Node **head, int key) {
    Node *p = *head, *prev = NULL;
    while (p != NULL && p->data != key) { prev = p; p = p->next; }
    if (p == NULL) { printf("%d not found\n", key); return; }
    if (prev == NULL) *head = p->next;            // deleting the head
    else prev->next = p->next;                    // bypass the node
    free(p);
}

int search(Node *head, int key) {
    for (int i = 0; head != NULL; head = head->next, i++)
        if (head->data == key) return i;
    return -1;
}

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

void freeList(Node **head) {
    while (*head) { Node *t = *head; *head = t->next; free(t); }
}

int main(void) {
    Node *head = NULL;
    insertTail(&head, 20);
    insertTail(&head, 30);
    insertHead(&head, 10);
    print(head);
    insertAt(&head, 2, 25);
    print(head);
    deleteValue(&head, 10);
    print(head);
    deleteValue(&head, 99);
    printf("30 is at position %d\n", search(head, 30));
    freeList(&head);
    print(head);
    return 0;
}
Output
10 -> 20 -> 30 -> NULL
10 -> 20 -> 25 -> 30 -> NULL
20 -> 25 -> 30 -> NULL
99 not found
30 is at position 2
NULL
Try it Yourself

Inserting in the middle, step by step

To insert 25 after node 20:

102030NULLhead
Before: p points at 20.
  1. Create the new node: n->data = 25.
  2. Point it at the rest of the list: n->next = p->next; (25 → 30).
  3. Point 20 at it: p->next = n; (20 → 25).
10202530NULLhead
After: only two pointers changed. No other node moved.

Deleting a node

Find the node and the one before it, make the previous node skip over it, then free it. Deleting the head is a special case: move head forward.

Costs: array vs linked list

Operation Array Singly linked list
Access the i-th element O(1) O(n)
Insert / delete at the front O(n) O(1)
Insert / delete at the end O(1) O(n), or O(1) with a tail pointer
Insert / delete after a known node O(n) O(1)
Search O(n) O(n)
Extra memory none one pointer per node
Memory layout contiguous, cache-friendly scattered

Test yourself

4 questions · pick an answer to check it instantly

  1. 1

    What does the last node of a singly linked list point to?

  2. 2

    What is the cost of inserting a node at the head of a linked list with n nodes?

  3. 3

    Why do insertion functions take Node **head instead of Node *head?

  4. 4

    Which operation is slower on a linked list than on an array?

Esc
↑↓ move↵ open