Java CheatSheet

Sorting

Arrays.sort()

Array Type	Algorithm	Average Time	Worst Time	Space	Stable	In-Place
Primitives (int[], double[], etc.)	Dual-Pivot Quicksort	O(n log n)	O(n²)	O(log n)	❌ No	✅ Yes
Objects (String[], Integer[], custom classes)	TimSort	O(n log n)	O(n log n)	O(n)	✅ Yes	❌ No

Data Structures

Queue

A Queue in Java is a FIFO (First-In-First-Out) data structure — elements are added at the rear and removed from the front. It’s defined in the java.util package and is part of the Java Collections Framework.

Implementation	Backing Structure	Notes
LinkedList	Doubly-linked list	Simple, general-purpose, O(1) enqueue/dequeue
ArrayDeque	Resizable circular array	Faster than LinkedList (preferred)
PriorityQueue	Heap-based	Orders by priority instead of FIFO
ConcurrentLinkedQueue	Lock-free linked nodes	For multi-threaded use

Method	Description	Behavior if empty/full	Time Complexity
offer(E e)	Insert at tail	Returns false if full	O(1)
add(E e)	Insert at tail	Throws IllegalStateException if full	O(1)
poll()	Remove and return head	Returns null if empty	O(1)
remove()	Remove and return head	Throws NoSuchElementException if empty	O(1)
peek()	View head without removing	Returns null if empty	O(1)
element()	View head without removing	Throws NoSuchElementException if empty	O(1)
isEmpty()	Check if queue is empty	—	O(1)
size()	Number of elements	—	O(1)

import java.util.*;

public class QueueExample {
    public static void main(String[] args) {
        Queue<Integer> q = new ArrayDeque<>();

        // Enqueue elements
        q.offer(10);
        q.offer(20);
        q.offer(30);

        // Peek at the front
        System.out.println("Front: " + q.peek());  // 10

        // Dequeue elements
        while (!q.isEmpty()) {
            System.out.println("Processing: " + q.poll());
        }
    }
}

---

Hash Set

Feature	Description
Package	java.util
Implements	Set<E>
Backed by	HashMap<E, Object> (values stored as a dummy constant PRESENT)
Ordering	Unordered (no guarantee of iteration order)
Allows Duplicates	❌ No
Allows Null	✅ Yes (only one null element)
Thread-Safe	❌ No (wrap with Collections.synchronizedSet() or use ConcurrentHashMap-based set)

Operation	Method	Avg Time	Worst Case*	Description
Add	add(E e)	O(1)	O(n)	Adds element if absent
Remove	remove(Object o)	O(1)	O(n)	Removes if present
Contains	contains(Object o)	O(1)	O(n)	Checks existence
Size	size()	O(1)	O(1)	Number of elements
Iterate	iterator()	O(n)	O(n)	Iterate all
Clear	clear()	O(n)	O(n)	Removes all elements

Backed by a HashMap<E, Object>.

Every HashSet element is a key in the internal map; the value is a dummy Object constant.

Uses:

hashCode() → compute hash bucket

equals() → collision resolution

From Java 8 onward, when buckets become large (>8 entries), the internal list converts to a balanced tree → improves worst-case from O(n) → O(log n).

import java.util.*;

public class HashSetDemo {
    public static void main(String[] args) {
        Set<String> countries = new HashSet<>();

        // Add elements
        countries.add("Japan");
        countries.add("USA");
        countries.add("India");
        countries.add("USA"); // duplicate ignored

        // Check existence
        System.out.println(countries.contains("India")); // true

        // Remove
        countries.remove("Japan");

        // Iterate
        for (String c : countries) {
            System.out.println(c);
        }

        // Size
        System.out.println("Size: " + countries.size());
    }
}

Use when you only care about uniqueness (not ordering).

⚠️ For predictable order, use:

• LinkedHashSet → preserves insertion order.
• TreeSet → sorted order (O(log n) ops).

⚙️ Choose initial capacity wisely if large inserts are expected:

new HashSet<>(expectedSize * 4 / 3 + 1);

Always implement hashCode() and equals() consistently in custom classes.

Stack

Operation	Method	Complexity	Description
Push	push(E e)	O(1)	Add item to top
Pop	pop()	O(1)	Remove and return top
Peek	peek()	O(1)	Return top without remove
Search	search(Object o)	O(n)	1-based position from top
Empty	empty()	O(1)	Check if empty

import java.util.Stack;

Stack<Integer> stack = new Stack<>();

stack.push(10);   // push element
stack.push(20);
stack.pop();      // removes and returns top -> 20
stack.peek();     // returns top without removing -> 10
stack.empty();    // true if stack is empty
stack.size();     // number of elements

ArrayDeque

• Resizable array–based double-ended queue.
• Supports LIFO (stack) and FIFO (queue) operations.
• Non-blocking and non-thread-safe, but faster than Stack or LinkedList.
• Introduced in Java 6.

Deque<String> stack = new ArrayDeque<>();

stack.push("A");
stack.push("B");
stack.push("C");

System.out.println(stack.pop());  // C
System.out.println(stack.peek()); // B
System.out.println(stack.size()); // 2