Linked Lists
Linked lists are fundamental data structures that store elements in a sequence, where each element points to the next. Unlike arrays, linked lists do not require contiguous memory — nodes can reside anywhere in memory and are connected through pointers. This makes them especially useful when the collection size changes frequently and predictable memory layout is not required.
What Is a Linked List?#
A linked list is a linear data structure where elements (called nodes) are connected through pointers. Each node stores two things: the data it holds, and a pointer (reference) to the next node in the sequence. The first node is called the head; the last node's pointer is set to null, marking the end of the list.
Key Characteristics#
| Property | Description |
|---|---|
| Dynamic Size | Can grow or shrink at runtime without reallocation |
| Non-Contiguous Memory | Nodes can be stored anywhere in memory |
| Pointer-Based | Each node contains a reference to the next node |
| Sequential Access | Must traverse from head to reach any element |
| Efficient Insertion/Deletion | O(1) at the head; O(1) anywhere if you already hold a reference to the target node |
Node Structure#
The building block of a linked list is the node. Each node contains two fields: the data it holds, and a next pointer that references the following node. When next is null (or None in Python), the node is the last one in the list.
Node Implementation
The basic building block of a linked list
Types of Linked Lists#
There are three main variants of linked lists. Each has distinct structural properties that make it better suited to certain problems.
| Type | Description | Traversal | Use Cases |
|---|---|---|---|
| Singly Linked | Each node points to next only | Forward only | Stacks, simple lists |
| Doubly Linked | Each node points to prev and next | Both directions | Browser history, undo/redo |
| Circular | Last node points back to first | Continuous loop | Round-robin scheduling |
Arrays vs Linked Lists#
Choosing between an array and a linked list is one of the most common trade-off decisions in data structure design. The key difference is how they store data in memory: arrays use a single contiguous block, while linked list nodes can be scattered anywhere.
| Operation | Array | Linked List | Winner |
|---|---|---|---|
| Access by index | O(1) | O(n) | Array |
| Search | O(n) | O(n) | Tie |
| Insert at beginning | O(n) | O(1) | Linked List |
| Insert at end | O(1)* | O(n) or O(1)** | Depends |
| Insert in middle | O(n) | O(n)* | Linked List* |
| Delete at beginning | O(n) | O(1) | Linked List |
| Delete at end | O(1) | O(n) or O(1)** | Depends |
| Memory usage | Less (no pointers) | More (pointers) | Array |
| Cache performance | Better (contiguous) | Worse (scattered) | Array |
* Amortized for dynamic arrays. ** O(1) with tail pointer. *** Both structures require O(n) to traverse to the position. The linked list advantage is that the insertion itself is O(1) — only two pointers change. Arrays must shift all subsequent elements, adding constant-factor overhead.
Basic Operations#
The table below summarizes the core operations on a singly linked list and their time complexities. Note that complexities marked with * or ** can be improved with extra bookkeeping (a tail pointer or a cached length).
| Operation | Description | Time Complexity |
|---|---|---|
| Traverse | Visit each node from head to tail | O(n) |
| Insert at Head | Add new node at the beginning | O(1) |
| Insert at Tail | Add new node at the end | O(n)* |
| Insert at Position | Add new node at specific index | O(n) |
| Delete at Head | Remove the first node | O(1) |
| Delete at Tail | Remove the last node | O(n) |
| Delete by Value | Remove node with specific value | O(n) |
| Search | Find node with specific value | O(n) |
| Get Length | Count number of nodes | O(n)** |
* O(1) with tail pointer. ** O(1) if length is cached.
When to Use Linked Lists#
Not every problem calls for a linked list. Use the table below as a decision guide — and remember that in most high-level languages, the built-in array or list type is a dynamic array, not a linked list.
| Scenario | Use Linked List? | Reason |
|---|---|---|
| Frequent insertions/deletions at beginning | Yes | O(1) vs O(n) for arrays |
| Unknown size, frequent size changes | Yes | No reallocation needed |
| Need to access elements by index | No | Arrays have O(1) access |
| Memory is limited | No | Linked lists have pointer overhead |
| Implementing stacks | Yes | O(1) push/pop at head |
| Implementing queues | Yes | O(1) with head and tail pointers |
| Cache-sensitive applications | No | Arrays have better cache locality |
| Need to iterate frequently | Depends | Arrays slightly faster due to cache |
Better Alternatives#
In practice, a linked list is often not the best tool even when its theoretical properties seem attractive. Here are common alternatives worth considering first:
| If You Need... | Consider Using |
|---|---|
| Fast index access + dynamic size | Dynamic Array (Python list, JavaScript array) |
| Fast insertion at both ends | Deque (double-ended queue) |
| Fast lookup by value | Hash Set or Hash Map |
| Sorted data with fast search | Balanced BST or Sorted Array |
Reviewing AI-Generated Code#
Linked list bugs are subtle and silent. A single pointer assigned in the wrong order can orphan the rest of the list — no error is thrown, but data disappears. When reviewing AI-generated linked list code, pay close attention to these common failure points:
| Issue | What to Check | Common AI Mistake |
|---|---|---|
| Null checks | Check node before accessing .next | Accessing node.next when node is None |
| Pointer updates | Order of pointer changes | Losing reference to rest of list |
| Edge cases | Empty list, single node | Not handling empty list case |
| Memory leaks | Orphaned nodes (in C/C++) | Not freeing deleted nodes |
| Loop termination | Correct stopping condition | Off-by-one errors in traversal |
Spotting AI Linked List Bugs
Common pointer manipulation errors in AI-generated code
Questions to Ask AI About Linked List Code#
When in doubt about AI-generated linked list code, prompt the AI with these targeted questions:
- "What happens with an empty list?" — The head is
null; code must check before dereferencing. - "What happens with a single-node list?" — An edge case that frequently exposes off-by-one errors.
- "Are pointer updates applied in the correct order?" — Updating in the wrong sequence silently drops nodes or creates a self-loop.
- "Does this code create a cycle?" — Verify that no node's
nextpointer accidentally points back to an earlier node.
Summary#
| Concept | Key Takeaway |
|---|---|
| Linked List | Sequential nodes connected by pointers |
| Node | Contains data and reference to next node |
| Singly Linked | One-way traversal, simpler structure |
| Doubly Linked | Two-way traversal, more flexible |
| Circular | No null end, continuous loop |
| vs Arrays | Better for insertions, worse for random access |
| Trade-offs | Memory overhead vs insertion efficiency |
Linked lists form the conceptual foundation for more advanced structures like trees, graphs, and hash tables. Understanding how nodes connect through pointers — and how easily those connections can go wrong — is a skill that applies far beyond linked lists themselves. Next, let's explore each variant in more detail.