Linked List
A linked list is a sequential structure where each element stores not only its value but also a reference to the next element. The collection is held together by connections between nodes rather than by one contiguous block of memory.
βΆArchitecture Diagram
π RelationshipDashed line animations indicate the flow direction of data or requests
Arrays are fast to index, but structural edits in the middle are expensive because later elements must be shifted. When a program keeps inserting, removing, or splicing items at changing positions, copying values around becomes wasteful. Linked lists address that pressure by changing connections instead of relocating large stretches of data.
In early systems software, compilers, and memory managers, structure sizes often changed at runtime and large contiguous regions were not always convenient to maintain. A model of 'allocate one more node and connect it' fit those environments better than dense contiguous storage. That is why linked lists became a foundational dynamic structure and an implementation tool for queues, stacks, free lists, and more.
A linked list starts from a head pointer. Each node contains its payload plus a reference to the next node. To find a target, traversal begins at the head and follows next links one node at a time. The benefit appears during insertion or deletion: if you know the surrounding node references, you can rewire links locally instead of shifting every later element.
The contrast with arrays comes directly from storage layout. Arrays trade flexibility for direct positional access. Linked lists trade positional access for easier structural edits. Linked lists are also not primarily search structures. When the real pressure becomes faster lookup over dynamically changing ordered data, the next step is often a search tree such as a binary search tree.
Linked lists are useful inside queues and stacks, free-list allocators, hash buckets that use separate chaining, and pipelines where nodes are frequently inserted, removed, or reordered. They are much less natural when code repeatedly needs the nth item or relies on cache-friendly dense scans. Their strength is flexible relinking, not fast random access.