Data Structures · Lesson 3 of 8

Linked Lists

Nodes, pointers, singly vs doubly linked, and tradeoffs vs arrays.

• Intermediate
• 14 min read
• 3 objectives

Before this lessonLesson 2: Arrays

A linked list is a chain of nodes. Each node holds a value and a reference (pointer) to the next node. The nodes can live anywhere in memory; the pointers are what tie them together. You keep track of the first node, called the head, and follow next pointers until you reach None.

A treasure hunt of clues

In a linked list each item (a node) holds its value and a note saying where the next node is. To find the fifth item you must follow four notes from the start, like a treasure hunt where each clue points to the next. Unlike an array, the nodes can be scattered anywhere in memory. The trade-off: reaching item k is slow, but inserting or removing next to a node you already hold takes a moment because you only rewrite a couple of pointers.

Building one

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

head = Node(1, Node(2, Node(3)))

cur = head
while cur:
    print(cur.val)
    cur = cur.next

1
2
3

Insert and delete

The big advantage: adding or removing at a known position is O(1), because you only rewire a pointer, and nothing shifts. Inserting at the head is the simplest case.

def push_front(head, val):
    return Node(val, head)     # new head points at old head

def delete_value(head, target):
    if head and head.val == target:
        return head.next
    cur = head
    while cur and cur.next:
        if cur.next.val == target:
            cur.next = cur.next.next   # skip the node
            break
        cur = cur.next
    return head

head = push_front(head, 0)
head = delete_value(head, 2)

Finding the node to delete still takes O(n), because you must walk the list to reach it.

Singly versus doubly linked

A singly linked list has only next pointers, so you can move in one direction. A doubly linked list also has prev, which allows walking backward and removing a node when you already hold a reference to it, at the cost of more memory.

Arrays vs linked lists

• Access by index: array O(1), linked list O(n).
• Insert/delete at the front: array O(n), linked list O(1).
• Memory: linked lists spend extra space on pointers and cache poorly.
• In practice arrays win most of the time; linked lists shine as building blocks (queues, LRU caches, adjacency lists).

Classic technique: fast and slow pointers

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow.val

print(middle(Node(1, Node(2, Node(3, Node(4, Node(5)))))))

3

The fast pointer moves twice as quickly, so when it reaches the end the slow pointer is at the middle. The same idea detects cycles.

Building and walking a list

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

head = Node("A")
head.next = Node("B")
head.next.next = Node("C")

current = head
while current:
    print(current.value, end=" -> ")
    current = current.next
print("None")

A -> B -> C -> None

Inserting after a node is just two pointer changes

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

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

head = Node(1, Node(2, Node(4)))
print(to_list(head))

two = head.next
two.next = Node(3, two.next)      # new node points at 4, node 2 points at new node
print(to_list(head))

[1, 2, 4]
[1, 2, 3, 4]

Worked example: reverse a linked list

This is the most famous linked-list exercise. Walk the list once and flip each pointer to face backwards, keeping track of the previous node.

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

def to_list(head):
    out = []
    while head:
        out.append(head.value)
        head = head.next
    return out

def reverse(head):
    prev = None
    while head:
        nxt = head.next      # remember the rest
        head.next = prev     # flip the pointer
        prev = head          # move prev forward
        head = nxt           # move on
    return prev

head = Node(1, Node(2, Node(3, Node(4))))
print(to_list(reverse(head)))

[4, 3, 2, 1]

Draw the four nodes on paper and follow the loop step by step. Watching the arrows flip is the fastest way to make this click.

Key takeaways

• A linked list is nodes chained by pointers; no index jumping, so lookup is O(n).
• Insert or delete next to a known node is O(1): just rewire pointers.
• Most linked-list problems are solved by careful pointer bookkeeping and one or two extra variables.

# Write your solution here