Linked List

Data Structures O(n) search O(n)

Nodes chained by pointers: O(1) insertion at the head, sequential traversal to search or delete.

head

NULL

Pick an operation to walk through the code.

InvariantEach node points to the next; the head is the only entry point, so a push is O(1) and an index lookup is not.

linked-list.c

typedef struct Node {
    int data;
    struct Node *next;
} Node;
 
Node *pushFront(Node *head, int value) {
    Node *node = malloc(sizeof(Node));
    node->data = value;
    node->next = head;
    return node;
}
 
Node *removeValue(Node *head, int value) {
    if (head == NULL) return NULL;
    if (head->data == value) {
        Node *rest = head->next;
        free(head);
        return rest;
    }
    head->next = removeValue(head->next, value);
    return head;
}

How Linked List works

Each node stores a value and a pointer to the next node. There is no random access — you reach the k-th element by walking k links — but inserting at the head is a single pointer change.

Best case

Push/pop at the head: O(1).

Worst case

Search or delete by value: O(n) walk.

When to use it

Frequent insertions/removals at the ends, unknown final size, or as the chain inside hash tables.