Traversal

A traversal visits every node in a structure (in first-to-last order in the case of a list) performing some operation at every node. The basic form is as follows:


accessfirst(exlist, exav)
while validaccess(exlist, exav) do
{
   process node pointed to by exav;
   accessnext(exlist, exav)
}

Note that this works for:

  • an empty list – the while loop body is never entered since exav is invalid immediately;
  • if the list has only one node the body of the loop is executed exactly once;
  • if there is more than one node the loop is executed N times (where N is the number of nodes);

For example, we could use a traversal to print the author attribute of every book in booklist:


accessfirst(booklist, bookav);
while validaccess(booklist, bookav) do
{
   print(bookav^.author)
   accessnext(booklist, bookav)
}

Next: Linear Search