Linked list
A data structure where each node points to the next.
A linked list is a linear collection of data elements in computer science where order is given by each element pointing to the next, rather than by physical placement in memory. It is a fundamental data structure consisting of nodes that together represent a sequence, allowing efficient insertion or removal of elements without reorganizing the entire 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 25-38
Elsewhere in the Algorithms And Data Structures universe
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