A linked list stores a sequence not as one contiguous block but as a chain of separate nodes, each holding a data element together with a pointer, the memory address, of the next node. Following the chain of pointers from the first node visits the elements in order. In a doubly linked list each node also points back to its predecessor, allowing the chain to be walked in both directions. The list as a whole is identified by a reference to its first node, and the final node’s “next” pointer is empty to mark the end.
The defining strength of a linked list is cheap insertion and deletion at a known position. To insert a new node, you allocate it and adjust a couple of pointers; nothing else in the list has to move. This is the opposite of an array, where inserting in the middle forces every following element to shift. The defining weakness is the mirror image: there is no address arithmetic to jump to position i, so reaching the i-th element means following pointers from the start, which costs time proportional to i, an O(n) operation. Because the nodes are scattered through memory rather than packed together, linked lists also have poor cache locality and so tend to be slower in practice than their big-O cost alone suggests.
List processing as a programming idea was pioneered in the 1950s by Allen Newell, Cliff Shaw, and Herbert Simon, whose Information Processing Language (IPL) was the first list-processing language, developed at the RAND Corporation and Carnegie to support early artificial-intelligence programs such as the Logic Theory Machine (the History of Programming Languages catalog entry for IPL, verified 2026-06-08). The data structure and its algorithms are treated in depth among the fundamental structures in Donald Knuth’s Volume 1, “Fundamental Algorithms” (Knuth’s pages at Stanford, verified 2026-06-08).
Linked lists also serve as the underlying representation for other structures. A stack or a queue can be built directly on a linked list, using insertion and removal at an end where those operations are cheapest, which is why the list is treated as a building block rather than only an end in itself.