April 29, 2014
This post is the first of many documenting my progress on a TypeScript data structures & algorithms library named dstruct. It aims to provide some of the popular data structures and algorithms available in languages like Java, C#, and Scala which enable programmers to efficiently solve problems with less code.
Next steps was to determine the most popular data structures and algorithms. This was a bit of a challenge since there is no authoritative source and none are objectively the best for all problems. I looked across the standard libraries of Java(1), Scala(2), C#(3), as well as popular online learning resources (4) and textbooks (5). Eventually I decided on what I believe to be the most widely used and ubiquitous data structures and algorithms.
The lists I chose to implement were ArrayList, and DoublyLinkedList. The lists can be found here.
The maps that I chose to implement were HashMap, WeakHashMap, LinkedHashMap, HashBiMap, TreeMap. The maps can be found here.
The tree implemented was a RedBlackTree which is a self-balancing binary search tree that provides average logarithmic time per operation. It is useful for implementing tree data structures since it avoids the inefficient worst cases of other self-balancing binary search trees like AVL trees which can degenerate in to LinkedList. The trees can be found here
For these data structures an emphasis on the separation between implementation and interface was an important goal. To achieve that all of the data structures were implemented according to abstract generic interfaces. Programmers who use the library are encouraged to use these interfaces when typing their programs rather than the implementations. Implementations are tested with unit tests suites per interface ensuring that implementations which implement the same interface should pass the same tests.
The next steps of the project are to comprehensively document the existing code written and implement the Sets, Queues, and Stacks.
Written by Cody Stebbins who is a full-stack software engineer living in Austin, TX. Twitter