I was working on a problem last week that required a doubly-linked list in TypeScript. I also got to work with generators for the first time.

Let’s begin by creating our NodeDef object. This is the object that represents the nodes of our linked list. You’ll notice that it has both append and prepend functions, depending on where we are adding to our linked list.

class NodeDef {
    index: number;
    nextNode: NodeDef | undefined = undefined;
    previousNode: NodeDef | undefined = undefined;

    constructor(index: number) {
        this.index = index;
    }

    append(node: NodeDef): void {
        if (this.nextNode) {
            let nextNode = this.nextNode;
            node.nextNode = nextNode;
            nextNode.previousNode = node;
        }
        this.nextNode = node;
        node.previousNode = this;
    }

    prepend(node: NodeDef): void {
        if (this.previousNode) {
            let previousNode = this.previousNode;
            node.previousNode = previousNode;
            previousNode.nextNode = node;
        }
        this.previousNode = node;
        node.nextNode = this;
    }

    toString(): string {
        return `${this.index}`;
    }
}

Now, let’s create a class that holds a generator. It will return an iterable of NodeDef instances. We also need to be able to insert the node in its correct place. Specifically, the NodeDef will be inserted in index order.

class MyGenerator {
    firstNode: NodeDef | undefined = undefined;
    key: string;

    get path(): NodeDef[] {
        let arr: NodeDef[] = [];
        for (let nextNode of this.getNextNode()) {
            if (nextNode) {
                arr.push(nextNode);
            }
        }
        return arr;
    }

    constructor(key: string) {
        this.key = key;
    }

    addNode(newNode: NodeDef): void {
        let done: boolean = false;

        // If the first node is not defined, then this node
        // is the first to be added to the subject.
        if (this.firstNode === undefined) {
            this.firstNode = newNode;
            done = true;
        }
        // If this new node has a lower index than the first node,
        // then this node is the new first node.
        else if (newNode.index < this.firstNode.index) {
            this.firstNode.prepend(newNode);
            this.firstNode = newNode;
            done = true;
        }

        let currentNode: NodeDef = this.firstNode;
        while (!done) {
            // If the new node has a lower index than the current node,
            // then this node should be prepended to the current node.
            if (newNode.index < currentNode.index) {
                currentNode.prepend(newNode);
                done = true;
            }
            // If the current node does not have a next node,
            // then append the new node to the current node.
            else if (currentNode.nextNode === undefined) {
                currentNode.append(newNode);
                done = true;
            }
            // Otherwise, advance to the next node.
            else {
                currentNode = currentNode.nextNode;
                done = false;
            }
        }
    }
    
    /**
     * Generator function, returning NodeDef instances as long as
     * there is still a next NodeDef in the linked list.
     */
    *getNextNode(): Iterable<NodeDef | undefined> {
        let nextNode = this.firstNode;
        while (nextNode !== undefined) {
            yield nextNode;
            nextNode = nextNode.nextNode;
        }
    }   

    toString(): string {
        return `Subject ${this.key}: ${this.path.join(", ")}`;
    }
}

Finally, let’s create a generator and check out the output.

let generator = new MyGenerator("ABC");
for (let i = 0; i < 10; i++) {
    let rand = Math.floor(Math.random() * 1e6);
    let node = new NodeDef(rand);
    generator.addNode(node);
}

console.log(generator.toString());

The console output will look like the following.

Subject ABC: 49454, 122178, 186983, 307018, 456169, 558372, 632665, 838801, 847234, 914944

You can find this code in the TypeScript Playground.