The data structures project
Data structures are amongst the most fundamental ingredients in the recipe for efficient algorithms and good software design. Knowledge of how to create and design excellent data structures is an essential skill required in becoming an exemplary programmer. The goal of this repository is to provide a complete and thorough explanation of the most common data structures.
- Balanced Trees
- Binary Search Tree
- Bloom Filter
- Dynamic Array
- Fenwick Tree
- Linked List
- Priority Queue
- Quad Tree [WIP]
- Segment Tree
- Skip List [UNTESTED]
- Suffix Array
- Union Find
This repository is contribution friendly
This project uses Gradle as a build system and for testing. To get started install the gradle command-line tool and run the build command to make sure you don't get any errors:
data-structures$ gradle build
Adding a new data structure
The procedure to add a new data structure named Foo is the following:
- Create a new folder called Foo in com/williamfiset/datastrutures/Foo
- Add the data structure implementation for Foo in com/williamfiset/datastrutures/Foo/Foo.java
- Add tests for Foo in javatests/com/williamfiset/datastrutures/Foo/FooTest.java
- Edit the build.gradle file and add Foo to the project.
- Add tests for your data structure
- Send pull request for review
This repository places a large emphasis on good testing practice to ensure that published data structures are bug free and high quality. Testing is done using a combinations of frameworks including: JUnit, Mockito and the Google Truth framework, but mostly JUnit.
When developing you likely do not want to run all tests but only a subset of them. For example, if you want to run the LinkedListTest.java file under javatests/com/williamfiset/datastructures/linkedlist/LinkedListTest.java you can execute:
data-structures$ gradle test --tests "javatests.com.williamfiset.datastructures.linkedlist.LinkedListTest"
Sometimes there are many test files for one data structure. One example is the
gradle test --tests "javatests.com.williamfiset.datastructures.fenwicktree.FenwickTree*Test"
This repository is released under the MIT license. In short, this means you are free to use this software in any personal, open-source or commercial projects. Attribution is optional but appreciated.