What Is a Linked List?
A linked list is a sequence of nodes where each node stores a value and a pointer to the next node. Unlike arrays, nodes are not stored in contiguous memory — each one can live anywhere in the heap. You traverse the list by following pointers from one node to the next.
With an array, you can jump to any element by index in O(1). With a linked list, you must walk from the head node to reach element k — that's O(k). But inserting or deleting at the head is O(1) because you only update one pointer, no shifting required.
Each node has two fields:
val— the data stored in the nodenext— a reference (pointer) to the next node, orNoneif it's the last node
Visual: Linked List Structure
A singly linked list with three nodes. Each box is a node; the arrow is the next pointer. The last node points to None.
Singly Linked List: 1 → 2 → 3 → None
Inserting at the Head — O(1)
New node's next points to old head, then update head pointer.
Node Class & Traversal
The ListNode class is the building block. Each node stores val and next. Traversal means walking from head to the end, following next pointers until you hit None.
head. Print the value. Move to current.next. Repeat until current is None. This is O(n) — you visit every node exactly once.
Insert & Delete Operations
Linked list operations revolve around pointer manipulation. The key is to update next pointers in the right order — otherwise you lose references to nodes.
Insert at head — O(1)
Insert at tail — O(n)
Delete by value — O(n)
head.val == val, just return head.next. Using a "dummy node" before the head avoids this edge case entirely — you'll see this pattern in the merge problem later.
Big O: Linked List vs Array
When should you pick a linked list over an array? This table shows where each data structure wins.
| Operation | Array (Python list) | Linked List |
|---|---|---|
| Access by index | O(1) | O(n) |
| Search by value | O(n) | O(n) |
| Insert at head | O(n) | O(1) |
| Insert at tail | O(1) amortized | O(n)* |
| Delete at head | O(n) | O(1) |
| Delete at tail | O(1) | O(n) |
*With a tail pointer, insert at tail becomes O(1). But singly linked lists typically don't maintain one.
Problem: Reverse a Linked List
This is the single most common linked list interview question. You'll see it at every company. The iterative approach uses three pointers: prev, curr, and next_node.
Idea: Walk through the list. At each step, reverse the current node's pointer to point backward instead of forward. When you reach the end, prev is the new head.
Pointer Movements — Reversing 1 → 2 → 3
curr.next before overwriting it, otherwise you lose the rest of the list.
Problem: Detect Cycle (Floyd's Algorithm)
Given a linked list, determine if it contains a cycle — that is, some node's next points back to an earlier node, creating an infinite loop.
Floyd's Tortoise and Hare: Use two pointers. The slow pointer moves one step at a time; the fast pointer moves two steps. If there's a cycle, they will eventually meet. If there's no cycle, the fast pointer hits None.
Cycle Detection — Fast & Slow Pointers
Node 5's next points to node 3, creating a cycle. Slow and fast will meet inside the loop.
Problem: Merge Two Sorted Lists
Given two sorted linked lists, merge them into one sorted list by splicing nodes together. This is LeetCode 21 — another essential interview problem.
Strategy: Use a dummy node to simplify the code. Compare the heads of both lists, attach the smaller one to the result, and advance that pointer. When one list runs out, attach the rest of the other.
curr.next and return dummy.next at the end. This pattern appears in many linked list problems — it eliminates edge cases for empty lists and first-node selection.
Try It Yourself
Reverse a Linked List — Write Your Solution
Implement reverse_list(head) using the iterative 3-pointer approach. The function should return the new head of the reversed list.
Challenge
Write a function find_middle(head) that returns the middle node of a linked list. If the list has an even number of nodes, return the second of the two middle nodes.
Example: For 1 → 2 → 3 → 4 → 5, return the node with value 3. For 1 → 2 → 3 → 4, return the node with value 3.
Constraint: Solve it in one pass (O(n) time, O(1) space) without counting the length first.
slow one step and fast two steps. When fast reaches the end, slow is at the middle. The loop condition is while fast and fast.next.Quiz
curr.next before reversing the pointer?You've mastered linked lists.
Now ace the full interview.
Join the Best AI Programs — three 5-month courses, fully online, with placement assistance. Week 1 is free.
Explore our AI-era courses →