ES6 Iterators and Generators by example

Recently while working on my data structures skills I’ve implemented ArrayList and LinkedList data structures. While doing so I’ve come across a great case for generators and iterators. ES6 introduced a new iteration mechanism for traversing data and corresponding protocols that define a uniform approach to iterating structures in JavaScript. Objects implementing the iteration and iterator protocols can define or customize their iteration behavior that many new language constructs like for..of loop and spread operator benefit from.

This article doesn’t explain these concepts in depth but rather shows an apt use case for their usage. For the in-depth explanation please see MDN and great Exploring ES6 book by Axel Rauschmayer.

LinkedList vs ArrayList
Link to this section

LinkedList and ArrayList are two fundamental data structures that are the basis for all other complex structures. They belong to the List abstract data type (ADT) and differ in the runtime complexity when the following operations are performed:

get item
insert item
remove item

ArrayList is a contiguous data structure that dynamically grows or shrinks the underlying fixed length array by reallocating memory and copying elements to the new array.

It allows efficient random element access — constant time access regardless of how many elements are in the list. But it takes linear time to insert/delete an element in the beginning since most of the elements must be moved.

LinkedList is a linked data structure that uses pointers to bind distinct chunks of memory together.

It allows efficient inserting/deleting of elements in the beginning but takes linear time to access an element in the middle.

For the purpose of this article we’re not interested in inserting/deleting of elements, but only in the underlying representation and the get operation implementation.

Basic implementation
Link to this section

Let’s see how both can be implemented. I’ll use ES6 classes to do so. Since we’re not interested in the insert method I will initialize lists with data in the constructor and only implement the method get. Also I will not add error handing logic like out of range indexes etc.

ArrayList
Link to this section

<>Copy
module.exports = class ArrayList {
    constructor() {
        const el1 = {value: 1};
        const el2 = {value: 2};
        const el3 = {value: 3};

        this.list = [];
        this.list.push(el1);
        this.list.push(el2);
        this.list.push(el3);

        this.size = 3;
    }

    get(index) {
        return this.list[index];
    }
};

LinkedList
Link to this section

<>Copy
module.exports = class LinkedList {
    constructor() {
        const el1 = {data: {value: 1}, next: null};
        const el2 = {data: {value: 2}, next: null};
        const el3 = {data: {value: 3}, next: null};
        
        // link elements together
        el1.next = el2;
        el2.next = el3;

        // set a pointer to the first node
        this.head = el1;
        this.size = 3;
    }

    get(index) {
        let counter = 0;
        let element = this.head;

        while (counter < index) {
            element = element.next;
            counter++;
        }

        return element.data;
    }
};

If you’ve never before worked with a linked list you can see that getting the last element is one operation for an array list and N operations for the linked list. It’s an important observation to remember for the next part of the article.

Iterating over objects
Link to this section

Now suppose we are given a list object and we need to filter out numbers in the list that are less than 3. That doesn’t seem like a difficult task. We know that the list implements get method that returns an item by the index. So we can use simple for loop to iterate over the elements:

<>Copy
const filtered = [];
for (let i = 0; i < list.size; i++) {
    const element = list.get(i);
    if (element.value > 2) {
        filtered.push(element);
    }
}

At first glance all seems OK here. But a hidden problem occurs if the list is an instance of a linked list. We’ve seen that get operation in a linked list iterates over the elements to get to the element by an index. It means that for each iteration of the for loop we’re also iterating the list inside to get to the requested element. We’re duplicating the work and this is very inefficient.

Since both lists have to be iterated in the same way regardless of the underlying structure, we can solve this problem by implementing forEach method for each data structure. Let’s see how this is done:

<>Copy
// implement the method on prototype and extend ArrayList
class ForEachArrayListIterator {
    forEach(fn) {
        for (let i = 0; i < this.list.length; i++) {
            fn(this.list[i]);
        }
    }
}
// implement the method on prototype and extend LinkedList
class ForEachLinkedListIterator {
    forEach(fn) {
        let element = this.head;

        while (element !== null) {
            fn(element.data);
            element = element.next;
        }
    }
}
class ArrayList extends ForEachArrayListIterator { ... }
class LinkedList extends ForEachLinkedListIterator { ... }

And the usage:

<>Copy
const filtered = [];
list.forEach((element) => {
    if (element.value > 2) {
        filtered.push(element);
    }
});

This works fine and solves our original problem with duplicate iteration, but there are a couple of shortcomings with this solution:

we can’t break out of the loop
we can’t use list inside language constructs that support iteration, namely for..of loop and spread operator

Let’s see how we can solve these by implementing an iterator.

Implementing iterator
Link to this section

The iterable protocol specifies than an object is iterable if it implements a method accessed by the [Symbol.iterator] key. It’s called implicitly when using for..of loop or other constructs that expect an iterable object. The method should return an object that implements the iterator protocol — an object with the next method.

The implementation is pretty easy for both an array and a linked list. We store a reference to the current value to be returned and proceed to the next item on each call to the next. When there are no more values, we return {done: true}. Here is how it can be done:

<>Copy
class ForEachLinkedListIterator {
    [Symbol.iterator]() {
        let element = this.head;

        return {
            next() {
                let value, done = true;
                if (element !== null) {
                    value = element.data;
                    done = false;
                    element = element.next;
                }
                return {
                    value: value,
                    done: done
                }
            }
        }
    }
}

class ForEachArrayListIterator {
    [Symbol.iterator]() {
        const self = this;
        let i = 0;

        return {
            next() {
                let value, done = true;
                if (self.list[i] !== undefined) {
                    value = self.list[i];
                    done = false;
                    i += 1;
                }

                return {
                    value: value,
                    done: done
                }
            }
        };
    }
}

Having done that, we can now use the list inside for..of and spread operator:

<>Copy
const list = new LinkedList();

for (let element of list) {
    console.log(element);
}

console.log([...list]);

The problems we identified above are solved with the help of an iterator. However, the implementation of the iterator’s next method is error prone and not very intuitive. Is there anything we can do to simply it?

As it turns out we can. ES6 introduced generators functions that look like a normal function but allow multiple returns over a period of time. This is accomplished by implicit returning of the generator object that implements the iterator protocol. And this is exactly what we need.

Using a generator
Link to this section

Generator functions can also be used for method definitions in a class. Inside the generator function each yield operator statement corresponds to the value returned by the call to the next method. It means that we can write our iteration as we did in the case with forEach but instead of calling a callback we yield the value. So here is the final implementation:

<>Copy
class ForEachLinkedListIterator {
    *[Symbol.iterator]() {
        let element = this.head;

        while (element !== null) {
            yield element.data;
            element = element.next;
        }
    }
}

class ForEachArrayListIterator {
    *[Symbol.iterator]() {
        for (let i = 0; i < this.list.length; i++) {
            yield this.list[i];
        }
    }
}

That’s all folks. All the code is available on GitHub.

Our content is free thanks to

ES6 Iterators and Generators by example