Rung 2 — Data Structure Library from Scratch

Month: M2–M3 | Mode: Implementation | Platform: GitHub (public)

There is a meaningful difference between a developer who can use a HashMap and a developer who can build one. The first can call map.get(key). The second understands why that call is O(1) amortized, what happens when the load factor exceeds 0.75, and what separate chaining looks like at the memory layout level. This rung is about becoming the second kind of developer.

Every data structure you implement here will later be used — sometimes literally, always conceptually — in LeetCode hard problems and Codeforces problems. When you understand the mechanism, the problem becomes a question about mechanism. When you don’t, it remains a question about memorized syntax.

What It Is

A GitHub repository named ds-from-scratch containing clean, tested implementations of 7 fundamental data structures. Each implementation is written by you, from your understanding, in a language you’re comfortable with (Java, C, or C++ — all work).

The constraint that matters: no copy-paste from Stack Overflow, no AI generation. You can use a reference (CLRS, a textbook, your own notes) to understand the algorithm, but the code must be yours. The tests must be yours. The README for each structure must be yours.

The 7 Data Structures

1. Dynamic Array

A resizable array that doubles in capacity when full.

Must implement:

  • push(element) — append to end, resize if needed

  • get(index) — O(1) access

  • set(index, element) — O(1) update

  • delete(index) — shift elements, O(n)

  • size() and capacity() — both exposed

  • Internal: private resize() that doubles capacity and copies

Key design decision to document: Why doubling (not +1, not +10)? What growth factor produces O(1) amortized push?

Test cases (minimum 10):

  • Push elements until a resize is triggered; verify capacity doubled

  • Get on empty array throws exception or returns sentinel

  • Delete at index 0, middle, last

  • Push 1000 elements; verify size is 1000 and all are retrievable

  • Edge: delete the only element

2. Doubly Linked List

A linked list with both next and prev pointers per node.

Must implement:

  • insertFront(element)

  • insertBack(element)

  • insertAfter(node, element)

  • delete(node) — O(1) given the node

  • find(element) — O(n) search returning node or null

  • toArray() — for test assertions

Key design decision to document: Why O(1) delete given the node? What does having both pointers enable that a singly linked list cannot do?

Test cases (minimum 10):

  • Insert front + insert back: verify ordering

  • Delete head, tail, middle node

  • Insert after a specific node

  • Find element that doesn’t exist

  • Delete the only node (list becomes empty)

3. Stack (Array-backed)

A LIFO stack backed by a dynamic array (use your own Dynamic Array if done, or the language’s built-in array with manual size tracking).

Must implement:

  • push(element)

  • pop() — returns top element, raises exception if empty

  • peek() — returns top without removing

  • isEmpty()

  • size()

Key design decision to document: Array-backed stack vs. linked-list-backed stack — trade-offs in memory allocation pattern and cache performance.

Test cases (minimum 10):

  • Push N elements, pop all N in reverse order

  • Pop on empty stack: exception or error

  • Peek doesn’t modify the stack

  • Interleaved push/pop

  • Stack with a single element: push, peek, pop, confirm empty

4. Queue (Circular Buffer)

A FIFO queue backed by a fixed-size circular buffer (array with front and rear pointers modulo capacity).

Must implement:

  • enqueue(element) — add to rear

  • dequeue() — remove from front

  • peek() — return front without removing

  • isFull(), isEmpty(), size()

  • Internal: pointer arithmetic using % capacity

Key design decision to document: Why circular buffer instead of a simple array with shifting? What makes both enqueue and dequeue O(1)?

Test cases (minimum 10):

  • Enqueue until full, verify isFull

  • Dequeue from empty: exception or error

  • Enqueue 5, dequeue 3, enqueue 3 more — verify wrap-around works

  • Size stays correct across interleaved enqueue/dequeue

  • Enqueue 1 element, dequeue it, enqueue again (reuse slot)

5. Min-Heap

A binary min-heap backed by an array, where parent(i) = (i-1)/2, left(i) = 2i+1, right(i) = 2i+2.

Must implement:

  • insert(element) — push to end, heapify-up

  • extractMin() — swap root with last, pop, heapify-down

  • peekMin() — return root without removing

  • size()

  • Internal: heapifyUp(index) and heapifyDown(index)

Key design decision to document: Why array indexing works for a binary tree. Why heapify-up is O(log n) — derive via height of tree.

Test cases (minimum 10):

  • Insert [5, 3, 8, 1, 4]: extractMin should return 1, then 3, then 4…

  • Insert duplicate values

  • Extract from a 1-element heap

  • Extract from empty heap: exception

  • Insert 100 random integers, extract all: verify sorted ascending

6. HashMap (Separate Chaining)

A hash map using an array of linked lists (buckets) with a load factor threshold that triggers rehashing.

Must implement:

  • put(key, value) — insert or update

  • get(key) — returns value or null/exception

  • delete(key)

  • containsKey(key)

  • size()

  • Internal: hash(key) function, rehash() when load factor > 0.75

Key design decision to document: Why load factor 0.75 is a common threshold. What happens to average chain length as load factor increases. Why rehashing doubles the bucket count.

Test cases (minimum 10):

  • Put 10 keys, get all 10

  • Update an existing key: get returns new value

  • Delete a key, confirm containsKey returns false

  • Get on missing key: null or exception

  • Put enough keys to trigger rehash: all keys still retrievable after rehash

  • Hash collision: two keys that map to same bucket, both retrievable

7. Trie

A prefix tree for string keys.

Must implement:

  • insert(word) — add word to trie

  • search(word) — return true if exact word exists

  • startsWith(prefix) — return true if any word has this prefix

  • delete(word) — remove word (mark end-of-word flag, prune dead branches optional)

Key design decision to document: Why Trie search is O(L) where L is word length (not O(n) where n is number of words). When a Trie outperforms a HashMap for string keys.

Test cases (minimum 10):

  • Insert [“apple”, “app”, “application”]: search(“app”) = true, search(“ap”) = false

  • startsWith(“app”) = true, startsWith(“ban”) = false

  • Delete “app”: search(“app”) = false, search(“apple”) = true (subtree preserved)

  • Insert and search empty string (edge case)

  • Insert same word twice: no duplication, search still returns true

Repository Structure

ds-from-scratch/
├── README.md                    ← Overview + links to each DS
├── dynamic-array/
│   ├── DynamicArray.java        ← (or .c / .cpp)
│   ├── DynamicArrayTest.java
│   └── README.md
├── doubly-linked-list/
│   ├── DoublyLinkedList.java
│   ├── DoublyLinkedListTest.java
│   └── README.md
├── stack/
│   ├── Stack.java
│   ├── StackTest.java
│   └── README.md
├── queue/
│   ├── CircularQueue.java
│   ├── CircularQueueTest.java
│   └── README.md
├── min-heap/
│   ├── MinHeap.java
│   ├── MinHeapTest.java
│   └── README.md
├── hashmap/
│   ├── HashMap.java
│   ├── HashMapTest.java
│   └── README.md
└── trie/
    ├── Trie.java
    ├── TrieTest.java
    └── README.md

Acceptance Criteria

  • All 7 data structures implemented

  • All test files present with minimum 10 tests each

  • All tests pass (run them; don’t just write them)

  • Each data structure has its own README.md with: what it is, key design decisions, complexity table

  • A peer can read the code and understand what it does without you explaining it

  • No AI-generated code (the point is that you built the understanding, not the file)

  • Repo is public and linked from your GitHub profile

Where to Publish

  1. Create a public GitHub repository named ds-from-scratch

  2. Top-level README.md links to each data structure’s subdirectory

  3. Include a complexity table at the top: operation | DS | time | space

  4. Add to portfolio README and optionally pin to GitHub profile alongside complexity-audit

Signal It Sends

“This person can implement abstractions from scratch, not just use library functions.”

The bar for this signal is surprisingly low to meet but very few people actually do it. Every working engineer uses data structures daily. Maybe 10% have ever implemented a hash map. Maybe 2% have implemented one with proper rehashing and tests. A public repo with 7 clean implementations and 70+ passing tests is a concrete artifact that takes “I know data structures” from a claim to a fact.

It also separates you from engineers who learned DS for interviews and forgot them afterward. This repo becomes a reference you’ll actually use.

Practical Notes

  • Start with Dynamic Array. It’s the simplest and establishes the pattern (implementation file + test file + README) you’ll replicate six more times.

  • The Min-Heap is the most transferable. Heap operations appear constantly in graph algorithms (Dijkstra), scheduling, and stream processing. Get it right.

  • The HashMap is the most conceptually rich. Budget extra time. The rehashing logic is where most first-time implementations have bugs.

  • For testing: use your language’s built-in test framework (JUnit for Java, assert for C/C++ with a test runner). If you don’t know a test framework, write a main() that prints PASS/FAIL and verifies manually — that’s fine for this purpose.

  • If you get stuck on a specific DS, look at pseudocode in CLRS or a trusted reference to understand the algorithm — then close the reference and write the code yourself.

Timeline

Week

Target

Week 1 (overlap M2)

Dynamic Array + Stack (simpler structures)

Week 2 (M2/M3)

Doubly Linked List + Circular Queue

Week 3 (M3)

Min-Heap

Week 4 (M3)

HashMap with rehashing

Week 5 (M3)

Trie

Week 6 (M3)

Review, add missing tests, clean READMEs, publish