Data Structures and Algorithms in Java (DSA Tutorial)

A comprehensive, hands-on repository containing Java implementations and demonstrations of fundamental Data Structures, Classic Algorithms, and Dynamic Programming techniques.

---

📚 Table of Contents

• Overview
• Project Directory Structure
• Topics Covered
  • 1. Data Structures
  • 2. Sorting & Searching Algorithms
  • 3. Graph Algorithms
  • 4. Dynamic Programming & Optimization
• Complexity Reference Table
• Getting Started & Prerequisites
• How to Run the Demonstrations
  • Running via IntelliJ IDEA
  • Running via Command Line
• Code Conventions

---

📖 Overview

This repository serves as a practical, code-first tutorial and reference guide for core computer science concepts implemented in Java. Each topic contains self-contained demonstration files (demo_*.java) that illustrate operations, edge cases, traversals, and problem-solving strategies with clear step-by-step logic.

---

📂 Project Directory Structure

DSA-Tutorial-Java/
│
├── DSAArrays/                          # Array-based algorithms & search/sort techniques
│   ├── DSABinarySearch/               # Binary search implementations
│   ├── DSABubbleSort/                 # Bubble sort variations
│   ├── DSACountingSort/               # Counting sort implementation
│   ├── DSAInsertionSort/              # Insertion sort
│   ├── DSALinearSearch/               # Linear search
│   ├── DSAMergeSort/                  # Merge sort (divide & conquer)
│   ├── DSAQuicksort/                  # Quicksort (partitioning)
│   ├── DSARadixSort/                  # Radix sort (digit-by-digit)
│   └── DSASelectionSort/              # Selection sort
│
├── DSALinkedLists/                     # Linked list data structures and operations
│   ├── DSALinkedListsTypes/           # Singly, Doubly, and Circular Linked Lists
│   └── DSALinkedListsOperations/      # Insertion, deletion, search, reversal, and traversal
│
├── DSAStacks/                          # Stack implementations (LIFO operations)
│
├── DSAQueues/                          # Queue implementations (FIFO, Circular queues)
│
├── DSAHashTables/                      # Hash-based data structures
│   ├── DSAHashMaps/                   # Key-value associative mapping
│   └── DSAHashSets/                   # Unique value sets and collisions
│
├── DSATrees/                           # Tree data structures and algorithms
│   ├── ArrayImplBinaryTrees/          # Array-backed binary tree representations
│   ├── DSABinaryTrees/                # Standard pointer/node-based binary trees
│   ├── DSABinarySearchTrees/          # Binary Search Trees (BST search, insertion, deletion)
│   ├── DSAAVLTrees/                   # Self-balancing AVL trees (rotations & balance factors)
│   └── BinaryTreeTraversal/           # Tree traversal strategies
│       ├── BreadthFirstSearch/        # Level-order traversal
│       └── DepthFirstSearch/          # In-order, Pre-order, and Post-order traversals
│
├── DSAGraphs/                          # Graph representations and traversal algorithms
│   ├── GraphImplClasses/              # Adjacency matrix & adjacency list representations
│   ├── DSAGraphsImpl/                 # Graph construction and edge modeling
│   ├── DSAGraphsTraversal/            # Breadth-First Search (BFS) & Depth-First Search (DFS)
│   └── DSAGraphsCycleDetection/       # Cycle detection in directed and undirected graphs
│
├── DSAShortestPath/                    # Shortest path algorithms on graphs
│   ├── DSADijkstrasAlgorithm/         # Dijkstra's Algorithm (single-source, non-negative weights)
│   └── DSABellmanFordAlgorithm/       # Bellman-Ford Algorithm (supports negative edge weights)
│
├── DSAMinimumSpanningTree/             # Minimum Spanning Tree (MST) algorithms
│   ├── DSAPrimsAlgorithm/             # Prim's algorithm (greedy vertex-based)
│   └── DSAKruskalsAlgorithm/          # Kruskal's algorithm (greedy edge-based + Disjoint Set / Union-Find)
│
├── DSADynamicProgramming/              # Foundational dynamic programming examples
├── DSAMemoization/                     # Top-down dynamic programming with memo tables
├── DSATabulation/                      # Bottom-up dynamic programming with iterative state tables
├── DSAKnapsackProblem/                 # 0/1 Knapsack Problem (brute-force, memoization, tabulation)
└── DSATravelingSalesmanProblem/        # Traveling Salesperson Problem (TSP) optimization

---

🧠 Topics Covered

1. Data Structures

• Linear Data Structures:
  • Arrays: Fixed-size contiguous memory blocks, sub-array partitioning, searching, and in-place transformations.
  • Linked Lists: Node-based dynamic memory structures including Singly Linked Lists, Doubly Linked Lists, and Circular Linked Lists; pointer manipulation for insertion, deletion, and search.
  • Stacks: Last-In-First-Out (LIFO) structure supporting push, pop, peek, and stack-based recursion simulation.
  • Queues: First-In-First-Out (FIFO) structure including standard queues and circular buffers.
• Associative Structures:
  • Hash Maps & Hash Sets: Key-value pair storage, hash functions, collision handling, and constant average-time lookup.
• Hierarchical & Non-Linear Structures:
  • Binary Trees & BSTs: Node hierarchies, binary search properties, minimum/maximum queries, insertion, and deletion.
  • AVL Trees: Self-balancing binary search trees using Balance Factor calculations and single/double rotations (LL, RR, LR, RL).
  • Graphs: Directed and undirected graphs modeled via Adjacency Matrices and Adjacency Lists.

2. Sorting & Searching Algorithms

Algorithm	Best Time	Average Time	Worst Time	Space	Characteristics
Linear Search	$O(1)$	$O(n)$	$O(n)$	$O(1)$	Sequential scan, works on unsorted collections
Binary Search	$O(1)$	$O(\log n)$	$O(\log n)$	$O(1)$	Divide-and-conquer on sorted collections
Bubble Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Simple comparison sort, stable
Selection Sort	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O(1)$	Repeatedly selects minimum element, unstable
Insertion Sort	$O(n)$	$O(n^2)$	$O(n^2)$	$O(1)$	Efficient for small or nearly-sorted datasets
Merge Sort	$O(n \log n)$	$O(n \log n)$	$O(n \log n)$	$O(n)$	Divide & conquer, stable, predictable performance
Quicksort	$O(n \log n)$	$O(n \log n)$	$O(n^2)$	$O(\log n)$	In-place partition-based sort, cache-friendly
Counting Sort	$O(n + k)$	$O(n + k)$	$O(n + k)$	$O(k)$	Non-comparison integer sort (bounded range $k$)
Radix Sort	$O(d \cdot (n + k))$	$O(d \cdot (n + k))$	$O(d \cdot (n + k))$	$O(n + k)$	Digit-by-digit distribution sort

3. Graph Algorithms

• Traversals:
  • Breadth-First Search (BFS): Level-order traversal using a FIFO queue; explores shortest unweighted path.
  • Depth-First Search (DFS): Deep branch exploration using recursion/stack; explores topological reachability.
• Connectivity & Cycles:
  • Cycle detection in directed graphs (via recursion stack state) and undirected graphs (via visited parent tracking).
• Shortest Paths:
  • Dijkstra's Algorithm: Greedy single-source shortest path using priority cues for non-negative weighted graphs ($O((V + E) \log V)$).
  • Bellman-Ford Algorithm: Dynamic relaxation algorithm capable of detecting negative weight cycles ($O(V \cdot E)$).
• Minimum Spanning Tree (MST):
  • Prim's Algorithm: Greedy vertex-addition algorithm maintaining a growing spanning tree.
  • Kruskal's Algorithm: Greedy edge-addition algorithm utilizing Disjoint Set Union (Union-Find) with path compression and union by rank.

4. Dynamic Programming & Optimization

• Core Paradigms:
  • Memoization (Top-Down): Recursive exploration with cache storage for previously computed subproblems.
  • Tabulation (Bottom-Up): Iterative filling of DP state tables from base cases to target state.
• Classic Problems:
  • Fibonacci Sequence: Demonstrating progression from exponential recursion $O(2^n)$ to linear DP $O(n)$ time.
  • 0/1 Knapsack Problem: Complete implementations comparing Brute-Force, Memoization, and Tabulation (including item reconstruction).
  • Traveling Salesperson Problem (TSP): NP-hard combinatorial optimization explored through state-space search and DP.

---

⚡ Complexity Reference Table

Data Structure / Operation	Access	Search	Insertion	Deletion	Space Complexity
Array	$O(1)$	$O(n)$	$O(n)$	$O(n)$	$O(n)$
Stack	$O(n)$	$O(n)$	$O(1)$	$O(1)$	$O(n)$
Queue	$O(n)$	$O(n)$	$O(1)$	$O(1)$	$O(n)$
Singly Linked List	$O(n)$	$O(n)$	$O(1)$	$O(1)$	$O(n)$
Doubly Linked List	$O(n)$	$O(n)$	$O(1)$	$O(1)$	$O(n)$
Hash Table	$N/A$	$O(1)$ avg / $O(n)$ worst	$O(1)$ avg / $O(n)$ worst	$O(1)$ avg / $O(n)$ worst	$O(n)$
Binary Search Tree	$O(\log n)$ avg / $O(n)$ worst	$O(\log n)$ avg / $O(n)$ worst	$O(\log n)$ avg / $O(n)$ worst	$O(\log n)$ avg / $O(n)$ worst	$O(n)$
AVL Tree	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(\log n)$	$O(n)$

---

🚀 Getting Started & Prerequisites

Prerequisites

• Java Development Kit (JDK): Version 8 or higher (JDK 17+ recommended).
• IDE: IntelliJ IDEA, Eclipse, VS Code with Java extensions, or standard CLI terminal.

---

💻 How to Run the Demonstrations

Running via IntelliJ IDEA

1. Clone or open the repository folder in IntelliJ IDEA:

   File -> Open -> Select "DSA-Tutorial-Java" directory
   

2. Navigate to any demo class (e.g., DSAArrays/DSABinarySearch/demo_binarysearch.java).
3. Click the green Run button next to the main method or press Shift + F10.

Running via Command Line

Compile and run individual programs from the repository root:

# Example 1: Compiling and running Binary Search
javac DSAArrays/DSABinarySearch/demo_binarysearch.java
java DSAArrays.DSABinarySearch.demo_binarysearch

# Example 2: Compiling and running Fibonacci Tabulation
javac DSATabulation/demo_findfibo_tab.java
java DSATabulation.demo_findfibo_tab

# Example 3: Compiling and running 0/1 Knapsack Tabulation
javac DSAKnapsackProblem/demo_knapsack_tabulation.java
java DSAKnapsackProblem.demo_knapsack_tabulation

---

🏷️ Code Conventions

• File Naming: Classes and files follow the demo_<topic_name>.java pattern for easy discovery and execution.
• Packages: Folders correspond directly to Java packages matching their algorithmic domain (e.g., package DSATrees.DSAAVLTrees;).
• Self-Contained Programs: Each demo class includes its own main method and supporting inner/helper classes for standalone execution.