Linked lists
Each item in its own node with a pointer to the next one (and, when doubly linked, the previous): O(1) to insert or remove at a node you hold, O(n) to reach position i.
How they work
A linked list stores each item in a node that holds the item and a pointer to the next node, and keeps a pointer to the first node, the head. Changing the list means relinking pointers, so inserting or deleting at the front takes Θ(1), but reaching item i means walking there, O(n). A doubly linked list also links backwards: Java’s LinkedList walks from whichever end is closer, and C++’s std::list inserts and removes in constant time anywhere you already have an iterator, without fast random access.
In practice the pointers cost more than Big-O shows. Every node is a separate allocation, and following a pointer can miss the CPU cache. Rust’s docs say it is “almost always better” to use Vec or VecDeque, and keep LinkedList for when you can’t tolerate amortized resizing or need to split and join lists cheaply: appending one LinkedList to another is O(1). Java’s docs note that ArrayList has a low constant factor compared with LinkedList.
The standard types are Java’s LinkedList, C++’s std::list and singly linked std::forward_list, Rust’s LinkedList and Go’s container/list, all doubly linked except forward_list. Linked lists also live inside other structures: the first hash table design, described by Hans Peter Luhn in 1953, put items in buckets and used a linked list for overflow.
Sources
- MIT 6.006 Introduction to Algorithms (Spring 2020), Lecture 2 notes: Data Structures (linked list sequence)
- Java SE 21 API: LinkedList (operations that index into the list traverse from the nearer end)
- Java SE 21 API: ArrayList (constant factor low compared with LinkedList)
- cppreference: std::list
- Rust std docs: LinkedList (almost always better to use Vec or VecDeque)
- Rust std docs: std::collections (when to use a LinkedList; cost table)
- Go standard library: package container/list (a doubly linked list)
- The Go Blog: Faster Go maps with Swiss Tables (Michael Pratt, Feb 2025): Luhn’s 1953 buckets with linked-list overflow