Imagine checking every card in a collection to write down its owner and age. Traversal does the same job for a data structure: it visits its elements and applies an operation to each one. In an array, the straightforward route is to start at index 0 and move through the occupied positions. section 2.17 section 2.14
def traverse(self, callback):
for index in range(self._size):
callback(self._array[index])
This Python method loops over the array’s occupied positions and calls the supplied function on each value. For example, passing `print` prints every element. It assumes the function has a useful side effect; collecting transformed results would instead be a map operation. section 2.14
A traversal can also carry information forward. To find the largest value, begin with the first element as the current maximum, then compare each remaining element with it. When a larger value appears, remember its value and index. Check for an empty array first: there is no first element to use. section 2.16
def max_in_array(array):
if len(array) == 0:
raise Exception('Max of an empty array')
max_index = 0
for index in range(1, len(array)):
if array[index] > array[max_index]:
max_index = index
return max_index, array[max_index]
This version remembers the index of the largest value, then returns both the index and value. Starting with the first element avoids assuming that values are nonnegative. section 2.16
Checking dice rolls
Keep six counters, one for each die face, and increment the appropriate counter after every roll. Traverse those counters to find the most- and least-frequent results. Because array indices start at zero, add 1 to a returned index to identify the corresponding die face. section 2.16
The goal stays similar across data structures, but the route changes:
- A linked list follows links from node to node. Finding where to insert into a sorted list requires traversal and takes linear time. section 6.12
- A doubly linked list can be traversed in either direction, although reverse travel does not generally improve an ordinary search. section 6.18
- A circular linked list needs a stopping rule: following links without one can loop forever. section 6.23
- A binary search tree offers pre-order, post-order, and in-order traversal; in-order visits its elements in sorted sequence. section 11.13
