Data Structures and Algorithms

These are my node-based implementations of common data structures and algorithms.

All implementations are done in Python, with some additional implementations also available in JavaScript.

Also includes full test suites and test coverage reports using Pytest and Jest, respectively.

Features:

• Multiple different implementations of many data structures, including graphs (using an edge list, an adjacency list, and an adjacency matrix), and hash tables (using separate chaining/open hashing, and open addressing/closed hashing).
• Both iterative and recursive implementations of:
  • Binary Trees - iterative, recursive
  • Binary Search Trees - iterative, recursive
  • K-ary Trees - iterative, recursive
  • Linked Lists - iterative, recursive
  • Also includes more advanced and non-standard versions of algorithms, such as:
    • Iterative version of DFS for binary trees.
    • Recursive version of BFS for binary trees.
    • Delete methods for BST, binary tree, or k-ary tree, both iteratively and recursively.
    • Examples of recursive implementations extracting the recursive logic into the Node class (for linked lists in Python).
    • Examples of recursive implementations keeping the recursive logic in the respective data structure (for binary trees in Python).
• Multiple implementations of quicksort:
  1. Simplified
  2. Using Lomuto's partitioning
  3. Using Hoare's partitioning

Python

Data Structures

Graphs

• Graph - with Adjacency Matrix
• Graph - with Adjacency List
• Graph - with Edge List

Hash Tables

• Hash Table - with Open Addressing/Closed Hashing - with double hashing for the probe sequence
• Hash Table - with Separate Chaining/Open Hashing - with linked lists for each bucket

Trees

• K-ary Tree - Fully Recursion
• K-ary Tree - Fully Iterative
• Binary Search Tree - Fully Recursive
• Binary Search Tree - Fully Iterative
• Binary Tree - Fully Recursive
• Binary Tree - Fully Iterative

Linear Data Structures

• Singly Linked List - Fully Iterative
• Singly Linked List - Fully Recursive
• Stack - with node-based implementation
• Queue - with node-based implementation

Algorithms

Searching

Search Algorithms

• Linear Search
• Binary Search

Sorting

Sorting Algorithms

• Bubble Sort
• Selection Sort
• Insertion Sort
• Merge Sort
• Quicksort, with a simplified implementation and a random pivot
• Quicksort, with Lomuto partitioning and Sedgewick's median-of-three pivot choice
• Quicksort, with Hoare partitioning and 2 different versions with different pivot choices

Other

• Fibonacci Sequence - using dynamic programming in different variations, including memoization via a closure and a space-optimized, bottom-up iterative approach.
• Generators

To Do List

• Additional Implementations:
  • Finding the height of a tree
  • Finding the depth of a node in a tree
  • Validating if a tree is balanced
  • Array-based implementations of trees
• Additional Data Structures:
  • Dynamic Array
  • Priority Queue
  • Double-ended Queue
  • Binary Heap
  • Trie
  • Binary space partitioning tree
  • Self-Balancing Trees:
    • Red-Black Tree
    • AVL Tree
    • B-tree
• Additional Graph Algorithms:
  • Dijkstra's algorithm:
    • using an array for unvisited nodes (simplified implementation)
    • using a priority queue for unvisited nodes (optimized implementation)
  • Bellman-Ford algorithm (for weighted graph with negative weights)
  • Backtracking algorithm
  • Minimum spanning tree (MST)
  • Floyd-Warshall algorithm
  • Graph coloring
  • Bidirectional sort
  • Topological sort
• Additional Sorting Algorithms
  • Bucket sort
  • Heapsort
  • Timsort - more efficient for doing multiple sorting passes by taking advantage of the current ordering
  • Radix sort
  • Counting sort
  • Shellsort
  • Implement stable versions of unstable sorting algorithms
• Other Algorithms
  • Quickselect (search)
  • Golomb Sequence
  • Unique paths problem

JavaScript

Data Structures

Graphs

• Directed Graph - Using Adjacency List

Hash Tables

• Hash Table

Trees

• Binary Tree, Binary Search Tree, and K-ary Tree with Depth First Traversal (Pre-Order, In-Order, and Post-Order)

Linear Data Structures

• Doubly Linked List
• Singly Linked List
• Stack and Queue

Algorithms

Sorting

• Merge Sort
• Insertion Sort

Other

• Business Trip - Traversing A Weighted, Directed Graph
• Hash Map Left Join
• Tree Intersection
• Tree Fizz Buzz
• Validate Brackets
• Zip Two Linked Lists

Testing

Python

From the python directory:

• Run pytest or coverage run -m pytest to run the full test suite for Python implementations.
• Run open htmlcov/index.html after running the test suite to see the coverage report in the browser.
• Run coverage run -m pytest -k <test_name> to run an individual test.

JavaScript

From the javascript directory:

• Run npm test to run the full test suite for JavaScript implementations.

Notes To Self for Future Implementations

• Many data structure methods require direct access to node objects. Instead of abstracting away the node class for reuse, try coupling separate node classes to each data structure class in future implementations. This might improve encapsulation of the data structure class.
• Try implementing dunder methods for each data structure, such as __iter__ and __next__ for iteration.