Linked Lists
Nodes and pointers.
A list keeps items side by side in memory. A linked list doesn't. Each item lives in its own little box, called a node, and every node holds a pointer to the next one, like a treasure hunt where each clue tells you where the next clue is.

- Not side by side
- Each item in its own node
- Each node points to the next
Array or linked list?
In an array, you can jump to any position instantly, but adding at the front shifts everything. In a linked list it's the opposite. Adding at the front is O of one, you just point a new node at the old first one. But reaching the hundredth item means walking through ninety nine nodes first. That's O of N.
Three nodes
A node is a tiny class with two things, a value, and next, which points to the next node. Here we link three nodes together by hand. The head is the first node. To print them all, we follow the next pointers until we reach none. Run it.
class Node:
def __init__(self, value, next=None):
self.value = value
self.next = next
head = Node("A", Node("B", Node("C")))
node = head
while node:
print(node.value, end=" -> ")
node = node.next
print("None")A -> B -> C -> None
Summary
A linked list is a chain of nodes, each pointing to the next. Adding at the front is O of one, but finding an item is O of N. Next, we'll build a proper linked list class.
Key takeaways- Node: value + next
- Follow next pointers
- head is the first node