Why the humble linked list remains a cornerstone of digital architecture and beyond
In short: A linked list is a sequence of data nodes where each element points to the next, rather than sitting in a fixed memory slot. This structure allows for effortless insertion and deletion, though it sacrifices the speed of random access. It is a fundamental concept that has shaped computing since 1955.
At its core, a linked list is a collection of nodes where each contains data and a reference to the next node in the sequence. Unlike arrays, which require contiguous memory, linked lists allow elements to be scattered. This flexibility means that adding or removing items is a constant-time operation, provided you already have a pointer to the relevant position. In contrast, modifying an array often requires shifting all subsequent elements, a costly process that can impede performance.
The concept predates modern computers by millennia. Ancient scribes used catchwords, or reclamantes, at the end of papyrus scrolls to guide readers to the next section. This practice later migrated to early European printing, where printers placed catchwords at the bottom of pages to ensure correct binding. In 1955, Allen Newell, Cliff Shaw, and Herbert A. Simon formalized this logic for digital systems, using it as the backbone for their Information Processing Language. Their work on early artificial intelligence, including the Logic Theory Machine, earned them the ACM Turing Award in 1975.
Despite their utility, linked lists are not a universal solution. Because they lack random access, finding a specific element requires traversing the list linearly, which is significantly slower than the direct indexing possible with arrays. Furthermore, the overhead of storing pointers for every node can double the memory usage compared to simpler data structures. Modern systems often use hybrid approaches, such as unrolled linked lists or balanced trees, to balance the need for efficient insertion with the requirement for fast data retrieval. Today, they remain essential for managing dynamic objects like active processes and threads, though they are also a common target for rootkits attempting to evade detection by unlinking themselves from system lists.
Opens the Intellect+ feed with this card first. Swipe up for the next one.
Sources
- Summary by Intellect · source: Linked list
To cite this card, link to https://intellectplus.co.uk/app/science-linked-list.
How we source, check and correct cards: Editorial standards.
General information, not professional advice. Spotted an error? Flag the card or see corrections and complaints.
Intellect Plus is a visual educational discovery platform for exploring fascinating facts and ideas. Brain Food, Not Brain Rot. What is Intellect Plus?