A linked list is a data structure that stores a sequence of elements as separate nodes, each holding a value and a reference to the next node, rather than in one contiguous block of memory the way an array does. This makes inserting or removing an element cheap wherever it happens, at the cost of slower access to an arbitrary position, and it remains one of the most fundamental data structures taught in computer science, underlying many other structures such as stacks, queues and trees.
Facts
Disputed
Origin Year1955
No single agreed inventor or date exists. The Information Processing Language, built by Allen Newell, Cliff Shaw and Herbert Simon around 1955 and 1956, is commonly cited among the earliest systems to use linked list style structures, and John McCarthy's Lisp, released in 1958, popularized the idea widely through its list cells; historians do not treat either as a clean single point of origin. Core PrincipleA sequence of elements stored as separate nodes, each pointing to the next, making insertion and removal cheap wherever they happen. 1 FAQs
When is a linked list a better choice than an array?
Choose it for frequent insertions and removals; avoid it when you need fast access by position.
A linked list is the better choice when elements are often inserted or removed. Its elements can be added or removed without reallocating or reorganizing the whole structure, because the items do not need to be stored contiguously in memory. The trade-off is that simple linked lists do not allow random access, so finding a node that holds a given value may mean stepping through most or all of the list. Each node also needs extra storage for its reference, which can make linked lists impractical for small data items such as characters.
Connections
In Field
Source Encyclopedia Britannica: Computer ScienceEncyclopedia Britannica Editors
Sources
1. Encyclopedia Britannica: Computer Science
Encyclopedia Britannica Editors, Encyclopaedia Britannica Inc, 2024View the Source Wikipedia: Linked list
Wikimedia FoundationLead section
a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.
In Group: Linear and Sequence Structures, Lead
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory.
View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.