LearnFrenzy
Sign in Take a free test

Java Programming · Topic 28 of 28

Data Structures in Java

  • 4 exercises
  • 60 questions
  • ~60 min
  • Answers explained

Introduction & Syntax

Data Structures in Java · Study material

A data structure is a way of organising data so that the operations your program needs most are fast. An array gives instant access by index but slow insertion in the middle; a linked list inserts in O(1) but must walk to find anything; a hash table finds a key in O(1) on average; a balanced tree keeps keys sorted with O(log n) operations; a heap always hands you the smallest (or largest) item; a graph models networks of roads, friends or dependencies. Java's Collections Framework already ships tuned versions of most of these – ArrayList, LinkedList, ArrayDeque, PriorityQueue, HashMap, TreeMap – but interviews and real design decisions need you to know how they work. This page builds each structure from scratch in plain Java, measures it with Big-O, and maps it to the JDK class you would use in production. Then practise with 60 questions – 20 MCQs, 20 predict-the-output puzzles, 10 find-the-error programs and 10 complete programs – compiled and run on Java 21.

On this page

  • Big-O and choosing a structure
  • Dynamic arrays: how ArrayList grows
  • Singly linked lists: insert, delete, reverse
  • Stacks, queues and deques with ArrayDeque; circular queues
  • Binary heaps and PriorityQueue
  • Binary search trees and tree traversals
  • Graphs: adjacency lists, BFS and DFS

Big-O in one minute

Big-O describes how the work grows as the input size n grows, ignoring constants: O(1) is constant, O(log n) halves the problem each step (binary search, balanced trees), O(n) touches every element once, O(n log n) is efficient sorting, and O(n²) is a nested loop over the data. "Amortized O(1)" means an operation is occasionally expensive but cheap on average over many calls – exactly how a dynamic array's add behaves.

Dynamic arrays

An array has a fixed length. A dynamic array keeps a bigger backing array than it needs and, when it fills up, copies everything into a larger one. Because the capacity grows by a factor (ArrayList uses 1.5×, this example 2×), the copies are rare and appending is amortized O(1). Access by index is O(1); inserting or removing in the middle shifts elements and is O(n).

import java.util.Arrays;

public class Main {
    // A growable int array – the idea behind ArrayList
    static class IntList {
        private int[] data = new int[2];
        private int size;

        void add(int x) {
            if (size == data.length) {                              // full: copy into a bigger array (rare)
                data = Arrays.copyOf(data, data.length * 2);
                System.out.println("  grew to " + data.length);
            }
            data[size++] = x;                                       // usual case: O(1)
        }

        int get(int i) {
            if (i < 0 || i >= size) throw new IndexOutOfBoundsException("index " + i + ", size " + size);
            return data[i];                                         // random access: O(1)
        }

        void removeAt(int i) {
            System.arraycopy(data, i + 1, data, i, size - i - 1);   // shift the tail left: O(n)
            size--;
        }

        @Override public String toString() {
            return Arrays.toString(Arrays.copyOf(data, size)) + " size=" + size + " capacity=" + data.length;
        }
    }

    public static void main(String[] args) {
        IntList list = new IntList();
        for (int i = 1; i <= 5; i++) list.add(i * 10);
        System.out.println(list);
        list.removeAt(1);
        System.out.println(list + " get(1)=" + list.get(1));
        try { list.get(4); } catch (IndexOutOfBoundsException e) { System.out.println(e.getMessage()); }
    }
}

Output

  grew to 4
  grew to 8
[10, 20, 30, 40, 50] size=5 capacity=8
[10, 30, 40, 50] size=4 capacity=8 get(1)=30
index 4, size 4

Linked lists

A linked list is a chain of nodes, each holding a value and a reference to the next node. Adding at the head is O(1) and no shifting is ever needed, but reaching the i-th element means walking from the head – O(n). A doubly linked list (java.util.LinkedList) also stores a prev reference, so a known node can be unlinked in O(1) and the list can be walked backwards.

public class Main {
    static class Node {
        int val;
        Node next;
        Node(int val, Node next) { this.val = val; this.next = next; }
    }

    static class SinglyLinkedList {
        Node head;
        int size;

        void addFirst(int v) { head = new Node(v, head); size++; }          // O(1)

        void addLast(int v) {                                              // O(n) without a tail pointer
            Node n = new Node(v, null);
            if (head == null) head = n;
            else { Node cur = head; while (cur.next != null) cur = cur.next; cur.next = n; }
            size++;
        }

        boolean remove(int v) {                                            // unlink the first match
            if (head == null) return false;
            if (head.val == v) { head = head.next; size--; return true; }
            for (Node cur = head; cur.next != null; cur = cur.next)
                if (cur.next.val == v) { cur.next = cur.next.next; size--; return true; }
            return false;
        }

        void reverse() {                                                   // O(n) time, O(1) extra space
            Node prev = null, cur = head;
            while (cur != null) { Node next = cur.next; cur.next = prev; prev = cur; cur = next; }
            head = prev;
        }

        @Override public String toString() {
            StringBuilder sb = new StringBuilder();
            for (Node cur = head; cur != null; cur = cur.next) sb.append(cur.val).append(cur.next != null ? " -> " : "");
            return sb.append(" (size ").append(size).append(')').toString();
        }
    }

    public static void main(String[] args) {
        SinglyLinkedList list = new SinglyLinkedList();
        list.addLast(20); list.addLast(30); list.addFirst(10); list.addLast(40);
        System.out.println(list);
        System.out.println(list.remove(30) + " " + list.remove(99));
        list.reverse();
        System.out.println(list);
    }
}

Output

10 -> 20 -> 30 -> 40 (size 4)
true false
40 -> 20 -> 10 (size 3)

Stacks, queues and deques

A stack is last-in, first-out (undo history, the call stack, matching brackets); a queue is first-in, first-out (print jobs, BFS); a deque allows both ends. In Java use ArrayDeque for all three – push/pop/peek for a stack, offer/poll/peek for a queue. The legacy Stack class is synchronized and extends Vector, so it is slower and exposes index methods a stack should not have.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Queue;
import java.util.StringJoiner;

public class Main {
    static boolean balanced(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (char c : s.toCharArray()) {
            switch (c) {
                case '(', '[', '{' -> stack.push(c);                     // remember every opener
                case ')', ']', '}' -> {
                    if (stack.isEmpty()) return false;                   // closer with no opener
                    char open = stack.pop();
                    if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
                }
                default -> { }                                           // ignore other characters
            }
        }
        return stack.isEmpty();                                          // unclosed openers left?
    }

    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>();     // LIFO: push / pop / peek at the head
        stack.push("a"); stack.push("b"); stack.push("c");
        System.out.println(stack + " pop=" + stack.pop() + " peek=" + stack.peek());

        Queue<String> queue = new ArrayDeque<>();     // FIFO: offer at the tail, poll from the head
        queue.offer("a"); queue.offer("b"); queue.offer("c");
        System.out.println(queue + " poll=" + queue.poll() + " peek=" + queue.peek());

        StringJoiner sj = new StringJoiner(" ");
        for (String s : new String[]{"{[()()]}", "([)]", "((", "a(b)c"}) sj.add(s + "=" + balanced(s));
        System.out.println(sj);
    }
}

Output

[c, b, a] pop=c peek=b
[a, b, c] poll=a peek=b
{[()()]}=true ([)]=false ((=false a(b)c=true

Circular queues

A queue on a plain array would run out of room at the end even when the front is empty. A circular queue (ring buffer) wraps its indexes with % capacity, reusing freed slots – the structure behind ArrayDeque, keyboard buffers and audio streams.

public class Main {
    // A fixed-size FIFO queue on an array whose indexes wrap around (a ring buffer)
    static class RingBuffer {
        private final int[] data;
        private int head, tail, size;          // head: next slot to read, tail: next slot to write

        RingBuffer(int capacity) { data = new int[capacity]; }

        boolean offer(int x) {
            if (size == data.length) return false;           // full – nothing is overwritten
            data[tail] = x;
            tail = (tail + 1) % data.length;                 // wrap around to 0 after the last slot
            size++;
            return true;
        }

        int poll() {
            if (size == 0) throw new IllegalStateException("empty");
            int x = data[head];
            head = (head + 1) % data.length;
            size--;
            return x;
        }

        @Override public String toString() {
            StringBuilder sb = new StringBuilder("[");
            for (int i = 0; i < size; i++) sb.append(i == 0 ? "" : ", ").append(data[(head + i) % data.length]);
            return sb.append("] head=").append(head).append(" tail=").append(tail).toString();
        }
    }

    public static void main(String[] args) {
        RingBuffer q = new RingBuffer(4);
        boolean fifth = false;
        for (int i = 1; i <= 5; i++) fifth = q.offer(i * 10);
        System.out.println(q + " fifth offer=" + fifth);
        System.out.println("polled " + q.poll() + " and " + q.poll());
        q.offer(50);
        q.offer(60);                                         // these two reuse slots 0 and 1
        System.out.println(q);
    }
}

Output

[10, 20, 30, 40] head=0 tail=0 fifth offer=false
polled 10 and 20
[30, 40, 50, 60] head=2 tail=2

Heaps and PriorityQueue

A binary heap is a complete binary tree stored in an array: the children of index i are at 2i + 1 and 2i + 2, and every parent is ≤ its children (a min-heap). peek is O(1); offer and poll are O(log n) because one element "sifts" up or down a single path. Java's PriorityQueue is a min-heap by default; pass a Comparator for any other order. Its iterator and toString show the heap array, not sorted order – only repeated poll gives sorted output.

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    record Task(String name, int priority) { }

    public static void main(String[] args) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(List.of(42, 7, 19, 3, 25));
        System.out.println("peek=" + minHeap.peek() + " size=" + minHeap.size());
        List<Integer> sorted = new ArrayList<>();
        while (!minHeap.isEmpty()) sorted.add(minHeap.poll());      // each poll removes the current minimum
        System.out.println(sorted);

        // The 3 largest values with a min-heap that never holds more than 3: O(n log k)
        PriorityQueue<Integer> top = new PriorityQueue<>();
        for (int x : new int[]{15, 4, 99, 23, 8, 61, 42, 77}) {
            top.offer(x);
            if (top.size() > 3) top.poll();                           // drop the smallest of the four
        }
        List<Integer> best = new ArrayList<>(top);
        best.sort(Comparator.reverseOrder());
        System.out.println("top 3: " + best);

        // Highest priority first, ties broken by name
        PriorityQueue<Task> tasks = new PriorityQueue<>(Comparator.comparingInt(Task::priority).reversed().thenComparing(Task::name));
        tasks.add(new Task("email", 1));
        tasks.add(new Task("deploy", 5));
        tasks.add(new Task("bugfix", 5));
        tasks.add(new Task("review", 3));
        StringBuilder order = new StringBuilder();
        while (!tasks.isEmpty()) order.append(tasks.poll().name()).append(tasks.isEmpty() ? "" : ", ");
        System.out.println(order);
    }
}

Output

peek=3 size=5
[3, 7, 19, 25, 42]
top 3: [99, 77, 61]
bugfix, deploy, review, email

Binary search trees

In a BST every key in a node's left subtree is smaller and every key in its right subtree is larger, so search, insert and delete follow one root-to-leaf path: O(height). A balanced tree has height about log₂ n, but inserting sorted data into a plain BST builds a "linked list" of height n. That is why the JDK's TreeMap and TreeSet use a self-balancing red-black tree. An inorder traversal (left, node, right) visits a BST's keys in sorted order.

import java.util.ArrayList;
import java.util.List;

public class Main {
    static class BST {
        private static class Node {
            final int key;
            Node left, right;
            Node(int key) { this.key = key; }
        }

        private Node root;
        private int size;

        void insert(int key) { root = insert(root, key); }
        private Node insert(Node n, int key) {
            if (n == null) { size++; return new Node(key); }
            if (key < n.key) n.left = insert(n.left, key);
            else if (key > n.key) n.right = insert(n.right, key);      // equal keys are ignored
            return n;
        }

        boolean contains(int key) {                                    // walk one path: O(height)
            Node n = root;
            while (n != null) {
                if (key == n.key) return true;
                n = key < n.key ? n.left : n.right;
            }
            return false;
        }

        int height() { return height(root); }
        private int height(Node n) { return n == null ? 0 : 1 + Math.max(height(n.left), height(n.right)); }

        int min() { Node n = root; while (n.left != null) n = n.left; return n.key; }

        List<Integer> inorder() { List<Integer> out = new ArrayList<>(); inorder(root, out); return out; }
        private void inorder(Node n, List<Integer> out) {
            if (n == null) return;
            inorder(n.left, out); out.add(n.key); inorder(n.right, out);   // left, node, right
        }

        List<Integer> preorder() { List<Integer> out = new ArrayList<>(); preorder(root, out); return out; }
        private void preorder(Node n, List<Integer> out) {
            if (n == null) return;
            out.add(n.key); preorder(n.left, out); preorder(n.right, out); // node, left, right
        }
    }

    public static void main(String[] args) {
        BST t = new BST();
        for (int k : new int[]{50, 30, 70, 20, 40, 60, 80, 35, 30}) t.insert(k);
        System.out.println("inorder  " + t.inorder());
        System.out.println("preorder " + t.preorder());
        System.out.println("size=" + t.size + " height=" + t.height() + " min=" + t.min());
        System.out.println(t.contains(35) + " " + t.contains(65));

        BST skewed = new BST();
        for (int k = 1; k <= 6; k++) skewed.insert(k);                   // sorted input: every node goes right
        System.out.println("sorted input -> height " + skewed.height());
    }
}

Output

inorder  [20, 30, 35, 40, 50, 60, 70, 80]
preorder [50, 30, 20, 40, 35, 70, 60, 80]
size=8 height=4 min=20
true false
sorted input -> height 6

Graphs, BFS and DFS

A graph is a set of vertices joined by edges. Store a sparse graph as an adjacency list (Map<V, List<V>>, O(V + E) space) or a dense one as an adjacency matrix (O(V²)). Breadth-first search uses a queue and finds the fewest-edge path; depth-first search uses recursion (or an explicit stack) and powers cycle detection, topological sorting and connected components. Both run in O(V + E).

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Main {
    static void dfs(Map<String, List<String>> g, String u, Set<String> seen, List<String> order) {
        if (!seen.add(u)) return;                     // already visited
        order.add(u);
        for (String v : g.get(u)) dfs(g, v, seen, order);
    }

    public static void main(String[] args) {
        // Undirected graph as an adjacency list: vertex → neighbours
        Map<String, List<String>> g = new LinkedHashMap<>();
        String[][] edges = {{"A", "B"}, {"A", "C"}, {"B", "D"}, {"C", "D"}, {"D", "E"}, {"F", "G"}};
        for (String[] e : edges) {
            g.computeIfAbsent(e[0], k -> new ArrayList<>()).add(e[1]);
            g.computeIfAbsent(e[1], k -> new ArrayList<>()).add(e[0]);
        }
        System.out.println(g);

        // BFS: visits level by level, so it finds the fewest-edges distance
        Map<String, Integer> dist = new LinkedHashMap<>();
        Deque<String> queue = new ArrayDeque<>();
        dist.put("A", 0);
        queue.add("A");
        while (!queue.isEmpty()) {
            String u = queue.poll();
            for (String v : g.get(u))
                if (!dist.containsKey(v)) { dist.put(v, dist.get(u) + 1); queue.add(v); }
        }
        System.out.println("BFS " + dist);

        // DFS: goes as deep as possible before backtracking
        List<String> order = new ArrayList<>();
        dfs(g, "A", new HashSet<>(), order);
        System.out.println("DFS " + order);

        // Connected components: start a new DFS from every unvisited vertex
        Set<String> seen = new HashSet<>();
        int components = 0;
        for (String v : g.keySet())
            if (!seen.contains(v)) { components++; dfs(g, v, seen, new ArrayList<>()); }
        System.out.println("components " + components);
    }
}

Output

{A=[B, C], B=[A, D], C=[A, D], D=[B, C, E], E=[D], F=[G], G=[F]}
BFS {A=0, B=1, C=1, D=2, E=3}
DFS [A, B, D, C, E]
components 2

Choosing a data structure

NeedStructureJDK classKey costs
Index access, appendDynamic arrayArrayListget O(1), add amortized O(1), insert middle O(n)
Add/remove at both endsCircular array dequeArrayDequeO(1) at either end
Remove a known node oftenDoubly linked listLinkedListunlink O(1), get(i) O(n)
Lookup by keyHash tableHashMap / HashSetO(1) average
Sorted keys, rangesRed-black treeTreeMap / TreeSetO(log n)
Repeatedly take the min/maxBinary heapPriorityQueuepeek O(1), offer/poll O(log n)
Prefix searchTrie(write your own)O(length of word)
Networks, dependenciesGraphMap<V, List<V>>BFS/DFS O(V + E)

Common mistakes

  • Using java.util.Stack instead of ArrayDeque for a stack.
  • Expecting PriorityQueue's toString or for-each to be sorted – only poll returns items in order.
  • Calling LinkedList.get(i) inside a loop – that turns an O(n) loop into O(n²).
  • Losing the rest of a linked list by overwriting next before saving it.
  • Forgetting the visited set in BFS/DFS on a graph with cycles – the search never ends.
  • Inserting sorted data into an unbalanced BST and getting O(n) operations.
  • Making a node class an inner (non-static) class when it does not need the outer instance.

Key points to remember

  • Pick the structure whose cheap operations match your most frequent operations.
  • Arrays: O(1) index; linked lists: O(1) splice; hash tables: O(1) average lookup.
  • Stack = LIFO, queue = FIFO; use ArrayDeque for both.
  • A heap gives the min (or max) in O(1) and removes it in O(log n).
  • BST operations cost O(height); balance keeps the height near log n.
  • BFS uses a queue (shortest path in edges); DFS uses a stack or recursion.

Frequently asked questions

ArrayList or LinkedList?

ArrayList in almost every case: it is compact, cache-friendly and O(1) by index. LinkedList only wins when you remove or insert through an iterator at known positions very often.

Why is ArrayDeque faster than Stack and LinkedList?

It is an unsynchronized circular array: no locking (unlike Stack) and no node object per element (unlike LinkedList).

Is a heap the same as a sorted array?

No. A heap only guarantees that each parent is ≤ its children, which is enough to find the minimum in O(1) and keep that property in O(log n) per change.

Where can I learn more?

Read Java Collections Framework and Java HashMap, then practise with the exercises below.

Ready to test your Programming?

Timed online tests with instant scores and explanations.

About this section

About Java Programming

Java is one of the most used languages in the world – for enterprise software, Android apps, banking systems and backend services. This section covers core Java from syntax and data types to OOP, strings, arrays, exceptions, collections and multithreading, with clear explanations and practice questions for every topic.

Why it matters

  • Java is the main language in service-company placement tests and many product companies
  • OOP, String, collections and exception questions appear in nearly every Java interview
  • Strong core Java is the base for Spring Boot, Android and backend development
  • Java questions are common in university exams and certification tests

Who it is for

  • School students (Class 11–12 / ICSE computer applications) learning Java
  • College students (B.Tech, BCA, MCA) preparing for exams, labs and projects
  • Freshers preparing for placements, Java developer roles and technical interviews
  • Developers revising core Java before an interview

What every topic gives you

  • Study material in five tabs: concepts with runnable examples, coding techniques, programs, interview questions and a cheat sheet
  • MCQs that check your understanding of every concept
  • "Predict the output" puzzles – the trickiest part of written tests
  • "Find the error" programs that train you to spot bugs quickly
  • Complete programs with solutions and real output, verified on a compiler

Asked in

  • Campus placements
  • Java developer interviews
  • Service company tests
  • University exams
  • Certification exams
  • Government IT exams

How to use this section

  1. Read the study material of a topic and run the examples yourself.
  2. Practise the four exercises – MCQs, output, errors, programs – and read every explanation.
  3. Test yourself with the timed online test, then revise the topics you got wrong.

Search LearnFrenzy

Esc

Quick links