Linked List
Subject: Computer and Technology noun /ˌlɪŋkt ˈlɪst/ 1 definition
- data-structures
- computer-science
- memory-management
- algorithms
-
Definition (noun)
Entry #42 · UpdatedA Linked List is a linear data structure composed of sequentially connected elements called nodes, where each node stores a data payload alongside one or more pointers or references linking it to adjacent nodes. Unlike contiguous arrays that require a single unbroken block of memory for index-based random access, a linked list can store nodes at arbitrary memory addresses and grow or shrink dynamically without reallocating or shifting existing elements. This pointer-based structure supports constant-time (
O(1)) insertions and deletions once a target node position is reached, while trading offO(n)sequential traversal instead of direct indexed lookup and adding per-element memory overhead for link fields.Common Types
Singly Linked List: Stores only a
nextreference in each node for one-way traversal from head to anull-terminated tail, minimizing per-node memory overhead for stacks and FIFO queues.Doubly Linked List: Maintains both
prevandnextreferences in every node, enabling bidirectional traversal and constant-time removal of a referenced node without scanning for its predecessor.Circular Linked List: Connects the tail node back to the head node instead of terminating at
null(in either singly or doubly linked layouts), forming a continuous ring suited to round-robin schedulers and cyclic buffers.Skip List: Layers multiple forward-pointing linked lists of exponentially decreasing density above a sorted base list, achieving
O(log n)average search and insertion time without complex tree rebalancing.
Example
A music streaming app stores its editable "Up Next" playlist as a doubly linked list in which each node holds a track ID alongside
prevandnextpointers to adjacent songs. When a listener removes the third queued track or inserts a newly selected song immediately after the currently playing node, the app reassigns only the neighboring nodes' pointers inO(1)time rather than shifting subsequent tracks in a contiguous array.