Java Data Structures

Complete Reference Guide

Arrays • Linked Lists • Stacks • Queues • HashMaps • Sets • Trees • Heaps • Graphs

Table of Contents

01 Array — Fixed-size contiguous memory, index access

02 Linked List — Node-pointer chain, cheap insertion/deletion

03 Stack — LIFO — push / pop / peek

04 Queue & Deque — FIFO + Priority Queue (min/max heap)

05 HashMap & HashTable — Key-value store, O(1) average lookup

06 HashSet & TreeSet — Unique elements, fast membership test

07 Binary Tree & BST — Hierarchical search with O(log n) ops

08 Heap / PriorityQueue — Complete binary tree, always access min/max

09 Graph — Vertices + edges, BFS/DFS/Dijkstra

Each section covers: definition · Java syntax · time/space complexity · when to use
 01 Array
An Array is a fixed-size, contiguous block of memory that stores elements of the same type, accessed via a
zero-based integer index. It is the most fundamental data structure and forms the backbone of many algorithms.

Java Types & Interfaces

Type / Class Description

int[] / String[] Primitive or reference type arrays

ArrayList Dynamic resizable array ([Link])

Arrays utility class Sorting, searching, copying helpers

Java Code Examples

// Primitive array
int[] arr = new int[5];
arr[0] = 10;

// Array initializer
String[] names = {"Alice", "Bob", "Charlie"};

// Dynamic array (ArrayList)

List<Integer> list = new ArrayList<>();
[Link](42);
[Link](0, 99); // insert at index 0
[Link]([Link](42));
[Link](list); // O(n log n)

// 2-D array
int[][] matrix = new int[3][4];
matrix[1][2] = 7;

Time & Space Complexity

Operation Time Complexity Space Notes

Access by index O(1) O(1) Direct memory calculation

Search (unsorted) O(n) O(1) Linear scan

Search (sorted) O(log n) O(1) Binary search

Insert at end O(1) amort. O(n) ArrayList auto-grows

Insert at index O(n) O(n) Shifts elements right

Delete at index O(n) O(1) Shifts elements left

When to Use — Problem Patterns

 Use Case / Problem Why This Structure?

Storing fixed-size data Constant-time access by index is ideal

Sliding window problems Two-pointer / window needs index arithmetic

Prefix sum / difference arrays Cumulative queries in O(1) after O(n) build

Matrix / 2-D grid problems Natural row-column mapping

Sorting algorithms In-place sorts (quicksort, mergesort) need arrays

Dynamic programming table DP states stored in 1-D or 2-D array

Heap implementation Binary heap stored as array for O(1) parent/child

Tip: Use [Link]() and [Link]() from [Link].

Tip: [Link]() and [Link]() convert between the two forms.

 02 Linked List
A Linked List is a sequential collection of nodes where each node holds a value and a pointer to the next (and
optionally previous) node. Unlike arrays, nodes are scattered in memory — there is no index-based access, but
insertions and deletions at known positions are O(1).

Java Types & Interfaces

Type / Class Description

LinkedList Doubly-linked list ([Link]) — implements List & Deque

Custom Node class Build singly/doubly linked lists from scratch

Java Code Examples

// Built-in doubly linked list

LinkedList<String> ll = new LinkedList<>();
[Link]("Head");
[Link]("Tail");
[Link](1, "Middle");
String val = [Link](0); // O(n) — no direct index!
[Link]();

// Custom singly linked list node

class ListNode {
int val;
ListNode next;
ListNode(int val) { [Link] = val; }
}

// Traverse
ListNode cur = head;
while (cur != null) {
[Link]([Link] + " -> ");
cur = [Link];
}

Time & Space Complexity

Operation Time Complexity Space Notes

Access by index O(n) O(1) Must traverse from head

Search O(n) O(1) Linear scan

Insert at head O(1) O(1) Update head pointer

Insert at tail O(1)* O(1) O(1) if tail pointer kept

Insert at index O(n) O(1) Traverse to position first

Delete at head O(1) O(1) Update head pointer

 Delete at index O(n) O(1) Traverse to predecessor

When to Use — Problem Patterns

Use Case / Problem Why This Structure?

Implementing Stack / Queue / Deque Cheap head/tail insertion & deletion

LRU Cache (least recently used) Doubly linked list + HashMap gives O(1) all ops

Reversing a sequence Classic linked list pointer reversal problem

Cycle detection (Floyd's algorithm) Fast/slow pointer on linked list

Merging / sorting lists Merge sort works naturally on linked lists

Undo / browser history Doubly linked list models backward navigation

Polynomial representation Each node = one term (coeff + exponent)

Tip: Use a dummy/sentinel head node to simplify edge cases in insert/delete.

Tip: [Link] also implements Deque — use it as a stack or queue.

 03 Stack
A Stack is a Last-In-First-Out (LIFO) data structure. The only accessible element at any time is the top. It models call
stacks, undo history, expression parsing, and depth-first traversal elegantly.

Java Types & Interfaces

Type / Class Description

Stack Legacy class — synchronized, avoid in new code

Deque / ArrayDeque Preferred — use push/pop/peek from Deque interface

LinkedList Also implements Deque; slightly slower than ArrayDeque

Java Code Examples

// Preferred: ArrayDeque as Stack

Deque<Integer> stack = new ArrayDeque<>();
[Link](10); // adds to top
[Link](20);
[Link](30);
int top = [Link](); // 30 — no removal
int popped = [Link](); // 30 — removes top
boolean empty = [Link]();

// Iterate (top to bottom)

for (int val : stack) {
[Link](val);
}

Time & Space Complexity

Operation Time Complexity Space Notes

Push O(1) O(1) Add element to top

Pop O(1) O(1) Remove element from top

Peek/Top O(1) O(1) Read top without removal

isEmpty O(1) O(1) Check empty in constant time

Search O(n) O(1) No random access

When to Use — Problem Patterns

Use Case / Problem Why This Structure?

Balanced parentheses / bracket matching Push open, pop on close, check match

Expression evaluation (RPN, infix) Operator/operand stacks

DFS — iterative graph traversal Stack mimics recursion call stack

Undo / Redo functionality Push state on action; pop on undo

Next Greater Element problems Monotonic stack technique O(n)

Browser back-button history Stack of visited URLs

Compiler syntax checking Push tokens, validate grammar rules

Tip: Prefer ArrayDeque<> over legacy Stack<> — it's faster and not synchronized.

Tip: Monotonic stack solves 'next greater/smaller element' in O(n) — a must-know pattern.
 04 Queue & Deque
A Queue is a First-In-First-Out (FIFO) structure. Elements are added at the rear (enqueue) and removed from the
front (dequeue). A Deque (double-ended queue) supports insertion and deletion at both ends, making it both a stack
and a queue.

Java Types & Interfaces

Type / Class Description

Queue / LinkedList Interface + common impl; use offer/poll/peek

ArrayDeque Fastest Deque; no null elements

PriorityQueue Min-heap queue — poll() returns smallest element

Java Code Examples

// Basic Queue (FIFO)

Queue<String> q = new LinkedList<>();
[Link]("first"); // enqueue
[Link]("second");
String front = [Link](); // 'first'
String out = [Link](); // 'first' — removed

// Deque — both ends

Deque<Integer> dq = new ArrayDeque<>();
[Link](1);
[Link](2);
[Link](); // 1
[Link](); // 2

// Priority Queue (min-heap)

PriorityQueue<Integer> pq = new PriorityQueue<>();
[Link](5); [Link](1); [Link](3);
[Link](); // returns 1 (smallest)

Time & Space Complexity

Operation Time Complexity Space Notes

offer / enqueue O(1) O(1) Add to rear

poll / dequeue O(1) O(1) Remove from front

peek O(1) O(1) Read front element

PQ offer O(log n) O(1) Heap sift-up

PQ poll O(log n) O(1) Heap sift-down

PQ peek O(1) O(1) Root of heap

When to Use — Problem Patterns
Use Case / Problem Why This Structure?

BFS — level-order graph/tree traversal Queue processes nodes level by level

Task scheduling / job queues FIFO ensures fairness

Sliding window maximum (Deque) Monotonic deque gives O(n) solution

Top-K elements PriorityQueue of size K; O(n log K)

Merge K sorted lists PriorityQueue holds one element per list

Dijkstra's shortest path Min-heap PriorityQueue for greedy selection

Print binary tree level by level Classic BFS with Queue

Tip: Never use [Link]() / element() — they throw exceptions; use poll() / peek() instead.

Tip: For max-heap, pass [Link]() to PriorityQueue constructor.

 05 HashMap & HashTable
A HashMap stores key-value pairs using a hash function to map keys to bucket indices, giving average O(1) lookup,
insertion, and deletion. Java 8+ uses a tree (red-black) inside buckets when chains exceed 8 nodes, guaranteeing
O(log n) worst-case instead of O(n).

Java Types & Interfaces

Type / Class Description

HashMap Non-synchronized, allows one null key — most common

LinkedHashMap Maintains insertion order — great for LRU

TreeMap Sorted by key (Red-Black Tree); O(log n) ops

Hashtable Legacy, synchronized — avoid; use ConcurrentHashMap

Java Code Examples

HashMap<String, Integer> map = new HashMap<>();

// Insert / Update
[Link]("apple", 3);
[Link]("banana", 5);
[Link]("apple", 1, Integer::sum); // apple -> 4

// Read
int val = [Link]("apple", 0);
boolean has = [Link]("cherry");

// Delete
[Link]("banana");

// Iterate
for ([Link]<String, Integer> e : [Link]()) {
[Link]([Link]() + " = " + [Link]());
}

// Frequency counter pattern

int[] nums = {1, 2, 2, 3, 3, 3};
Map<Integer, Integer> freq = new HashMap<>();
for (int n : nums) [Link](n, 1, Integer::sum);

Time & Space Complexity

Operation Time Complexity Space Notes

get / containsKey O(1) avg O(1) O(log n) worst after Java 8 treeify

put O(1) avg O(1) O(n) on rehash, O(log n) worst

remove O(1) avg O(1) Same as get

 Iteration O(n + cap) O(1) Iterates all buckets

TreeMap get/put O(log n) O(1) Red-black tree traversal

When to Use — Problem Patterns

Use Case / Problem Why This Structure?

Frequency / count problems Count characters, words, occurrences

Two-Sum / pair sum problems Store complement; O(1) lookup vs O(n^2) brute

Anagram / grouping problems Sort key or char-frequency key

Memoization in recursion (top-down DP) Cache subproblem results

Graph adjacency list Map> for sparse graphs

LRU Cache LinkedHashMap with removeEldestEntry

Substring / subarray problems Prefix sum + HashMap for target-sum subarrays

Tip: Use getOrDefault(key, 0) or computeIfAbsent() to avoid null checks.

Tip: Initial capacity = expectedSize / 0.75 + 1 to minimize rehashing.

 06 HashSet & TreeSet
A HashSet is an unordered collection of unique elements backed by a HashMap (values are dummy objects). It
provides O(1) average for add, remove, and contains. TreeSet keeps elements sorted using a Red-Black Tree with
O(log n) operations and supports range queries.

Java Types & Interfaces

Type / Class Description

HashSet Unordered unique set; O(1) average

LinkedHashSet Unique + insertion-ordered

TreeSet Sorted unique set; O(log n); supports floor/ceiling/range

Java Code Examples

// HashSet — uniqueness + O(1) lookup

Set<String> seen = new HashSet<>();
[Link]("cat");
[Link]("dog");
[Link]("cat"); // duplicate — ignored
boolean has = [Link]("cat"); // true
[Link]("dog");
int size = [Link](); // 1

// Set operations
Set<Integer> a = new HashSet<>([Link](1,2,3,4));
Set<Integer> b = new HashSet<>([Link](3,4,5,6));
[Link](b); // intersection: {3, 4}

// TreeSet — sorted, range queries

TreeSet<Integer> ts = new TreeSet<>([Link](5,1,3,2,4));
[Link](); // 1
[Link](); // 5
[Link](3); // <= 3 -> 3
[Link](3); // >= 3 -> 3
[Link](3); // {1, 2}
[Link](2, 5); // {2, 3, 4}

Time & Space Complexity

Operation Time Complexity Space Notes

add O(1) avg O(1) O(log n) for TreeSet

remove O(1) avg O(1) O(log n) for TreeSet

contains O(1) avg O(1) O(log n) for TreeSet

floor/ceil O(log n) O(1) TreeSet only

 Iteration O(n) O(1) Sorted for TreeSet

When to Use — Problem Patterns

Use Case / Problem Why This Structure?

Duplicate detection Add to HashSet; duplicate if add() returns false

Visited nodes in BFS/DFS O(1) containsCheck avoids revisiting

Longest Consecutive Sequence HashSet + O(n) scan — classic problem

Set intersection / union / difference retainAll / addAll / removeAll

Sliding window — unique elements Maintain a window set; add/remove ends

Find missing / extra elements XOR or Set difference

Range queries / ordered data TreeSet floor, ceiling, subSet

Tip: contains() on HashSet is O(1); on List it is O(n) — convert to Set for fast lookup.

Tip: [Link](x) returns largest element <= x; ceiling(x) returns smallest >= x.
 07 Binary Tree & BST
A Binary Tree is a hierarchical structure where each node has at most two children (left, right). A Binary Search Tree
(BST) adds the invariant: left subtree values < node < right subtree, enabling efficient O(log n) search on balanced
trees. Java's TreeMap/TreeSet use Red-Black Trees internally.

Java Types & Interfaces

Type / Class Description

Custom TreeNode Standard LeetCode / interview node definition

TreeMap Self-balancing BST (Red-Black); sorted map

TreeSet Self-balancing BST; sorted set

Java Code Examples

// Standard tree node

class TreeNode {
int val;
TreeNode left, right;
TreeNode(int val) { [Link] = val; }
}

// Inorder traversal — gives sorted output for BST

void inorder(TreeNode node) {
if (node == null) return;
inorder([Link]);
[Link]([Link] + " ");
inorder([Link]);
}

// Level-order traversal (BFS)

Queue<TreeNode> q = new LinkedList<>();
[Link](root);
while (![Link]()) {
TreeNode cur = [Link]();
if ([Link] != null) [Link]([Link]);
if ([Link] != null) [Link]([Link]);
}

Time & Space Complexity

Operation Time Complexity Space Notes

Search (balanced) O(log n) O(h) h = height; O(log n) balanced

Insert (balanced) O(log n) O(h) Sift down to leaf position

Delete (balanced) O(log n) O(h) Find in-order successor/predecessor

Search (skewed) O(n) O(n) Degenerates to linked list

 Traversal O(n) O(h) Visit every node once

Height O(n) O(h) Recursive depth calculation

When to Use — Problem Patterns

Use Case / Problem Why This Structure?

Sorted data with fast insert/search BST keeps sorted order with O(log n) ops

LCA — Lowest Common Ancestor Fundamental tree recursion problem

Serialize / deserialize trees Common interview problem

Path sum problems DFS traversal + running sum

Range queries on sorted data TreeMap subMap / TreeSet subSet

Expression tree evaluation Leaf = operand, internal = operator

Segment trees / Fenwick trees Advanced range query structures

Tip: Inorder traversal of a BST always gives elements in sorted order.

Tip: For balanced BST operations in Java, rely on TreeMap / TreeSet (Red-Black Tree).
 08 Heap / Priority Queue
A Heap is a complete binary tree stored as an array satisfying the heap property: parent <= children (min-heap) or
parent >= children (max-heap). Java provides [Link] as a min-heap by default. It excels at always
retrieving the minimum (or maximum) element in O(1).

Java Types & Interfaces

Type / Class Description

PriorityQueue Min-heap; O(log n) offer/poll

PriorityQueue(reverseOrder()
) Max-heap via comparator

Custom Comparator PQ Sort by multiple fields, custom objects

Java Code Examples

// Min-Heap (default)
PriorityQueue<Integer> minH = new PriorityQueue<>();
[Link](5); [Link](1); [Link](3);
[Link](); // 1 — always smallest

// Max-Heap
PriorityQueue<Integer> maxH =
new PriorityQueue<>([Link]());
[Link](5); [Link](1); [Link](3);
[Link](); // 5 — always largest

// Custom object heap

PriorityQueue<int[]> pq = new PriorityQueue<>(
(a, b) -> a[1] - b[1] // sort by second element
);
[Link](new int[]{1, 10});
[Link](new int[]{2, 5});
[Link](); // {2, 5} — smallest second element

// Top-K pattern
// Keep min-heap of size K; if size > K, remove min
PriorityQueue<Integer> topK = new PriorityQueue<>();
for (int n : nums) {
[Link](n);
if ([Link]() > k) [Link]();
}

Time & Space Complexity

Operation Time Complexity Space Notes

offer / insert O(log n) O(1) Sift up to restore heap property

 poll / extract O(log n) O(1) Sift down after swap with last

peek / min-max O(1) O(1) Root is always min or max

heapify array O(n) O(1) Build heap from unsorted array

heap sort O(n log n) O(1) In-place; not stable

When to Use — Problem Patterns

Use Case / Problem Why This Structure?

Top-K largest / smallest elements O(n log K) — better than sort O(n log n)

K closest points to origin Max-heap of size K on distance

Merge K sorted arrays / lists Min-heap of (value, list-index, elem-index)

Dijkstra's shortest path Min-heap on (distance, node)

Median of data stream Two heaps: max-heap (lower) + min-heap (upper)

Task scheduling — greedy PQ on deadline / priority

Huffman encoding Min-heap to build optimal prefix tree

Tip: Java PriorityQueue does NOT guarantee order during iteration — only poll() is ordered.

Tip: To find Kth largest, use a min-heap of size K; Kth smallest — max-heap of size K.
 09 Graph
A Graph is a collection of vertices (nodes) and edges (connections). Edges can be directed or undirected, weighted
or unweighted. Graphs model networks, dependencies, maps, social connections, and more. Common
representations: adjacency list (sparse) or adjacency matrix (dense).

Java Types & Interfaces

Type / Class Description

Map> Adjacency list — most common in Java

boolean[][] / int[][] Adjacency matrix — dense graphs

int[][] edges Edge list — for algorithms like Kruskal's

Java Code Examples

// Adjacency List — undirected graph

int n = 5;
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) [Link](new ArrayList<>());
// Add edge 1-2
[Link](1).add(2);
[Link](2).add(1);

// BFS
boolean[] visited = new boolean[n];
Queue<Integer> q = new LinkedList<>();
[Link](0); visited[0] = true;
while (![Link]()) {
int node = [Link]();
for (int nbr : [Link](node)) {
if (!visited[nbr]) {
visited[nbr] = true; [Link](nbr);
}
}
}

// DFS (recursive)
void dfs(int node, boolean[] vis, List<List<Integer>> adj){
vis[node] = true;
for (int nbr : [Link](node))
if (!vis[nbr]) dfs(nbr, vis, adj);
}

Time & Space Complexity

Operation Time Complexity Space Notes

BFS / DFS O(V + E) O(V) V = vertices, E = edges

 Dijkstra (PQ) O((V+E)logV) O(V+E) Min-heap; non-negative weights

Bellman-Ford O(V * E) O(V) Handles negative weights

Topological Sort O(V + E) O(V) Kahn's BFS or DFS postorder

Union-Find ops O(alpha(n)) O(V) Nearly O(1) with path compression

When to Use — Problem Patterns

Use Case / Problem Why This Structure?

Shortest path — unweighted BFS gives shortest path in hops

Shortest path — weighted Dijkstra (non-neg) / Bellman-Ford (neg)

Detect cycle in directed graph DFS with recursion stack coloring

Topological sort (DAG ordering) Kahn's BFS algorithm

Connected components BFS/DFS or Union-Find

Minimum Spanning Tree Kruskal (Union-Find) / Prim (PQ)

Word ladder / grid path problems BFS on implicit graph

Tip: Use Union-Find (Disjoint Set Union) for cycle detection and connectivity in O(alpha(n)).

Tip: Grid problems are just graphs — treat each cell as a node, edges to 4 neighbors.
 Quick Cheat Sheet

Structure Best For Avoid When

Array Index access, prefix sum, DP table Frequent mid-insert/delete

LinkedList LRU cache, deque operations Random index access needed

Stack DFS, parentheses, undo Need FIFO order

Queue/PQ BFS, top-K, Dijkstra Need LIFO order

HashMap Frequency count, two-sum Sorted key order needed

HashSet Duplicate check, visited nodes Need sorted iteration

BST/TreeMap Sorted data, range queries O(log n) too slow — use hash

Heap Top-K, median stream, Dijkstra Need arbitrary index access

Graph Paths, connectivity, ordering Purely linear relationships

Generated by Claude AI • Java Data Structures Complete Reference • 2024