Iterators

Let's now use one of our list implementations to solve a problem: counting the number of times a given item appears in a list.

We can write a function to do so. However, let's write it from the perspective of a program that it outside of the ArrayList or LLList class:

from lllist import LLList
import random

def count(list_impl, item):
    total = 0
    for i in range(list_impl.length()):
        list_item = list_impl.get_item(i)
        if list_item == item:
            total += 1
    return total

# create a new LLList
my_list = LLList()

# add one million random numbers to the list
for i in range(10000):
    my_list.add_item(random.randint(1, 100), 0)

# count how many times 13 is in the list
print(count(my_list, 13))

This program creates a new list, adds one million random numbers to it, and then counts the number of times 13 appears in the list.

However, there's something surprising about this function: it is inefficient! To see why, watch the following video:

To summarize, the count() function as written above is efficient when the list that is passed in as a parameter is an ArrayList. However, when an LLList is passed in as a parameter, the function isn't very efficient.

To fix this issue, we'll need to use an iterator.

Iterators

An iterator is an object that can be used to maintain state about the current position of a traversal over a data structure. The main benefit of an iterator is that it allows functions outside of the data structure's class to efficiently iterate over an instance of a data structure.

Iterators typically have just two methods:

has_next(): whether there is another item in the traversal
next(): returns the next item and advances the iterator

Functions can then create iterators and call these methods. For example, the count() method could be changed to use an iterator:

def count(list_impl, item):
    total = 0
    it = list_impl.iterator()
    while it.has_next():
        list_item = it.next()
        if list_item == item:
            total += 1
    return total

In order for each implementation of the list ADT to have an iterator, we can add an iterator() method to the list of expected methods:

iterator(): returns an iterator for the list

Making an efficient `LLList` iterator

Watch the video below to see how to make an efficient iterator for the LLList class:

By using the iterator, we've improved the time complexity of the count() function from O(n²) to O(n)!

Check your understanding

In the above video, we added an iterator for the LLList class. However, in order for the count() function to work if list_impl is an ArrayList, we also need to implement the iterator the ArrayList class. What would the implementations of the has_next() and next() methods look like?

Click to reveal the answer.

Answer. This is the implementation of the ArrayListIterator:

class ArrayList:
    ...


    class ArrayListIterator:
        def __init__(self, items, num_items):
            self.i = 0
            self.items = items
            self.num_items = num_items

        def has_next(self):
            return self.i < self.num_items

        def next(self):
            item = self.items[self.i]
            self.i += 1
            return item


    def iterator():
        return ArrayListIterator(self.items, self.num_items)

The iterator() method simply creates a new ArrayListIterator object, and passes in the list of items (and the number of items). This allows the iterator to access the data. In its constructor, the iterator also initializes a variable self.i to use as the index of where the iterator currently is in the list.

The has_next() method just needs to check whether the index has moved past the number of items yet.

The next() method is also quite simple: it just saves the item at index i, advances the iterator, and returns the item.

Data Structures and Algorithms

Iterators

Iterators

Making an efficient LLList iterator

Making an efficient `LLList` iterator