A comprehensive implementation of fundamental data structures in Java, built from scratch without using Java's built-in collection classes. This library was developed as part of my computer science coursework to deepen my understanding of how data structures work at a fundamental level.
This library provides implementations of core data structures that are essential in computer science. Each data structure has been implemented manually, giving insight into their internal mechanisms, performance characteristics, and trade-offs. The codebase reflects an iterative development approach with practical problem-solving patterns.
A resizable array that automatically grows when capacity is exceeded and shrinks when too much space is unused. This provides the convenience of a list with the efficiency of array-based access.
Key Operations:
add(element)- Adds an element to the end (O(1) amortized)add(index, element)- Inserts at a specific position (O(n))get(index)- Retrieves an element (O(1))remove(index)- Removes an element (O(n))size()- Returns the number of elements (O(1))
Complexity Analysis:
- Time: Most operations are O(1) except insertion and removal at specific indices which are O(n) due to element shifting
- Space: O(n) where n is the number of elements
Design Decisions:
- Uses a growth factor of 1.5 to balance between frequent resizing and memory waste
- Implements shrinking when utilisation drops below 25% to manage memory efficiently
- Initial capacity of 10 provides a reasonable starting point for most use cases
A linked list where each node points to the next node. Useful when frequent insertions and deletions are needed at various positions, though sequential access is required.
Key Operations:
add(element)- Adds to the end (O(n))addFirst(element)- Adds to the beginning (O(1))add(index, element)- Inserts at index (O(n))remove(element)- Removes first occurrence (O(n))get(index)- Retrieves element at index (O(n))
Complexity Analysis:
- Time: Access by index is O(n), but insertion/deletion at known positions can be O(1) with proper node references
- Space: O(n) for storing n elements plus overhead of node pointers
Use Cases:
- When you need frequent insertions/deletions but don't need random access
- Implementing stacks and queues
- Memory-efficient when size is unpredictable
Similar to SinglyLinkedList but each node maintains references to both the next and previous nodes. This enables efficient bidirectional traversal.
Key Operations:
- All operations similar to SinglyLinkedList
- Optimised traversal: chooses to traverse from head or tail based on index position
getFirst()andgetLast()- Constant time access to endpoints
Complexity Analysis:
- Time: Similar to SinglyLinkedList but with optimised traversal (O(n/2) in best case)
- Space: O(n) with slightly more overhead due to additional prev pointers
Design Decisions:
- Traversal direction is chosen based on index position relative to size/2 for efficiency
- Tail pointer maintains O(1) insertion at the end
Stack implementation using a dynamic array as the underlying storage. Follows Last In First Out (LIFO) principle.
Key Operations:
push(element)- Adds element to top (O(1) amortized)pop()- Removes and returns top element (O(1))peek()- Returns top element without removing (O(1))isEmpty()- Checks if stack is empty (O(1))
Complexity Analysis:
- Time: All operations are O(1) due to array-based access
- Space: O(n) where n is the maximum number of elements
Use Cases:
- Expression evaluation
- Function call stack simulation
- Undo/redo functionality
- Balanced parentheses checking
Stack implementation using a linked list. Provides O(1) operations without the need for resizing, but with slightly more memory overhead per element.
Key Operations:
- Same interface as ArrayStack
- All operations are guaranteed O(1) without amortisation
Complexity Analysis:
- Time: All operations are O(1) worst case
- Space: O(n) with node overhead
Trade-offs:
- No resizing overhead but more memory per element
- Better when exact memory requirements are unknown
Queue implementation using a dynamic array. Follows First In First Out (FIFO) principle. This implementation shifts elements when dequeuing, making it less efficient than CircularQueue.
Key Operations:
enqueue(element)- Adds element to rear (O(1) amortized)dequeue()- Removes and returns front element (O(n) due to shifting)peek()- Returns front element (O(1))
Complexity Analysis:
- Time: Enqueue is O(1) but dequeue requires O(n) to shift elements
- Space: O(n)
Design Note:
- While functional, the O(n) dequeue operation makes this less efficient than CircularQueue
- Included to demonstrate different implementation approaches
Efficient queue implementation using a circular buffer. Eliminates the need for element shifting by using modulo arithmetic to wrap around the array.
Key Operations:
enqueue(element)- Adds to rear (O(1))dequeue()- Removes from front (O(1))peek()- Returns front element (O(1))isFull()- Checks if queue is at capacity (O(1))
Complexity Analysis:
- Time: All operations are O(1)
- Space: O(n) where n is the fixed capacity
Design Decisions:
- Uses fixed capacity (unlike ArrayQueue) for simplicity and guaranteed O(1) operations
- Modulo arithmetic handles wrap-around when rear reaches end of array
- Front and rear indices reset when queue becomes empty
Use Cases:
- When maximum queue size is known in advance
- Systems requiring predictable memory usage
- Buffering in networking and I/O operations
Hash table implementation with chaining for collision resolution. Uses linked lists (buckets) at each index to handle hash collisions.
Key Operations:
put(key, value)- Associates value with key (O(1) average, O(n) worst case)get(key)- Retrieves value by key (O(1) average, O(n) worst case)remove(key)- Removes key-value mapping (O(1) average, O(n) worst case)containsKey(key)- Checks if key exists (O(1) average)
Complexity Analysis:
- Time: Average case O(1) for all operations, worst case O(n) if all keys hash to same bucket
- Space: O(n) where n is the number of key-value pairs
Design Decisions:
- Chaining chosen over open addressing for simplicity and to avoid clustering issues
- Load factor of 0.75 triggers resizing to maintain performance
- Initial capacity of 16 balances memory usage and collision probability
- Resizing doubles capacity and rehashes all entries
Hash Function:
- Uses Java's hashCode() with bitwise AND to ensure positive indices
- Modulo operation maps hash code to bucket index
A binary tree where each node's left subtree contains values less than the node, and right subtree contains values greater. Provides efficient search, insertion, and deletion when tree remains balanced.
Key Operations:
insert(key, value)- Adds or updates key-value pair (O(log n) average, O(n) worst)search(key)- Finds value by key (O(log n) average, O(n) worst)delete(key)- Removes node with key (O(log n) average, O(n) worst)contains(key)- Checks if key exists (O(log n) average)- Traversal methods:
inOrderTraversal(),preOrderTraversal(),postOrderTraversal()
Complexity Analysis:
- Time: Average case O(log n) for search/insert/delete, O(n) for traversals. Worst case O(n) if tree becomes unbalanced
- Space: O(n) for storing n nodes
Design Decisions:
- Recursive implementation for clarity and alignment with tree structure
- In-order successor used for deletion when node has two children
- Height calculation included for tree analysis
- No self-balancing (AVL/Red-Black) to keep implementation focused on core BST concepts
Use Cases:
- Maintaining sorted data with dynamic updates
- Implementing ordered maps and sets
- Range queries and finding nearest values
DynamicArray<String> array = new DynamicArray<>();
array.add("Hello");
array.add("World");
array.add(1, "Beautiful"); // Insert at index 1
System.out.println(array.get(0)); // "Hello"
System.out.println(array.size()); // 3SinglyLinkedList<Integer> list = new SinglyLinkedList<>();
list.add(10);
list.add(20);
list.addFirst(5); // Adds to beginning
System.out.println(list.get(0)); // 5
list.remove(20);ArrayStack<String> stack = new ArrayStack<>();
stack.push("first");
stack.push("second");
stack.push("third");
System.out.println(stack.pop()); // "third"
System.out.println(stack.peek()); // "second"CircularQueue<Integer> queue = new CircularQueue<>(10);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
System.out.println(queue.dequeue()); // 1
System.out.println(queue.peek()); // 2HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 5);
map.put("banana", 10);
map.put("apple", 7); // Updates existing key
System.out.println(map.get("apple")); // 7
System.out.println(map.containsKey("banana")); // trueBinarySearchTree<Integer, String> tree = new BinarySearchTree<>();
tree.insert(5, "five");
tree.insert(3, "three");
tree.insert(7, "seven");
tree.insert(1, "one");
System.out.println(tree.search(3)); // "three"
DynamicArray<Integer> sorted = tree.inOrderTraversal(); // Returns [1, 3, 5, 7]This project uses Maven for dependency management and building.
- Java 11 or higher
- Maven 3.6 or higher
mvn clean compilemvn testmvn packageThis will create a JAR file in the target directory.
java-data-structures/
├── src/
│ ├── main/
│ │ └── java/
│ │ └── com/
│ │ └── datastructures/
│ │ ├── DynamicArray.java
│ │ ├── SinglyLinkedList.java
│ │ ├── DoublyLinkedList.java
│ │ ├── ArrayStack.java
│ │ ├── LinkedStack.java
│ │ ├── ArrayQueue.java
│ │ ├── CircularQueue.java
│ │ ├── HashMap.java
│ │ └── BinarySearchTree.java
│ └── test/
│ └── java/
│ └── com/
│ └── datastructures/
│ └── [Test files]
├── pom.xml
└── README.md
| Data Structure | Access | Search | Insertion | Deletion | Space |
|---|---|---|---|---|---|
| DynamicArray | O(1) | O(n) | O(1)* | O(n) | O(n) |
| SinglyLinkedList | O(n) | O(n) | O(1) | O(n) | O(n) |
| DoublyLinkedList | O(n) | O(n) | O(1) | O(1) | O(n) |
| ArrayStack | - | - | O(1)* | O(1) | O(n) |
| LinkedStack | - | - | O(1) | O(1) | O(n) |
| ArrayQueue | - | - | O(1)* | O(n) | O(n) |
| CircularQueue | - | - | O(1) | O(1) | O(n) |
| HashMap | O(1)* | O(1)* | O(1)* | O(1)* | O(n) |
| BinarySearchTree | O(log n)* | O(log n)* | O(log n)* | O(log n)* | O(n) |
*Average case complexity. Worst case may differ. See individual data structure documentation for details.
This library was developed with a focus on learning and understanding rather than production optimisation. The implementations prioritise:
- Clarity: Code is written to be understandable, with comments explaining key decisions
- Educational Value: Each implementation demonstrates core concepts without hiding complexity
- Completeness: All fundamental operations are implemented to provide full functionality
- Realistic Development: Code shows iterative refinement and practical problem-solving approaches
Some design choices reflect a learning journey - for example, ArrayQueue uses element shifting despite inefficiency, demonstrating different implementation strategies. The HashMap uses chaining as it's more straightforward to understand than open addressing techniques.
Potential enhancements that could be made:
- Self-balancing BST (AVL or Red-Black tree)
- Open addressing for HashMap (linear probing, quadratic probing)
- Iterator implementations for traversal
- Thread-safe versions
- More sophisticated resizing strategies
- Performance benchmarking utilities
This project is for educational purposes as part of university coursework.
This library represents my exploration of fundamental data structures. Implementing these from scratch has provided invaluable insight into their internal workings, performance characteristics, and trade-offs. The code reflects genuine learning and iterative development, including various approaches and refinements made during the implementation process.
Understanding these structures at this level is crucial for making informed decisions about which data structure to use in different scenarios, and for appreciating the sophisticated implementations found in standard libraries.