A linked list is a sequence of nodes where each node holds a value and a pointer to the next node. The nodes need not be contiguous in memory; the pointer is what links them. The head pointer is the entry point; the last node's next pointer is NULL. Insertion and deletion at any position where you already hold a pointer costs O(1) — no elements shift — but reaching a position by index requires traversing from the head, costing O(n).

struct node {
    int         val;
    struct node *next;
};
 
struct node *head = NULL;
 
// prepend 42
struct node *n = malloc(sizeof *n);
n->val  = 42;
n->next = head;
head    = n;

The primary advantage over an Array is O(1) insertion and deletion without moving other elements: splice in a node by redirecting two pointers. The primary disadvantage is poor cache behaviour — nodes are scattered in memory and each next pointer dereference is a potential cache miss. Sequential iteration over a linked list is significantly slower than over an array in practice, even though both are O(n) asymptotically.

A doubly linked list adds a prev pointer to each node, allowing traversal in both directions and O(1) deletion given a pointer to the node itself (no need to find the predecessor). The cost is an extra pointer of storage per node.