Lessons · Python · linked lists
Nodes that point at the next node
A linked list is not one block of memory. It is small objects, each holding a value and a reference to the next one, ending at None.
Hone is a place to practise programming. This is one of its lessons, written out in full and free to read without an account.
What it is for
You will rarely build one at work, because a Python list is better for almost everything. You will be asked about one in interviews, and the reason matters: it is the clearest example of paying for one thing (cheap insertion anywhere) with another (no jumping to an index).
How to think about it
Every linked-list loop has the same skeleton: start at the head, do something, move to node.next, stop when the node is None. Write that skeleton first and fill in the middle.
Worked example
class Node:One value, one arrow.
def __init__(self, value, nxt=None):nxt is the next node, or None at the end.
self.value, self.next = value, nxtTwo attributes; that is the whole structure.
head = Node('a', Node('b', Node('c')))Built inside out: c first, then b pointing at it, then a.node, out = head, []The walking variable, and somewhere to collect.
while node is not None:The skeleton. This is the line to memorise.
out.append(node.value)Do the work for this node.
node = node.nextStep. Forgetting this line is an infinite loop.
print(out)['a', 'b', 'c']
Your turn
Move to the next node so the walk makes progress.
node = head
while node is not None:
print(node.value)
node = Solve one with the tests running
The trap
There is no index. To reach the 500th value you must take 500 steps, and there is no length unless you counted one yourself.