d2s is a clean, educational, and modular implementation of fundamental Data Structures and Algorithms (DSA) in Java 21. Built from the ground up without relying on Java's built-in collection classes (java.util.*), the project demonstrates core memory layouts, abstract data type (ADT) design patterns, and algorithmic mechanics.
- Overview
- Key Features
- Implemented Data Structures
- Architecture & Design Principles
- Project Structure
- Getting Started
Modern software often abstracts away underlying memory layouts and algorithmic nuances behind standard libraries. d2s explores and explains these structures by implementing them natively:
- Self-contained: Data structures reuse custom-built components rather than Java collections (e.g.,
ArrayBasedStackis backed byArrayList,LinkedListQueueis backed byDoublyLinkedList, andBinarySearchTree's level-order iterator usesLinkedListQueue). - ADT-Driven: Each data structure defines an interface contract specifying behavior, supported operations, and constraints.
- Fail-Fast & Safe: Modifiable collections track state updates using modification counters (
modificationCount) to detect concurrent modifications during iteration.
-
ListADT<T>: Common interface for sequential collections extendingIterable<T>.- Core operations:
size(),isEmpty(),clear(),addFirst(),addLast(),add(index, data),get(index),set(index, data),removeFirst(),removeLast(),removeAt(index),remove(object),indexOf(object),contains(object).
- Core operations:
-
ArrayList<T>(dsa.list.arraylist):- Dynamic array implementation with automatic geometric resizing (
grow()). - Supports random access by index in
$O(1)$ time. - Linear-time shifting for insertions and deletions at non-tail positions.
- Dynamic array implementation with automatic geometric resizing (
-
SinglyLinkedList<T>(dsa.list.linkedlist.singly):- Unidirectional linked list with node pointers (
head,tail). - Constant-time
$O(1)$ head insertion and deletion.
- Unidirectional linked list with node pointers (
-
DoublyLinkedList<T>(dsa.list.linkedlist.doubly):- Bidirectional linked list with
prevandnextpointers. - Constant-time
$O(1)$ insertions and removals at both ends (headandtail).
- Bidirectional linked list with
-
StackADT<T>: Standard LIFO (Last-In, First-Out) interface.- Methods:
push(element),pop(),top(),size(),isEmpty().
- Methods:
-
ArrayBasedStack<T>:- Stack implemented on top of the custom
ArrayList<T>. - Amortized
$O(1)$ push and pop operations with zero reliance onjava.util.Stack.
- Stack implemented on top of the custom
-
QueueADT<T>: Standard FIFO (First-In, First-Out) interface extendingIterable<T>.- Methods:
enQueue(element),deQueue(),peek(),size(),isEmpty().
- Methods:
-
LinkedListQueue<T>:- Queue implemented using the custom
DoublyLinkedList<T>. - Guaranteed
$O(1)$ enqueue and dequeue operations without memory waste from shifts.
- Queue implemented using the custom
-
HashTableADT<K, V>: Key-value associative mapping interface extendingIterable<K>.- Methods:
insert(key, value),get(key),remove(key),has(key),size(),isEmpty(),clear().
- Methods:
-
Separate Chaining (
dsa.hashtable.separatechaining):-
SeparateChainingHashTable<K, V>resolves collisions using buckets ofDoublyLinkedList<Node<K, V>>. - Automatic table resizing and rehashing when load factor exceeds threshold.
-
-
Open Addressing (
dsa.hashtable.openaddressing):-
OpenAddressingHashTable<K, V>uses contiguous memory slots with tombstone markers for deleted elements. - Configurable collision resolution strategies:
-
LinearProbe:$h(k, i) = (h(k) + i) \pmod N$ -
QuadraticProbe:$h(k, i) = (h(k) + c_1 i + c_2 i^2) \pmod N$ -
DoubleHashingProbingStrategy:$h(k, i) = (h_1(k) + i \cdot h_2(k)) \pmod N$
-
- Flexible capacity policies:
-
PrimeCapacityPolicy: Ensures bucket capacity is always prime. -
PowerOfTwoCapacityPolicy: Keeps capacity as powers of 2 for bitwise masking. -
LinearProbingCapacityPolicy: Dynamic growth tailored to linear probing constraints.
-
-
OpenAddressingHashTableFactory: Fluent helper for building preconfigured hash table variants.
-
-
TreeADT<T extends Comparable<T>>: Binary Search Tree interface extendingIterable<T>.- Methods:
add(element),remove(element),contains(element),height(),findMin(),findMax(),size(),isEmpty(),clear(),traverse(order).
- Methods:
-
BinarySearchTree<T>:- Binary search tree ordering property: left subtree
$\le$ node$<$ right subtree. - Node deletion handling all three cases: leaf node, single child, and two children (using in-order successor).
- Four iterative traversal orders (non-recursive, maintaining traversal state on the heap):
-
PRE_ORDER: Node$\to$ Left$\to$ Right (usingArrayBasedStack). -
IN_ORDER: Left$\to$ Node$\to$ Right (produces sorted order; default iterator). -
POST_ORDER: Left$\to$ Right$\to$ Node (using two stacks). -
LEVEL_ORDER: Breadth-First Search level by level (usingLinkedListQueue).
-
- Fail-fast traversal with
ConcurrentModificationExceptionon structural mutations during iteration.
- Binary search tree ordering property: left subtree
-
Layered Interfaces: High-level abstract data types (
*ADT) decouple consumers from underlying implementations. -
Reusability across Modules: Higher-level data structures reuse lower-level primitives created in this repository:
-
ArrayBasedStack$\to$ ArrayList -
LinkedListQueue$\to$ DoublyLinkedList -
SeparateChainingHashTable$\to$ DoublyLinkedList -
BinarySearchTree.LevelOrderIterator$\to$ LinkedListQueue -
BinarySearchTree.PreOrderIterator$\to$ ArrayBasedStack
-
- Comprehensive Unit Testing: Every structure has full test coverage under JUnit 5, validating edge cases (empty states, null inputs, capacity expansion, duplicate handling, and concurrent modification checks).
d2s/
├── app/
│ ├── src/
│ │ ├── main/java/io/github/arisnguyen/d2s/
│ │ │ ├── App.java
│ │ │ └── dsa/
│ │ │ ├── hashtable/
│ │ │ │ ├── HashTableADT.java
│ │ │ │ ├── Node.java
│ │ │ │ ├── openaddressing/
│ │ │ │ │ ├── capacity/
│ │ │ │ │ ├── probing/
│ │ │ │ │ ├── OpenAddressingHashTable.java
│ │ │ │ │ └── OpenAddressingHashTableFactory.java
│ │ │ │ └── separatechaining/
│ │ │ │ └── SeparateChainingHashTable.java
│ │ │ ├── list/
│ │ │ │ ├── ListADT.java
│ │ │ │ ├── arraylist/
│ │ │ │ │ ├── ArrayList.java
│ │ │ │ │ └── ArrayListADT.java
│ │ │ │ └── linkedlist/
│ │ │ │ ├── LinkedListADT.java
│ │ │ │ ├── Node.java
│ │ │ │ ├── doubly/
│ │ │ │ └── singly/
│ │ │ ├── queue/
│ │ │ │ ├── LinkedListQueue.java
│ │ │ │ └── QueueADT.java
│ │ │ ├── stack/
│ │ │ │ ├── ArrayBasedStack.java
│ │ │ │ └── StackADT.java
│ │ │ └── tree/
│ │ │ ├── BinarySearchTree.java
│ │ │ ├── Node.java
│ │ │ ├── TreeADT.java
│ │ │ └── TreeTraversalOrder.java
│ │ └── test/java/io/github/arisnguyen/d2s/
│ │ ├── AppTest.java
│ │ └── dsa/
│ │ ├── hashtable/
│ │ ├── list/
│ │ ├── queue/
│ │ ├── stack/
│ │ └── tree/
│ └── build.gradle
├── gradle/
├── gradlew
├── gradlew.bat
├── settings.gradle
└── README.md
- Java: JDK 21 or higher
- Gradle: Gradle 9.x (or use the included
./gradlewwrapper)
Compile the project:
./gradlew buildRun the application:
./gradlew runExecute the comprehensive test suite:
./gradlew testTo force rerun all unit tests and view the output report:
./gradlew test --rerunTest reports are generated in HTML format at app/build/reports/tests/test/index.html.