Give an example of when it would be more efficient to use an

Give an example of when it would be more efficient to use an iterator to access the nodes in a singly linked list.

Solution

An example when it is more efficient to use an iterator to access nodes in a singly linked list.

suppose we want to add an area code to every listing in a telephone directory stored in a singly linked list. In this case an update operation performed in the key field mode will not be useful as we would have to generate the names of all the telephone customers in order to operate on each node. In addition even if the update method was coded in the node number mode, using it to change the area code of every item in the database would be a time consuming process since each invocation begins its traversal at the front of the list. when updating the first listing,one node would be traversed, two nodes would be traversed to update the second listing, three node for third listing, etc. Thus the total number of node traversed for updating each of n nodes would be : 1+2+3+4+...+n = n(n+1)/2, which is O(n²).

An iterator object, on the other hand, retains its postion in the list after an operation is performed. Therefore, if an iterator\'s class contained an update method, after updating one listing, it would simply traverse one more node in order to update next listing. The total number of nodes traversed to update each of n nodes would be :1 +1+1+1+1+1......+1+1+1=n, which is O(n) , hence speeding up the operation.