Passive and Active Traversals

The George Washington University
School of Engineering and Applied Science
Department of Computer Science
CSci 131 -- Algorithms and Data Structures I

Passive and Active Traversals (Iteration)

The linked-list package introduced in Section 8.2 provides an operation called Traverse, which moves through the list, from beginning to end, one element at a time, until each element has been “visited” exactly once.

Formally, this Traverse operation is an example of a passive iterator operation. An iterator is any operation that iterates through a data structure one element at a time; we call it passive because the client program simply calls it once and “stands back” passively while the iterator roams through the entire structure. In this note, we use the terms traversal and iteration interchangeably.

Sometimes an application requires iterating through a structure, touching each element once, but allowing the client program the flexibility to decide just when to proceed to the next element. Moving through a structure in this fashion is called active iteration, because the client program is actively involved in the process at every step.

Active Iterator Operations

To be actively involved in the iteration, the client program must execute a loop. We know that any loop must contain statements for loop initialization, termination, and incrementation; to support active iteration, the data structure package must provide these operations, and also one for retrieval of the current element in the traversal.

For the case of singly-linked lists whose nodes contain elements of type ElementType, we will call these operations StartTraversal, AtEndOfList, MoveToNextElement, and RetrieveCurrentElement, respectively. If the list being used by the client is called MyList, and MyElement is a variable of type ElementType, then the basic client-program algorithm is

StartTraversal(MyList); -- loop initialization
LOOP
EXIT WHEN AtEndOfList(MyList); -- loop termination condition

MyElement := RetrieveCurrentElement(MyList);

-- process the current element MyElement here

MoveToNextElement(MyList); -- loop incrementation step
END LOOP;

The implementation details of these operations depend upon the way the data structure is implemented. For linked lists, we include, as a field in the record defining the list type, an extra pointer, WhichElement, indicating which element of the list is being processed. In this implementation,

StartTraversal sets WhichElement to its initial value at the beginning of the list. This value will, of course, be NULL if the list is empty.
AtEndOfList returns True if and only if WhichElement is NULL -- that is, either the list is empty or we've reached the end of it.
MoveToNextElement increments WhichElement (using the Next field).
RetrieveCurrentElement returns the value of the current element.