Data Structures

1. Arrays

int[] arr = new int[10];
arr[1] = 34;
arr[1] = 35;

int i = arr[1];
int size = arr.length;

// Fill array with a value
Arrays.fill(arr, -1);

// Sort
Arrays.sort(arr); // Ascending
Arrays.sort(arr, (a, b) -> b - a); // Descending

// Create array using a range. Useful for printing array index
int[] range = IntStream.range(0, 10).toArray();

2. Character

char c1 = 'a';
char[] arr = "test".toCharArray();
char c2 = str.charAt(2);

// Character
Character.toLowerCase(c)
Character.isLowerCase(c);

Character.toUpperCase(c)
Character.isUpperCase(c);

Character.isLetter(c)
Character.isDigit(c)
Character.isAlphabetic(c);
Character.isLetterOrDigit(c)

3. String & StringBuilder

// String
String str = new String();
str = "abc";
int size = str.length();
char[] arr = str.toCharArray();
String sub = str.substring(1, 3); //[a, b)
str.toLowerCase();
str.toUpperCase();
str.replaceAll("a", "z");

// String Builder
StringBuilder sb = new StringBuilder();
sb.append("hellohowareyou?"); // Returns StringBuilder
sb.insert(2, "z");            // Returns StringBuilder
sb.delete(1, 3)               // [from, to) | Returns StringBuilder
sb.deleteCharAt(0);           // Returns StringBuilder
sb.reverse();                 // Returns StringBuilder

sb.substring(1);              // Returns String
sb.substring(3, 5);           // [from, to) | Returns String

4. List & ArrayList

List<Integer> list = new ArrayList<>();
list.add(5);
list.addAll(List.of(6, 7, 8, 9, 10));

// Index based
list.remove(3);
list.set(0, 9);
list.get(0);

int size = list.size();
list.clear();
list.isEmpty();

// Inefficient - O(n)
list.contains(77);
list.indexOf(10);

Integer[] arr = list.toArray(new Integer[0]);
int[] arrPrimitive = list.stream().mapToInt(Integer::intValue).toArray();

// Sort O(nlog(n))
Collections.sort(list);
Collections.sort(list, (a, b) -> b - a);
Collections.sort(personList, (p1, p2) -> p2.age - p1.age);

5. Stack

Stack<Integer> st = new Stack<>();
st.push(1);
st.pop();

st.peek();

6. Queue & Deque

// -----------------Queue-----------------
Queue<Integer> q = new LinkedList<>();
q.add(1);
q.remove();
q.peek();


// Without exception
q.offer(2);
q.poll()

// -----------------Deque-----------------

Deque<Integer> dq = new LinkedList<>();
dq.addFirst(1);
dq.addLast(2);

int f1 = dq.getFirst();
int l1 = dq.getLast();

int f2 = dq.removeFirst();
int l2 = dq.removeLast();

7. PriorityQueue

// Basics
PriorityQueue<Integer> pq = new PriorityQueue<>();
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Comparator.reverseOrder());

// Add/Offer
pq.add(5);

// Remove/Poll
Integer item = pq.remove();

// Return without removing
Integer item = pq.peek();

// -----------------Inefficient-----------------
// Contains
boolean exists = pq.contains(5);

// Remove specific object
pq.remove(5);

//--------------Custom comparators--------------------

// Max heap
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

// Based on string length
PriorityQueue<String> strPQByLength = new PriorityQueue<>((s1, s2) -> s2.length() - s1.length());

// Lexicographical Order
PriorityQueue<String> strPQLexi = new PriorityQueue<>();

// Reverse Lexicographical Order
PriorityQueue<String> strPQLexiDesc = new PriorityQueue<>(Comparator.reverseOrder());

// ----------------Custom Objects------------------

class Person {
    String name;
    int age;
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

// Based on age in descending order
PriorityQueue<Person> personPQ = new PriorityQueue<>((p1, p2) -> p2.age - p1.age);

Formulas

Arrays

1d to 2d and 2d to 1d array

// Convert 1d array arr to 2d array of size mxn
int[][] matrix = new int[m][n];
for(int i=0; i<arr.length; i++) {
    int row = i/n;
    int col = i%n;
    matrix[row][col] = arr[i];
}

int[][] matrix = new int[m][n];
int idx = r*cols + cols;l.07

Concepts

Subarray, substring, subsequence and subsets

Term		Use When	Key Method
Subset		Combination of elements, any order	Backtracking
Subsequence	2^n	Keep order, skip allowed	Include/exclude recursion
Subarray		Continuous portion of array	Nested loops (start → end)
Substring		Continuous portion of string	`substring(i, j)` in loops

Java DSA cheatsheet

Comments

Cheatsheet

Git Cheatsheet

More from this blog

Redis Cheatsheet

InfluxDB3 cheatsheet

Linux cheatsheet

Milestone: 1 year of leetcode

Git Cheatsheet

Data Structures

1. Arrays

2. Character

3. String & StringBuilder

4. List & ArrayList

5. Stack

6. Queue & Deque

7. PriorityQueue

Formulas

Arrays

1d to 2d and 2d to 1d array

Concepts

Subarray, substring, subsequence and subsets

Command Palette

Comments

Cheatsheet

Git Cheatsheet

More from this blog

Data Structures

1. Arrays

2. Character

3. String & StringBuilder

4. List & ArrayList

5. Stack

6. Queue & Deque

7. PriorityQueue

Formulas

Arrays

1d to 2d and 2d to 1d array

Concepts

Subarray, substring, subsequence and subsets