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()); }
}
}
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);
}
}
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);
}
}
[c, b, a] pop=c peek=b
[a, b, c] poll=a peek=b
{[()()]}=true ([)]=false ((=false a(b)c=trueCircular 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);
}
}
[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);
}
}
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());
}
}
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);
}
}
{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 2Choosing a data structure
| Need | Structure | JDK class | Key costs |
|---|---|---|---|
| Index access, append | Dynamic array | ArrayList | get O(1), add amortized O(1), insert middle O(n) |
| Add/remove at both ends | Circular array deque | ArrayDeque | O(1) at either end |
| Remove a known node often | Doubly linked list | LinkedList | unlink O(1), get(i) O(n) |
| Lookup by key | Hash table | HashMap / HashSet | O(1) average |
| Sorted keys, ranges | Red-black tree | TreeMap / TreeSet | O(log n) |
| Repeatedly take the min/max | Binary heap | PriorityQueue | peek O(1), offer/poll O(log n) |
| Prefix search | Trie | (write your own) | O(length of word) |
| Networks, dependencies | Graph | Map<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
nextbefore 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.