Linked List
A linked list is a linear data structure in which elements, called nodes, are stored in separate memory locations and connected through pointers. Each node...
Dynamic Node-Based Storage with Pointer-Linked Elements
A linked list is a linear data structure in which elements, called nodes, are stored in separate memory locations and connected through pointers. Each node contains two parts: a data field holding the element's value and a next pointer holding the memory address of the next node in the sequence. The last node's next pointer is set to null to mark the end of the list.
Unlike arrays, linked list nodes do not need to occupy contiguous memory. The operating system allocates each node wherever free memory is available, and the pointer chain connects them logically. This means a linked list never needs to be resized or copied to accommodate new elements; inserting a node is as simple as adjusting two pointers.
The primary advantage of linked lists is efficient insertion and deletion at any known position. Given a pointer to the node before the insertion point, inserting a new node requires only two pointer changes: new_node.next equals current.next, then current.next equals new_node. Both operations are O(1). Similarly, deleting a node requires setting the previous node's next pointer to skip over the deleted node, also O(1). This contrasts sharply with arrays, where insertion or deletion in the middle costs O(n) due to element shifting.
The primary disadvantage is the absence of random access. To reach the k-th element, you must start at the head and follow next pointers k times. This traversal is O(k), and in the worst case O(n). There is no index arithmetic shortcut. For workloads that require frequent random access, arrays are superior.
Linked lists also consume more memory per element than arrays because each node stores a data value plus a pointer (typically eight bytes on 64-bit systems). For small data types like bytes, the pointer overhead can double or triple the memory footprint compared to an array.
There are three main variants: singly linked lists where each node has only a next pointer, doubly linked lists where each node has both next and previous pointers, and circular linked lists where the last node points back to the first rather than to null. Each variant suits different use cases.
Worked example: implementing an undo stack in a text editor. Each edit is pushed onto the head of a linked list in O(1). Undo pops from the head in O(1). If the number of edits is unbounded, a linked list avoids the resizing cost of a fixed array.
Interview tip: many linked list problems are solved by carefully managing two or three pointers simultaneously. Practice problems like reversing a list, finding the middle, and merging sorted lists until pointer manipulation feels natural.