Linked Lists

Nodes connected by pointers: cheap insertions anywhere, but no random access.

Easy

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

Singly linked — each node points to the next.
Doubly linked — also points to the previous node.
Circular — the last node points back to the first.

Insert/delete after a known node: $O(1)$ . Find the $k$ -th element: $O(n)$ . Linked lists are used inside OS kernels, free-memory lists and LRU caches.

Spotted a mistake or want to add detail? Suggest an improvement — Content Contributors' edits are reviewed by editors before they go live.

Discussion (0)