Advanced

Linked lists

Store items where each one points to the next, making inserts and deletes cheap.

What you will see

A C

About 2 min of reading

Quick check

Before this new lesson, one small question about the lesson you just finished. Recall it, do not look it up.

Try It

A linked list chains nodes, each holding data and a pointer to the next. I walk from the head, insert a node at the front, and remove one by rewiring a pointer to see how easy it makes edits.

Each node points to the next and there is no index. I build three nodes, set the head, then walk the whole list from the front to visit every one.

class Node: def __init__(self, data): self.data = data self.next = None a = Node("A"); b = Node("B"); c = Node("C") a.next = b; b.next = c current = a while current is not None: print(current.data) current = current.next

Before you run it, say out loud what it will print. Then open the answer.

What it prints

A B C

Singly lists are simple, but to reach item 50 you must walk all 49 in front of it. Random access is slow.

To insert at the front I point a new node at the old head, then move the head to the new node. I walk the list to confirm the new order came first.

class Node: def __init__(self, data): self.data = data self.next = None head = Node("B"); head.next = Node("C") new_node = Node("A") new_node.next = head head = new_node current = head while current is not None: print(current.data) current = current.next

Before you run it, say out loud what it will print. Then open the answer.

What it prints

A B C

Order the two moves carefully: point the new node at the old head before you overwrite head, or you lose the rest of the list.

To remove a node I rewire the previous node to skip it. I find the node named B and relink around it, then walk the list to confirm it is gone.

class Node: def __init__(self, data): self.data = data self.next = None head = Node("A"); head.next = Node("B"); head.next.next = Node("C") current = head while current is not None and current.next is not None: if current.next.data == "B": current.next = current.next.next break current = current.next current = head while current is not None: print(current.data) current = current.next

Before you run it, say out loud what it will print. Then open the answer.

What it prints

A C

You must remember the node before the one you want to drop, because only that pointer can be rewired. That is why doubly linked lists also keep a back pointer.

Data Flow

Nodes chain together via pointers; you traverse from the head and can rewire pointers to insert or remove quickly.

1 Start at the head node

↓

2 Follow each pointer to the next node

↓

3 Rewire a pointer to insert a new node

↓

4 Skip a node to remove it

Why this works

When you have a choice

Singly vs doubly linked

Two common kinds:

**Singly*: each node points only forward.
**Doubly*: each node points both forward and back, so you can move in reverse.

Singly:   A -> B -> C
Doubly:   A <-> B <-> C

Doubly lists cost more memory (two arrows) but let you go backward. Singly lists are simpler and use less space.

When to use a linked list

Use a linked list when you insert and delete a lot and rarely need random access.

Operation	Array	Linked list
Access by index	fast	slow
Insert at front	slow	fast
Insert in middle	slow	fast

Array:    great for reading by number
Linked:   great for building and tearing down

If you mostly read data, arrays usually win. If you reorder constantly, linked lists shine.

Examples

Chaining nodes

Each node points forward

[ data | -> ]  [ data | -> ]  [ data | null ]
   head        next           last

A linked list is a chain of nodes, each holding data and an arrow to the next node. The last points to null.

Why it works: to add a node you just point at it, no shifting required.

Walking the list

Visiting every node

start at head
follow the arrow
visit the data
repeat until null

To find something you must walk from the front, one node at a time. That is the trade-off: easy to change, slower to search.

current = head
while current is not None:
    print(current.data)
    current = current.next

Words this lesson uses

Each one is defined here on this site. Open the entry for the full definition and the other words it points at.

← Stacks & queues

Previous Lesson

Stacks & queues

Next Lesson

Trees & graphs

Trees & graphs →