In the absence of any abstraction, how does one normally identify an element of an array, an element of a linked list, or an element of a tree? The most straightforward way would be to use a pointer to the element's address in memory. Here are some examples of pointers to elements of various data structures:
To iterate over an array, all we need is that pointer; we can handle all the elements in the array by starting with a pointer to the first element and simply incrementing that pointer until it reaches the last element. In C:
for (node *p = lst.head_; p != nullptr; p = p->next) {
if (pred(p->data)) {
sum += 1;
}
}
But in order to efficiently iterate over a linked list, we need more than just a raw pointer; incrementing a pointer of type node* is highly unlikely to produce a pointer to the next node in the list! In that case...