Data Structures with Iterable Protocol

Published in

Smelly Code

3 min readJan 27, 2019

Iterating data structures with for-of loop and spreading them with spread operator(…).

Iterators and Generators have been around for a while. They have changed the way we loop through the values of an object. Earlier, we used to use the for-in loop to iterate over the values, but there was no guarantee of the order in which values will be iterated. Also, it was quite cumbersome cause we had to use keys from the for-in loop to get values. Generator and Iterators remove the pain of iterating objects. For an object to be iterable, it just needs to comply with iteration protocols. This post provides a quick overview of Generators and Iterators/Iterables and explains how common data structures can be made iterable.

Iteration Protocols

The advent of ES5 brought two iteration protocols to JavaScript: Iterable Protocol and Iterator Protocol.

Iterable Protocol

For an object to be iterable, it must have an iterator method. An iterator method is defined using @@iterator key i.e. the Symbol.iterator constant. Iterator method can be any javascript function which takes zero arguments and returns an object conforming Iterator Protocol(will be discussing soon). Here’s the sample code, if you are lost in jargon.

Iterator Protocol

The iterator protocol defines a standard way to produce a sequence of values (either finite or infinite), and potentially a return value when all values have been generated. ~MDN

For an object to be an iterator object, it needs to implement a next method which fulfils below criteria:

It should take zero arguments. Although, you may pass arguments to next and there won’t be any error but you shouldn’t cause when your iterable object will be used with spread operator or for-of loop you won’t be able to pass any arguments.
It should return an object with at least one of the two properties.

value: Any javascript value which we want to return from our iterator.
done: A boolean flag to indicate whether we reached the end of the sequence or not.

Here’s a quick range iterator example borrowed from MDN.

Generators

Sometimes explicitly maintaining the internal state of iterators and returning an iterable object is too much of work. Generators reduce that amount of work and provide an alternate approach to make an object iterable with the help of yield keyword. Generators functions have special syntax. They are written as function *. You can read more on generators here.

Here’s our previous example re-written with the help of generators.

Alright, enough about Iterators and Generators. Let’s use them with common data structures like LinkedList, Stack, BinaryTree.

LinkedList

LinkedList is a linear data structures where each node/element holds the data and pointer to the next node. The start and end of the list are called head and tail. Here’s an implementation of Linked List.

We need to add an iterator to make the linked list iterable. Our iterator function will have an internal state variable called current (which initially refers to head) representing the current node we are at. Every next call, will return the data of the current node and move the current node to the next node. Once the next method is done traversing all nodes, it returns done as true to stop the iteration.

Generator version of the above.

You can find the full code here.

Stack

A Stack is a linear data structure which follows Last In First Out(LIFO) pattern which means items inserted into the stack last will come off first. To keep things DRY, we’ll use our earlier Linked List data structure to implement Stack. We’ll also leverage its iterator method to make our stack iterable.

Binary Tree

Binary Tree is a subclass of Tree data structure. In Binary Tree, each node can have maximum 2 children called left and right. You can read more about Binary Trees in my post A Bit About Binary Tree. Since trees are non-linear data structure so they can be traversed in many ways. We’ll implement their Level Order or Breadth First Order traversal in our iterator method. Here’s the class which represents BinaryTreeNode for our BinaryTree.

And finally, BinaryTree with iterator method.

Well, that’s all about Data Structures with Iterable Protocol. I have created a git-repository of examples used in this post. I hope you find them useful. Thanks for reading 🙏🏻.