A linked list is a train
Build a train where each carriage is hooked to the next one. Add a carriage at the front or after another, take one out, and find one, and count how many links you have to follow each time, because a linked list has no index to jump to.
Core concept
A linked list stores each item in a node with a link to the next node; adding at the front is instant, but reaching node i means following i links from the head
Topic: Data structures
A linked list is like a train. Each carriage (a node) carries something (its value) and is hooked to the carriage behind it (its link, or next). The list only remembers the first carriage, called the head; the last one links to nothing, NULL. Unlike an ordinary list, a linked list has no numbered places to jump to: to reach the fourth carriage you start at the head and follow the links one by one, called hops. That makes some jobs slow and others fast. Adding a carriage at the front needs no walking at all: hook it in front of the head and make it the new head. Adding one after carriage 1, or taking carriage 2 out, means walking there first, then changing just one or two links; nothing else has to move. Finding a carriage means walking until you meet it, or reach NULL.
What you will learn
- Describe a linked list as nodes, each with a value and a link to the next.
- Add a node at the front, add one after another node, and remove one.
- Count the hops each operation needs, and explain why there is no index to jump to.
- Compare adding at the front of a linked list with adding in the middle.
Before you start
- Know what a list (array) is and that its items have indexes from 0.
Materials
- A notebook to draw the train and its links
Equipment
- None
Procedure
- Add the dining car after carriage 1 and count the hops.
- Take carriage 2 out of the train.
- Find the cargo wagon and watch the walk from the head.
- Answer the practice challenges.