🔍

Intuition

▶

Real-life analogy

🚂

Train cars: each car (node) holds cargo (data) and is connected to the next car (pointer). You must walk car-by-car from the engine (head) to reach any car. You can't jump directly to car #5.

🔗

Chain links: each link holds data and knows only the next link. Removing a link? Just re-connect the neighbours.

📌

Scavenger hunt: the first clue (head) tells you where to find the next. Each clue leads to the next, until a clue says "done!" (None).

Linked List vs Array — when to choose

Feature	Array / List	Linked List
Access by index	O(1) — direct	O(n) — must traverse
Insert at head	O(n) — shift all	O(1) — rewire head
Insert at tail	O(1) amortised	O(n) (singly) / O(1) (with tail ptr)
Delete from head	O(n)	O(1)
Memory	Contiguous block	Scattered — each node anywhere
Dynamic resize	Expensive realloc	Free — add node anywhere

Use linked lists when inserts/deletes at the front are frequent, or when size is highly dynamic (e.g., LRU cache, undo history, queue/deque).

📘

Definitions

▶

Node

A node is the basic unit of a linked list. It contains two things:

data — the value stored (int, string, object, anything)
next — a reference (pointer) to the next node, or None if last

head

10

next →

→

20

next →

→

tail

30

next →

→

None

Types of Linked Lists

Singly Each node points to only the next node. Traversal: one direction only.

A

→

B

→

C

→

None

Doubly Each node has prev + next pointers. Can traverse both ways.

None ← [A] ⇄ [B] ⇄ [C] → None

Circular Tail's next points back to head. No None terminator.

[A] → [B] → [C] → back to [A]

Head & Tail

head — reference to the first node. Entry point to the list. If head is None, the list is empty.
tail — reference to the last node. Its next is always None (singly). Maintained explicitly for O(1) appends.

🧠

Core Concepts

▶

Dynamic memory & references

Python manages memory automatically. A node object lives in the heap. The variable holding it is just a reference (pointer) — a label that says "look over here". Reassigning a reference does not move the node, it just changes where the label points.

Key mental model: current = current.next means "move the label to the next node", not "move the node".

Traversal pattern (the cursor loop)

# canonical traversal — O(n)
current = self.head          # start at head
while current is not None:
    print(current.data)      # do something
    current = current.next   # advance cursor

Think of current as a flashlight scanning the chain. When it hits None, you've reached the end.

⚙️

CRUD Operations — Interactive Step-by-Step

▶

Create

Read

Update

Delete

Create — Insert at head O(1)

def prepend(self, data):
    new_node = Node(data)        # 1. create node
    new_node.next = self.head    # 2. point new → old head
    self.head = new_node         # 3. head = new node

Press "Next step" to walk through prepend(5) on list [10→20→30]

0 / 4

Create — Append at tail O(n) / O(1) with tail ptr

def append(self, data):
    new_node = Node(data)
    if not self.head:
        self.head = new_node; return
    current = self.head
    while current.next:        # walk to last node
        current = current.next
    current.next = new_node   # attach at end

Create — Insert after given node O(n) to find, O(1) to insert

def insert_after(self, target_data, data):
    current = self.head
    while current and current.data != target_data:
        current = current.next
    if current:
        new_node = Node(data)
        new_node.next = current.next  # new → current's next
        current.next = new_node       # current → new

Read — Traverse (print all) O(n)

def display(self):
    current = self.head
    while current:
        print(current.data, end=" → ")
        current = current.next
    print("None")

Read — Search by value O(n)

def search(self, target):
    current = self.head
    position = 0
    while current:
        if current.data == target:
            return position    # found!
        current = current.next
        position += 1
    return -1               # not found

Press "Next step" to walk through search(20) on [10→20→30]

0 / 4

Update — Modify node value O(n)

def update(self, old_val, new_val):
    current = self.head
    while current:
        if current.data == old_val:
            current.data = new_val  # in-place update
            return True
        current = current.next
    return False                # not found

💡

Update never rewires pointers — only the data field changes. Pointers stay identical. This means update is "safe" — no risk of losing nodes.

Delete — Three cases

Case 1: Delete head — just move head forward

Case 2: Delete tail — traverse to second-last, set its next = None

Case 3: Delete middle — prev.next = current.next (bypass)

def delete(self, target):
    if not self.head: return          # empty list
    if self.head.data == target:      # case 1: head
        self.head = self.head.next
        return
    prev, current = None, self.head
    while current:
        if current.data == target:
            prev.next = current.next  # bypass node
            return
        prev = current
        current = current.next

Press "Next step" to walk through delete(20) on [10→20→30]

0 / 5

Never lose the prev pointer before bypassing. Losing track of prev means you can't reconnect the chain — nodes get orphaned in memory.

🐍

Full Python Implementation

▶

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None     # pointer to next node

class LinkedList:
    def __init__(self):
        self.head = None     # empty list

    # ── CREATE ───────────────────────────────
    def prepend(self, data):          # O(1)
        node = Node(data)
        node.next = self.head
        self.head = node

    def append(self, data):           # O(n)
        node = Node(data)
        if not self.head:
            self.head = node; return
        cur = self.head
        while cur.next: cur = cur.next
        cur.next = node

    # ── READ ─────────────────────────────────
    def display(self):                # O(n)
        cur, res = self.head, []
        while cur:
            res.append(str(cur.data))
            cur = cur.next
        print(" → ".join(res) + " → None")

    def search(self, target):         # O(n)
        cur, i = self.head, 0
        while cur:
            if cur.data == target: return i
            cur, i = cur.next, i + 1
        return -1

    # ── UPDATE ───────────────────────────────
    def update(self, old, new):       # O(n)
        cur = self.head
        while cur:
            if cur.data == old:
                cur.data = new; return True
            cur = cur.next
        return False

    # ── DELETE ───────────────────────────────
    def delete(self, target):         # O(n)
        if not self.head: return
        if self.head.data == target:
            self.head = self.head.next; return
        prev, cur = None, self.head
        while cur:
            if cur.data == target:
                prev.next = cur.next; return
            prev, cur = cur, cur.next

# ── USAGE ────────────────────────────────────
ll = LinkedList()
ll.append(10); ll.append(20); ll.append(30)
ll.prepend(5)
ll.display()           # 5 → 10 → 20 → 30 → None
print(ll.search(20))   # 2
ll.update(20, 99)
ll.delete(10)
ll.display()           # 5 → 99 → 30 → None

⚡

Complexity Table

▶

Operation	Time	Space	Notes
Prepend (insert head)	O(1)	O(1)	Just rewire head pointer
Append (insert tail)	O(n)	O(1)	O(1) if tail pointer maintained
Insert after node	O(n)	O(1)	O(n) to find, O(1) to link
Access by index	O(n)	O(1)	No random access — must traverse
Search by value	O(n)	O(1)	Linear scan
Update value	O(n)	O(1)	Find then mutate data field
Delete head	O(1)	O(1)	Move head pointer forward
Delete tail / middle	O(n)	O(1)	Must find predecessor
Reverse (iterative)	O(n)	O(1)	Three-pointer technique
Detect cycle (Floyd's)	O(n)	O(1)	Fast + slow pointer

🧩

Patterns & Use Cases

▶

Reverse a linked list (iterative) O(n) time, O(1) space

def reverse(self):
    prev, current = None, self.head
    while current:
        nxt = current.next      # save next
        current.next = prev     # flip pointer
        prev = current          # advance prev
        current = nxt           # advance current
    self.head = prev            # new head

Before: [1]→[2]→[3]→None | After: [3]→[2]→[1]→None

Three variables: prev, current, nxt. Never lose nxt before flipping!

Detect a cycle — Floyd's algorithm O(n) time, O(1) space

def has_cycle(self):
    slow = fast = self.head
    while fast and fast.next:
        slow = slow.next         # 1 step
        fast = fast.next.next    # 2 steps
        if slow == fast:
            return True          # cycle!
    return False

🏃

Imagine two runners on a circular track. The faster one eventually laps the slower one — they meet. If there's no cycle, the fast runner just falls off the end (hits None).

Common use cases

Undo/Redo — each action is a node; undo = move head back
LRU Cache — doubly linked list + hash map
Browser history — doubly LL for back/forward
Queue / Deque — O(1) enqueue at tail, O(1) dequeue at head
Polynomial arithmetic — each term is a node

💻

Dry Runs

▶

Dry run: delete(20) on [10→20→30]

1

Is head None? No. Is head.data (10) == 20? No. Continue.

head/prev=None / cur

10

→

20

→

30

→

None

2

prev = node(10), current = node(20). Is current.data (20) == 20? YES!

→

current (target)

20
→

→

30

→

None

3

Execute: prev.next = current.next → node(10).next = node(30). Node(20) is bypassed.

head

10

→

→→

30

→

None

20

✕

4

Result: [10 → 30 → None]. Node 20 has no references, Python GC will reclaim it.

🧠

Concept Checks

▶

🧪

Practice Problems

▶

🚀

Interview Tips

▶

Common mistakes

Losing the reference: Always save nxt = current.next before modifying current.next. One wrong assignment and you orphan half your list.

Null/None handling: Always check if not self.head before any operation. Forgetting this causes AttributeError on empty lists.

Off-by-one in traversal: To reach the last node, stop when current.next is None, not when current is None.

Forgetting to update head: When deleting head or reversing, explicitly reassign self.head. It doesn't move itself.

Interview best practices

Draw the list before writing code — interviewers love visual thinkers
Always ask: singly or doubly? size constraints? what if empty?
Use two-pointer technique for cycle detection, finding middle, nth-from-end
For in-place reversal, articulate the three-pointer setup clearly
Mention time + space complexity unprompted — shows awareness
Edge cases to always mention: empty list, single node, duplicate values, cycle

Linked Lists & Nodes

Linked Lists in Python — Interactive Notes

Intuition

Real-life analogy

Linked List vs Array — when to choose

Definitions

Node

Types of Linked Lists

Head & Tail

Core Concepts

Dynamic memory & references

Traversal pattern (the cursor loop)

CRUD Operations — Interactive Step-by-Step

Create — Insert at head O(1)

Create — Append at tail O(n) / O(1) with tail ptr

Create — Insert after given node O(n) to find, O(1) to insert

Read — Traverse (print all) O(n)

Read — Search by value O(n)

Update — Modify node value O(n)

Delete — Three cases

Full Python Implementation

Complexity Table

Patterns & Use Cases

Reverse a linked list (iterative) O(n) time, O(1) space

Detect a cycle — Floyd's algorithm O(n) time, O(1) space

Common use cases

Dry Runs

Dry run: delete(20) on [10→20→30]

Concept Checks

Practice Problems

Interview Tips

Common mistakes

Interview best practices