Lesson 10: Linked lists

Picture a treasure hunt: each note holds a value and a clue to the next note, and reaching the fifth means going one at a time. That's a 'linked list' — a chain of 'nodes'. The upside: inserting or deleting in the middle is O(1), you just redirect a clue. The downside: reaching a given position is s

A linked list is like a treasure hunt: each note holds a value and a clue to where to go next. To reach the fifth note you must follow the clues one by one — you can't jump straight to the middle like in an array, where you can reach any spot at once.

class: A template for a small box with fields. class Node defines a box with two fields: val (the value) and next (a pointer to the next node). Node(1) creates such a box, and self simply means "this box".
linked list: A data structure of nodes, each holding a value and a next pointer to the following node; O(1) insert/delete next to a known node, but O(n) access by position.
node: The building block of a linked list: a small object holding a value (val) and a pointer (next) to the next node, or None at the end.
cache locality: How close in memory data that is used together is stored; a contiguous array is cache-friendly, while scattered linked-list nodes are less so.