Your cookie choices
Essential cookies keep your basket and sign-in working. Optional cookies help us understand visits and measure ads. Privacy details.
Essential cookies keep your basket and sign-in working. Optional cookies help us understand visits and measure ads. Privacy details.
Linear data structure where elements are stored in nodes connected by pointers.
AI-assisted explanation. It may contain errors; use a textbook or original source to check important details.
A linked list isn’t really a single equation—it’s a simple, beautiful idea for organizing information. Imagine a scavenger hunt where each clue tells you two things: (1) the information you care about (the “treasure”), and (2) where to find the next clue. That’s a linked list. In a linked list, each element lives inside a node (a small container). Each node holds: - data: the payload (a number, a name, an object—whatever you’re storing) - pointer / link: a reference to the next node (and sometimes also to the previous one) The list is accessed through a special pointer called the head (the first node). You move through the list by following pointers: head → next → next → … until you reach a node whose next pointer is null (meaning “end of the line”). Why do this instead of using an array? Because linked lists are flexible: inserting or removing items in the middle can be done without shifting a bunch of elements around. The tradeoff is that you usually can’t “jump” directly to the k-th element—you must walk node-by-node, like following the clues in order.
Linked lists emerged in the early days of computing when memory was scarce, expensive, and not always laid out in neat contiguous blocks. Early programmers needed a way to build dynamic collections—lists that could grow and shrink—without requiring a large continuous chunk of memory. This idea became especially important in artificial intelligence and symbolic computing, where programs manipulate flexible structures (expressions, trees, graphs) rather than fixed-size numeric tables. Linked lists were a natural fit: they let you allocate little pieces (nodes) wherever space was available, and stitch them together with pointers. They also became foundational in languages and systems that emphasized dynamic memory management—most famously Lisp, where lists are a central data type and the linked-list node (the “cons cell”) became iconic.
Pioneered by: No single person is universally credited, but linked lists are commonly associated with: - Allen Newell, Cliff Shaw, and Herbert A. Simon (mid-1950s, in the IPL programming language) - John McCarthy (late 1950s, popularized list-based structures via Lisp and the cons cell)