Operation 9 – Traverse List :

Algorithm that traverse a list start at the first node and examine each node in succession until the last node has been processed. Traversal logic is used by several different types of algorithms, such as changing a value in each node, printing the list, summing a field in the list, or calculating the average of a field. Any application that requires that the entire list be processed uses a traversal.

To traverse the list we need a walking pointer, a pointer that moves from node to node as each element is processed. Assuming a linked list with a head structure, the following pseudocode uses a walking pointer to traverse the list. Each loop modifies the pointer to move to the next node in sequence as we traverse the list.

pos = list.head

loop (pos not null)

process (pos->data)

pos = pos->link

We begin by setting the walking pointer to the first node in the list. Then, using a loop, we continue until all of the data have been processed. Each loop calls a process module and passes it the data and then advances the walking pointer to the next node. When the last node has been processed, the walking pointer becomes null and the loop terminates.

Because we need to remember where we are in the list from one call to the next, we need to add a current position pointer to the head structure. It keeps track of the node processed after the last call. The head structure is shown in Figure 17. The figure also shows how the position pointer is modified to move from one node to the next as the traversal algorithm is called.

Each call also needs to know whether we are starting from the beginning of the list or continuing from the last node processed. This information is communicated through the parameter list. The basic logic to traverse a list is

shown in Algorithm 9. We name it getNext because it is called to get the next node in the traversal.

Algorithm – 9 Traverse linked list

algorithm getNext (ref list ,

val fromWhere ,

ref dataOut )

Traverses a linked list. Each call returns the location of an element in the list.

Pre list is metadata structure to a valid list

fromWhere is 0 to start at the first element

fromWhere is 1 to continue from current position

dataOut is variable to receive data

Post dataOut contains data and true returned

-or- if end of list, returns false

Return true if next element located, false if end of list

1 if (fromWhere is 0)

Start from first

1 if (list.count is zero)

1 success = false

2 else

1 list.pos = list.head

2 dataOut = list.pos->data

3 success = true

3 end if

2 else

Continue from pos

1 if (list.pos->link equal null)

End of List

1 success = false

2 else

1 list.pos = list.pos->link

2 dataOut = list.pos->data

3 success = true

3 end if

3 end if

4 return success

end getNext