What is the difference between iteration and traversing?

Question

The past few weeks I have been learning about iterators. I still do not understand the main difference between iterating through a link list and traversing through one. I know that traversing means to go through (visiting every element) the link list, and when iterating you basically do the same thing, but what is different, and why cannot you iterate through everything (standard library data-structures)?

Answer 1

“Traversal” just means walking through (all or some) elements of a data structure.

Historically, “iteration” in computer science is a special form of recursion for which no additional stack space is needed¹ – in other words, tail recursion. This form is computationally exactly equivalent to what we now colloquially know as “iteration”, namely a finite loop (such as a for loop with a fixed lower and upper bound).

Now this makes iteration especially well suited (compared to general recursion) for traversing linear data structures². Note that it does not work for all containers (e.g. general graphs) because here you need to remember the already visited nodes (e.g. using depth-first search, which is defined recursively in terms of adjacent nodes, rather than via the C++ concept of iterators).

It is in this context that the term “iteration” is used in C++ applied to containers.

In summary: not every traversal is an iteration but every iteration (over a data structure) is a traversal. However, it’s worth noting that many people make no such distinction and use the terms interchangeably.

---

¹ In particular this is the usage of Gerald Sussman of SICP fame.

² But seemingly non-linear data structures such as trees can be linearised for the purpose of iteration by applying the right-hand rule (wall-following algorithm) and can thus be traversed without a stack.

Answer 2

Note: I just made this definition up, but it fits my mental model, so I'm going with it.

Iteration is discrete, traversal may or may not be. So, you can traverse the range of allowable volumes on the analog volume knob on your speaker, but you cannot iterate through them.

But iteration is a type of traversal. So every iteration is a traversal, but not every traversal is an iteration.

Answer 3

AFAIK they are synonymous. What makes you think there is a difference?

I feel ;) that "traverse" is sometimes used to indicate that internal structure is exploited. You traverse a tree by going from parentnodes to childnodes or you traverse a list by following the next pointers.

An array on the other hand you iterate over. You have all the elements, just work through them one by one.

Answer 4

I would call iterator the "agent" and traverse the "action". Actually, it often confuses me when people refer to traversing over something as iterating over something (because to me iteration is related to numerical methods which are converging towards a mathematical point via iteration). On the other hand, even I use the words interchangeably.

You cannot iterate over containers for which there is no concept of traversal. At a minimum, in order to traverse something, you need to know at least whether you have a neighbor, and how to get to it.

Answer 5

A iterator basically gives you the functionality to traverse through a datastructure - visiting every element. I would call traversing and iterating synonyms. There are iterators, but I don't know traversers in programming.

and why cannot you iterate through everything(STL datastructures)?

Some datastructures do not have information that allows this. For example on a stack you should not be able to traverse though all the elements because you can only access the top of the stack.