Parin's musings

Absolutely! Here's an exhaustive list of common data structures in Java, along with their initialization, common methods, and usage. These are the most essential structures and methods you'll need to brush up on to tackle a wide variety of coding problems.

Common Data Structures in Java

1. Arrays

Initialization:

int[] arr = new int[5]; // Array of size 5
int[] arr = {1, 2, 3, 4, 5}; // Array with predefined values

Common Methods:

  • Accessing Elements: arr[index]
  • Length: arr.length
  • Sorting: Arrays.sort(arr)
  • Binary Search: Arrays.binarySearch(arr, key)
  • Copying: Arrays.copyOf(arr, newLength)

Usage Examples:

  • Traversing an array:
for (int i = 0; i < arr.length; i++) {
    System.out.println(arr[i]);
}

2. ArrayList (Dynamic Array)

Initialization:

List<Integer> list = new ArrayList<>(); // List of Integers

Common Methods:

  • Add: list.add(element)
  • Get: list.get(index)
  • Size: list.size()
  • Remove: list.remove(index) or list.remove(Object)
  • Contains: list.contains(element)
  • Sort: Collections.sort(list)
  • Convert to Array: list.toArray()

Usage Example:

ArrayList<String> list = new ArrayList<>();
list.add("apple");
list.add("banana");
System.out.println(list.get(0)); // apple

3. LinkedList

Initialization:

List<Integer> linkedList = new LinkedList<>(); // LinkedList of Integers

Common Methods:

  • Add to head/tail: linkedList.addFirst(element) or linkedList.addLast(element)
  • Remove head/tail: linkedList.removeFirst() or linkedList.removeLast()
  • Get head/tail: linkedList.getFirst() or linkedList.getLast()
  • Size: linkedList.size()
  • Add at position: linkedList.add(index, element)

Usage Example:

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.addFirst(1);
linkedList.addLast(2);
System.out.println(linkedList.getFirst()); // 1

4. HashMap (Dictionary/Hash Table)

Initialization:

Map<String, Integer> map = new HashMap<>(); // Map with String keys and Integer values

Common Methods:

  • Put: map.put(key, value)
  • Get: map.get(key)
  • Contains Key/Value: map.containsKey(key) or map.containsValue(value)
  • Remove: map.remove(key)
  • Size: map.size()
  • Iterate:
    for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

Usage Example:

HashMap<String, Integer> map = new HashMap<>();
map.put("apple", 1);
map.put("banana", 2);
System.out.println(map.get("apple")); // 1

5. HashSet (Set)

Initialization:

Set<String> set = new HashSet<>();

Common Methods:

  • Add: set.add(element)
  • Remove: set.remove(element)
  • Contains: set.contains(element)
  • Size: set.size()
  • Iterate:
    for (String s : set) {
    System.out.println(s);
}

Usage Example:

HashSet<Integer> set = new HashSet<>();
set.add(1);
set.add(2);
System.out.println(set.contains(1)); // true

6. Stack

Initialization:

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

Common Methods:

  • Push: stack.push(element)
  • Pop: stack.pop()
  • Peek: stack.peek() (returns the top element without removing it)
  • Is Empty: stack.isEmpty()
  • Size: stack.size()

Usage Example:

Stack<Integer> stack = new Stack<>();
stack.push(1);
stack.push(2);
System.out.println(stack.pop()); // 2

7. Queue

Initialization:

Queue<Integer> queue = new LinkedList<>();

Common Methods:

  • Add (enqueue): queue.add(element)
  • Remove (dequeue): queue.remove()
  • Peek: queue.peek() (returns the head element without removing it)
  • Is Empty: queue.isEmpty()
  • Size: queue.size()

Usage Example:

Queue<Integer> queue = new LinkedList<>();
queue.add(1);
queue.add(2);
System.out.println(queue.remove()); // 1

8. PriorityQueue (Min-Heap by default)

Initialization:

PriorityQueue<Integer> pq = new PriorityQueue<>();
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Collections.reverseOrder()); // Max-Heap

Common Methods:

  • Add: pq.add(element)
  • Poll: pq.poll() (removes and returns the smallest/largest element)
  • Peek: pq.peek() (returns but does not remove the smallest/largest element)
  • Size: pq.size()

Usage Example:

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(3);
pq.add(1);
pq.add(2);
System.out.println(pq.poll()); // 1 (smallest)

9. TreeMap (Sorted Map)

Initialization:

Map<String, Integer> treeMap = new TreeMap<>();

Common Methods:

  • Put: treeMap.put(key, value)
  • Get: treeMap.get(key)
  • Remove: treeMap.remove(key)
  • First Key: treeMap.firstKey()
  • Last Key: treeMap.lastKey()
  • Tail Map: treeMap.tailMap(fromKey)

Usage Example:

TreeMap<String, Integer> treeMap = new TreeMap<>();
treeMap.put("apple", 1);
treeMap.put("banana", 2);
System.out.println(treeMap.firstKey()); // apple

10. Deque (Double-ended Queue)

Initialization:

Deque<Integer> deque = new LinkedList<>();

Common Methods:

  • Add First/Last: deque.addFirst(element) or deque.addLast(element)
  • Remove First/Last: deque.removeFirst() or deque.removeLast()
  • Peek First/Last: deque.peekFirst() or deque.peekLast()
  • Is Empty: deque.isEmpty()
  • Size: deque.size()

Usage Example:

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);
deque.addLast(2);
System.out.println(deque.peekFirst()); // 1

11. Graph Representation

Adjacency List (using HashMap):

Map<Integer, List<Integer>> graph = new HashMap<>();

Common Methods:

  • Add Edge:
    graph.putIfAbsent(node, new ArrayList<>());
graph.get(node).add(neighbor);

Usage Example:

Map<Integer, List<Integer>> graph = new HashMap<>();
graph.putIfAbsent(1, new ArrayList<>());
graph.get(1).add(2);
System.out.println(graph.get(1)); // [2]

12. StringBuilder (Efficient String Manipulation)

Initialization:

StringBuilder sb = new StringBuilder();

Common Methods:

  • Append: sb.append(str)
  • Insert: sb.insert(index, str)
  • Delete: sb.delete(start, end)
  • Reverse: sb.reverse()
  • To String: sb.toString()

Usage Example:

StringBuilder sb = new StringBuilder();
sb.append("Hello");
sb.append(" World");
System.out.println(sb.toString()); // Hello World

By brushing up on these data structures, methods, and initializations, you'll have the foundation to tackle a wide variety of coding problems in Java. Let me know if you need further examples or additional explanations!

The list I provided covers the most commonly used data structures and methods you'll need to solve a wide variety of coding problems on platforms like LeetCode. However, based on your goals, there are a few additional advanced data structures and techniques that can further prepare you for edge-case problems and more complex scenarios.

Let me expand the list to include more advanced structures and common algorithms to ensure you have everything you need:

13. Trie (Prefix Tree)

Initialization:

class TrieNode {
    Map<Character, TrieNode> children = new HashMap<>();
    boolean isEndOfWord;
}

class Trie {
    TrieNode root;
    public Trie() {
        root = new TrieNode();
    }
    // Insert, search, etc.
}

Common Methods:

  • Insert Word: Add a word to the trie.
  • Search Word: Search for a word in the trie.
  • StartsWith Prefix: Check if any word in the trie starts with a given prefix.

Usage Example:

Trie trie = new Trie();
trie.insert("apple");
System.out.println(trie.search("apple")); // true
System.out.println(trie.startsWith("app")); // true

14. Union-Find (Disjoint Set)

Initialization:

class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 1;
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}

Common Methods:

  • Find: Find the root of the set containing x.
  • Union: Merge the sets containing x and y.

Usage Example:

UnionFind uf = new UnionFind(10);
uf.union(1, 2);
uf.union(3, 4);
System.out.println(uf.find(1)); // 1
System.out.println(uf.find(2)); // 1 (since 1 and 2 are united)

15. TreeSet (Balanced Binary Search Tree)

Initialization:

TreeSet<Integer> treeSet = new TreeSet<>();

Common Methods:

  • Add: treeSet.add(element)
  • Remove: treeSet.remove(element)
  • Ceiling (>= element): treeSet.ceiling(element)
  • Floor (<= element): treeSet.floor(element)
  • First/Last: treeSet.first() or treeSet.last()

Usage Example:

TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(1);
treeSet.add(5);
treeSet.add(3);
System.out.println(treeSet.floor(4)); // 3
System.out.println(treeSet.ceiling(4)); // 5

16. LinkedHashMap (Maintains Insertion Order)

Initialization:

Map<String, Integer> linkedHashMap = new LinkedHashMap<>();

Common Methods:

  • Put: linkedHashMap.put(key, value)
  • Get: linkedHashMap.get(key)
  • Remove: linkedHashMap.remove(key)
  • Iterate: Maintains insertion order when iterating.

Usage Example:

LinkedHashMap<String, Integer> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("apple", 1);
linkedHashMap.put("banana", 2);
linkedHashMap.put("cherry", 3);
for (String key : linkedHashMap.keySet()) {
    System.out.println(key); // apple, banana, cherry (in order)
}

17. Doubly Linked List

Initialization:

class DoublyLinkedList {
    class Node {
        int val;
        Node prev, next;
        Node(int val) {
            this.val = val;
        }
    }

    Node head, tail;
}

Common Methods:

  • Add to Front: addFirst(Node node)
  • Add to End: addLast(Node node)
  • Remove Node: remove(Node node)

Usage Example:

DoublyLinkedList dll = new DoublyLinkedList();
dll.addFirst(new DoublyLinkedList.Node(1));
dll.addLast(new DoublyLinkedList.Node(2));
// Traverse the list

18. Segment Tree (Range Queries)

Initialization:

class SegmentTree {
    int[] tree;
    int n;

    public SegmentTree(int[] arr) {
        n = arr.length;
        tree = new int[2 * n];
        build(arr);
    }

    private void build(int[] arr) {
        for (int i = 0; i < n; i++)
            tree[n + i] = arr[i];
        for (int i = n - 1; i > 0; --i)
            tree[i] = tree[2 * i] + tree[2 * i + 1];
    }

    public void update(int pos, int value) {
        pos += n;
        tree[pos] = value;
        for (int i = pos / 2; i > 0; i /= 2)
            tree[i] = tree[2 * i] + tree[2 * i + 1];
    }

    public int query(int l, int r) {
        int sum = 0;
        l += n;
        r += n + 1;
        while (l < r) {
            if ((l & 1) == 1) sum += tree[l++];
            if ((r & 1) == 1) sum += tree[--r];
            l /= 2;
            r /= 2;
        }
        return sum;
    }
}

Common Methods:

  • Build: Build the segment tree from the initial array.
  • Update: Update an element in the array.
  • Range Query: Get the sum of elements in a range.

Usage Example:

int[] arr = {1, 2, 3, 4, 5};
SegmentTree st = new SegmentTree(arr);
System.out.println(st.query(1, 3)); // Sum from index 1 to 3: 9
st.update(2, 10); // Update value at index 2 to 10
System.out.println(st.query(1, 3)); // Sum from index 1 to 3: 16

19. LRU Cache Implementation (Using LinkedHashMap)

Initialization:

class LRUCache extends LinkedHashMap<Integer, Integer> {
    private int capacity;

    public LRUCache(int capacity) {
        super(capacity, 0.75f, true);
        this.capacity = capacity;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
        return size() > capacity;
    }

    public int get(int key) {
        return super.getOrDefault(key, -1);
    }

    public void put(int key, int value) {
        super.put(key, value);
    }
}

Common Methods:

  • Get: Get the value from the cache if it exists.
  • Put: Add or update a key-value pair in the cache.
  • Eviction: Automatically evicts the least recently used element when the capacity is exceeded.

Usage Example:

LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1)); // returns 1
cache.put(3, 3); // evicts key 2
System.out.println(cache.get(2)); // returns -1 (not found)

20. Bit Manipulation (Common Techniques)

Common Methods:

  • AND, OR, XOR, NOT: a & b, a | b, a ^ b, ~a
  • Shift Operations: << (left shift), >> (right shift)
  • Checking if the nth Bit is Set: (a & (1 << n)) != 0
  • Setting the nth Bit: a |= (1 << n)
  • Clearing the nth Bit: a &= ~(1 << n)

Usage Example:

int a = 5; // 0101 in binary
int b = 3; // 0011 in binary
System.out.println(a & b); // 1 (bitwise AND)
System.out.println(a | b); //

 7 (bitwise OR)
System.out.println(a ^ b); // 6 (bitwise XOR)

Bonus: Algorithmic Techniques

  • Sorting Algorithms: QuickSort, MergeSort, HeapSort.
  • Searching Algorithms: Binary Search, Breadth-First Search (BFS), Depth-First Search (DFS).
  • Graph Algorithms: Dijkstra’s Algorithm, Floyd-Warshall, Bellman-Ford.
  • Dynamic Programming Patterns: Memoization, Tabulation, Knapsack Problems, Subsequence Problems.

By studying these additional data structures and common algorithmic patterns, you should be well-prepared to solve advanced coding problems in interviews. Let me know if you need more specific examples or explanations!

Java DS Summary Published on 2024-10-02