DSA Concepts
Quick reference guide for Java Data Structure and Algorithms.
🔢 Arrays
// 1) Declaring and initializing arrays
int[] numbers = new int[5]; // Fixed-size array with default values (0)
int[] primes = {2, 3, 5, 7, 11}; // Array literal
String[] fruits = new String[3]; // Array of Strings (null by default)
// 2) Accessing elements
int firstPrime = primes[0]; // Access by index (zero-based): 2
primes[4] = 13; // Modify element
// 3) Array properties
int length = primes.length; // Array length: 5
// 4) Multi-dimensional arrays
int[][] matrix = new int[3][3]; // 3x3 matrix with default values
int[][] grid = {
{1, 2, 3},
{4, 5, 6},
{7, 8, 9}
}; // 2D array literal
// Accessing elements in 2D array
int center = grid[1][1]; // 5
// 5) Array utilities (java.util.Arrays)
import java.util.Arrays;
// Sorting
int[] unsorted = {5, 2, 8, 1, 9};
Arrays.sort(unsorted); // Sorts in-place: [1, 2, 5, 8, 9]
// Binary search (on sorted array)
int index = Arrays.binarySearch(unsorted, 5); // Returns index: 2
// Fill
int[] zeros = new int[5];
Arrays.fill(zeros, 0); // [0, 0, 0, 0, 0]
// Copy
int[] copy = Arrays.copyOf(primes, primes.length);
int[] partial = Arrays.copyOfRange(primes, 1, 4); // [3, 5, 7]
// Compare
boolean equal = Arrays.equals(primes, copy); // true
// Convert to String
String arrayStr = Arrays.toString(primes); // "[2, 3, 5, 7, 13]"
// 6) Dynamic arrays (ArrayList)
import java.util.ArrayList;
ArrayList<Integer> dynamicArray = new ArrayList<>();
dynamicArray.add(10); // Add to end
dynamicArray.add(20); // [10, 20]
dynamicArray.add(0, 5); // Add at index: [5, 10, 20]
dynamicArray.set(1, 15); // Replace: [5, 15, 20]
int value = dynamicArray.get(0); // Get by index: 5
dynamicArray.remove(2); // Remove by index: [5, 15]
int size = dynamicArray.size(); // Size: 2
boolean contains = dynamicArray.contains(15); // true📋 Lists
import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Arrays;
// 1) ArrayList (dynamic array implementation)
List<String> namesList = new ArrayList<>();
namesList.add("Alice"); // Add element
namesList.add("Bob");
namesList.add("Charlie");
// Common list operations
namesList.add(1, "David"); // Insert at index: [Alice, David, Bob, Charlie]
namesList.set(2, "Eve"); // Replace: [Alice, David, Eve, Charlie]
namesList.remove("Eve"); // Remove by value: [Alice, David, Charlie]
namesList.remove(0); // Remove by index: [David, Charlie]
boolean exists = namesList.contains("David"); // true
int size = namesList.size(); // 2
boolean empty = namesList.isEmpty(); // false
String first = namesList.get(0); // "David"
// 2) LinkedList (doubly-linked list implementation)
List<Integer> linkedNumbers = new LinkedList<>();
linkedNumbers.add(10);
linkedNumbers.add(20);
linkedNumbers.add(30);
// LinkedList specific operations
LinkedList<Integer> numbers = (LinkedList<Integer>) linkedNumbers;
numbers.addFirst(5); // Add to front: [5, 10, 20, 30]
numbers.addLast(40); // Add to end: [5, 10, 20, 30, 40]
int first = numbers.getFirst(); // 5
int last = numbers.getLast(); // 40
numbers.removeFirst(); // [10, 20, 30, 40]
numbers.removeLast(); // [10, 20, 30]
// 3) Creating lists from arrays
List<String> fixedList = Arrays.asList("Red", "Green", "Blue");
// fixedList.add("Yellow"); // Error: Fixed size!
// Java 9+ immutable lists
List<String> immutableList = List.of("Red", "Green", "Blue");
// 4) Iterating through lists
// Using for-each loop
for (String name : namesList) {
System.out.println(name);
}
// Using iterator
import java.util.Iterator;
Iterator<String> it = namesList.iterator();
while (it.hasNext()) {
String name = it.next();
// it.remove(); // Safe removal during iteration
}
// Using forEach method (Java 8+)
namesList.forEach(name -> System.out.println(name));
// 5) Sorting lists
import java.util.Collections;
Collections.sort(namesList); // Natural ordering
// Custom comparator
import java.util.Comparator;
Collections.sort(namesList, Comparator.reverseOrder());
// Java 8+
namesList.sort(Comparator.naturalOrder());🔍 Sets
import java.util.Set;
import java.util.HashSet;
import java.util.TreeSet;
import java.util.LinkedHashSet;
// 1) HashSet (unordered, fastest)
Set<String> fruits = new HashSet<>();
fruits.add("Apple"); // Add element
fruits.add("Banana");
fruits.add("Apple"); // Duplicate ignored
System.out.println(fruits); // [Banana, Apple] (order not guaranteed)
boolean contains = fruits.contains("Apple"); // true
fruits.remove("Banana"); // Remove element
int size = fruits.size(); // 1
// 2) TreeSet (sorted)
Set<Integer> numbers = new TreeSet<>();
numbers.add(5);
numbers.add(1);
numbers.add(10);
System.out.println(numbers); // [1, 5, 10] (natural ordering)
// TreeSet with custom comparator
Set<String> orderedStrings = new TreeSet<>(Comparator.comparing(String::length));
orderedStrings.add("aaa");
orderedStrings.add("b");
orderedStrings.add("cc");
System.out.println(orderedStrings); // [b, cc, aaa] (ordered by length)
// 3) LinkedHashSet (insertion-ordered)
Set<String> orderedFruits = new LinkedHashSet<>();
orderedFruits.add("Banana");
orderedFruits.add("Apple");
orderedFruits.add("Orange");
System.out.println(orderedFruits); // [Banana, Apple, Orange] (insertion order)
// 4) Set operations
Set<Integer> set1 = new HashSet<>(Arrays.asList(1, 2, 3, 4, 5));
Set<Integer> set2 = new HashSet<>(Arrays.asList(4, 5, 6, 7, 8));
// Union
Set<Integer> union = new HashSet<>(set1);
union.addAll(set2); // [1, 2, 3, 4, 5, 6, 7, 8]
// Intersection
Set<Integer> intersection = new HashSet<>(set1);
intersection.retainAll(set2); // [4, 5]
// Difference
Set<Integer> difference = new HashSet<>(set1);
difference.removeAll(set2); // [1, 2, 3]
// Subset testing
boolean isSubset = set1.containsAll(intersection); // true
// 5) Iterating through sets
for (String fruit : fruits) {
System.out.println(fruit);
}
// 6) Creating immutable sets (Java 9+)
Set<String> immutableSet = Set.of("Red", "Green", "Blue");🔑 Maps
import java.util.Map;
import java.util.HashMap;
import java.util.TreeMap;
import java.util.LinkedHashMap;
// 1) HashMap (unordered, fastest)
Map<String, Integer> ages = new HashMap<>();
ages.put("Alice", 30); // Add key-value pair
ages.put("Bob", 25);
ages.put("Charlie", 35);
// 2) Accessing elements
int aliceAge = ages.get("Alice"); // 30
Integer davidAge = ages.get("David"); // null
int defaultAge = ages.getOrDefault("David", 0); // 0
boolean exists = ages.containsKey("Bob"); // true
boolean hasAge30 = ages.containsValue(30); // true
// 3) Updating and removing
ages.put("Bob", 26); // Update value
ages.remove("Charlie"); // Remove key-value pair
// 4) Map properties
int size = ages.size(); // 2
boolean isEmpty = ages.isEmpty(); // false
// 5) Views of the map
Set<String> keys = ages.keySet(); // [Alice, Bob]
Collection<Integer> values = ages.values(); // [30, 26]
Set<Map.Entry<String, Integer>> entries = ages.entrySet();
// 6) TreeMap (sorted by keys)
Map<String, String> employees = new TreeMap<>();
employees.put("C123", "Charlie");
employees.put("A789", "Alice");
employees.put("B456", "Bob");
System.out.println(employees); // {A789=Alice, B456=Bob, C123=Charlie}
// 7) LinkedHashMap (insertion order)
Map<String, Double> prices = new LinkedHashMap<>();
prices.put("Banana", 1.99);
prices.put("Apple", 0.99);
prices.put("Orange", 1.49);
System.out.println(prices); // {Banana=1.99, Apple=0.99, Orange=1.49}
// 8) Iterating through maps
// Over keys
for (String name : ages.keySet()) {
System.out.println(name + " is " + ages.get(name) + " years old");
}
// Over entries
for (Map.Entry<String, Integer> entry : ages.entrySet()) {
System.out.println(entry.getKey() + " is " + entry.getValue() + " years old");
}
// Java 8+ forEach
ages.forEach((name, age) -> System.out.println(name + " is " + age + " years old"));
// 9) Immutable maps (Java 9+)
Map<String, Integer> immutableMap = Map.of(
"Red", 1,
"Green", 2,
"Blue", 3
);
// 10) Specialized maps
// LinkedHashMap with access-order (LRU cache)
Map<String, String> lruCache = new LinkedHashMap<>(16, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<String, String> eldest) {
return size() > 3; // Maximum size of 3
}
};🔄 Collections Utilities
import java.util.*;
// 1) Sorting
List<Integer> numbers = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9));
Collections.sort(numbers); // [1, 2, 5, 8, 9]
Collections.sort(numbers, Collections.reverseOrder()); // [9, 8, 5, 2, 1]
// 2) Searching
List<String> names = Arrays.asList("Alice", "Bob", "Charlie", "David");
int index = Collections.binarySearch(names, "Charlie"); // 2 (requires sorted list)
// 3) Min/Max
int min = Collections.min(numbers); // 1
int max = Collections.max(numbers); // 9
// Custom comparator
String shortest = Collections.min(names, Comparator.comparing(String::length)); // "Bob"
// 4) Frequency and disjoint
List<String> letters = Arrays.asList("a", "b", "a", "c", "a");
int freq = Collections.frequency(letters, "a"); // 3
boolean disjoint = Collections.disjoint(
Arrays.asList(1, 2, 3),
Arrays.asList(4, 5, 6)
); // true - no elements in common
// 5) Fill, copy, and replace
List<String> filledList = new ArrayList<>(Arrays.asList("", "", ""));
Collections.fill(filledList, "X"); // ["X", "X", "X"]
List<String> source = Arrays.asList("A", "B", "C");
List<String> dest = Arrays.asList("", "", "");
Collections.copy(dest, source); // dest becomes ["A", "B", "C"]
Collections.replaceAll(letters, "a", "z"); // ["z", "b", "z", "c", "z"]
// 6) Unmodifiable views
List<String> readOnlyList = Collections.unmodifiableList(names);
// readOnlyList.add("Eve"); // Throws UnsupportedOperationException
// 7) Synchronized views (thread-safe)
List<String> syncList = Collections.synchronizedList(new ArrayList<>());
Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
// 8) Empty collections
List<Object> emptyList = Collections.emptyList();
Set<Object> emptySet = Collections.emptySet();
Map<Object, Object> emptyMap = Collections.emptyMap();
// 9) Singleton collections
Set<String> singletonSet = Collections.singleton("only element");
List<Integer> singletonList = Collections.singletonList(42);
Map<String, Integer> singletonMap = Collections.singletonMap("key", 1);
// 10) Shuffle
List<Integer> deck = new ArrayList<>(Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9, 10));
Collections.shuffle(deck); // Random order
Collections.shuffle(deck, new Random(42)); // Deterministic shuffle with seed📊 Queues and Stacks
import java.util.Queue;
import java.util.LinkedList;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Stack;
import java.util.Deque;
// 1) Queue (FIFO - First In, First Out)
Queue<String> queue = new LinkedList<>();
queue.offer("First"); // Add to end
queue.offer("Second");
queue.offer("Third");
String front = queue.peek(); // Examine the front: "First"
String removed = queue.poll(); // Remove and return front: "First"
int size = queue.size(); // 2
// 2) Stack (LIFO - Last In, First Out)
// Using legacy Stack class
Stack<Integer> stack = new Stack<>();
stack.push(1); // Add to top
stack.push(2);
stack.push(3);
int top = stack.peek(); // Examine the top: 3
int popped = stack.pop(); // Remove and return top: 3
boolean empty = stack.empty(); // false
// 3) Deque (double-ended queue)
// Preferred way to implement both stacks and queues
Deque<Integer> deque = new ArrayDeque<>();
// Queue operations
deque.offer(1); // Add to end
deque.offer(2);
deque.poll(); // Remove from front: 1
// Stack operations
deque.push(10); // Add to front
deque.push(20);
deque.pop(); // Remove from front: 20
// Deque-specific operations
deque.offerFirst(0); // Add to front
deque.offerLast(3); // Add to end
deque.peekFirst(); // Examine front
deque.peekLast(); // Examine end
deque.pollFirst(); // Remove from front
deque.pollLast(); // Remove from end
// 4) PriorityQueue (min-heap by default)
PriorityQueue<Integer> minHeap = new PriorityQueue<>();
minHeap.offer(5);
minHeap.offer(2);
minHeap.offer(8);
minHeap.offer(1);
while (!minHeap.isEmpty()) {
System.out.print(minHeap.poll() + " "); // Prints: 1 2 5 8
}
// Max-heap using custom comparator
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
maxHeap.offer(5);
maxHeap.offer(2);
maxHeap.offer(8);
maxHeap.offer(1);
while (!maxHeap.isEmpty()) {
System.out.print(maxHeap.poll() + " "); // Prints: 8 5 2 1
}
// 5) PriorityQueue with custom objects
class Task implements Comparable<Task> {
String name;
int priority;
Task(String name, int priority) {
this.name = name;
this.priority = priority;
}
@Override
public int compareTo(Task other) {
return Integer.compare(this.priority, other.priority);
}
@Override
public String toString() {
return name + "(" + priority + ")";
}
}
PriorityQueue<Task> tasks = new PriorityQueue<>();
tasks.offer(new Task("Email", 3));
tasks.offer(new Task("Report", 1));
tasks.offer(new Task("Meeting", 2));
while (!tasks.isEmpty()) {
System.out.println(tasks.poll()); // Ordered by priority
}🧩 Common Algorithms
import java.util.*;
// 1) Binary Search
public static int binarySearch(int[] arr, int target) {
int left = 0;
int right = arr.length - 1;
while (left <= right) {
int mid = left + (right - left) / 2;
if (arr[mid] == target) {
return mid;
}
if (arr[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1; // Not found
}
// 2) Sorting algorithms
// Bubble Sort O(n²)
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// Swap arr[j] and arr[j+1]
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
// Merge Sort O(n log n)
public static void mergeSort(int[] arr) {
if (arr.length <= 1) return;
int mid = arr.length / 2;
int[] left = Arrays.copyOfRange(arr, 0, mid);
int[] right = Arrays.copyOfRange(arr, mid, arr.length);
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
private static void merge(int[] arr, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
arr[k++] = left[i++];
} else {
arr[k++] = right[j++];
}
}
while (i < left.length) {
arr[k++] = left[i++];
}
while (j < right.length) {
arr[k++] = right[j++];
}
}
// 3) Graph traversal
// BFS (Breadth-First Search)
public static void bfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
Queue<Integer> queue = new LinkedList<>();
visited.add(start);
queue.offer(start);
while (!queue.isEmpty()) {
int vertex = queue.poll();
System.out.print(vertex + " ");
for (int neighbor : graph.getOrDefault(vertex, Collections.emptyList())) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.offer(neighbor);
}
}
}
}
// DFS (Depth-First Search)
public static void dfs(Map<Integer, List<Integer>> graph, int start) {
Set<Integer> visited = new HashSet<>();
dfsHelper(graph, start, visited);
}
private static void dfsHelper(Map<Integer, List<Integer>> graph, int vertex, Set<Integer> visited) {
visited.add(vertex);
System.out.print(vertex + " ");
for (int neighbor : graph.getOrDefault(vertex, Collections.emptyList())) {
if (!visited.contains(neighbor)) {
dfsHelper(graph, neighbor, visited);
}
}
}
// 4) Shortest path (Dijkstra's algorithm)
public static Map<Integer, Integer> dijkstra(Map<Integer, Map<Integer, Integer>> graph, int start) {
Map<Integer, Integer> distances = new HashMap<>();
PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
Set<Integer> visited = new HashSet<>();
// Initialize distances
for (int node : graph.keySet()) {
distances.put(node, Integer.MAX_VALUE);
}
distances.put(start, 0);
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int currentNode = current[0];
int currentDist = current[1];
if (visited.contains(currentNode)) continue;
visited.add(currentNode);
for (Map.Entry<Integer, Integer> neighbor : graph.getOrDefault(currentNode, Collections.emptyMap()).entrySet()) {
int neighborNode = neighbor.getKey();
int weight = neighbor.getValue();
if (!visited.contains(neighborNode)) {
int distance = currentDist + weight;
if (distance < distances.get(neighborNode)) {
distances.put(neighborNode, distance);
pq.offer(new int[]{neighborNode, distance});
}
}
}
}
return distances;
}