Linked list
Linked list
A linked list is a linear data structure in which elements, called nodes, are linked together using pointers. Each node contains a data field and a reference (or link) to the next node in the sequence. Unlike arrays, linked lists allow efficient insertion and removal of elements at arbitrary positions without reallocation or reorganization of the entire structure. However, they provide slower access to individual elements because traversal must start from the head node.
Features
- Dynamic size: Nodes are allocated as needed, so the list grows and shrinks during execution.
- Ease of insertion and deletion: Adding or removing a node only requires updating a few pointers, not shifting other elements.
- Sequential access: Elements are accessed linearly; random access is O(n) time.
- Variable memory overhead: Each node carries the extra storage for at least one pointer.
- Types: Singly linked lists have only a next pointer; doubly linked lists also have a previous pointer; circular linked lists connect the last node back to the first.
History
The linked list was introduced in the 1950s by Allen Newell, Cliff Shaw, and Herbert A. Simon as part of their work on the Information Processing Language (IPL), an early symbolic programming language. IPL used lists as the primary data structure for artificial intelligence research. The concept was later refined and implemented in Lisp, which made lists a fundamental data type. Since then, linked lists have become a standard topic in computer science curricula and are widely used in operating systems, memory management, and graph representations.