Master DSA in Java - Part 2

The Intense and Complete Continuation

Metadata

Field	Value
Series	Master DSA in Java
Part	2
Topic	Core and Advanced DSA Structures and Algorithms in Java
Audience	Serious learners who want a complete DSA mental model in Java
Goal	Build enough conceptual and coding depth that the reader does not need a second introductory DSA source
Outcome	Reader understands linked lists, stacks, queues, hashing, trees, heaps, tries, graphs, greedy, backtracking, union find, and dynamic programming through a Java-first lens

1. What Part 2 Is Really Doing

Part 1 gave the DSA foundation:

• data vs information
• ADT vs implementation
• complexity
• recursion basics
• arrays
• strings
• core linear patterns

Part 2 now does the heavy lifting.

This is where DSA becomes a real system:

• linked structures
• controlled access structures
• fast lookup structures
• hierarchical structures
• graph models
• optimization paradigms
• state-based reasoning

If Part 1 taught you how to think about data, Part 2 teaches you how to control complex data.

2. The High-Level DSA Map

Before diving into individual topics, keep the big map in your mind:

Linear structures -> Array, Linked List, Stack, Queue, Deque
Lookup structures -> HashMap, HashSet
Hierarchical structures -> Tree, BST, Heap, Trie
Network structures -> Graph
Problem paradigms -> Recursion, Backtracking, Greedy, Dynamic Programming
Disjoint grouping -> Union Find

This map matters because students often learn topics as isolated chapters.

They are not isolated.

Each structure exists because some operation pattern appears frequently in real problems.

3. Linked List: Why It Exists

An array gives:

• fast index access
• fixed contiguous indexing

But arrays are costly for:

• insertions in the middle
• deletions in the middle

That is why linked lists exist.

Core idea

A linked list stores each element in a node, and each node points to the next node.

Singly linked node

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
    }
}

Mental model

[10|next] -> [20|next] -> [30|null]

Key properties

• dynamic size
• insertion at head is easy
• deletion at head is easy
• random access is slow

4. Singly Linked List Implementation

class SinglyLinkedList {
    private Node head;

    void insertAtHead(int data) {
        Node newNode = new Node(data);
        newNode.next = head;
        head = newNode;
    }

    void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }
}

Why this matters

This teaches the first major non-array memory model:

• traversal happens by following references
• not by index arithmetic

That is a huge mental transition in DSA.

5. Linked List Operations and Complexity

Operation	Complexity
Insert at head	O(1)
Insert at tail	O(n) without tail pointer
Delete at head	O(1)
Search	O(n)
Access kth element	O(n)

Important truth

Linked list is not "better than array."

It is better only for specific operation patterns.

That is always how DSA should be understood.

6. Doubly Linked List

A doubly linked list stores:

• pointer to next node
• pointer to previous node

Node structure

class DNode {
    int data;
    DNode prev;
    DNode next;

    DNode(int data) {
        this.data = data;
    }
}

Why use it

• easier deletion when node is known
• easier backward traversal
• useful in LRU cache style problems

Tradeoff:

• more memory per node
• more pointer updates

7. Common Linked List Patterns

If you want to get strong at linked lists, master these patterns:

1. Traverse with one pointer
2. Reverse pointers
3. Use slow and fast pointers
4. Merge two sorted lists
5. Detect cycle
6. Find middle node
7. Remove nth node from end

Example: Reverse linked list

Node reverse(Node head) {
    Node prev = null;
    Node current = head;

    while (current != null) {
        Node nextNode = current.next;
        current.next = prev;
        prev = current;
        current = nextNode;
    }

    return prev;
}

This is one of the most important linked list questions in all DSA study.

8. Stack: Last In, First Out

Stack is an ADT.

Its rule is:

• last inserted element comes out first

Real examples

• undo operation
• browser back
• recursion call stack
• expression evaluation

Core operations

• push
• pop
• peek
• isEmpty

9. Stack in Java

For interview and contest-style coding, ArrayDeque is often better than legacy Stack.

Example

import java.util.ArrayDeque;
import java.util.Deque;

Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
System.out.println(stack.peek()); // 20
System.out.println(stack.pop());  // 20

Why ArrayDeque

• faster in practice than legacy synchronized Stack
• modern API
• can behave as both stack and queue

10. Stack Problems You Must Recognize

Whenever you see:

• nested structure
• reverse evaluation
• nearest previous/next relation
• expression parsing

start thinking about stack.

Classic stack problems

• valid parentheses
• next greater element
• infix to postfix
• postfix evaluation
• largest rectangle in histogram
• monotonic stack problems

11. Queue: First In, First Out

Queue is another core ADT.

Its rule is:

• first inserted element comes out first

Real examples

• printer queue
• task scheduling
• BFS traversal
• customer service line

Core operations

• offer
• poll
• peek
• isEmpty

12. Queue in Java

import java.util.ArrayDeque;
import java.util.Queue;

Queue<Integer> queue = new ArrayDeque<>();
queue.offer(10);
queue.offer(20);
System.out.println(queue.peek()); // 10
System.out.println(queue.poll()); // 10

Complexity

• insertion at rear: O(1)
• removal from front: O(1)

13. Deque: Double-Ended Queue

Deque allows insertion and deletion from both ends.

Why it matters

Deque is powerful in:

• sliding window maximum
• palindrome checking
• implementing both stack and queue behavior

Example

Deque<Integer> deque = new ArrayDeque<>();
deque.addFirst(10);
deque.addLast(20);
System.out.println(deque.removeFirst());
System.out.println(deque.removeLast());

14. Hashing: Fast Lookup by Key

Hashing is one of the most important DSA ideas in real software.

Goal

Turn lookup, insertion, and deletion into near-constant-time operations on average.

Mental model

key -> hash function -> index/bucket -> value location

Java structures

• HashMap
• HashSet

Why hashing matters

Whenever you need:

• fast membership check
• counting frequency
• mapping key to value
• duplicate detection

hashing should immediately come to mind.

15. HashMap in Java

import java.util.HashMap;
import java.util.Map;

Map<String, Integer> marks = new HashMap<>();
marks.put("Math", 95);
marks.put("Science", 90);
System.out.println(marks.get("Math"));

Common uses

• frequency maps
• index maps
• memoization
• grouping

Complexity

Average:

• insert: O(1)
• search: O(1)
• delete: O(1)

Worst-case behavior can degrade, but average-case is the key idea for most practical use.

16. HashSet in Java

Use HashSet when you only care about presence, not mapped value.

import java.util.HashSet;
import java.util.Set;

Set<Integer> seen = new HashSet<>();
seen.add(10);
seen.add(20);
System.out.println(seen.contains(10));

Typical patterns

• remove duplicates
• check if element seen before
• intersection logic
• distinct count

17. Tree: Hierarchical Data Structure

A tree is a non-linear hierarchical structure.

Core language

• root
• child
• parent
• leaf
• subtree
• height
• depth

Why trees matter

Trees appear when data naturally branches:

• file systems
• HTML/DOM
• organization charts
• expression evaluation
• search structures

18. Binary Tree

A binary tree is a tree where each node has at most two children:

• left
• right

Node

class TreeNode {
    int data;
    TreeNode left;
    TreeNode right;

    TreeNode(int data) {
        this.data = data;
    }
}

19. Binary Tree Traversals

These are fundamental.

DFS traversals

• Preorder: root, left, right
• Inorder: left, root, right
• Postorder: left, right, root

Example: Inorder

void inorder(TreeNode root) {
    if (root == null) {
        return;
    }
    inorder(root.left);
    System.out.print(root.data + " ");
    inorder(root.right);
}

BFS traversal

Use queue for level-order traversal.

void levelOrder(TreeNode root) {
    if (root == null) {
        return;
    }

    Queue<TreeNode> queue = new ArrayDeque<>();
    queue.offer(root);

    while (!queue.isEmpty()) {
        TreeNode node = queue.poll();
        System.out.print(node.data + " ");

        if (node.left != null) queue.offer(node.left);
        if (node.right != null) queue.offer(node.right);
    }
}

This is the first major tree + queue connection students should master.

20. Binary Search Tree

BST is a binary tree with ordering property:

• left subtree values < node value
• right subtree values > node value

Why BST matters

It supports searching, insertion, and deletion in better time than linear structures when balanced.

Search code

boolean searchBST(TreeNode root, int target) {
    while (root != null) {
        if (root.data == target) {
            return true;
        } else if (target < root.data) {
            root = root.left;
        } else {
            root = root.right;
        }
    }
    return false;
}

Complexity

Average balanced case:

O(log n)

Worst skewed case:

O(n)

This is why tree balance matters.

21. Heap and Priority Queue

A heap is a specialized tree-like structure commonly used to access highest or lowest priority efficiently.

Min-heap

Smallest element stays at top.

Max-heap

Largest element stays at top.

Java PriorityQueue

By default, Java's PriorityQueue is a min-heap.

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.offer(30);
pq.offer(10);
pq.offer(20);

System.out.println(pq.poll()); // 10

Why heaps matter

• top-k problems
• scheduling
• Dijkstra
• merge k sorted lists
• running median variants

22. Trie

A trie is a tree-like structure used for efficient prefix-based string operations.

Use cases

• autocomplete
• prefix search
• dictionary checks
• word suggestions

Core idea

Each edge represents a character.

Paths represent prefixes or words.

Java node idea

class TrieNode {
    TrieNode[] children = new TrieNode[26];
    boolean isEnd;
}

Why trie matters

For massive string-prefix operations, trie can outperform repeated raw comparisons.

23. Graph: The Most General Data Model

Graphs model entities and connections.

Examples:

• cities and roads
• users and friendships
• pages and links
• tasks and dependencies

Terms

• vertex / node
• edge
• directed / undirected
• weighted / unweighted

24. Graph Representations

Adjacency list

Best for sparse graphs.

List<List<Integer>> graph = new ArrayList<>();

Adjacency matrix

Useful when graph is dense or direct edge lookup is needed.

int[][] matrix = new int[n][n];

Strong rule

Most graph coding in Java interview/CP settings prefers adjacency list.

25. BFS on Graph

BFS explores level by level.

It uses a queue.

Java code

void bfs(List<List<Integer>> graph, int start) {
    boolean[] visited = new boolean[graph.size()];
    Queue<Integer> queue = new ArrayDeque<>();

    visited[start] = true;
    queue.offer(start);

    while (!queue.isEmpty()) {
        int node = queue.poll();
        System.out.print(node + " ");

        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                queue.offer(neighbor);
            }
        }
    }
}

Use cases

• shortest path in unweighted graph
• connected components
• level traversal

26. DFS on Graph

DFS explores deeply before backtracking.

It can be written recursively or iteratively.

Recursive DFS

void dfs(List<List<Integer>> graph, int node, boolean[] visited) {
    visited[node] = true;
    System.out.print(node + " ");

    for (int neighbor : graph.get(node)) {
        if (!visited[neighbor]) {
            dfs(graph, neighbor, visited);
        }
    }
}

Use cases

• connected components
• cycle detection
• topological ideas
• path exploration

27. Shortest Path Thinking

Not every shortest path problem is the same.

Unweighted graph

Use BFS.

Weighted graph with non-negative weights

Use Dijkstra.

Graph with negative edges

Need different thinking such as Bellman-Ford.

Dijkstra intuition

Use a priority queue to always expand the currently best-known node first.

This is one of the most important graph algorithms in practice.

28. Topological Sort

Topological sort applies to Directed Acyclic Graphs.

It gives an order where dependencies come before dependents.

Real examples

• course prerequisites
• build systems
• task scheduling

Core methods

• DFS-based
• indegree / Kahn's algorithm using queue

This is a critical algorithmic pattern when dependencies appear.

29. Union Find / Disjoint Set Union

Union Find is used when you need to manage connected components dynamically.

Core operations

• find
• union

Uses

• cycle detection
• connected components
• Kruskal's MST

Basic Java structure

class DSU {
    int[] parent;

    DSU(int n) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void union(int a, int b) {
        int pa = find(a);
        int pb = find(b);
        if (pa != pb) {
            parent[pa] = pb;
        }
    }
}

This is a beautiful example of efficient structure plus recursion plus optimization.

30. Greedy Algorithms

Greedy means:

• make the locally best choice now
• hope it leads to global optimum

But greedy is not always valid.

That is the crucial truth.

When greedy works

It works only when the problem has specific properties.

Common greedy problems

• activity selection
• interval scheduling
• minimum coins in canonical systems
• Huffman coding
• minimum spanning tree

Real lesson

Do not use greedy because it looks simple.

Use greedy only when you can justify why local choice is safe.

31. Backtracking

Backtracking means:

• try a choice
• go deeper
• if it fails, undo the choice
• try another path

Typical problems

• permutations
• combinations
• N-Queens
• Sudoku
• subset generation

Example: Generate subsets

void generateSubsets(int[] arr, int index, List<Integer> current) {
    if (index == arr.length) {
        System.out.println(current);
        return;
    }

    current.add(arr[index]);
    generateSubsets(arr, index + 1, current);
    current.remove(current.size() - 1);

    generateSubsets(arr, index + 1, current);
}

Key insight

Backtracking is controlled recursion with undo logic.

That mental model helps enormously.

32. Dynamic Programming

Dynamic Programming, or DP, solves problems with:

• overlapping subproblems
• optimal substructure

Core idea

Do not solve the same subproblem repeatedly.

Store the result.

Two common forms

• memoization: top-down recursion + cache
• tabulation: bottom-up iterative table

Example: Fibonacci with memoization

int fib(int n, int[] dp) {
    if (n <= 1) {
        return n;
    }
    if (dp[n] != -1) {
        return dp[n];
    }
    dp[n] = fib(n - 1, dp) + fib(n - 2, dp);
    return dp[n];
}

Example: Fibonacci tabulation

int fibTab(int n) {
    if (n <= 1) {
        return n;
    }

    int[] dp = new int[n + 1];
    dp[0] = 0;
    dp[1] = 1;

    for (int i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }

    return dp[n];
}

33. The Real DP Mental Model

Students often fear DP because they try to memorize formulas.

That is the wrong way.

Instead ask:

1. What is the state?
2. What choices exist?
3. What transition connects states?
4. What is the base case?
5. What is the final answer location?

This is how top DSA learners solve DP.

34. Sliding Window

Sliding window is essential for arrays and strings with contiguous segments.

Use when

You need:

• longest substring
• minimum subarray
• fixed-size window processing
• contiguous range optimization

Example: Sum of each window of size k

int windowSum(int[] arr, int k) {
    int sum = 0;

    for (int i = 0; i < k; i++) {
        sum += arr[i];
    }

    int maxSum = sum;

    for (int i = k; i < arr.length; i++) {
        sum += arr[i] - arr[i - k];
        maxSum = Math.max(maxSum, sum);
    }

    return maxSum;
}

Sliding window is one of the most reusable interview patterns.

35. Monotonic Data Structures

This is a more advanced but very important topic.

A monotonic stack or queue maintains order while processing elements.

Use cases

• next greater element
• stock span
• sliding window maximum
• histogram problems

These patterns feel magical at first, but they are really about storing only useful candidates.

36. Recursion vs Iteration vs DP

Strong learners compare approaches.

Recursion

• elegant
• natural for tree and combinatorial problems
• may repeat work

Iteration

• often memory efficient
• explicit control

DP

• structured solution for repeated overlapping work

The strongest DSA solutions often come from knowing when to transform one style into another.

37. Java Collections in DSA

For serious Java DSA work, know these well:

• ArrayList
• LinkedList
• ArrayDeque
• PriorityQueue
• HashMap
• HashSet
• TreeMap
• TreeSet

Important rule

Do not use collection classes blindly.

Know:

• what operation you need
• what complexity you get
• whether ordering matters

That is what separates syntax users from actual problem solvers.

38. Complexity-Based Structure Selection

When choosing a structure, think like this:

Need	Likely Structure
Fast index access	Array / ArrayList
Frequent head insertion	Linked List / Deque
LIFO behavior	Stack / Deque
FIFO behavior	Queue / Deque
Fast lookup by key	HashMap
Fast distinct tracking	HashSet
Ordered key retrieval	TreeMap / TreeSet
Priority access	PriorityQueue
Prefix search	Trie
Hierarchical traversal	Tree
Network relation	Graph

This is one of the best DSA selection tables to memorize with understanding.

39. How to Read a Problem Like an Advanced DSA Learner

When you see a problem, ask:

1. Is the data linear, hierarchical, or graph-like?
2. Is order important?
3. Is lookup dominant?
4. Is the problem about contiguous ranges?
5. Is there repeated subproblem work?
6. Is a greedy choice likely safe?
7. Are we tracking connectivity?
8. Are we searching states?

These questions point you toward the correct topic family.

40. Common DSA Topic Triggers

If you see:

• "next greater"
• "previous smaller"

Think:

• monotonic stack

If you see:

• "shortest in unweighted graph"

Think:

• BFS

If you see:

• "choose or not choose"

Think:

• recursion, backtracking, or DP

If you see:

• "dynamic connectivity"

Think:

• union find

If you see:

• "best current candidate repeatedly"

Think:

• heap or greedy

These trigger patterns are extremely useful.

41. Common DSA Mistakes at Higher Levels

Mistake 1

Using the right structure with the wrong traversal logic.

Mistake 2

Understanding theory but not writing implementation from scratch.

Mistake 3

Not tracing recursive calls.

Mistake 4

Ignoring edge cases such as:

• empty input
• single node
• disconnected graph
• duplicate keys
• overflow risk

Mistake 5

Memorizing algorithms without understanding problem triggers.

That last mistake is especially dangerous.

42. The Professional Truth About DSA

Strong software engineers know:

• DSA is not a list of tricks
• DSA is structured thinking about data and operations
• the best solution depends on constraints
• clean implementation matters as much as idea
• debugging pointer logic, recursion, and graph traversal is part of mastery

Top-level DSA skill comes from combining:

• theory
• coding
• pattern recognition
• complexity reasoning

43. What You Should Be Able to Do After Part 2

After mastering this part, a serious learner should be able to:

• implement core structures in Java
• choose structures based on operations
• explain ADT vs implementation
• write tree and graph traversals
• use heaps, hashing, and queues correctly
• recognize greedy, backtracking, and DP patterns
• reason about complexity before coding

That is already a very serious DSA base.

44. Final Compression Summary

If you remember only the deepest truths from Part 2, remember these:

• Linked lists trade index access for flexible structural changes
• Stacks handle nested and reverse-order behavior
• Queues handle level-order and ordered processing
• Hashing gives fast average lookup
• Trees model hierarchy
• BST adds ordered search logic
• Heaps solve priority problems
• Tries solve prefix problems
• Graphs model general connectivity
• BFS and DFS are core traversal engines
• Union Find manages dynamic grouping
• Greedy needs proof of safe local choices
• Backtracking explores choices with undo
• DP prevents repeated subproblem work

45. Final Mental Model

Problem Pattern -> Required Operations -> Best ADT -> Best Java Implementation -> Complexity Check -> Correct Algorithm

That is the full DSA loop.

46. Closing Note

If Part 1 gave you the foundation and Part 2 gave you the structures and paradigms, then together they form a complete serious DSA roadmap for Java learners.

From here, growth no longer depends on finding a new theory source.

It depends on:

• solving many questions
• tracing logic carefully
• revising patterns repeatedly
• writing clean Java implementations

That is how real DSA mastery is built.