Imagine a treasure hunt. One card holds a clue and tells you where the next card is. That next card points to another card. This is how a linked list works.
Each little box is called a node. A node keeps some data and a link to the next node.
Follow the arrows
The first node is called the head. To find something, we start at the head and follow the links one by one. The last node points to nothing, which tells us the list is finished.
Picture a list named cat, dog, owl. The cat node points to dog. Dog points to owl. Owl points to nothing.
Why not always use an array?
Array boxes sit in one neat row. Linked-list nodes can live in different places because the links keep them connected. This makes inserting a new node easy when we already know where it belongs.
To put fox between dog and owl, we make dog point to fox and fox point to owl. We do not need to move every other node.
The trade-off
- Adding or removing a known node can be quick.
- The list can grow one node at a time.
- Finding the tenth item means following the first nine links.
- Each node needs extra space for its link.
A linked list is helpful when things change often and walking through them in order is okay. A music playlist is a friendly example: every song can point to the next song.
class Node:
def __init__(self, value):
self.value = value
self.next = None
cat = Node("cat")
dog = Node("dog")
owl = Node("owl")
cat.next = dog
dog.next = owl
current = cat
while current:
print(current.value)
current = current.nextYour tiny challenge
Draw four circles. Put a toy name in each one and draw arrows between them. Add a new circle in the middle by changing only two arrows. You have just edited a linked list.