Linked Lists - Chains of Connected Nodes

A Linked List is a linear data structure where elements — called nodes — are not stored in contiguous memory. Instead, each node holds its value and a pointer to the next node, forming a chain. This deceptively simple idea unlocks dynamic sizing and $O(1)$ insertion and deletion at known positions — trade-offs that arrays cannot match.

A Brief History

Linked lists were developed in the late 1950s at RAND Corporation by Allen Newell, Cliff Shaw, and Herbert Simon as the internal data structure for their groundbreaking AI program IPL (Information Processing Language). The concept of chaining memory cells with pointers was radical at the time — memory was precious and fixed-size allocation was the norm. The linked list idea proved so fundamental that it became a core concept in the design of early programming languages, including Lisp, which built its entire evaluation model on cons cells (essentially linked list nodes). John McCarthy, Lisp’s creator, credited linked lists as central to the language’s power.

Singly vs Doubly Linked Lists

There are two main variants:

Singly Linked List: Each node has a value and one pointer (next) pointing to the next node. The last node’s next is null. You can only traverse forward.

Doubly Linked List: Each node has a value, a next pointer, and a prev pointer. You can traverse in both directions. This enables $O(1)$ deletion of a node when you have a direct reference to it — something singly linked lists can’t do without knowing the previous node.

Core Operations and Their Complexity

Operation	Singly	Doubly	Notes
Access by index	$O(n)$	$O(n)$	Must traverse from head
Search	$O(n)$	$O(n)$	No random access
Insert at head	$O(1)$	$O(1)$	Update head pointer
Insert at tail	$O(1)$ with tail pointer	$O(1)$	—
Insert in middle	$O(n)$	$O(n)$	Finding position costs $O(n)$
Delete at head	$O(1)$	$O(1)$	—
Delete known node	$O(n)$	$O(1)$	Singly needs the previous node

Space Complexity

Linked lists use $O(n)$ space for $n$ nodes. However, each node carries overhead beyond just its value — the pointer(s). A singly linked list node storing a 64-bit integer also needs one 64-bit pointer: 2× the raw data size. A doubly linked list needs two pointers: 3×. This memory overhead is often the hidden cost that makes arrays more efficient in practice for small, fixed-size data.

Advantages and Disadvantages

Advantages:

• Dynamic size — grows and shrinks without declaring capacity upfront (unlike arrays)
• $O(1)$ insertion and deletion at the head (or anywhere if you have a direct node reference in doubly linked lists)
• No memory waste from pre-allocation — nodes are allocated exactly as needed
• Natural building block for stacks, queues, and more complex structures

Disadvantages:

• No random access — reaching the $k$-th element costs $O(k)$, unlike arrays’ $O(1)$
• Extra memory per node for the pointer(s)
• Poor cache performance — nodes are scattered across memory, causing frequent cache misses. Arrays store elements contiguously, so sequential access is cache-friendly
• No built-in index — searching always requires linear traversal

When to Use a Linked List

Linked lists earn their place when:

• Frequent insertion/deletion at the head or tail — implementing stacks and queues efficiently
• Unknown or highly variable size — when you can’t predict how many elements you’ll have
• You need $O(1)$ deletion of an arbitrary node — in a doubly linked list, if you hold a reference to a node, removing it is $O(1)$ (pointer surgery with no shifting)
• Implementing an LRU cache — a doubly linked list paired with a hash map gives $O(1)$ eviction

Prefer an array when:

• You need fast indexed access (arr[i] in $O(1)$)
• Cache performance matters (sequential access patterns)
• Your data is fixed-size or rarely inserted/deleted in the middle

In JavaScript, there’s no built-in linked list. Arrays ([]) handle most cases well because V8 optimizes them aggressively. A linked list is worth implementing explicitly only when the algorithmic trade-offs genuinely apply — usually in interview problems or specialized data structure implementations like LRU caches.

In conclusion, linked lists are a cornerstone of computer science because they introduced the idea of dynamic, pointer-based data organization. Master the pointer mechanics — insertion, deletion, reversal — and you’ll find linked lists appearing inside more complex structures everywhere: hash tables, adjacency lists, memory allocators, and operating system kernels.