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.

🔗
Key difference from arrays
No index access, but O(1) insert at head

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 node
  • next — a reference (pointer) to the next node, or None if 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

1
valnext →
→
2
valnext →
→
3
valnext →
→
None

Inserting at the Head — O(1)

New node's next points to old head, then update head pointer.

0
newnext →
→
1
valnext →
→
2
valnext →
→
3
valnext →
→
None

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.

linked_list_basics.py Node class + traversal
Output
1 -> 2 -> 3 -> None
How traversal works:
Start at 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_head.py O(1) — just update one pointer
Output
0 -> 1 -> 2 -> 3 -> None

Insert at tail — O(n)

insert_tail.py O(n) — must walk to the end
Output
1 -> 2 -> 3 -> 4 -> None

Delete by value — O(n)

delete_node.py O(n) — find the node, then re-link
Output
1 -> 2 -> 4 -> None
Common bug:
When deleting the head node, many people forget to handle that case separately. If 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.

Interview insight:
In practice, arrays (Python lists) are almost always faster due to CPU cache locality — elements sit next to each other in memory. Linked lists shine in theory when you need frequent inserts/deletes at the head, or when you can't afford O(n) shifts.

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

Step 1: Start — prev=None, curr=1
None
←
1
→
2
→
3
→
None
Step 2: Reverse 1's pointer — prev=1, curr=2
1
←
2
→
3
→
None
Step 3: Reverse 2's pointer — prev=2, curr=3
1
←
2
←
3
→
None
Step 4: Reverse 3's pointer — prev=3 (new head!), curr=None
None
←
1
←
2
←
3
prev
curr
next_node
reverse_list.py O(n) time, O(1) space
Output
Before: 1 -> 2 -> 3 -> 4 -> 5 -> None After: 5 -> 4 -> 3 -> 2 -> 1 -> None
The 4-line core:
Save next, reverse pointer, advance prev, advance curr. Memorize this pattern — it appears in dozens of linked list problems. The key insight is that you must save 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

1
→
2
→
3
→
4
→
5
↩ back to 3

Node 5's next points to node 3, creating a cycle. Slow and fast will meet inside the loop.

has_cycle.py O(n) time, O(1) space
Output
Has cycle: False Has cycle: True
Why does this work?
Think of it like two runners on a circular track. The fast runner laps the slow runner eventually. Mathematically, once both pointers are inside the cycle, the gap between them decreases by 1 each step, so they must meet within one full loop. O(n) time, O(1) space — no hash set needed.

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.

merge_sorted.py O(n + m) time, O(1) space
Output
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> None
The dummy node trick:
Without a dummy, you'd need special logic to set the head of the merged list. With a dummy, you always append to 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

Find the Middle of a Linked List
Your task:

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.

Use the same fast/slow pointer technique from Floyd's algorithm. Move 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

Question 1 of 5
What is the time complexity of accessing the k-th element in a singly linked list?
Question 2 of 5
In the iterative reverse algorithm, why must you save curr.next before reversing the pointer?
Question 3 of 5
How does Floyd's cycle detection algorithm work?
Question 4 of 5
What is the purpose of the "dummy node" in the merge two sorted lists solution?
Question 5 of 5
What advantage does a linked list have over a Python list (array) for insertions?
0
/5
Great work! You understand linked lists.
Africa & India's Best AI Academy
🤖 AI-first 🎓 Placement Assistance

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 →