Paul's Python CoursePPC

Linked lists

Not met yet

A linked list keeps each item in a node that also holds a reference to the next node; the last node's next is None, and the list itself only knows the first. The order lives in the links, not in positions. Reaching the nth item means walking past every node before it, O(n), but putting a node in or taking one out changes an arrow or two and moves nothing. Change arrows in the right order: an arrow you overwrite forgets where it pointed.

Try it

main.py

Output

Press Run and what your program prints shows up here.

Easy to get wrong

  • Thinks a linked list's order is the order its nodes were made, rather than the order of the links between them.
  • Thinks a while loop that walks a linked list until None reads past the last node and crashes.
  • Thinks pointing a node's next at a new node keeps the old rest of the list hanging on after it.
  • Thinks changing a node's next swaps out just the following node, like assigning one position of a list, and keeps everything after it.
  • Thinks reaching the nth node of a linked list takes one step, as indexing a list does, rather than walking past every node before it.
  • Thinks a node's next can be pointed backwards before keeping hold of the node it used to point at.

Where it comes up