Data Structures and Algorithms for Every Java Developer

Whether you're preparing for a coding interview, building scalable backend systems, or aiming to write high-performance applications, a solid understanding of data structures and algorithms (DSA) is non-negotiable. In this blog, we’ll walk through the must-know DSA topics specifically for Java developers, with real-world relevance and Java-specific tips.

 Why Java Developers Must Learn DSA

  • Interviews: DSA is the backbone of technical interviews at FAANG and top-tier companies.

  • Performance: The right data structure can drastically reduce latency and resource usage.

  • Scalability: Efficient algorithms make your systems handle 10x more users without 10x cost.

  • Problem Solving: Builds logical thinking and improves your debugging abilities.

Core Data Structures in Java

1. Linear Data Structures

Data Structure Use Case Java API
Array Fast access by index int[], ArrayList<T>
Linked List Dynamic memory allocation LinkedList<T>
Stack LIFO operations (undo, backtracking) Stack<T>
Queue/Deque FIFO, Double-ended operations Queue<T>, Deque<T>

2. Hash-Based Structures

Data Structure Use Case Java API
HashMap Key-value storage HashMap<K, V>
HashSet Fast membership test HashSet<T>

3. Tree-Based Structures

Data Structure Use Case Java API
Binary Tree/BST Hierarchical storage Custom
Red-Black Tree Balanced search tree TreeMap<K, V>, TreeSet<T>
Trie Prefix searching (e.g., autocomplete) Custom

4. Heap (Priority Queue)

Used for scheduling, top-k problems, and greedy algorithms
 Java: PriorityQueue<T> with custom Comparator

5. Graph

Represent networks (social, pathfinding, dependency graphs)
Java: Adjacency List/Matrix with custom classes or JGraphT

6. Advanced

Structure Use Case
Segment Tree Range queries
Fenwick Tree Prefix sums
Disjoint Set (Union-Find) Connected components, Kruskal’s MST

Algorithms to Focus On

Searching & Sorting

  • Binary Search, Merge Sort, Quick Sort

  • Heap Sort, Counting Sort

  • Java APIs: Arrays.sort(), Collections.sort(), custom Comparator

Recursion & Backtracking

  • N-Queens, Maze Path, Subsets, Permutations

Dynamic Programming

  • Knapsack, Fibonacci, LCS, Matrix DP

  • Practice via tabulation and memoization

Greedy Algorithms

  • Activity selection, Huffman Coding, Interval Scheduling

Graph Algorithms

  • BFS, DFS, Topological Sort

  • Dijkstra, Kruskal, Prim, Union-Find

Bit Manipulation

  • XOR Tricks, Set/Unset Bits, Power of 2

Sliding Window & Two Pointers

  • Max sum subarrays, Longest substring without repeating chars

Math & Number Theory

  • GCD/LCM, Sieve of Eratosthenes, Modular Exponentiation

 Java-Specific Tips for DSA

  • Master Collections Framework (List, Map, Set, Queue)

  • Use Comparator & Comparable for custom sorting logic

  • Understand autoboxing, generics, and performance tradeoffs

  • Dive into Concurrency APIs: ExecutorService, ConcurrentHashMap

 Learning Plan for Java DSA

  1. Start with Collections API – understand how ArrayList, HashMap, TreeMap, etc. work under the hood.

  2. Implement Data Structures Manually – Build your own LinkedList, Stack, etc.

  3. Tackle Real Problems – Use LeetCode, GeeksForGeeks, or HackerRank.

  4. Practice Patterns – Sliding window, recursion with memoization, etc.

  5. Master Algorithms – Solve classic problems and understand trade-offs.

Top Resources

  • 📘 Cracking the Coding Interview – Gayle Laakmann McDowell

  • 📘 Effective Java – Joshua Bloch

  • 💻 LeetCode's Top 100 Liked Problems

  • 📚 GeeksForGeeks Java Data Structures Section

Whether you’re targeting top companies, building scalable software, or just enhancing your core dev skills—mastering DSA is your gateway. For Java developers, pairing algorithmic thinking with powerful tools like the Collections Framework will elevate your code from functional to exceptional.


Least Recently Used (LRU) cache in Java

What is LRU Cache?

Least Recently Used (LRU) is a caching strategy that evicts the least recently accessed item when the cache exceeds its capacity. It ensures that the most frequently or recently used data stays in memory while discarding older, less useful entries.

Real-World Use Case

  • Android image loading: Cache recently viewed images to avoid reloading from the network.

  • Database query results: Store recently used queries for faster results.

  • Web browsers: Maintain a small history of visited pages.

  • Memory-constrained systems: Manage resource usage by limiting active items in memory.

Best Way to Implement LRU in Java

The simplest and most effective way to implement an LRU Cache in Java is by using LinkedHashMap with access-order enabled.

LRU Cache Using LinkedHashMap (Best Practice)

import java.util.LinkedHashMap;
import java.util.Map;

public class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int capacity;

    public LRUCache(int capacity) {
        // initialCapacity, loadFactor, accessOrder
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > capacity;
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);

        cache.put(1, "One");
        cache.put(2, "Two");
        cache.put(3, "Three");

        // Access key 2 (makes 2 most recently used)
        cache.get(2);

        // Add key 4 - should evict key 1 (least recently used)
        cache.put(4, "Four");

        System.out.println(cache);
        // Output: {3=Three, 2=Two, 4=Four}
    }
}

 Output

{3=Three, 2=Two, 4=Four}

Explanation:

  • Initially added 1, 2, 3.

  • Accessed key 2 → usage order becomes [1, 3, 2]

  • Adding key 4 → evicts 1 as it is the Least Recently Used.

Custom LRU Without LinkedHashMap (for interviews)

Here’s how you can manually implement an LRU Cache using a Doubly Linked List and HashMap in Java — this is the classic approach commonly asked in interviews because it guarantees O(1) time complexity for both get() and put() operations.

Key Concepts

  • HashMap gives O(1) lookup for keys.

  • Doubly Linked List maintains access order (most recent at the front, least at the end).

  • Each node contains key & value and links to its previous and next node.

import java.util.HashMap;

public class LRUCache<K, V> {
    private final int capacity;
    private final HashMap<K, Node> map;
    private final Node head, tail;

    private class Node {
        K key;
        V value;
        Node prev, next;

        Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();

        // Dummy head and tail nodes to avoid null checks
        head = new Node(null, null);
        tail = new Node(null, null);
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        if (!map.containsKey(key)) return null;
        Node node = map.get(key);
        moveToHead(node); // Mark as most recently used
        return node.value;
    }

    public void put(K key, V value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            node.value = value;
            moveToHead(node);
        } else {
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addToHead(newNode);

            if (map.size() > capacity) {
                Node lru = tail.prev;
                removeNode(lru);
                map.remove(lru.key);
            }
        }
    }

    // Helper methods for doubly linked list operations
    private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;

        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }

    public void printCache() {
        Node current = head.next;
        while (current != tail) {
            System.out.print(current.key + "=" + current.value + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LRUCache<Integer, String> cache = new LRUCache<>(3);
        cache.put(1, "One");
        cache.put(2, "Two");
        cache.put(3, "Three");

        cache.printCache(); // 3=Three 2=Two 1=One

        cache.get(2); // Access 2 to move it to front
        cache.printCache(); // 2=Two 3=Three 1=One

        cache.put(4, "Four"); // Evicts 1 (least recently used)
        cache.printCache(); // 4=Four 2=Two 3=Three
    }
}

Output

3=Three 2=Two 1=One
2=Two 3=Three 1=One
4=Four 2=Two 3=Three

Benefits of This Approach

Feature Description
Time Complexity O(1) for both get() and put()
Space Complexity O(capacity)
No built-in Java tricks Great for coding interviews
Full control Easy to customize or extend

Key Takeaways

  • Use LinkedHashMap with accessOrder = true for easy and efficient LRU.

  • Override removeEldestEntry() to control eviction.

  • Prefer it for in-memory caches in performance-sensitive apps.

  • For interviews, know the manual implementation using Doubly Linked List + HashMap.

📢 Feedback: Did you find this article helpful? Let me know your thoughts or suggestions for improvements! 😊 please leave a comment below. I’d love to hear from you! 👇

Happy coding! 💻✨

Longest Common Subsequence (LCS) in Java

Longest Common Subsequence (LCS) problem, including its problem statement, solution, and Java implementation using the best possible approach — Dynamic Programming (Tabulation - Bottom-Up) for optimal performance.

Problem Statement: Longest Common Subsequence (LCS)

Given two strings text1 and text2, return the length of their longest common subsequence.

A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.

Example:

Input: text1 = "abcde", text2 = "ace"
Output: 3
Explanation: The LCS is "ace" with length 3.

Optimal Solution: Dynamic Programming (Bottom-Up Tabulation)

💡 Idea:

We use a 2D DP array dp[i][j] where each cell represents the length of the LCS of the first i characters of text1 and the first j characters of text2.

Transition Formula:

  • If text1[i-1] == text2[j-1]
    → dp[i][j] = 1 + dp[i-1][j-1]

  • Else
    → dp[i][j] = max(dp[i-1][j], dp[i][j-1])

Java Code (Bottom-Up Approach)

public class LongestCommonSubsequence {

    public static int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length();
        int n = text2.length();

        // Create a 2D dp array
        int[][] dp = new int[m + 1][n + 1];

        // Fill the dp array from bottom up
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                // If characters match, move diagonally and add 1
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = 1 + dp[i - 1][j - 1];
                } else {
                    // Else take max from left or top
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }

        // The answer is in dp[m][n]
        return dp[m][n];
    }

    public static void main(String[] args) {
        String text1 = "abcde";
        String text2 = "ace";
        int result = longestCommonSubsequence(text1, text2);
        System.out.println("Length of LCS: " + result);  // Output: 3
    }
}

Time and Space Complexity

Complexity Value
Time O(m * n)
Space O(m * n)

You can optimize space to O(min(m, n)) by using a 1D rolling array instead of a 2D array if needed.

Bonus: To Reconstruct the LCS String

If you want to reconstruct the LCS itself, not just its length, we can backtrack from dp[m][n] to dp[0][0] while tracing the matching characters.

📢 Feedback: Did you find this article helpful? Let me know your thoughts or suggestions for improvements! 😊 please leave a comment below. I’d love to hear from you! 👇

Happy coding! 💻✨