Advanced Java Data Structures and Their Best Use Cases

This content originally appeared on DEV Community and was authored by AnkitDevCode

Introduction

While Java’s standard collections like List, Set, and Map cover most needs, complex applications often require advanced data structures for efficiency, concurrency, and memory optimization.

This guide explores key advanced Java data structures, their core operations, complexities, and best use cases to help developers build high-performance, scalable applications.

1. PriorityQueue (Heap)

PriorityQueue in Java (from java.util) is a queue that arranges elements according to their priority.

PriorityQueue in Java is a min-heap by default, implemented as a binary heap using an array. It maintains elements in a partially ordered tree where the smallest element is always at the root.

A heap is a specialized binary tree-based data structure that satisfies the heap property:

• In a Min-Heap, the parent node is always smaller (or equal) than its children.
• In a Max-Heap, the parent node is always larger (or equal) than its children.

Heaps are typically implemented using arrays (not linked nodes) because the tree is always a complete binary tree (all levels filled except possibly the last, which is filled left to right).

Key Properties

• Time Complexity: O(log n) for insertion and deletion, O(1) for peek
• Space Complexity: O(n)
• Not thread-safe
• Unbounded (grows dynamically)
• Natural ordering or custom Comparator

Basic Syntax for PriorityQueue

PriorityQueue<Integer> minHeap = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder());

Core Operations

Classic Use Cases & Problems

• K Largest/Smallest Elements
• Merge K Sorted Lists
• Dijkstra’s Shortest Path
• Task Scheduler with Priority
• Top K Frequent Elements
• Sliding Window Maximum
• Meeting Rooms II (Minimum Conference Rooms)
• Kth Largest Element in Stream
• Memory Management

Example

1. PriorityQueue to implement Heap Sort

import java.util.PriorityQueue;
import java.util.Arrays;

public class HeapSortExample {
    public static void main(String[] args) {
        int[] nums = {20, 5, 15, 10};

        // Min-Heap for ascending order
        PriorityQueue<Integer> pq = new PriorityQueue<>();

        // Add all elements to the heap
        for (int num : nums) {
            pq.add(num);
        }

        // Extract elements to get sorted order
        int index = 0;
        while (!pq.isEmpty()) {
            nums[index++] = pq.poll();
        }

        System.out.println("Sorted array: " + Arrays.toString(nums)); // [5, 10, 15, 20]
    }
}

• Add all elements to a Min-Heap (PriorityQueue by default).
• Poll elements one by one → smallest element comes first.
• Store them back → array becomes sorted in ascending order.
• For descending order, use a Max-Heap: PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());

2. PriorityQueue with Objects

import java.util.PriorityQueue;
import java.util.Comparator;

class Student {
    String name;
    int score;

    Student(String name, int score) {
        this.name = name;
        this.score = score;
    }

    @Override
    public String toString() {
        return name + " (" + score + ")";
    }
}

public class Main {
    public static void main(String[] args) {
        // Max-Heap: higher score = higher priority
        PriorityQueue<Student> pq = new PriorityQueue<>(Comparator.comparingInt((Student s) -> s.score).reversed());

        pq.add(new Student("Alice", 85));
        pq.add(new Student("Bob", 92));
        pq.add(new Student("Charlie", 78));

        System.out.println("Students served by priority:");
        while (!pq.isEmpty()) {
            System.out.println(pq.poll());
        }
    }
}

Rule of Thumb:

• Use Comparable for natural/default sorting.
• Use Comparator for custom/multiple sorting logic.

// Comparable
class Student implements Comparable<Student> {
    int score;
    public int compareTo(Student s) { return this.score - s.score; }
}

// Comparator
Comparator<Student> byScoreDesc = (a, b) -> b.score - a.score;

Summary

PriorityQueue is the go-to choice when you need efficient access to the minimum/maximum element with frequent insertions and deletions, making it perfect for algorithms that require greedy selection based on priority.

2. Deque (ArrayDeque/LinkedDeque)

Deque (pronounced “deck” is part of the java.util package ) is a double-ended queue that allows insertion and deletion at both ends. Java provides two main implementations:

• ArrayDeque: Resizable array implementation
• LinkedList: Doubly-linked list implementation (also implements Deque)

Key Properties

• Double-ended operations – Insert/remove from both front and rear
• No capacity restrictions – Dynamically resizable
• Not thread-safe – Requires external synchronization
• Null elements not allowed (ArrayDeque) vs Null allowed (LinkedList)
• Faster than Stack and LinkedList for stack/queue operations
• More memory efficient than LinkedList (ArrayDeque)
• Implements both Queue and Deque interfaces
• Supports both LIFO and FIFO operations

Basic Syntax for ArrayDeque and LinkedList

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

public class Main {
    public static void main(String[] args) {
        // Using ArrayDeque
        Deque<Integer> arrayDeque = new ArrayDeque<>();
        arrayDeque.addFirst(10);
        arrayDeque.addLast(20);
        System.out.println("ArrayDeque peekFirst: " + arrayDeque.peekFirst()); // 10
        System.out.println("ArrayDeque peekLast: " + arrayDeque.peekLast());   // 20
        arrayDeque.removeFirst();
        arrayDeque.removeLast();

        // Using LinkedList
        Deque<Integer> linkedListDeque = new LinkedList<>();
        linkedListDeque.addFirst(30);
        linkedListDeque.addLast(40);
        System.out.println("LinkedList peekFirst: " + linkedListDeque.peekFirst()); // 30
        System.out.println("LinkedList peekLast: " + linkedListDeque.peekLast());   // 40
        linkedListDeque.removeFirst();
        linkedListDeque.removeLast();
    }
}

Core Operations

ArrayDeque vs LinkedList Performance

Classic Use Cases & Problems

• Sliding Window Maximum/Minimum – Maintain elements in window
• Palindrome Checking – Compare characters from both ends
• Undo/Redo Functionality – Stack-like operations with flexibility
• BFS with Level Tracking – Process nodes level by level
• Expression Evaluation – Handle nested brackets and operators
• Implementing Stack and Queue – Single data structure for both
• Monotonic Deque Problems – Maintain increasing/decreasing order
• Circular Buffer Implementation – Ring buffer with dynamic size
• Browser History Navigation – Forward/backward navigation
• Task Scheduling – Priority-based insertion at both ends

Example

sliding-window-maximum

import java.util.*;

public class SlidingWindowMaximum {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k <= 0) {
            return new int[0];
        }

        Deque<Integer> deque = new ArrayDeque<>(); // Stores indices
        int[] result = new int[nums.length - k + 1];
        int resultIndex = 0;

        for (int i = 0; i < nums.length; i++) {
            // Remove indices that are out of current window
            while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
                deque.pollFirst();
            }

            // Remove indices whose corresponding values are smaller than current
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
                deque.pollLast();
            }

            // Add current index
            deque.offerLast(i);

            // If we have processed at least k elements, add to result
            if (i >= k - 1) {
                result[resultIndex++] = nums[deque.peekFirst()];
            }
        }

        return result;
    }

    public static void main(String[] args) {
        SlidingWindowMaximum solution = new SlidingWindowMaximum();
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;

        int[] result = solution.maxSlidingWindow(nums, k);
        System.out.println("Sliding Window Maximum: " + Arrays.toString(result));
        // Output: [3, 3, 5, 5, 6, 7]
    }
}

Summary

Use ArrayDeque for better performance and LinkedList when frequent insertions/removals in the middle are needed.

3. BlockingQueue (ArrayBlockingQueue, LinkedBlockingQueue)

BlockingQueue is a thread-safe queue interface that supports operations that wait for the queue to become non-empty when retrieving an element, and wait for space to become available when storing an element. It’s part of the java.util.concurrent package.

Key Properties

• Thread-safe – Built-in synchronization for concurrent access
• Blocking operations – Threads wait when queue is full/empty
• Producer-Consumer pattern – Perfect for multi-threaded scenarios
• No null elements – Null values are not permitted
• Capacity management – Can be bounded or unbounded
• Multiple implementations – ArrayBlockingQueue, LinkedBlockingQueue, etc.
• Timeout support – Operations can have time limits
• Collection interface – Implements Queue and Collection interfaces
• Atomic operations – All operations are atomic and thread-safe
• Fair access – Optional fairness policy for thread scheduling

Basic Syntax for ArrayBlockingQueue and LinkedBlockingQueue

import java.util.concurrent.BlockingQueue;
import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;

public class Main {
    public static void main(String[] args) throws InterruptedException {
        // ArrayBlockingQueue
        BlockingQueue<Integer> arrayQueue = new ArrayBlockingQueue<>(3);
        arrayQueue.put(1);
        arrayQueue.put(2);
        System.out.println("ArrayBlockingQueue peek: " + arrayQueue.peek()); // 1
        System.out.println("ArrayBlockingQueue removed: " + arrayQueue.take()); // 1

        // LinkedBlockingQueue
        BlockingQueue<Integer> linkedQueue = new LinkedBlockingQueue<>(3);
        linkedQueue.put(10);
        linkedQueue.put(20);
        System.out.println("LinkedBlockingQueue peek: " + linkedQueue.peek()); // 10
        System.out.println("LinkedBlockingQueue removed: " + linkedQueue.take()); // 10
    }
}

Core Operations

ArrayBlockingQueue vs LinkedBlockingQueue features:

Classic Use Cases & Problems

• Producer-Consumer Pattern – Multiple threads producing/consuming data
• Thread Pool Task Queues – Executor framework uses BlockingQueue
• Rate Limiting and Throttling – Control processing speed
• Batch Processing Systems – Accumulate work units for batch processing
• Event-Driven Architectures – Decouple event producers from consumers
• Message Passing Systems – Inter-thread communication
• Resource Pool Management – Manage limited resources among threads
• Data Pipeline Processing – Chain of processing stages
• Load Balancing – Distribute work across multiple worker threads
• Bounded Buffer Problem – Classic synchronization problem
• Work Stealing Algorithms – Task distribution in parallel computing
• Real-time Data Processing – Handle continuous data streams
• Microservices Communication – Async communication between services
• Cache Warming – Pre-load cache data in background threads

Example

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.BlockingQueue;

/**
 * Simple Producer-Consumer Example using BlockingQueue
 * 
 * Real scenario: Online Store Order Processing
 * - Customer places orders (Producer)
 * - Warehouse processes orders (Consumer)
 */
public class SimpleProducerConsumer {

    public static void main(String[] args) {
        // Shared queue between producer and consumer (max 5 orders)
        BlockingQueue<String> orderQueue = new ArrayBlockingQueue<>(5);

        // Producer: Customer placing orders
        Thread customer = new Thread(() -> {
            String[] orders = {
                "Order-1: iPhone 14", 
                "Order-2: MacBook Pro", 
                "Order-3: AirPods", 
                "Order-4: iPad", 
                "Order-5: Apple Watch",
                "Order-6: Magic Mouse",
                "Order-7: Keyboard"
            };

            try {
                for (String order : orders) {
                    System.out.println("Customer placing: " + order);
                    orderQueue.put(order); // Blocks if queue is full
                    Thread.sleep(500); // Customer thinks for 500ms before next order
                }
                System.out.println("Customer finished placing all orders");

            } catch (InterruptedException e) {
                System.out.println("Customer interrupted");
            }
        });

        // Consumer: Warehouse processing orders
        Thread warehouse = new Thread(() -> {
            try {
                Thread.sleep(2000); // Warehouse starts working after 2 seconds

                while (true) {
                    String order = orderQueue.take(); // Blocks if queue is empty
                    System.out.println("Warehouse processing: " + order);
                    Thread.sleep(1000); // Takes 1 second to process each order
                    System.out.println("Warehouse completed: " + order);
                }

            } catch (InterruptedException e) {
                System.out.println("Warehouse stopped working");
            }
        });

        // Start both threads
        customer.start();
        warehouse.start();

        // Let them run for 10 seconds, then stop
        try {
            Thread.sleep(10000);
            warehouse.interrupt(); // Stop the warehouse
            customer.join(); // Wait for customer to finish
            System.out.println("\n Store closed for the day!");

        } catch (InterruptedException e) {
            System.out.println("Main interrupted");
        }
    }
}

Summary

BlockingQueue is the cornerstone of concurrent programming in Java, providing thread-safe, blocking operations that are essential for producer-consumer patterns. ArrayBlockingQueue offers better memory efficiency for bounded scenarios, while LinkedBlockingQueue provides higher throughput for demanding applications. Choose based on your specific concurrency needs, memory constraints, and performance requirements.

4. BitSet

BitSet is a resizable array of bits that provides efficient storage and manipulation of boolean values. Each bit can be set (1) or cleared (0), making it extremely memory-efficient for representing large sets of boolean flags or performing set operations on integers.It’s part of the java.util package.

Key Properties

• Memory efficient – Uses only 1 bit per boolean value (vs 8 bits for boolean array)
• Dynamically resizable – Grows automatically as needed
• Fast bitwise operations – Hardware-optimized bit manipulation
• Set operations support – AND, OR, XOR, NOT operations
• Thread-unsafe – Requires external synchronization for concurrent access
• Zero-based indexing – Bits are numbered from 0 to size-1
• Automatic bit clearing – Unset bits are automatically 0 (false)
• Efficient iteration – Special methods to iterate over set bits only
• Serializable – Can be serialized/deserialized
• Cloneable – Supports deep copying
• No null values – Only boolean states (set/clear)
• Compact representation – Internally uses long arrays for storage

Basic Syntax for BitSet

import java.util.BitSet;

public class Main {
    public static void main(String[] args) {
        // Create a BitSet
        BitSet bits = new BitSet();

        // Set bits
        bits.set(0);          // set bit at index 0
        bits.set(2);          // set bit at index 2
        bits.set(4, 7);       // set bits from index 4 to 6 (7 exclusive)

        // Get bits
        System.out.println("Bit at index 2: " + bits.get(2)); // true
        System.out.println("Bit at index 3: " + bits.get(3)); // false

        // Clear bits
        bits.clear(2);        // clear bit at index 2

        // Flip bits
        bits.flip(0);         // flip bit at index 0

        // Size and length
        System.out.println("BitSet length: " + bits.length());
        System.out.println("BitSet size: " + bits.size());

        // Print BitSet
        System.out.println("BitSet: " + bits);
    }
}

Core Operations

BitSet vs Alternatives

Classic Use Cases & Problems

• Sieve of Eratosthenes – Finding prime numbers efficiently
• Bloom Filters – Probabilistic membership testing
• Set Operations – Union, intersection, difference of integer sets
• Graph Algorithms – Visited node tracking in BFS/DFS
• Permutation Generation – Track used elements in backtracking
• Bit Manipulation Problems – Subset generation, bit counting
• Database Indexing – Bitmap indexes for fast queries
• Compiler Design – Register allocation, live variable analysis
• Image Processing – Binary image representation and operations
• Game Development – Collision detection, state flags
• Network Protocols – Flag management, packet filtering
• Cryptography – One-time pad, stream ciphers
• Data Compression – Run-length encoding preprocessing
• Memory Management – Free/allocated block tracking
• Scheduling Algorithms – Resource availability tracking
• Machine Learning – Feature selection, sparse data representation

Example

Finding Primes Using BitSet

import java.util.BitSet;

public class SieveBitSet {
    public static void main(String[] args) {
        int N = 50;
        BitSet primes = new BitSet(N + 1);

        // Initially assume all numbers >=2 are prime
        primes.set(2, N + 1); // set bits 2..N

        for (int i = 2; i * i <= N; i++) {
            if (primes.get(i)) {
                // Mark multiples of i as non-prime
                for (int j = i * i; j <= N; j += i) {
                    primes.clear(j);
                }
            }
        }

        // Print primes
        System.out.println("Primes up to " + N + ":");
        for (int i = 2; i <= N; i++) {
            if (primes.get(i)) {
                System.out.print(i + " ");
            }
        }
    }
}

Summary

BitSet is a specialized, highly efficient data structure for boolean operations and set manipulation. It shines in mathematical algorithms, large-scale boolean flag management, and memory-constrained environments. Choose BitSet when you need fast bitwise operations on large datasets, especially for algorithms like sieve methods, graph traversal state tracking, or any scenario involving set theory operations on integers. Its memory efficiency (1 bit per boolean vs 8 bits for boolean arrays) makes it invaluable for applications handling millions of boolean flags.

5. CopyOnWriteArrayList/CopyOnWriteArraySet

CopyOnWriteArrayList is a thread-safe variant of ArrayList (in java.util.concurrent) where all mutative operations (add, set, remove, etc.) create a fresh copy of the underlying array. Its iterators work on an immutable snapshot, so they never throw ConcurrentModificationException.

CopyOnWriteArraySet is a thread-safe Set that uses CopyOnWriteArrayList internally. It enforces uniqueness with addIfAbsent, and iterators also operate on a snapshot.

Both are ideal for read-heavy, infrequently modified data—iterations are fast and lock-free, while writes are costly due to array copying. Common use cases include listener registries, configuration snapshots, and caches. They are not suitable for write-heavy workloads because of high write overhead and GC pressure.

Key Properties

• Thread-safe, suitable for concurrent read-heavy scenarios.
• All mutative operations (add, set, remove) create a fresh copy of the underlying array.
• Iterators are weakly consistent: do not throw ConcurrentModificationException.
• Reads are lock-free, writes are expensive due to array copying.

Basic Syntax for CopyOnWriteArrayList and CopyOnWriteArraySet

import java.util.concurrent.CopyOnWriteArrayList;
import java.util.concurrent.CopyOnWriteArraySet;

public class Main {
    public static void main(String[] args) {
        // -------------------------
        // CopyOnWriteArrayList
        // -------------------------
        CopyOnWriteArrayList<String> list = new CopyOnWriteArrayList<>();
        list.add("Apple");
        list.add("Banana");
        list.add("Orange");

        System.out.println("CopyOnWriteArrayList elements:");
        for (String fruit : list) {
            System.out.println(fruit);
        }

        list.remove("Banana");
        System.out.println("After removal: " + list);

        // -------------------------
        // CopyOnWriteArraySet
        // -------------------------
        CopyOnWriteArraySet<String> set = new CopyOnWriteArraySet<>();
        set.add("Apple");
        set.add("Banana");
        set.add("Apple"); // duplicate ignored

        System.out.println("\nCopyOnWriteArraySet elements:");
        for (String fruit : set) {
            System.out.println(fruit);
        }

        set.remove("Banana");
        System.out.println("After removal: " + set);
    }
}

Core Operations

Example

import java.util.concurrent.CopyOnWriteArrayList;

// Subscriber interface
interface Subscriber {
    void notify(String message);
}

// Event Bus
class EventBus {
    private CopyOnWriteArrayList<Subscriber> subscribers = new CopyOnWriteArrayList<>();

    // Add a subscriber
    public void subscribe(Subscriber subscriber) {
        subscribers.add(subscriber);
    }

    // Remove a subscriber
    public void unsubscribe(Subscriber subscriber) {
        subscribers.remove(subscriber);
    }

    // Publish an event to all subscribers
    public void publish(String message) {
        for (Subscriber s : subscribers) {
            s.notify(message);
        }
    }
}

// Demo
public class Main {
    public static void main(String[] args) {
        EventBus bus = new EventBus();

        // Add subscribers
        bus.subscribe(msg -> System.out.println("Subscriber 1 received: " + msg));
        bus.subscribe(msg -> System.out.println("Subscriber 2 received: " + msg));

        // Publish events
        bus.publish("Event A");
        bus.publish("Event B");

        // Remove a subscriber
        bus.unsubscribe(msg -> System.out.println("Subscriber 2 received: " + msg));

        // Publish another event
        bus.publish("Event C");
    }
}

• Multiple threads can publish events (read/iterate) safely while subscribers are added/removed.
• Iteration is snapshot-based, so no ConcurrentModificationException occurs.
• Writes (adding/removing subscribers) are rare, which suits the cost of copying the array.

Classic Use Cases & Problems

• Event listener lists where reads are frequent but modifications are rare.
• Caching read-heavy data structures.
• Pub-sub systems where many threads read concurrently.
• Iterating safely without worrying about ConcurrentModificationException.
• Maintaining snapshots in concurrent applications.

Problems / Considerations:

• High memory and CPU overhead if writes are frequent (copying entire array on every write).
• Not suitable for write-heavy workloads.

Summary

Use CopyOnWriteArrayList / CopyOnWriteArraySet when reads far exceed writes and you need thread-safe, snapshot-style iteration without extra synchronization. Avoid them for write-heavy workloads due to the high cost of copying the array on every modification.

6. Disjoint Set Union (DSU) / Union-Find in Java

A Disjoint Set Union (DSU) is a data structure that keeps track of a partition of a set into disjoint (non-overlapping) subsets. It is especially useful in problems involving connectivity, merging groups, and cycle detection.

Supports two main operations:

• Find: Determine which subset a particular element belongs to.
• Union: Merge two subsets into a single subset.

Optimizations include:

• Path Compression in find()
• Union by Rank / Sizeinunion()`

Key Properties

• Efficient for connectivity problems in graphs (like detecting cycles, Kruskal’s MST algorithm).
• Each element belongs to exactly one subset.
• Supports dynamic connectivity queries.
• Almost constant time per operation: O(α(n)), where α(n) is the inverse Ackermann function.

Core Operations

Classic Use Cases

• Kruskal’s Minimum Spanning Tree algorithm.
• Detecting cycles in undirected graphs.
• Dynamic connectivity problems (e.g., network connectivity).
• Union of sets in clustering algorithms or percolation problems.

Example

public class DSU {
    private int[] parent;
    private int[] rank;

    // Initialize n elements
    public DSU(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i; // each element is its own parent
            rank[i] = 0;
        }
    }

    // Find with path compression
    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    // Union by rank
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return;

        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }

    // Check if two elements are connected
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
}

// Demo
public class Main {
    public static void main(String[] args) {
        DSU dsu = new DSU(5);

        dsu.union(0, 1);
        dsu.union(1, 2);

        System.out.println(dsu.connected(0, 2)); // true
        System.out.println(dsu.connected(0, 3)); // false
    }
}

Summary

Use Disjoint Set Union for connectivity problems and graph algorithms.
Highly efficient due to path compression and union by rank, almost constant time per operation. Ideal for Kruskal’s MST, dynamic connectivity, clustering, and percolation problems.

7. Fenwick Tree (Binary Indexed Tree) in Java

A Fenwick Tree, also called Binary Indexed Tree (BIT), is a data structure that efficiently supports:

• Prefix sum queries (sum of first k elements)
• Point updates (update a single element)
  • Time complexity: O(log n) for both query and update.
  • Space complexity: O(n).
  • Ideal for scenarios where you have frequent prefix sum or cumulative frequency queries with dynamic updates.

Key Properties

• Efficient for range sum queries on mutable arrays.
• Uses binary representation of indices to traverse parent/child relationships.
• Supports additive operations (sum, XOR, etc.).
• Not suitable for arbitrary range updates unless combined with advanced variants (like range update BIT).

Core Operations

Classic Use Cases

• Range sum queries with dynamic updates (e.g., cumulative frequency tables).
• Counting inversions in an array.
• Competitive programming problems involving prefix sums, frequencies, or 2D variants.
• Efficiently implementing histograms or cumulative statistics.

Example

public class FenwickTree {
    private int[] bit; // Binary Indexed Tree array (1-based indexing)
    private int size;  // Size of the original array

    /**
     * Constructs a Fenwick Tree for an array of a given size.
     * The tree is initialized with all zeros.
     *
     * @param size The size of the original array for which the Fenwick Tree is built.
     */
    public FenwickTree(int size) {
        this.size = size;
        this.bit = new int[size + 1]; // 1-based indexing, so size + 1
    }

    /**
     * Updates the value at a specific index in the original array by adding 'delta'.
     * This update propagates through the Fenwick Tree.
     *
     * @param index The 0-based index in the original array to update.
     * @param delta The value to add to the element at the given index.
     */
    public void update(int index, int delta) {
        // Convert to 1-based indexing for BIT operations
        index++; 
        while (index <= size) {
            bit[index] += delta;
            // Move to the next parent node by adding the rightmost set bit
            index += (index & -index); 
        }
    }

    /**
     * Queries the prefix sum up to a specific index (inclusive) in the original array.
     *
     * @param index The 0-based index in the original array up to which to calculate the sum.
     * @return The sum of elements from index 0 to 'index' in the original array.
     */
    public int query(int index) {
        int sum = 0;
        // Convert to 1-based indexing for BIT operations
        index++; 
        while (index > 0) {
            sum += bit[index];
            // Move to the next parent node by subtracting the rightmost set bit
            index -= (index & -index); 
        }
        return sum;
    }

    /**
     * Calculates the sum of elements within a given range [left, right] (inclusive, 0-based).
     *
     * @param left The 0-based starting index of the range.
     * @param right The 0-based ending index of the range.
     * @return The sum of elements from 'left' to 'right'.
     */
    public int rangeSum(int left, int right) {
        if (left > right) {
            throw new IllegalArgumentException("Left index cannot be greater than right index.");
        }
        return query(right) - (left > 0 ? query(left - 1) : 0);
    }

    // Example Usage
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        FenwickTree ft = new FenwickTree(arr.length);

        // Initialize Fenwick Tree with values from the array
        for (int i = 0; i < arr.length; i++) {
            ft.update(i, arr[i]);
        }

        System.out.println("Prefix sum up to index 2 (0-based): " + ft.query(2)); // Expected: 1 + 2 + 3 = 6
        System.out.println("Prefix sum up to index 4 (0-based): " + ft.query(4)); // Expected: 1 + 2 + 3 + 4 + 5 = 15

        // Update value at index 2 (change 3 to 10)
        ft.update(2, 7); // Add 7 to the existing value at index 2 (3 + 7 = 10)
        System.out.println("Prefix sum up to index 2 after update: " + ft.query(2)); // Expected: 1 + 2 + 10 = 13

        System.out.println("Range sum from index 1 to 3 (0-based): " + ft.rangeSum(1, 3)); // Expected: 2 + 10 + 4 = 16
    }
}

Summary

Use Fenwick Tree for dynamic prefix sums or cumulative frequency queries.
Efficient alternative to segment trees for point updates and prefix queries. Time complexity per operation: O(log n), space complexity: O(n).
Ideal for competitive programming, range queries, and real-time cumulative statistics.

8. Trie (Prefix Tree) in Java

A Trie, also known as a Prefix Tree, is a tree-like data structure used to store a dynamic set of strings efficiently, particularly for operations involving prefixes.

• There is no built-in Trie in Java.
• Typically implemented manually using custom classes with Map or arrays.
• Can use java.util.Map or java.util.HashMap for child nodes.

Key Properties

• Tree-based data structure storing strings or sequences.
• Each node represents a single character or part of the key.
• Supports fast prefix-based searches.
• Root node represents empty string.
• Efficient for word lookup, autocomplete, and dictionary operations.
• Can store boolean flag to mark end of a word.

Core Operations

Classic Use Cases & Problems

• Use Cases:
  • Autocomplete / Search suggestions
  • Spell checking
  • IP routing (storing prefixes)
  • Dictionary / word frequency problems
  • Longest prefix matching
• Problems / Considerations:
  • High memory usage for large alphabets if implemented naïvely.
  • Insertion and search depend on word length, not number of words.
  • Typically implemented with arrays (fixed alphabet) or HashMaps for children.

Example

import java.util.HashMap;

import java.util.Map;

class TrieNode {

    Map children = new HashMap<>();

    boolean isEndOfWord = false;

}

class Trie {

    private TrieNode root;

    public Trie() {

        root = new TrieNode();

    }

// Insert a word
public void insert(String word) {
    TrieNode node = root;
    for (char ch : word.toCharArray()) {
        node.children.putIfAbsent(ch, new TrieNode());
        node = node.children.get(ch);
    }
    node.isEndOfWord = true;
}

// Search for exact word
public boolean search(String word) {
    TrieNode node = root;
    for (char ch : word.toCharArray()) {
        node = node.children.get(ch);
        if (node == null) return false;
    }
    return node.isEndOfWord;
}

// Search for prefix
public boolean startsWith(String prefix) {
    TrieNode node = root;
    for (char ch : prefix.toCharArray()) {
        node = node.children.get(ch);
        if (node == null) return false;
    }
    return true;
}


}





// Demo

public class Main {

    public static void main(String[] args) {

        Trie trie = new Trie();

        trie.insert("apple");

        trie.insert("app");

        trie.insert("banana");

    System.out.println(trie.search("apple"));  // true
    System.out.println(trie.search("app"));    // true
    System.out.println(trie.search("appl"));   // false
    System.out.println(trie.startsWith("ap")); // true
    System.out.println(trie.startsWith("ba")); // true
}


}

Summary

Use Trie when you need efficient prefix searches or word lookups.
Ideal for autocomplete, dictionary, spell check, and IP prefix matching.
Efficient in search time (O(L)) but can be memory-intensive for large datasets.
Use HashMap children for dynamic alphabets, or arrays for fixed small alphabets.

This content originally appeared on DEV Community and was authored by AnkitDevCode