Skip to content

README.md

Latest commit

 

History

History
112 lines (96 loc) · 4.97 KB

README.md

File metadata and controls

112 lines (96 loc) · 4.97 KB

DSA Implementations

This repository contains custom implementations of various data structures in Java. The project explores different algorithmic optimizations for standard operations.

Contents

The DSA directory contains the source code and documentation for the following:

1. Queue using Stacks

  • QueueStackPushFriendly.java: Implementation where the Enqueue operation is O(1).
  • QueueStackPopFriendly.java: Implementation where the Dequeue operation is O(1).

2. Stack using Queues

  • StackQueueEnqueueFriendly.java: Implementation where the Push operation (via Enqueue) is O(1).
  • StackQueueDequeueFriendly.java: Implementation where the Pop operation (via Dequeue) is O(1).

3. Unbounded Stack

  • UnboundedArrayStack.java: A stack implementation using a dynamically resizing array. It doubles in size when full and shrinks when one-quarter full to optimize memory usage.

4. Circular Queue

  • ArrayCircularQueue.java: A queue implementation using a circular array for efficient space utilization.

5. Linked Lists

  • SinglyLinkedList.java: A singly linked list implementation with forward traversal only.
  • DoublyLinkedList.java: A doubly linked list implementation with bidirectional traversal.
  • CircularDoublyLinkedList.java: A circular doubly linked list implementation with bidirectional traversal and circular connections.
  • LinkedListStack.java: A stack implementation using a linked list (O(1) push/pop).
  • LinkedListFIFOQueue.java: A FIFO queue implementation using a linked list (O(1) enqueue/dequeue).

6. Mathematical Problems

  • RabbitProblem.java: Implementation of the classic rabbit population growth problem with multiple algorithmic approaches (recursive, memoization, and iterative).

7. Sorting Algorithms

  • BubbleSort.java: Standard Bubble Sort implementation.
  • OptimizedBubbleSort.java: Bubble Sort with a flag to stop early if sorted.
  • InsertionSort.java: Standard Insertion Sort implementation.
  • OptimizedInsertionSort.java: Binary Insertion Sort (uses binary search for finding position).
  • SelectionSort.java: Standard Selection Sort implementation.
  • MergeSort.java: Recursive Merge Sort implementation (Divide and Conquer).
  • QuickSort.java: Recursive Quick Sort implementation (Divide and Conquer).
  • OptimizedQuickSort.java: Quick Sort with randomized pivot and 3-way partitioning.
  • HanoiTower.java: Recursive solution to the Tower of Hanoi problem.

8. Trees

  • BinarySearchTree.java: Basic Binary Search Tree (BST) implementation.
  • AVLTree.java: Self-balancing Binary Search Tree (AVL Tree) implementation.

Documentation

Detailed explanations of the logic and complexity for each implementation can be found in the accompanying markdown files:

  • DSA/QueueStackDocs.md
  • DSA/UnboundedStackDocs.md
  • DSA/StackQueueDocs.md
  • DSA/StackQueueDequeueFriendlyDocs.md
  • DSA/ArrayCircularQueueDocs.md
  • DSA/SinglyLinkedListDocs.md
  • DSA/DoublyLinkedListDocs.md
  • DSA/CircularDoublyLinkedListDocs.md
  • DSA/LinkedListStackDocs.md
  • DSA/LinkedListFIFOQueueDocs.md
  • DSA/RabbitProblemDocs.md
  • DSA/BubbleSortDocs.md
  • DSA/OptimizedBubbleSortDocs.md
  • DSA/InsertionSortDocs.md
  • DSA/OptimizedInsertionSortDocs.md
  • DSA/SelectionSortDocs.md
  • DSA/MergeSortDocs.md
  • DSA/QuickSortDocs.md
  • DSA/OptimizedQuickSortDocs.md
  • DSA/HanoiTowerDocs.md
  • DSA/BinarySearchTreeDocs.md
  • DSA/AVLTreeDocs.md

Time Complexity Summary

Data Structure / Algorithm Operation / Case Complexity
QueueStackPushFriendly Enqueue O(1)
QueueStackPushFriendly Dequeue Amortized O(1)
QueueStackPopFriendly Enqueue O(n)
QueueStackPopFriendly Dequeue O(1)
StackQueueEnqueueFriendly Push O(1)
StackQueueEnqueueFriendly Pop O(n)
StackQueueDequeueFriendly Push O(n)
StackQueueDequeueFriendly Pop O(1)
ArrayCircularQueue Enqueue O(1)
ArrayCircularQueue Dequeue O(1)
UnboundedArrayStack Push Amortized O(1)
UnboundedArrayStack Pop Amortized O(1)
SinglyLinkedList Add First O(1)
SinglyLinkedList Add Last O(n)
SinglyLinkedList Remove First O(1)
SinglyLinkedList Remove Last O(n)
SinglyLinkedList Access by Index O(n)
DoublyLinkedList Add First O(1)
DoublyLinkedList Add Last O(1)
DoublyLinkedList Remove First O(1)
DoublyLinkedList Remove Last O(1)
DoublyLinkedList Access by Index O(n)
Bubble Sort Average/Worst O(n^2)
Optimized Bubble Sort Best Case O(n)
Insertion Sort Average/Worst O(n^2)
Optimized Insertion Sort Comparisons O(n log n)
Selection Sort All Cases O(n^2)
Merge Sort All Cases O(n log n)
Quick Sort Average Case O(n log n)
Quick Sort Worst Case O(n^2)
Optimized Quick Sort Average Case O(n log n)
Binary Search Tree Search/Insert O(h)
AVL Tree Search/Insert O(log n)

Built by Ronith