python-dsa-scratch

Data structures from scratch

🛠️ Data Structure Requirement Specs

1. Arrays & Dynamic Arrays (data_structures/arrays.py)

• Static Array Implementation
  • Implement a fixed-size array using Python's primitive ctypes array.
  • Implement __getitem__(index) and __setitem__(index, value).
  • Enforce strict index out-of-bounds error handling.
• Dynamic Array Implementation
  • Create a custom dynamic list using ctypes.
  • Track size (elements currently filled) and capacity (allocated blocks).
  • Implement automatic geometric expansion (resize to doubling capacity when full).
  • Implement automatic geometric contraction (shrink capacity by half when 1/4 full).
  • Implement append(element), insert(index, element), and delete(index).

2. Linked Lists (data_structures/linked_lists.py)

• Singly Linked List
  • Create a Node class with pointers data and next.
  • Implement insert_at_head(), insert_at_tail(), and delete_node(value).
  • Implement reverse_list() (In-place pointer reversal).
• Doubly Linked List
  • Modify Node to include pointers prev and next.
  • Track both head and tail nodes within the list instance.
  • Implement bidirectional traversal methods.
• Circular Linked List
  • Connect the tail.next reference back to the head node.
  • Implement split-list operations and cyclic infinite loop detection.

3. Stacks (data_structures/stacks.py)

• Static Array-Based Stack
  • Initialize with a strict maximum bound capacity constraint.
  • Track top element index location explicitly.
  • Implement push(), pop(), peek(), is_empty(), and is_full().
• Linked-List-Based Stack
  • Create a dynamic stack without bound limitations using your Node class.
  • Set insertions and deletions to point directly at the head node for $O(1)$ operations.
  • Implement push(), pop(), and peek().

4. Queues (data_structures/queues.py)

• Circular Array-Based Queue
  • Allocate a fixed-size underlying container array.
  • Explicitly track tracking indices front and rear.
  • Use modular arithmetic: rear = (rear + 1) % capacity for bounds management.
  • Implement enqueue(), dequeue(), is_empty(), and is_full().
• Linked-List-Based Queue
  • Track distinct front pointers and rear pointers inside the tracking instance.
  • Implement enqueue() at the tail node and dequeue() at the head node.

5. Double-Ended Queues / Deques (data_structures/deques.py)

• Circular Array Deque
  • Build using a fixed size array base layout with circular pointer wrapping.
  • Implement add_first(), add_last(), remove_first(), and remove_last().
• Doubly Linked List Deque
  • Build using structural pointer node modifications on both ends.
  • Implement add_first(), add_last(), remove_first(), and remove_last().

6. Hash Tables (data_structures/hash_tables.py)

• Hash Table with Chaining (Separate Chaining)
  • Implement a custom hash calculation algorithm using string polynomial conversion.
  • Resolve array collision paths using your custom Singly Linked List objects.
  • Implement put(key, value), get(key), and remove(key).
• Hash Table with Open Addressing (Linear Probing)
  • Resolve internal address conflicts by shifting sequentially down indices: (hash(k) + i) % capacity.
  • Support soft deletion using dummy tombstone sentinel objects to prevent query breakages.
  • Implement automatic dynamic map resizes when load balancing metrics cross a 0.70 threshold.

7. Trees & Priority Queues (data_structures/trees.py)

• Binary Search Tree (BST)
  • Implement manual pointer leaf nodes containing left, right, and value.
  • Implement recursive insert(), search(), and node-shifting delete().
  • Implement standard tree traversals: inorder(), preorder(), and postorder().
• AVL Tree (Self-Balancing Binary Search Tree)
  • Track an explicit height integer attribute directly within each tree node.
  • Calculate structural balance factors: $\text{height(left)} - \text{height(right)}$.
  • Implement balancing adjustments: left_rotate() and right_rotate().
• Binary Heap (Max/Min Priority Queue)
  • Implement using a single flattened array index structure.
  • Calculate relative positioning coordinates: $\text{left} = 2i + 1$, $\text{right} = 2i + 2$, $\text{parent} = \lfloor(i-1)/2\rfloor$.
  • Implement structural tree maintenance tools: sift_up() and sift_down().
  • Implement extraction engines: insert() and extract_root().

📦 python-dsa-scratch ┣ 📂 benchmarks ┃ ┣ 📜 init.py ┃ ┗ 📜 plotter.py # Helper functions to plot time/space complexity ┣ 📂 data_structures ┃ ┣ 📜 init.py ┃ ┣ 📜 arrays.py # Static and Dynamic Arrays ┃ ┣ 📜 linked_lists.py # Singly, Doubly, and Circular ┃ ┣ 📜 stacks.py # Array-based and Linked-List-based ┃ ┣ 📜 queues.py # Linear, Circular, and Linked-List-based ┃ ┣ 📜 deques.py # Array-based and Doubly Linked List ┃ ┣ 📜 hash_tables.py # Chaining and Open Addressing ┃ ┗ 📜 trees.py # BST, AVL, and Binary Heap ┣ 📜 run_benchmarks.py # Main script to execute and save plots ┗ 📜 README.md # Project roadmap