linked list
A linked list stores its items in separate little boxes called nodes, scattered anywhere in memory. Each node holds a value and a pointer (a link) to the next node; the last node points to nothing. Think of a treasure hunt: each clue tells you only where to find the next one. To reach the fifth item you must follow four links — there is no jumping ahead.
That layout flips the array's trade-offs. Because nothing is contiguous, there is no formula for the i-th element, so reaching position i or searching for a value is O(n) — you walk the chain. But if you are already holding a node, splicing a new node in or unlinking one is just a couple of pointer reassignments: O(1) insert/delete at a known position, with no shifting. Adding at the head is the classic O(1) move.
A singly linked list links only forward; a doubly linked list keeps a prev pointer too, so you can walk both ways and delete a node in O(1) given just that node. The price is extra memory per element (the pointers) and poor cache behaviour, since following links jumps around memory instead of marching through a tidy block.
struct Node { int v; Node* next; };
// head -> [10|*] -> [20|*] -> [30|/] (/ = nullptr)
Node* push_front(Node* head, int x) {
Node* n = new Node{x, head}; // point new node at old head
return n; // O(1): no shifting
}
int nth(Node* head, int i) { // O(n): must walk the chain
while (i-- && head) head = head->next;
return head ? head->v : -1;
}Inserting at the head is O(1); finding the i-th value is O(n).
Array vs linked list is the textbook trade-off: arrays win at random access, linked lists win at insert/delete once you already hold the spot.