Java DSA — Data Structures & Strings Cheat Sheet

Built-in structures · key methods · String & StringBuilder · iteration patterns | for technical interview rounds

■ 1 ArrayDeque — Stack / Queue / Deque

Declaration
Deque dq = new ArrayDeque<>();

Method Mode Notes

[Link](x) STACK add to front (top)

[Link]() STACK remove & return front

[Link]() STACK / QUEUE view front, no remove

[Link](x) QUEUE add to rear

[Link]() QUEUE remove & return front

[Link](x) / offerLast(x) DEQUE add to front / rear

[Link]() / pollLast() DEQUE remove from front / rear

[Link]() / peekLast() DEQUE view front / rear

[Link]() / [Link]() ALL check empty / size

Iteration
for (int x : dq) { } // front → rear
Iterator it = [Link]();
while ([Link]()) process([Link]()); // rear → front

■ Prefer ArrayDeque over Stack (legacy) for all LIFO/FIFO needs. O(1) amortised both ends.

■ 2 List — ArrayList & LinkedList

Declaration
List list = new ArrayList<>();
List ll = new LinkedList<>(); // prefer ArrayList unless front inserts needed

[Link](x) append to end O(1) amort.

[Link](i, x) insert at index O(n)

[Link](i) access by index O(1)

[Link](i, x) replace at index

[Link](i) remove by index O(n)

[Link]([Link](x)) remove first occurrence of value

[Link]() length

[Link](x) O(n) linear search

[Link](x) first index of value, -1 if absent

[Link](l, r) view [l, r) — zero-copy slice

[Link](list) natural sort O(n log n)

[Link](list) reverse in-place

[Link](list, i, j) swap elements

[Link](list, x) count occurrences

Iteration
for (int x : list) { }
for (int i = 0; i < [Link](); i++) { int x = [Link](i); }
[Link](x -> process(x));

Java DSA Cheat Sheet · Dark Edition Page 1

 [Link]().filter(x -> x > 0).forEach([Link]::println);

■ 3 Custom Sorting — Comparator Patterns

// Sort integers descending

[Link](list, (a, b) -> b - a);

// Sort 2-D array by first col, then second col

[Link](arr, (a, b) -> a[0] != b[0] ? a[0]-b[0] : a[1]-b[1]);

// Sort strings by length, then lexicographically

[Link](words, (a, b) -> [Link]() != [Link]()
? [Link]()-[Link]() : [Link](b));

// Sort objects by field

[Link]([Link](p -> [Link]));
[Link]([Link]((Person p)->[Link]).reversed());

// Chained comparator
[Link]([Link](Task::getPriority).thenComparing(Task::getName));

■ Use (a,b)->b-a only for integers — use [Link]() for objects (overflow-safe).

■ 4 PriorityQueue — Min Heap & Max Heap

Declaration
PriorityQueue minH = new PriorityQueue<>(); // default min-heap
PriorityQueue maxH = new PriorityQueue<>([Link]());
PriorityQueue pq = new PriorityQueue<>((a,b)->[Link](a)-[Link](b)); // by abs
PriorityQueue pq2 = new PriorityQueue<>((a,b)->a[0]-b[0]); // 2-D by first el

[Link](x) insert O(log n)

[Link]() remove & return min/max O(log n)

[Link]() view min/max O(1)

[Link]() / [Link]() size / empty check

[Link](x) O(n) — avoid in hot path

K Largest Elements Pattern

PriorityQueue minH = new PriorityQueue<>();
for (int n : nums) {
[Link](n);
if ([Link]() > k) [Link]();
}
// minH now holds exactly k largest; [Link]() = kth largest

// Drain iteration (destructive):

while (![Link]()) process([Link]());

■ 5 Map — HashMap · LinkedHashMap · TreeMap

Declaration
Map map = new HashMap<>(); // O(1) avg, unordered
Map lmap = new LinkedHashMap<>(); // insertion order
Map tmap = new TreeMap<>(); // sorted by key O(log n)

[Link](k, v) insert / overwrite

[Link](k) retrieve (null if absent)

[Link](k, def) retrieve with fallback — very handy

[Link](k) O(1) key check

[Link](k) delete key

[Link](k, v) insert only if key missing

Java DSA Cheat Sheet · Dark Edition Page 2

 [Link](k, 1, Integer::sum) freq counter idiom (k → old+1)

[Link](k, f) init + return value (e.g. list of lists)

[Link]() / [Link]() size / empty check

[Link]() Set of keys

[Link]() Collection of values

[Link]() Set> — use for full iteration

Iteration & Patterns

for ([Link] e : [Link]())
[Link]([Link]() + " -> " + [Link]());

[Link]((k, v) -> [Link](k + " -> " + v));

// Frequency counter
[Link](word, 1, Integer::sum);

// Group by first char (computeIfAbsent pattern)

[Link]([Link](0), k -> new ArrayList<>()).add(s);

// TreeMap: range queries

((TreeMap)tmap).firstKey(); // smallest
((TreeMap)tmap).floorKey(x); // largest key <= x
((TreeMap)tmap).ceilingKey(x); // smallest key >= x

■ 6 Set — HashSet · LinkedHashSet · TreeSet

Declaration
Set set = new HashSet<>(); // O(1) avg, unordered
Set lset = new LinkedHashSet<>(); // insertion order
Set tset = new TreeSet<>(); // sorted O(log n)

[Link](x) insert (returns false if duplicate)

[Link](x) delete

[Link](x) O(1) membership test — main DSA use case

[Link]() / [Link]() count / empty check

[Link](other) union in-place

[Link](other) intersection in-place

[Link](other) difference in-place

[Link]() / [Link]() min / max O(log n)

[Link](x) / [Link](x) largest ≤ x / smallest ≥ x

[Link](x) / [Link](x) strictly < x / strictly > x

[Link](x) / [Link](x) view < x / view ≥ x

[Link](a, b) view [a, b)

Iteration
for (int x : set) { } // unordered (HashSet)
for (int x : tset) { } // ascending (TreeSet)
for (int x : ((TreeSet)tset).descendingSet()) { } // descending

■ 7 String — Core Methods for DSA

String is immutable in Java — every modification creates a new object. Use StringBuilder for building/mutating.

Declaration & Conversion

String s = "hello";
String s = new String(charArray); // char[] → String
String s = [Link](123); // int/char/bool → String
String s = [Link]('A'); // char → String

Java DSA Cheat Sheet · Dark Edition Page 3

 int n = [Link]("42"); // String → int
char[] c = [Link](); // String → char[]
String s = [Link](n); // int → binary string
String s = [Link](n, radix); // int → string in given base

Length & Access

[Link]() number of characters

[Link](i) char at index i — O(1)

[Link](ch) first index of char/substring, -1 if absent

[Link](ch) last index of char/substring

[Link](sub, from) search starting at from

Comparison & Search

[Link](t) content equality (never use ==)

[Link](t) case-insensitive equality

[Link](t) lexicographic order — negative / 0 / positive

[Link](t) case-insensitive lexicographic compare

[Link](sub) true if sub exists anywhere

[Link](pre) prefix check

[Link](suf) suffix check

[Link](regex) full regex match

Slicing & Transformation

[Link](l) slice from l to end

[Link](l, r) slice [l, r) — very common in DSA

[Link]() / toUpperCase() case conversion

[Link]() strip leading & trailing whitespace

[Link]() Unicode-aware trim (prefer in new code)

[Link](old, new) replace all occurrences (char or String)

[Link](regex, rep) regex-based replace all

[Link](regex, rep) replace only first match

Split & Join

[Link](" ") split by space → String[]

[Link]("", 0) split into individual characters → String[] (trim trailing empty)

[Link]("-", arr) join array/list with delimiter

[Link](", ", list) join a List with delimiter

Character Classification (via Character class)

[Link](c) true if alpha

[Link](c) true if 0–9

[Link](c) true if alpha or digit

[Link](c) true if uppercase letter

[Link](c) true if lowercase letter

[Link](c) / toUpperCase(c) convert case of a single char

c - 'a' char → 0-based index (classic freq array trick)

(char)('a' + i) index → char

Common DSA Patterns

// Frequency array (lowercase letters only)
int[] freq = new int[26];

Java DSA Cheat Sheet · Dark Edition Page 4

 for (char c : [Link]()) freq[c - 'a']++;

// Reverse a string
String rev = new StringBuilder(s).reverse().toString();

// Check palindrome
int l = 0, r = [Link]()-1;
while (l < r) { if ([Link](l++) != [Link](r--)) return false; }

// Sliding window on chars

for (int i = 0; i < [Link](); i++) {
char c = [Link](i);
}

// Collect unique chars

Set seen = new HashSet<>();
for (char c : [Link]()) [Link](c);

■ 8 StringBuilder — Mutable String Building

Use StringBuilder whenever you build strings in a loop. String concatenation in a loop is O(n²); StringBuilder is O(n).

Declaration
StringBuilder sb = new StringBuilder();
StringBuilder sb = new StringBuilder("hello");
StringBuilder sb = new StringBuilder(capacity); // pre-size for performance

[Link](x) append char / int / String / boolean etc.

[Link](i, x) insert at index i

[Link](l, r) remove chars in [l, r)

[Link](i) remove single char at index

[Link](l, r, str) replace [l, r) with str

[Link]() reverse in-place — O(n)

[Link](i) read char at index O(1)

[Link](i, c) overwrite char at index O(1)

[Link](sub) first index of substring

[Link]() current length

[Link]() convert to immutable String

[Link](l, r) slice without modifying (returns String)

Patterns
// Build result string in loop (efficient)
StringBuilder sb = new StringBuilder();
for (String word : words) { [Link](word).append(' '); }
String result = [Link]().trim();

// Reverse a string
String rev = new StringBuilder(s).reverse().toString();

// Build char-by-char with condition

StringBuilder sb = new StringBuilder();
for (char c : [Link]()) {
if (![Link]() && [Link]([Link]()-1) == c) [Link]([Link]()-1);
else [Link](c);
}

// Simulate stack with StringBuilder (char stack)

[Link](c); // push
[Link]([Link]()-1); // pop
[Link]([Link]()-1); // peek

■ 9 Arrays — Utility Class

Java DSA Cheat Sheet · Dark Edition Page 5

 [Link](arr) sort primitive array O(n log n)

[Link](arr, l, r) sort range [l, r)

[Link](arr, cmp) object array with comparator

[Link](arr, x) returns index or -(insertion point)-1

[Link](arr, val) fill with value

[Link](arr, len) copy (truncate or zero-pad)

[Link](arr, l, r) copy slice [l, r)

[Link](a, b) element-wise equality

[Link](arr) readable string for debugging

[Link](1,2,3) fixed-size List — wrap in new ArrayList<>() to mutate

■ 10 Collections — Utility Class

[Link](list) sort list

[Link](list, cmp) sort with comparator

[Link](list) reverse in-place

[Link](list) random shuffle

[Link](list) / max(list) min / max element

[Link](list, x) count of x

[Link](n, val) immutable list of n copies

[Link](list) read-only wrapper

[Link](a, b) true if no common elements

[Link](list, key) O(log n) on sorted list

■ 11 Complexity Quick Reference

Structure Access Insert Delete Search

ArrayList O(1) O(1)* O(n) O(n)

ArrayDeque O(1) ends O(1)* O(1) ends —

HashMap — O(1)* O(1)* O(1)*

TreeMap — O(log n) O(log n) O(log n)

HashSet — O(1)* O(1)* O(1)*

TreeSet — O(log n) O(log n) O(log n)

PriorityQueue O(1) peek O(log n) O(log n) O(n)

String (ops) O(1) O(n) new O(n) new O(n)

StringBuilder O(1) O(1)* O(n) O(n)

* amortised average case ■ Prefer ArrayDeque over Stack · HashMap over Hashtable · ArrayList over Vector

Java DSA Cheat Sheet · Dark Edition Page 6