Skip to main content
Definition Website Computer and Technology

Linked List

Subject: Computer and Technology noun /ˌlɪŋkt ˈlɪst/ 1 definition

  1. Definition (noun)

    Entry #42 · Updated

    A 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 off O(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 next reference in each node for one-way traversal from head to a null-terminated tail, minimizing per-node memory overhead for stacks and FIFO queues.

    • Doubly Linked List: Maintains both prev and next references 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 prev and next pointers 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 in O(1) time rather than shifting subsequent tracks in a contiguous array.