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 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 sectionQuote, Lead 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.
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.