Linked list
A data structure where each node points to the next.
In computer science, a linked list is a linear data structure where the order of elements is determined by each element containing a reference, or link, to the next element, rather than by their physical arrangement in memory. This structure is composed of a sequence of nodes, with each basic node holding two fields: the data itself and a link to the subsequent node. The final node in the sequence points to a terminator that signifies the list's end. A primary advantage over conventional arrays is that elements can be inserted or removed without requiring reallocation or reorganization of the entire structure, as data items do not need to be stored contiguously. This allows insertion and removal at any point with a constant number of operations, provided the link preceding the insertion or removal point is kept in memory during traversal. However, a significant drawback is that data access time is linear relative to the number of nodes; because nodes are serially linked, accessing any node requires prior access to all preceding nodes, making random or direct access impossible. Arrays also offer better cache locality. Linked lists are among the simplest and most common data structures and can implement abstract data types such as stacks, queues, and associative arrays. The concept of linked listing predates digital computing by over two millennia, originating with scribes using "reclamantes" to indicate the order of papyrus scrolls, a practice that later appeared as catchwords in early printed books. The first computer-science implementation was developed in 1955–1956 by Allen Newell, Cliff Shaw, and Herbert A. Simon for their Information Processing Language (IPL), used for early artificial intelligence programs. The classic diagram of blocks with arrows appeared in 1957. Hans Peter Luhn suggested linked lists for chained hash tables in 1953, and John McCarthy created LISP in 1958, which uses the linked list as a major data structure.
- field
- Computer science
- known_for
- Linear data structure with nodes linked by pointers
- early_language_use
- Information Processing Language (IPL), LISP, COMIT
- pre_digital_origin
- Homeric era scribes using reclamantes on papyrus scrolls
Lore & Background
The concept of linked listing predates digital computing by over two millennia, originating in the Homeric era when scribes copying papyrus scrolls wrote the first word of the next scroll at the end of the current one, known as a reclamans. This practice resurfaced in early European printing as catchwords at page ends to aid printers in verifying page order during binding. Simon at RAND Corporation and Carnegie Mellon University as the primary data structure for their Information Processing Language (IPL). IPL was used for early artificial intelligence programs including the Logic Theory Machine, the General Problem Solver, and a computer chess program.
Reader's Guide
Linked lists are among the simplest and most common data structures, used to implement abstract data types such as lists, stacks, queues, associative arrays, and S-expressions. Their principal benefit over conventional arrays is that elements can be inserted or removed without reallocation or reorganization of the entire structure, as data items need not be stored contiguously. However, linked lists do not allow random access; accessing any node requires traversing prior nodes, resulting in linear data access time. Arrays have better cache locality. Variants such as doubly linked lists add a second link to the previous node, enabling more efficient insertion or removal at arbitrary positions. The technique remains foundational in computer science.
Did You Know?
- Linked listing predates digital computing by over two millennia, originating with Homeric-era scribes using reclamantes on papyrus scrolls.
Frequently Asked Questions
Who is Linked list?
Linked list is a linear data structure in computer science where each node stores a pointer to the next element, so sequence order comes from those references rather than from where items sit in memory. It is one of the most foundational structures students encounter when learning about collections.
What are Linked list's powers?
It can insert or remove a node in constant time once you have reached the right spot, without shifting any other elements out of the way. That makes it ideal whenever the collection's size is changing frequently and you don't want to pay a reorganization cost.
Why is Linked list important?
It demonstrates that order in a collection can be encoded through references rather than fixed positions, a principle that underpins stacks, queues, trees, and many other structures. It remains a go-to choice whenever dynamic resizing matters more than fast random access.
How does Linked list's story end?
Its Achilles' heel is that reaching the k-th element requires walking through every preceding node, so random access is linear rather than instant. In practice it is often swapped for arrays or hash tables when lookup speed becomes the bottleneck.
More in Algorithms And Data Structures 1-24
Spotted an error? Know more?
This is a living reference — every entry is fact-audited, and reader corrections feed straight into our audit queue. Suggest an edit · See this site's audit record