TwiddleLab / Code / Data Structures You Can See
Linked Lists: Chains of Arrows
What you will learn
- Putting an item at the front of a Python list shifts every other item: n moves for n items.
- A linked list is a chain of nodes. Each node holds a value and an arrow to the next node; the last points to None.
- Inserting or deleting is moving one or two arrows, however long the chain. Move them in the right order or part of the chain is lost.
- The price: to reach item 5 000 you must follow 5 000 arrows. A list jumps there in one step.
How the lesson goes
You add one song to the top of a 10 000 song playlist.
Does the phone really move 10 000 songs? Make a guess.
In a row of lockers, the top is locker 0.
Insert a new song there and count every move.
Lockers sit side by side, numbered from 0. To free locker 0, the song in it must go to 1, the one in 1 to 2, and so on to the end.
Another way: songs joined by arrows.
Pick a song, then move arrows so the playlist starts with it.
Each song knows only where the next one is. To put a song first, it must point to the old first song, and head must point to it. Nothing else changes.
That chain is a linked list.
A linked list is a chain of nodes. Each node holds a value and an arrow, called next, to the node after it.
head points to the first node. The last node's next is None: the end of the chain.
Without classes, a node can be a dictionary: {"val": "Ava", "next": None}. The arrow is just a reference to another dictionary.
Put Echo right after Bo.
Two arrows again. This time the order you move them matters.
If Bo lets go of Cleo first, nothing points to Cleo any more, and the program has no way to find Cleo or Dax again. So Echo must point to Cleo before Bo points to Echo.
How a program plays the chain.
Step through. Each time node moves, tap the song it lands on.
Rewire race.
Four jobs on a chain. Use as few arrow moves as you can.
So is a chain always better?
Two jobs on a 10 000 song playlist. For each, tap the faster structure, then Check.
In a list, item i sits at a known place, so jumping there is one step, but shifting is n moves. In a linked list there is no number to jump to, only arrows to follow, but changing two arrows is all an insert needs.
Two broken playlists. Fix them.
Each has one wrong arrow. Find it and point it where it belongs.
Previous lesson: Queues: First In, First Out · Next lesson: Hash Tables: How Dictionaries Find Things · Part of the course: Data Structures You Can See
Lessons are interactive and need JavaScript. Turn it on to play them.
