Linked Lists

EasyData Structures

Pointer manipulation mastery. Google loves linked list problems because they test careful thinking about references and edge cases. Learn reversal, cycle detection with Floyd's algorithm, and merge patterns.

AVG TIME

O(n)

SPACE

O(1)

BEST

O(1)

WORST

O(n)

Step-by-Step Walkthrough

step-by-step walkthrough

Linked List Reversal

1 / 8

algorithm.py

1def reverse_linked_list(head):

2 prev = None

3 curr = head

5 while curr is not None:

6 next_node = curr.next

7 curr.next = prev

8 prev = curr

9 curr = next_node

11 return prev

visualization

linked list

None

curr

→

variable inspectorO(1) setup

prev=None

curr=1 (head)

next_node=None

The Starting List

We have a linked list: 1 -> 2 -> 3 -> 4 -> 5 -> None. We want to make it: 5 -> 4 -> 3 -> 2 -> 1 -> None. We'll use three pointers: prev, curr, and next_node.

speedmed

← →space

In Python

Concept to Code- 1 structure for this topic

declare

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

common ops

curr = curr.next

O(n)

node.next = new_node

O(1)

node.next = node.next.next

O(1)

say in interview

"I'll define a ListNode class (interviewers usually provide this)"

Python has no built-in linked list. You always define the node class. Google usually provides it in the problem.

Math You Need For This

A chain of paper clips. To find clip number 50, you count through 50 clips one by one. But to add a clip in the middle, you just unhook one link and reattach.

Required concepts

Key math ideas

1 / 3

Linear growth - O(n)

If you have 10 items to check, you do 10 steps. 1,000 items? 1,000 steps. The work grows at exactly the same rate as the input.

Visual: A straight diagonal line on a graph. Double the input, double the time. No surprises.

Think of it this way: Reading every page of a book. If the book is twice as long, it takes twice as long to read.

For algorithms: O(n) is usually the target for one-pass algorithms like simple array traversals.

Interactive 3D Visualization

Linked List
Access: O(n)Insert head: O(1)Space: O(n)
Drag to orbit  -  Scroll to zoom

Brute Force vs Optimized

Interview Strategy - Detect Cycle in Linked List

Start brute force, explain it, THEN optimize. "I can see a straightforward approach. Let me start there, then we can optimize."

Brute Force

Hash Set - Track Visited

TimeO(n)

SpaceO(n)

"Store every visited node in a set. If we see a node twice, there is a cycle."

Pros

+Easy to understand
+Works on first try

Cons

-Uses O(n) extra space for the set

Optimized

Floyd's Tortoise and Hare

TimeO(n)

SpaceO(1)

"Two pointers at different speeds. If they meet, there is a cycle."

Pros

+O(1) space - no extra memory at all
+Elegant - shows deep understanding
+Google loves this

Cons

-Harder to understand why it works
-Need to prove correctness

The Tradeoff

Same time complexity, but the optimized version uses O(1) space instead of O(n). This matters when the list has millions of nodes.

For n=1,000

Brute Force1,000 ops

Optimized1,000 ops

Say This

Say: "I can detect the cycle with a hash set in O(n) time and space. But we can do O(1) space using the fast/slow pointer technique."

Watch It Run

Reverse a Linked List

Three pointers dance through, reversing arrows in-place.

SPEED

1 / 8

Your data

Values:

algorithm.py

1>def reverse_list(head):

2 prev = None

3 current = head

4 while current:

5 next_node = currentnext

6 currentnext = prev

7 prev = current

8 current = next_node

9 return prev

pointers visualization

1

-

2

-

3

-

4

-None

We're reversing the linked list: 1 -> 2 -> 3 -> 4 -> None. After reversal it should be 4 -> 3 -> 2 -> 1 -> None. The trick: do this in-place with only O(1) extra space.

VariablesStep 1 of 9 (setup)

head=1->2->3->4

Spaceplay/pause← →step+ -speed

Interactive Playground

Experiment hands-on before writing a single line in the practice editor. Try different inputs and watch the structure behave.

interactive sandbox

Data Structure Playground

HEAD

→

→ NULL

Click to select (then insert after) - Double-click to delete

Open full-screen playground

Python Implementation

example.py

Now try it yourself

2 challenges with test cases and AI feedback

Practice Now

Complexity Analysis

COMMON OPERATIONS

Array

Access:O(1)

Search:O(n)

Insert end:O(1)*

Insert mid:O(n)

Hash Map

Get/Set:O(1)*

Delete:O(1)*

Search value:O(n)

Iterate:O(n)

Linked List

Access:O(n)

Search:O(n)

Insert head:O(1)

Delete known:O(1)

Binary Search

Search:O(log n)

Insert:O(log n)

Balanced BST

Search:O(log n)

Insert:O(log n)

Delete:O(log n)

Heap

Peek min/max:O(1)

Push:O(log n)

Pop:O(log n)

Heapify:O(n)

Graph (BFS/DFS)

Traversal:O(V+E)

Dijkstra (heap):O((V+E) log V)

Merge / Quick Sort

Sort:O(n log n)

Space (merge):O(n)

Space (quick):O(log n)

* amortized average case

READY TO TEST YOURSELF?

Put Linked Lists into practice

The best way to lock in what you've learned is to write code. Solve real interview-style problems right now.

Next: Stacks & Queues

Linked Lists

Next: Stacks & Queues