# Data Structures with Iterable Protocol

January 26, 2019** ∙ **📖 8 min

## 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.

```
class IteratorDemo {
// Iterator Method with @@iterator key
// i.e. Symbol.iterator constant
[Symbol.iterator]() {
// Method stub which returns an iterator object.
}
}
```

### 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.

```
class RangeIterator {
constructor({ start = 0, end = 1000, step = 1 }) {
this.start = start;
this.end = end;
this.step = step;
}
[Symbol.iterator]() {
let start = this.start;
const iterable = {
// Next fn complying with Iterator protocol.
next: () => {
if (start <= this.end) {
const result = {
value: start,
done: false
};
start += this.step;
return result;
}
return {
done: true
};
}
};
return iterable;
}
}
const range = new RangeIterator({
start: 0,
end: 20,
step: 5
});
console.log(...range); // 0 5 10 15 20
```

## 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.

```
class RangeGenerator {
constructor({ start = 0, end = 1000, step = 1 }) {
this.start = start;
this.end = end;
this.step = step;
}
*[Symbol.iterator]() {
let start = this.start;
while (start <= this.end) {
yield start;
start += this.step;
}
}
}
const range = new RangeGenerator({
start: 0,
end: 20,
step: 5
});
console.log(...range); // 0 5 10 15 20
```

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.```
class Node {
constructor(value) {
this.value = value;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.tail = null;
}
get isEmpty() {
return this.head === null;
}
add(value) {
const node = new Node(value);
if (this.head === null) {
this.head = this.tail = node;
return this;
}
this.tail.next = node;
this.tail = node;
return this;
}
addHead(value) {
const node = new Node(value);
node.next = this.head;
this.head = node;
}
removeHead() {
if (this.isEmpty) {
return null;
}
const head = this.head;
this.head = this.head.next;
return head.value;
}
removeTail() {
if (this.isEmpty) {
return null;
}
const { value } = this.tail;
if (this.head === this.tail) {
// List with single node.
this.tail = this.head = null;
return value;
}
let prev = null;
let current = this.head;
while (current.next !== null) {
prev = current;
current = current.next;
}
// Adjust tail pointer.
prev.next = null;
this.tail = prev;
return value;
}
remove(x) {
let prev = null;
let current = this.head;
while (current !== null) {
const { value, next } = current;
if (value !== x) {
prev = current;
current = next;
continue;
}
// If value is at head.
if (prev === null) {
this.head = next;
} else {
prev.next = next;
}
return x;
}
return null;
}
}
const list = [2, 1, 3, 4, 5].reduce(
(list, value) => list.add(value),
new LinkedList()
);
```

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.

```
/**
* Iterator function.
*
* @returns
* @memberof LinkedList
*/
[Symbol.iterator]() {
let current = this.head;
const iterable = {
next: () => {
if (current === null) {
return {
done: true
};
}
const {
value,
next
} = current;
current = next;
return {
value,
done: false
};
}
};
return iterable;
}
```

Generator version of the above.

```
// Generator function.
*[Symbol.iterator]() {
let current = this.head;
while (current !== null) {
const { value } = current;
current = current.next;
yield value;
}
}
```

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.

```
class Stack {
constructor() {
this.list = new LinkedList();
}
get isEmpty() {
return this.list.isEmpty;
}
/**
* Iterator function.
*
* @returns
* @memberof Stack
*/
[Symbol.iterator]() {
return this.list[Symbol.iterator]();
}
push(value) {
this.list.addHead(value);
return this;
}
pop() {
if (this.isEmpty) {
throw new Error('STACK_UNDERFLOW');
}
return this.list.removeHead();
}
}
const stack = [1, 2, 3, 4, 5, 6].reduce(
(stack, value) => stack.push(value),
new Stack()
);
console.log(...stack); // 6 5 4 3 2 1
```

### 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`

.

```
export class BinaryTreeNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
/**
* Inserts node in level order.
*
* @param {*} x
* @returns
* @memberof BinaryTreeNode
*/
add(x) {
const queue = [this];
const newNode = new BinaryTreeNode(x);
while (true) {
const node = queue.shift();
if (node.left === null) {
node.left = newNode;
return this;
}
if (node.right === null) {
node.right = newNode;
return this;
}
queue.push(node.left);
queue.push(node.right);
}
return this;
}
}
```

And finally, `BinaryTree`

with iterator method.

```
import { BinaryTreeNode } from './BinaryTreeNode';
export class BinaryTree {
constructor() {
this.root = null;
}
get isEmpty() {
return this.root === null;
}
add(x) {
if (this.isEmpty) {
this.root = new BinaryTreeNode(x);
} else {
this.root.add(x);
}
return this;
}
/**
* Iterator. Traverses in level order.
*
* @memberof BinaryTree
*/
*[Symbol.iterator]() {
const queue = this.isEmpty ? [] : [this.root];
while (queue.length) {
const { value, left, right } = queue.shift();
if (left !== null) {
queue.push(left);
}
if (right !== null) {
queue.push(right);
}
yield value;
}
}
}
```

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 🙏🏻.

Hi, I am Hitesh.