Data Structures in Java: The Complete Guide with Examples

Data structures are the backbone of efficient programming. Whether you're handling large datasets, optimizing performance, or preparing for coding interviews, understanding Java’s built-in and custom data structures is essential.

In this guide, we’ll explore all significant data structures in Java, from basic arrays to advanced trees and graphs. You'll learn: 
✔️ When to use each data structure 
✔️ Code examples for hands-on learning 
✔️ Real-world use cases 

By the end of this guide, you'll have a solid understanding of Java data structures and be able to choose the right one for any problem. Let’s dive in! 🚀

🔹 Array

• A fixed-size, contiguous memory block that stores elements of the same type.
• Allows constant-time (O(1)) random access using indices.
• Insertion or removal (except at the end) requires shifting elements, making it O(n).
• Example:

private void array() {
    // Fixed-size array
    int[] array = new int[10];
    array[4] = 5;

    // Dynamic array
    List<Integer> list = new ArrayList<>();
    list.add(1);
    list.addFirst(0);

    System.out.println("Array output:\t array: " + Arrays.toString(array) + ", list: " + list);
    // array: [0, 0, 0, 0, 5, 0, 0, 0, 0, 0], list: [0, 1]
}

• Use Case: Static lists, and lookup-heavy or read-intensive operations.
• Note: Not dynamically resizable — use ArrayList for dynamic data storage with similar performance benefits.

🔹 String

• A String is an immutable sequence of characters, internally implemented as a character array (char[]).
• Once created, a String object cannot be modified — any change results in a new object.
• Stored in the String Pool to save memory and enable reuse of identical string literals.
• Example:

private void string() {
    // Immutable
    String str = "Hello";
    str = str + " World"; // A new object is created, old one is discarded

    // Mutable, fast
    StringBuilder sb = new StringBuilder("Hello");
    sb.append(" ").append("World");

    // Thread-safe
    StringBuffer sbuf = new StringBuffer("Hello");
    sbuf.append(" ").append("World").append('!');

    System.out.println("String output:\t str: " + str + ", sb: " + sb + ", sbuf: " + sbuf);
    // str: Hello World, sb: Hello World, sbuf: Hello World!
}

• Use Case: Text processing, pattern matching, and encoding operations.
• Note: Immutability aligns with Java’s design goals of security, predictability, and robustness.

🔹 Linked List

• A dynamic data structure where each element (node) stores data and a reference to the next node.
• Can grow or shrink in size at runtime — ideal for collections with frequent insertions or deletions.
• Supports constant-time (O(1)) insertion and deletion at the head or tail (using iterators or references).
• Does not support random access — lookups require sequential traversal (O(n)).
• Types of Linked Lists: 
  • Singly Linked List – Each node points to the next.
  • Doubly Linked List – Each node points to both previous and next nodes.
  • Circular Linked List – Last node links back to the first.
• Example:

private void list() {
    // Use ArrayList for fast access (random access) to elements and fewer insertions/removals.
    List<Integer> arrayList = new ArrayList<>();
    arrayList.add(1);
    arrayList.add(2);

    // Use LinkedList for frequent insertions/deletions at the beginning or middle, but not random access.
    List<Integer> linkedList = new LinkedList<>();
    linkedList.addFirst(5);
    linkedList.add(7);
    linkedList.add(1, 6);

    System.out.println("List output:\t arrayList: [" + arrayList.get(0) + ", " + arrayList.get(1) + "], linkedList: " + linkedList);
    // arrayList: [1, 2], linkedList: [5, 6, 7]
}

• Use Case: Undo operations, and chaining in HashMaps.
• Note: Preferred over arrays or ArrayLists when modifying elements frequently, especially at the start or middle.

🔹 Map

• A collection of key-value pairs, where each key is unique, and values can be duplicated.
• Provides fast retrieval (O(1) average case) based on keys — ideal for lookup-heavy use cases.
• Keys are hashed internally (in HashMap) for fast access.
• Supports different implementations for different needs:
  • HashMap – Fast, unordered, allows one null key.
  • LinkedHashMap – Maintains insertion order.
  • TreeMap – Sorted by natural order or a custom comparator.
  • ConcurrentHashMap – Thread-safe access for concurrent applications.
• Example:

private void map() {
    // HashMap: No order guarantee, fast lookups (O(1))
    Map<Integer, String> hashMap = new HashMap<>();
    hashMap.put(3, "C++");
    hashMap.put(1, "Java");
    hashMap.put(2, "Python");

    // TreeMap: Sorted by keys (Natural Ordering)
    Map<Integer, String> treeMap = new TreeMap<>(hashMap);

    // LinkedHashMap: Maintains insertion order
    Map<Integer, String> linkedHashMap = new LinkedHashMap<>();
    linkedHashMap.put(3, "C++");
    linkedHashMap.put(1, "Java");
    linkedHashMap.put(2, "Python");

    System.out.println("Map output:\t\t hashMap: " + hashMap + ", treeMap: " + treeMap + ", linkedHashMap: " + linkedHashMap);
    // hashMap: {1=Java, 2=Python, 3=C++}, treeMap: {1=Java, 2=Python, 3=C++}, linkedHashMap: {3=C++, 1=Java, 2=Python}
}

• Use Case: Caching, configuration storage, and indexing.

🔹 Set

• A collection that stores only unique elements — duplicates are automatically eliminated.
• Provides efficient membership testing using the contains() method (average O(1) in HashSet).
• Different implementations in Java:
  • HashSet – Unordered, fast, allows one null element.
  • LinkedHashSet – Maintains insertion order.
  • TreeSet – Sorted order, based on natural ordering or a custom comparator.
• Example:

private void set() {
    // HashSet: Unordered, fast access (O(1)), internally uses a HashMap
    Set<String> hashSet = new HashSet<>();
    hashSet.add("Java");
    hashSet.add("Python");
    hashSet.add("C++");

    // TreeSet: Sorted order (Natural Ordering)
    Set<String> treeSet = new TreeSet<>(hashSet);

    // LinkedHashSet: Maintains insertion order
    Set<String> linkedHashSet = new LinkedHashSet<>();
    linkedHashSet.add("Java");
    linkedHashSet.add("Python");
    linkedHashSet.add("C++");

    System.out.println("Set output:\t\t hashSet: " + hashSet + ", treeSet: " + treeSet + ", linkedHashSet: " + linkedHashSet);
    // hashSet: [Java, C++, Python], treeSet: [C++, Java, Python], linkedHashSet: [Java, Python, C++]
}

• Use Case: Removing duplicates, filtering data, caching unique values, and validating entries.

🔹 Stack

• Follows the Last-In, First-Out (LIFO) principle — the last element added is the first to be removed.
• Provides constant-time (O(1)) operations:
  • push() – Add element to the top
  • pop() – Remove and return the top element
  • peek() – View the top element without removing it
• Example:

private void stack() {
    // Stack (Legacy API) is a subclass of Vector, which is synchronized and generally slower due to thread safety overhead.
    Stack<Integer> stack = new Stack<>();
    stack.push(10);
    stack.pop();

    // ArrayDeque is not synchronized (unlike Stack, which extends Vector) and does not suffer from resizing overhead like an ArrayList-based stack.
    Deque<Integer> arrayDequeAsStack = new ArrayDeque<>(); // Recommended to use as Stack for java implementations
    arrayDequeAsStack.push(10);
    arrayDequeAsStack.push(20);
    arrayDequeAsStack.push(30);
    arrayDequeAsStack.pop();

    System.out.println("Stack output:\t top element: " + arrayDequeAsStack.peek() + ", arrayDequeAsStack:  " + arrayDequeAsStack);
    // top element: 20, arrayDequeAsStack:  [20, 10]
}

• Use Case: Backtracking algorithms (e.g., maze solvers), Function call stacks in recursion, Undo/redo operations, and Browser history navigation.
• Note: Use Deque (via ArrayDeque) for better performance and cleaner usage.

🔹 Queue

• Follows the First-In, First-Out (FIFO) principle — the first element added is the first to be removed.
• Supports primary operations:
  • add() / offer() – Insert element at the rear
  • remove() / poll() – Remove and return the front element
  • peek() – View the front element without removing it
• Example:

private void queue() {
    // LinkedList uses a doubly linked list, which requires O(1) for enqueue/dequeue but has extra memory overhead (pointers for each node).
    // LinkedList suffers from pointer chasing, which increases cache misses and degrades performance.
    Queue<Integer> linkedListAsQueue = new LinkedList<>();
    linkedListAsQueue.add(10);
    linkedListAsQueue.remove();

    // ArrayDeque is backed by a resizable array, providing O(1) time complexity for enqueue (offer/add) and dequeue (poll/remove) operations.
    // ArrayDeque has a better cache locality (since arrays are stored contiguously in memory), making it faster in practice.
    Queue<Integer> arrayDequeAsQueue = new ArrayDeque<>(); // Faster than LinkedList and Recommended to use as Queue for Java implementations
    // Enqueue elements
    arrayDequeAsQueue.offer(10);
    arrayDequeAsQueue.offer(20);
    arrayDequeAsQueue.offer(30);
    // Dequeue elements
    arrayDequeAsQueue.poll();

    System.out.println("Queue output:\t top element: " + arrayDequeAsQueue.peek() + ", arrayDequeAsQueue: " + arrayDequeAsQueue);
    // top element: 20, arrayDequeAsQueue: [20, 30]
}

• Use Case: Task scheduling, resource management, and producer-consumer patterns.

🔹 Deque

• Stands for Double-Ended Queue — allows insertion and removal from both the front and rear.
• Supports all queue and stack operations:
  • addFirst(), addLast()
  • removeFirst(), removeLast()
  • peekFirst(), peekLast()
• Offers O(1) time complexity for add/remove operations on both ends.
• In Java, use:
  • ArrayDeque – high-performance, non-thread-safe
  • LinkedList – supports Deque but with slightly more overhead
• Example: Refer Stack/Queue example.
• Use Case: Sliding window algorithms (e.g., max in window), palindrome checking, and undo/redo buffers.

🔹 Priority Queue

• A queue where elements are processed based on priority, not insertion order.
• Internally implemented as a binary heap, offering:
  • O(log n) insertion and removal
  • O(1) access to the highest (or lowest) priority element
• Supports min-heap by default (smallest element first) – can be configured as a max-heap using a custom comparator
• Key operations:
  • offer() / add() – inserts with automatic ordering
  • poll() – removes the highest priority element
  • peek() – views the highest priority element
• Example:

private void priorityQueue() {
    PriorityQueue<Integer> priorityQueueAsMinHeap = new PriorityQueue<>(); // Min-Heap
    // Adding elements
    priorityQueueAsMinHeap.offer(30);
    priorityQueueAsMinHeap.offer(10);
    priorityQueueAsMinHeap.offer(20);
    priorityQueueAsMinHeap.offer(5);
    // Removing elements
    priorityQueueAsMinHeap.poll();

    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Max-Heap

    System.out.println("Heap output:\t top element: " + priorityQueueAsMinHeap.peek() + ", priorityQueueAsMinHeap: " + priorityQueueAsMinHeap);
    // top element: 10, priorityQueueAsMinHeap: [10, 30, 20]
}

• Use Case: Task scheduling, pathfinding algorithms like Dijkstra’s, load balancing and job queues.

🔹 Binary Tree

• A tree data structure where each node has at most two children: left and right.
• Represents hierarchical relationships and is the foundation for many advanced trees.
• Not inherently sorted — structure depends on insertion order.
• Example:

class TreeNode<T> {
    T data;
    TreeNode<T> left, right;

    public TreeNode(T data) {
        this.data = data;
        this.left = this.right = null;
    }
}

class BinaryTree<T> {
    TreeNode<T> root;

    public BinaryTree(T rootData) {
        this.root = new TreeNode<>(rootData);
    }

    // Inorder Traversal (Left -> Root -> Right)
    public void inorder(TreeNode<T> node) {
        if (node == null) return;
        inorder(node.left);
        System.out.print(node.data + " ");
        inorder(node.right);
    }

    // Level Order Traversal (BFS)
    public void levelOrder() {
        if (root == null) return;

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

        while (!queue.isEmpty()) {
            TreeNode<T> current = queue.poll();
            System.out.print(current.data + " ");

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

private void tree() {
    // Create a binary tree
    BinaryTree<Integer> tree = new BinaryTree<>(1);
    // Manually create left and right children
    tree.root.left = new TreeNode<>(2);
    tree.root.right = new TreeNode<>(3);
    tree.root.left.left = new TreeNode<>(4);
    tree.root.left.right = new TreeNode<>(5);
    tree.root.right.left = new TreeNode<>(6);
    tree.root.right.right = new TreeNode<>(7);

    System.out.print("Tree output:\t level order traversal: ");
    tree.levelOrder();
    // level order traversal: 1 2 3 4 5 6 7
}

• Use Case: Expression trees (e.g., arithmetic parsing), game trees (e.g., minimax algorithms), recursive structures in compilers and interpreters.
• Note: Java doesn't have a built-in BinaryTree class — typically implemented via custom Node classes with left and right references.

🔹 Binary Search Tree

• A binary tree where each node follows the rule:
  Left child < Root < Right child
• Designed for fast search, insertion, and deletion operations — average-case O(log n).
• Enables efficient range queries, sorted traversal, and duplicate avoidance (if enforced).
• If unbalanced, performance degrades to O(n) — behaves like a linked list.
• Example:

class BinarySearchTree {
    private TreeNode<Integer> root;

    public void insert(int key) {
        root = insertElement(root, key);
    }

    private TreeNode<Integer> insertElement(TreeNode<Integer> root, int key) {
        if (root == null) return new TreeNode<>(key);
        if (key < root.data) root.left = insertElement(root.left, key);
        else if (key > root.data) root.right = insertElement(root.right, key);
        return root;
    }

    public boolean search(int key) {
        return searchElement(root, key);
    }

    private boolean searchElement(TreeNode<Integer> root, int key) {
        if (root == null) return false;
        if (key == root.data) return true;
        return key < root.data ? searchElement(root.left, key) : searchElement(root.right, key);
    }

    public void inorder() {
        inorderTraversal(root);
    }

    private void inorderTraversal(TreeNode<Integer> root) {
        if (root != null) {
            inorderTraversal(root.left);
            System.out.print(root.data + " ");
            inorderTraversal(root.right);
        }
    }
}

private void binarySearchTree() {
    BinarySearchTree bst = new BinarySearchTree();
    bst.insert(5);
    bst.insert(3);
    bst.insert(9);
    bst.insert(2);
    bst.insert(4);
    bst.insert(6);
    bst.insert(8);

    // Displaying the BST (keys are sorted)
    System.out.print("BST output:\t\t search 4: " + bst.search(4) + ", search 7: " + bst.search(7) + ", in-order traversal: ");
    bst.inorder();
    // search 4: true, search 7: false, in-order traversal: 2 3 4 5 6 8 9
}

• Use Case: Symbol tables, dictionary lookups, sorted data storage, and auto-complete suggestions.
• Note: Java doesn't provide a direct BinarySearchTree class — use TreeSet or TreeMap for built-in BST-based structures (implemented as Red-Black Trees).

🔹 Red-Black Tree

• A type of self-balancing Binary Search Tree (BST) that maintains O(log n) time for insertion, deletion, and search.
• Ensures balance by enforcing coloring rules (red/black) and performing rotations after insertions/deletions.
• Guarantees that the tree height is always logarithmic, preventing degeneration into a linked list.
• Used internally by Java’s:
  • TreeMap – sorted key-value storage
  • TreeSet – sorted unique element storage
• Slightly slower lookups than HashMap, but maintains sorted order and supports range queries.
• Example:

private void redBlackTree() {
    // A TreeMap in Java is a sorted map implementation based on a Red-Black Tree.
    // It maintains keys in sorted order and provides O(log n) time complexity for insertion, deletion, and lookup.
    TreeMap<Integer, String> treeMap = new TreeMap<>(); // keys sorted in natural order
    // Adding key-value pairs
    treeMap.put(3, "Three");
    treeMap.put(1, "One");
    treeMap.put(2, "Two");
    treeMap.put(5, "Five");
    treeMap.put(4, "Four");
    // Removing an entry
    treeMap.remove(2);

    Map<Integer, String> descTreeMap = new TreeMap<>(Comparator.reverseOrder()); // keys sorted in descending order

    // Displaying the TreeMap (keys are sorted)
    System.out.println("RedBlackTree:\t first key: " + treeMap.firstKey() + ", last key: " + treeMap.lastKey() + ", treeMap: " + treeMap);
    // first key: 1, last key: 5, treeMap: {1=One, 3=Three, 4=Four, 5=Five}
}

• Use Case: Indexing, ordered collections, and range queries.

🔹 Graph

• A non-linear data structure used to represent networks or relationships between entities (nodes/vertices).
• Edges represent connections and can be:
  • Directed – edges have direction (e.g., one-way roads)
  • Undirected – edges have no direction (e.g., mutual friendship)
  • Weighted – edges have values (e.g., distances, costs)
  • Unweighted – all edges are treated equally
• Common representations:
  • Adjacency List – efficient for sparse graphs, stores a list of neighbors for each node
  • Adjacency Matrix – efficient for dense graphs, uses a 2D matrix to represent all possible connections
• Example:

class Graph {
    private final Map<Integer, List<Integer>> adjList;

    public Graph() {
        this.adjList = new HashMap<>();
    }

    // Add a vertex
    public void addVertex(int vertex) {
        adjList.putIfAbsent(vertex, new ArrayList<>());
    }

    // Add an edge (undirected)
    public void addEdge(int src, int dest) {
        adjList.putIfAbsent(src, new ArrayList<>());
        adjList.putIfAbsent(dest, new ArrayList<>());
        adjList.get(src).add(dest);
        adjList.get(dest).add(src);
    }

    // Print the graph
    public void printGraph() {
        for (var entry : adjList.entrySet()) {
            System.out.print(entry.getKey() + " -> " + entry.getValue() + "; ");
        }
    }
}

private void graph() {
    Graph graph = new Graph();
    graph.addVertex(1);
    graph.addVertex(2);
    graph.addVertex(3);
    graph.addVertex(4);
    graph.addEdge(1, 2);
    graph.addEdge(2, 3);
    graph.addEdge(3, 4);
    graph.addEdge(4, 1);

    // Displaying the Graph
    System.out.print("Graph output:\t ");
    graph.printGraph();
    // 1 -> [2, 4]; 2 -> [1, 3]; 3 -> [2, 4]; 4 -> [3, 1];
}

• Use Case: Social networks (users connected to users), web graphs (pages linking to pages), transportation systems (airports, routes), and algorithms like BFS, DFS, Dijkstra’s, etc.

🔹 Trie

• A tree-like data structure that stores strings by their prefixes.
• Enables fast lookup, insertion, and prefix-based searching in O(m) time, where m is the length of the key.
• Each node represents a single character, and paths from root to leaf represent full words.
• Reduces redundancy by sharing common prefixes, saving memory over storing full words individually.
• Example:

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean endOfWord;

    public TrieNode() {
        this.endOfWord = false;
    }
}

class Trie {
    private TrieNode root;

    public Trie() {
        root = new TrieNode();
    }

    // Insert a word into the trie
    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.endOfWord = true;
    }

    // Search for a word in the trie
    public boolean search(String word) {
        TrieNode node = root;
        for (char ch : word.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return false;
            }
            node = node.children.get(ch);
        }
        return node.endOfWord;
    }

    // Check if a prefix exists in the trie
    public boolean startsWith(String prefix) {
        TrieNode node = root;
        for (char ch : prefix.toCharArray()) {
            if (!node.children.containsKey(ch)) {
                return false;
            }
            node = node.children.get(ch);
        }
        return true;
    }
}

private void trie() {
    Trie trie = new Trie();
    trie.insert("apple");
    trie.insert("app");
    trie.insert("application");

    System.out.println("Trie output:\t " +
                       "search 'apple': " + trie.search("apple") +
        ", search 'app': " + trie.search("app") +
        ", search 'appl': " + trie.search("appl") +
        ", starts with 'app': " + trie.startsWith("app"));
    // search 'apple': true, search 'app': true, search 'appl': false, starts with 'app': true
}

• Use Case: Auto-complete, spell checkers, word games, and dictionary lookups.

📌 Summary Table

🚀 Final Thoughts

• Arrays: O(1) random access, but O(n) insertion/deletion.
• Linked Lists: O(1) insert/delete at head/tail, but O(n) search.
• HashMap: O(1) average-time operations, but O(n) worst-case with collisions.
• Stacks & Queues: O(1) insertion/deletion at one end.
• Heaps (Min/Max): O(log n) insert/delete due to heap property maintenance.
• BSTs: O(log n) search/insert/delete (balanced), but O(n) worst-case if unbalanced.
• Red-Black Trees: Always balanced, ensuring O(log n) operations.