RugvAI Labs

Linked Lists, Part 1: Singly Linked & Basics

Linked lists are LeetCode's bread and butter — "Reverse a Linked List" and "Detect Cycle" have been asked at Google more than 10,000 times. They're also how the Linux kernel manages process queues. Internally, Python's collections.deque is a doubly-linked list of arrays. Part 1 covers the singly linked foundation; Part 2 builds on it to cover doubly linked lists, merging, and LRU cache.

Learning Objectives

After this lesson, you will be able to:

Understand why linked lists exist and how they differ from arrays in memory layout
Build a complete singly linked list class with insert, delete, search, and in-place reverse
Apply the two-pointer (Floyd's) technique to detect cycles and find the middle node
Know exactly when to reach for a linked list versus Python's built-in list or deque

Prerequisites

Before You Start

Review

#Why Linked Lists? The Problem with Arrays

Why

Why This Matters

O(n) insertions at the front of a Python list force Python to shift every element one position to the right before placing the new value — for 1 million elements that is 1 million memory writes
O(1) front insertion with a linked list requires only updating two pointers regardless of list size — this is the core trade-off
Cache locality. Arrays win because their elements sit in contiguous memory (CPU cache loves sequential reads); linked list nodes are scattered across the heap
No pre-allocation needed. Linked lists grow dynamically with zero wasted capacity; arrays over-allocate to amortize resizing cost
The deque reality. Python's collections.deque is a doubly-linked list of fixed-size blocks, giving O(1) append and appendleft without any of the pointer-chasing penalty

#Memory Layout: Arrays vs Linked Lists

Picture a Python list [10, 20, 30, 40] in RAM:

Array (Contiguous Memory)

💾10 index 0

💾20 index 1

💾30 index 2

💾40 index 3

💾 storage

Linked List (Scattered in Memory)

💭10 addr: 0x1A4

💭20 addr: 0x3F8

💭30 addr: 0x2B0

💭40 | None addr: 0x5C2

💭 memory

Each node lives wherever Python's memory allocator decided to put it. To reach node at index i, you must follow the chain of pointers from the head — there is no direct address calculation.

#The Core Trade-Off

What You Gain	What You Lose
O(1) insert/delete at front or any known node	O(n) to access element at index i
No memory reallocation	Extra memory per node (the pointer itself)
Predictable insert/delete time (no shifting)	Poor cache performance (pointer chasing)

Linked List Visualizer — Build, Traverse & ReverseInteractive

Insert and delete nodes, watch pointers update, and step through Floyd's cycle detection. Every pointer operation is animated so you can see what the code is doing in memory.

Loading visualization...

What Do You Think?

You have a linked list: 1 → 2 → 3 → 4 → None. What is the time complexity of inserting a new node at index 2 (between 2 and 3)?

The answer is O(n). You must walk from the head to the node at index 1 before you can splice in the new node. The actual pointer update is O(1) — the traversal is what costs you.

#The Node Class: Foundation of Everything

Every linked list is built from individual Node objects that hold two things: a value and a reference to the next node.

pythonrunnable cell

class Node:
    def __init__(self, data):
        self.data = data        # The payload — any Python object
        self.next = None        # Reference to the next Node, or None

    def __repr__(self):
        return f"Node({self.data!r})"

The next attribute is just a normal Python variable that happens to hold either:

A reference to another Node instance (like any object reference in Python)
None — indicating this is the last node in the chain

Building a chain manually to see exactly what is happening:

pythonreference · read-only

# Create three nodes
a = Node(1)
b = Node(2)
c = Node(3)

# Wire them together with pointer assignments
a.next = b       # Node(1).next now points to Node(2)
b.next = c       # Node(2).next now points to Node(3)
c.next = None    # Node(3) is the tail (next is already None by default)

# Traverse: start at head, follow .next until None
current = a
while current is not None:
    print(current.data, end=" -> ")
    current = current.next
print("None")
# Output: 1 -> 2 -> 3 -> None

The chain in memory:

Three Nodes Wired Together

👤a (head)

💭Node a data: 1 | next

💭Node b data: 2 | next

💭Node c data: 3 | None

👤 user💭 memory

Loading visualization...

#Singly Linked List: Full Implementation

Here is a production-quality LinkedList class with every common operation explained line by line:

pythonrunnable cell

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

224

225

226

227

228

229

230

231

232

233

234

235

236

237

238

239

240

241

242

243

244

245

246

247

248

249

250

251

252

253

254

255

256

257

258

259

260

261

from __future__ import annotations
from typing import Any, Iterator, Optional


class Node:
    """A single node in a linked list."""

    def __init__(self, data: Any) -> None:
        self.data = data
        self.next: Optional[Node] = None

    def __repr__(self) -> str:
        return f"Node({self.data!r})"


class LinkedList:
    """
    Singly linked list with O(1) head/tail access.

    Maintains both a head pointer (front of list) and a tail pointer
    (end of list) so that append() is O(1) instead of O(n).
    """

    def __init__(self) -> None:
        self.head: Optional[Node] = None
        self._tail: Optional[Node] = None   # private tail pointer
        self._size: int = 0

    # ------------------------------------------------------------------
    # Core Mutations
    # ------------------------------------------------------------------

    def append(self, data: Any) -> None:
        """
        Add a new node to the END of the list.

        With a tail pointer this is O(1). Without it you would need to
        traverse the entire list to find the last node — O(n).
        """
        new_node = Node(data)
        if self.head is None:
            # Empty list: head and tail both point to the single node
            self.head = new_node
            self._tail = new_node
        else:
            # Link the current tail to the new node, then advance tail
            self._tail.next = new_node   # type: ignore[union-attr]
            self._tail = new_node
        self._size += 1

    def prepend(self, data: Any) -> None:
        """
        Add a new node to the FRONT of the list.

        Always O(1) — we only touch the head pointer, no traversal needed.
        This is the operation where linked lists beat arrays.
        """
        new_node = Node(data)
        new_node.next = self.head   # new node points to old head
        self.head = new_node         # head is now the new node
        if self._tail is None:
            # Was an empty list; tail = new node too
            self._tail = new_node
        self._size += 1

    def insert(self, index: int, data: Any) -> None:
        """
        Insert data BEFORE the node at the given index.

        O(n) — must traverse to index - 1 to splice in the new node.

        Raises IndexError if index is out of range.
        """
        if index < 0 or index > self._size:
            raise IndexError(f"Index {index} out of range for list of size {self._size}")

        if index == 0:
            self.prepend(data)
            return
        if index == self._size:
            self.append(data)
            return

        # Walk to the node BEFORE the insertion point
        new_node = Node(data)
        current = self.head
        for _ in range(index - 1):
            current = current.next  # type: ignore[union-attr]

        # Splice: new_node.next = what was at index, predecessor.next = new_node
        new_node.next = current.next  # type: ignore[union-attr]
        current.next = new_node       # type: ignore[union-attr]
        self._size += 1

    def delete(self, data: Any) -> bool:
        """
        Delete the FIRST node whose .data equals the given value.

        Returns True if a node was deleted, False if value not found.
        O(n) — must scan from head.
        """
        if self.head is None:
            return False

        # Special case: head contains the target value
        if self.head.data == data:
            self.head = self.head.next
            if self.head is None:
                self._tail = None   # list is now empty
            self._size -= 1
            return True

        # General case: walk until we find the predecessor of the target node
        current = self.head
        while current.next is not None:
            if current.next.data == data:
                if current.next is self._tail:
                    self._tail = current   # deleted node was the tail
                current.next = current.next.next   # bypass the target node
                self._size -= 1
                return True
            current = current.next

        return False   # value not found

    def delete_at(self, index: int) -> Any:
        """
        Delete and return the value at the given index.

        O(n) — must traverse to index - 1.
        Raises IndexError if index is out of range.
        """
        if index < 0 or index >= self._size:
            raise IndexError(f"Index {index} out of range for list of size {self._size}")

        if index == 0:
            value = self.head.data  # type: ignore[union-attr]
            self.head = self.head.next  # type: ignore[union-attr]
            if self.head is None:
                self._tail = None
            self._size -= 1
            return value

        current = self.head
        for _ in range(index - 1):
            current = current.next  # type: ignore[union-attr]

        target = current.next   # type: ignore[union-attr]
        value = target.data     # type: ignore[union-attr]
        current.next = target.next  # type: ignore[union-attr]
        if target is self._tail:
            self._tail = current
        self._size -= 1
        return value

    # ------------------------------------------------------------------
    # Queries
    # ------------------------------------------------------------------

    def search(self, data: Any) -> int:
        """
        Return the index of the first node with the given value.
        Returns -1 if not found. O(n).
        """
        current = self.head
        index = 0
        while current is not None:
            if current.data == data:
                return index
            current = current.next
            index += 1
        return -1

    def get(self, index: int) -> Any:
        """
        Return the value at the given index. O(n).
        Raises IndexError if index is out of range.
        """
        if index < 0 or index >= self._size:
            raise IndexError(f"Index {index} out of range for list of size {self._size}")
        current = self.head
        for _ in range(index):
            current = current.next  # type: ignore[union-attr]
        return current.data         # type: ignore[union-attr]

    # ------------------------------------------------------------------
    # Reversal — O(n) with three-pointer technique
    # ------------------------------------------------------------------

    def reverse(self) -> None:
        """
        Reverse the list in-place using the classic three-pointer technique.

        We maintain three pointers: prev, curr, next_node.
        At each step we flip curr.next to point BACKWARD, then advance.

        Before: head → 1 → 2 → 3 → None
        After:  head → 3 → 2 → 1 → None
        O(n) time, O(1) space.
        """
        prev = None
        curr = self.head
        self._tail = self.head   # old head becomes new tail

        while curr is not None:
            next_node = curr.next   # save next before overwriting
            curr.next = prev        # flip the pointer backward
            prev = curr             # advance prev
            curr = next_node        # advance curr

        self.head = prev   # prev is now the last node we processed = new head

    # ------------------------------------------------------------------
    # Python Protocol Methods
    # ------------------------------------------------------------------

    def __len__(self) -> int:
        """O(1) because we maintain a size counter."""
        return self._size

    def __str__(self) -> str:
        """Human-readable: '1 -> 2 -> 3 -> None'"""
        parts = []
        current = self.head
        while current is not None:
            parts.append(str(current.data))
            current = current.next
        parts.append("None")
        return " -> ".join(parts)

    def __repr__(self) -> str:
        return f"LinkedList([{', '.join(str(n) for n in self)}])"

    def __iter__(self) -> Iterator[Any]:
        """Make the list iterable — enables: for x in ll: ..."""
        current = self.head
        while current is not None:
            yield current.data
            current = current.next

    def __contains__(self, data: Any) -> bool:
        return self.search(data) != -1

    def __getitem__(self, index: int) -> Any:
        return self.get(index)

    # ------------------------------------------------------------------
    # Conversions
    # ------------------------------------------------------------------

    def to_list(self) -> list:
        """Convert to a regular Python list. O(n)."""
        return list(self)

    @classmethod
    def from_list(cls, lst: list) -> "LinkedList":
        """Create a LinkedList from a Python list. O(n)."""
        ll = cls()
        for item in lst:
            ll.append(item)
        return ll

Loading visualization...

#Seeing it in Action

pythonreference · read-only

# Build a list
ll = LinkedList.from_list([10, 20, 30, 40, 50])
print(ll)              # 10 -> 20 -> 30 -> 40 -> 50 -> None
print(len(ll))         # 5

# Prepend is O(1)
ll.prepend(5)
print(ll)              # 5 -> 10 -> 20 -> 30 -> 40 -> 50 -> None

# Insert in the middle
ll.insert(3, 25)       # insert 25 before index 3 (which is 30)
print(ll)              # 5 -> 10 -> 20 -> 25 -> 30 -> 40 -> 50 -> None

# Delete by value
ll.delete(25)
print(ll)              # 5 -> 10 -> 20 -> 30 -> 40 -> 50 -> None

# Reverse
ll.reverse()
print(ll)              # 50 -> 40 -> 30 -> 20 -> 10 -> 5 -> None

# Iteration works naturally
total = sum(ll)
print(total)           # 155

# Conversion
print(ll.to_list())    # [50, 40, 30, 20, 10, 5]

Loading visualization...

#The Reverse Operation: Step by Step

The three-pointer reversal is one of the most important linked list operations to internalize:

Three-Pointer Reversal — Step by Step

Loading visualization...

#Time Complexity Analysis

Intuition

Build Your Intuition

In Python, reach for collections.deque first — implement a linked list only when you need to control individual node references.

collections.deque is already a doubly-linked list under the hood (implemented in C as a list of fixed-size blocks). It gives you O(1) append and appendleft, thread-safe operations, and excellent cache performance without any pointer management.

pythonrunnable cell

from collections import deque

# deque covers 99% of "I need a linked list" use cases
queue = deque()
queue.append("job_1")      # O(1) right
queue.appendleft("urgent") # O(1) left
first = queue.popleft()    # O(1)

# When do you ACTUALLY write your own linked list?
# 1. You hold a reference to a specific node and need O(1) deletion without traversal
# 2. Implementing an LRU cache where you move a node to the front on every access
# 3. Interview problems that test your knowledge of pointer manipulation
# In production Python code, deque handles queues; list handles everything else

The trade-off to remember: deque gives O(n) random access (dq[50000] is slow). If you need random access, use a Python list. If you need fast prepend/append at both ends, use deque. You will almost never need a hand-written linked list in real Python code.

Watch Out

Watch out

Fix: Always create a separate current pointer for traversal. Never advance self.head itself — it is your permanent handle to the list.

Losing the head pointer during traversal by advancing self.head or the only reference to the list

This is the most common linked list bug that loses the entire list:

```python

WRONG: advancing self.head loses the list permanently

def print_all(self): while self.head: # self.head walks forward... print(self.head.val) self.head = self.head.next # BUG: now self.head is gone!

After this, self.head is None — the entire list is orphaned

RIGHT: use a local pointer

def print_all(self): current = self.head # local reference — safe to advance while current: print(current.val) current = current.next # self.head never moves ```

The same bug appears in reverse operations: if you reverse a linked list and accidentally overwrite head before saving the new head, the original list is lost. Always save new_head = None before the reversal loop and return it without touching self.head until the full reversal is complete.

#Linked List vs Python List (Dynamic Array)

Operation	Linked List (with tail)	Python `list`
Access by index `lst[i]`	O(n) — must traverse	O(1) — direct pointer arithmetic
Search (unsorted)	O(n)	O(n)
Insert at front	O(1)	O(n) — must shift all elements
Insert at end	O(1) amortized	O(1) amortized
Insert in middle	O(n) traverse + O(1) splice	O(n) traverse + O(n) shift
Delete at front	O(1)	O(n) — must shift all elements

#When to Actually Use a Linked List in Python

In practice, reach for Python's list 99% of the time. Here are the rare cases where linked list thinking is justified:

pythonrunnable cell

from collections import deque

# Case 1: You need O(1) popleft AND O(1) append — use deque (doubly LL internally)
queue = deque()
queue.append("task_1")      # O(1) right append
queue.append("task_2")
first = queue.popleft()     # O(1) left pop — Python list would be O(n)

# Case 2: Implementing an LRU Cache (OrderedDict + deque logic)
# Case 3: Undo/Redo where operations happen at specific history positions
# Case 4: When you hold a direct reference to a node and need O(1) removal

Never use a plain linked list when you need random access — ll[500000] traverses 500,000 nodes while lst[500000] is a single memory address calculation.

#Cycle Detection & Finding the Middle

Two of the most famous linked list techniques both use the two-pointer (Floyd's) algorithm: a "slow" pointer that moves 1 step at a time and a "fast" pointer that moves 2 steps at a time.

#Floyd's Cycle Detection: Tortoise and Hare

pythonreference · read-only

def has_cycle(head: Optional[Node]) -> bool:
    """
    Detect a cycle in O(n) time, O(1) space.
    Slow pointer moves 1 step, fast pointer moves 2 steps.
    If they meet, there is a cycle.
    """
    slow = head
    fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next           # 1 step
        fast = fast.next.next     # 2 steps
        if slow is fast:
            return True   # pointers met — cycle confirmed

    return False   # fast reached None — no cycle


def find_cycle_start(head: Optional[Node]) -> Optional[Node]:
    """
    Find the node where the cycle begins.
    Phase 1: detect the cycle (same as above).
    Phase 2: move one pointer back to head, advance both at speed 1.
             They will meet at the cycle entry point.
    """
    slow = fast = head

    # Phase 1: find the meeting point
    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            break
    else:
        return None   # no cycle

    # Phase 2: find the start
    slow = head
    while slow is not fast:
        slow = slow.next
        fast = fast.next

    return slow   # cycle start node

#Find the Middle: Same Trick, Different Goal

pythonreference · read-only

def find_middle(head: Optional[Node]) -> Optional[Node]:
    """
    Return the middle node in one pass.
    Fast pointer moves 2x — when fast reaches end, slow is at middle.
    For even-length list, returns the second middle node.
    O(n) time, O(1) space.
    """
    slow = fast = head

    while fast is not None and fast.next is not None:
        slow = slow.next
        fast = fast.next.next

    return slow

# Example:
# 1 -> 2 -> 3 -> 4 -> 5 -> None  =>  returns Node(3)
# 1 -> 2 -> 3 -> 4 -> None       =>  returns Node(3)  (second middle)

#Interactive Visualization: Linked List Operations

Watch linked list operations step by step. See append, prepend, insert, delete, reverse, and Floyd's cycle detection animated in real time:

Loading visualization...

#Code Playground

pythonplayground.py · Pyodide

class Node:
  def __init__(self, data):
      self.data = data
      self.next = None

class LinkedList:
  def __init__(self):
      self.head = None
      self._tail = None
      self._size = 0

def append(self, data):
      # TODO: Add to end in O(1) using self._tail
      pass

def prepend(self, data):
      # TODO: Add to front in O(1)
      pass

def delete(self, data):
      # TODO: Delete first node with matching data
      # Handle: empty list, deleting head, deleting middle/tail
      pass

def reverse(self):
      # TODO: Reverse in-place using three pointers (prev, curr, next_node)
      pass

def __len__(self):
      return self._size

def __str__(self):
      parts = []
      current = self.head
      while current is not None:
          parts.append(str(current.data))
          current = current.next
      parts.append("None")
      return " -> ".join(parts)

def __iter__(self):
      current = self.head
      while current is not None:
          yield current.data
          current = current.next

# Test your implementation:
ll = LinkedList()
ll.append(1)
ll.append(2)
ll.append(3)
ll.prepend(0)
print(ll)           # Expected: 0 -> 1 -> 2 -> 3 -> None
print(len(ll))      # Expected: 4

ll.delete(2)
print(ll)           # Expected: 0 -> 1 -> 3 -> None

ll.reverse()
print(ll)           # Expected: 3 -> 1 -> 0 -> None

Tests · assert str(ll) == '3 -> 1 -> 0 -> None'; assert len(ll) == 3; ll2 = LinkedList(); ll2.append(5); assert len(ll2) == 1

#Key Takeaways

Linked lists trade indexing for insertion speed: O(n) to reach position k, but O(1) to insert or delete once you hold a pointer to the node — the inverse of arrays
Python lists are dynamic arrays, not linked lists: list[i] is one pointer dereference and runs in O(1); use collections.deque when you need O(1) operations at both ends
Three-pointer in-place reversal rewires .next pointers without allocating new nodes — O(n) time and O(1) extra space
Two-pointer (Floyd's) technique is the universal linked list tool: fast/slow pointers detect cycles, find the midpoint, and locate the nth node from the end — all in a single O(n) pass with O(1) space
Interview signal: when an interviewer says "linked list", they almost always want the two-pointer approach or a reversal-in-place; practice both until they are automatic

#Quiz

Quick Check1 / 4

What is the time complexity of `prepend(data)` in a singly linked list?

Your Reflection

Continue Learning

Discussion

Linked Lists, Part 1: Singly Linked & Basics

After this lesson, you will be able to:

Before You Start

#Why Linked Lists? The Problem with Arrays

#Memory Layout: Arrays vs Linked Lists

#The Core Trade-Off

#The Node Class: Foundation of Everything

#Singly Linked List: Full Implementation

#Seeing it in Action

#The Reverse Operation: Step by Step

#Time Complexity Analysis

#Linked List vs Python List (Dynamic Array)

#When to Actually Use a Linked List in Python

#Cycle Detection & Finding the Middle

#Floyd's Cycle Detection: Tortoise and Hare

#Find the Middle: Same Trick, Different Goal

#Interactive Visualization: Linked List Operations

#Code Playground

Why Python Lists Are NOT Linked Lists — The CPython Dynamic Array Internals

#Key Takeaways

#Quiz