Suppose we want to provide an iterator for our Bag ADT implemented using a linked list as we did for the one implemented using a Python list. The process would be similar, but our iterator class would have to keep track of the current node in the linked list instead of the current element in the Python list. We define a bag iterator class in the listing below
Program Listing
# Defines a linked list iterator for the Bag ADT. class BagIterator : def __init__( self, listHead ): self._curNode = listHead def __iter__( self ): return self def __next__( self ): if self._curNode is None : raise StopIteration else : item = self._curNode.item self._curNode = self._curNode.next return item
|
which would be placed within the llistbag module that can be used to iterate over the linked list.
When iterating over a linked list, we need only keep track of the current node being processed and thus we use a single data field _curNode in the iterator. This reference will be advanced through the linked list as the for loop iterates over the nodes. As was done with our Python list-based Bag class, the linked list version must include the __iter__ method, which returns an instance of the BagIterator class.
Figure 7.7.1 illustrates the Bag and BagIterator objects at the beginning of the for loop. The _curNode pointer in the BagIterator object is used just like the curNode pointer we used when directly performing a linked list traversal earlier in the chapter. The only difference is that we don't include a while loop since Python manages the iteration for us as part of the for loop. Note, the iterator objects can be used with any singly linked list configuration to traverse the nodes and return the data contained in each.
Figure 7.7.1: Sample Bag and BagIterator objects at the beginning of the for loop.
