Course 3.1Lesson 2 of 5
A linked list is a chain of nodes. Each node holds a value and a link to the next node, and the last node links to None. The list is held by its head. Adding at the front is fast, because only the head changes, but finding a value or the end means walking from the head, one node at a time, with a loop that continues while the current node is not None. A node can be removed by making the node before it skip over it, and the list can be reversed by turning each link around. Compared with a Python list, a linked list is quick to insert and remove at the front and in the middle once you are there, and slow to reach the item at a position. A Python list is the better choice for most jobs, and a linked list teaches how nodes and links work.
Try the code and the simulations beside the lesson.
After this lesson you can
A Python list keeps its items side by side in memory. A linked list is different: it is a chain. Each node holds a value and a link to the next node. The last node's link is None: "no next node". You hold the chain by its first node, the head.
Think of a treasure hunt. Each clue holds a prize and says where the next clue is. To reach the third clue you must follow the first and the second. You cannot jump to it.
Predict first. What is the list after the four operations? Then run it.
The result: [1, 4, 9, 2], length 4, find(9) is 2, find(7) is -1.
The two things to remember about links: save the next node before you change a link, or you lose the rest of the chain. And the order of the lines matters.
To find node r, the program still walks from the head, one link at a time. That walk is what makes a linked list slow to reach a position.
| Job | Python list | Linked list |
|---|---|---|
| Item at position 500 | fast | walk 500 nodes: slow |
| Add at the end | fast | walk the whole chain (unless you keep the last node too) |
| Add at the front | slow (all items move) | fast |
| Remove a node you already hold | slow (items move) | fast |
| Memory | compact | one extra link for each item |
For most real programs, a Python list is the better choice: it is simple and fast enough, and Python's deque covers fast work at both ends. The linked list is worth learning for two reasons. It shows how nodes and links work, which you will need for trees and graphs. And the ideas, such as keeping a head and changing links, appear in many other structures.
head.next before saving the old next node.while current.next and then using current when it is None. Decide whether you want to stop at the last node, or after it.head is None).remove.while goes round for ever.Start with two quick questions. Each New numbers gives you a fresh one, so you can practise as long as you like.
Then the labs and the problems:
len.None.current = head, while current is not None, current = current.next.Try each one on your own first. If you are stuck, open a hint. Then check with Show the answer.
next of the last node hold?Every lesson is open to read. Enrolling also lets you:
Log in to join the discussion.
Loading…
This lesson is free to read. Enroll free to keep your place and take the tests.