Java Collections Framework

ArrayList — Add, Insert, and Remove Operations — Watch how ArrayList manages its internal array: appending at end is fast, but inserting and removing in the middle requires shifting elements.

import java.util.*;

public class ListDemo {
    public static void main(String[] args) {
        // --- ArrayList (default choice) ---
        List<Integer> arrayList = new ArrayList<>();
        arrayList.add(10);                // Append: [10]
        arrayList.add(20);                // Append: [10, 20]
        arrayList.add(30);                // Append: [10, 20, 30]
        arrayList.add(1, 15);             // Insert at index 1: [10, 15, 20, 30]
        System.out.println(arrayList.get(2));  // Random access: 20 (O(1))
        arrayList.remove(0);              // Remove first: [15, 20, 30]
        System.out.println(arrayList);    // [15, 20, 30]

        // --- LinkedList (also implements Deque) ---
        LinkedList<String> linkedList = new LinkedList<>();
        linkedList.add("B");              // [B]
        linkedList.addFirst("A");          // [A, B]
        linkedList.addLast("C");           // [A, B, C]
        System.out.println(linkedList.getFirst()); // A
        linkedList.removeFirst();          // [B, C]
        System.out.println(linkedList);   // [B, C]

        // --- Common operations ---
        List<Integer> nums = new ArrayList<>(Arrays.asList(5, 2, 8, 2, 1));
        System.out.println(nums.contains(8));     // true
        System.out.println(nums.indexOf(2));      // 1 (first occurrence)
        System.out.println(nums.lastIndexOf(2));  // 3 (last occurrence)
        System.out.println(nums.subList(1, 4));   // [2, 8, 2] (view)
    }
}

# Python equivalents of Java List implementations

# --- list (equivalent to Java ArrayList) ---
array_list = []
array_list.append(10)           # Append: [10]
array_list.append(20)           # Append: [10, 20]
array_list.append(30)           # Append: [10, 20, 30]
array_list.insert(1, 15)        # Insert at index 1: [10, 15, 20, 30]
print(array_list[2])            # Random access: 20 (O(1))
array_list.pop(0)               # Remove first: [15, 20, 30]
print(array_list)               # [15, 20, 30]

# --- collections.deque (equivalent to Java LinkedList as Deque) ---
from collections import deque
linked = deque()
linked.append("B")              # [B]
linked.appendleft("A")          # [A, B]
linked.append("C")              # [A, B, C]
print(linked[0])                # A
linked.popleft()                # [B, C]

# --- Common operations ---
nums = [5, 2, 8, 2, 1]
print(8 in nums)                # True (O(n))
print(nums.index(2))            # 1 (first occurrence)
nums_slice = nums[1:4]          # [2, 8, 2] (copy, not view)

#include <vector>
#include <list>
#include <deque>
#include <algorithm>
#include <iostream>
using namespace std;

int main() {
    // --- vector (equivalent to Java ArrayList) ---
    vector<int> vec;
    vec.push_back(10);                   // Append: {10}
    vec.push_back(20);                   // Append: {10, 20}
    vec.push_back(30);                   // Append: {10, 20, 30}
    vec.insert(vec.begin() + 1, 15);     // Insert at index 1: {10, 15, 20, 30}
    cout << vec[2] << endl;              // Random access: 20 (O(1))
    vec.erase(vec.begin());              // Remove first: {15, 20, 30}

    // --- list (equivalent to Java LinkedList) ---
    list<string> lst;
    lst.push_back("B");                  // {B}
    lst.push_front("A");                 // {A, B}
    lst.push_back("C");                  // {A, B, C}
    cout << lst.front() << endl;         // A
    lst.pop_front();                     // {B, C}

    // --- Common operations ---
    vector<int> nums = {5, 2, 8, 2, 1};
    bool found = find(nums.begin(), nums.end(), 8) != nums.end(); // true
    auto it = find(nums.begin(), nums.end(), 2);
    int idx = distance(nums.begin(), it); // 1 (first occurrence)

    return 0;
}

HashSet — Building a Set and Detecting Duplicates — Watch how a HashSet stores unique elements and silently rejects duplicates, enabling O(1) membership testing.

import java.util.*;

public class SetDemo {
    public static void main(String[] args) {
        // --- HashSet (unordered, fastest) ---
        Set<Integer> hashSet = new HashSet<>();
        hashSet.add(5);
        hashSet.add(2);
        hashSet.add(8);
        hashSet.add(2);  // Duplicate - ignored
        System.out.println(hashSet);            // e.g., [2, 5, 8] (order varies)
        System.out.println(hashSet.contains(5)); // true (O(1))

        // --- LinkedHashSet (insertion order preserved) ---
        Set<String> linkedSet = new LinkedHashSet<>();
        linkedSet.add("Banana");
        linkedSet.add("Apple");
        linkedSet.add("Cherry");
        linkedSet.add("Apple");  // Duplicate - ignored
        System.out.println(linkedSet);  // [Banana, Apple, Cherry] (insertion order)

        // --- TreeSet (sorted) ---
        TreeSet<Integer> treeSet = new TreeSet<>(Arrays.asList(5, 2, 8, 1, 9));
        System.out.println(treeSet);         // [1, 2, 5, 8, 9] (sorted)
        System.out.println(treeSet.first()); // 1 (smallest)
        System.out.println(treeSet.last());  // 9 (largest)
        System.out.println(treeSet.headSet(5));    // [1, 2] (elements < 5)
        System.out.println(treeSet.tailSet(5));    // [5, 8, 9] (elements >= 5)
        System.out.println(treeSet.subSet(2, 9));  // [2, 5, 8] (2 <= x < 9)
        System.out.println(treeSet.floor(6));      // 5 (greatest <= 6)
        System.out.println(treeSet.ceiling(6));    // 8 (smallest >= 6)

        // --- Set operations ---
        Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4));
        Set<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5, 6));

        Set<Integer> union = new HashSet<>(a);
        union.addAll(b);  // {1, 2, 3, 4, 5, 6}

        Set<Integer> intersection = new HashSet<>(a);
        intersection.retainAll(b);  // {3, 4}

        Set<Integer> difference = new HashSet<>(a);
        difference.removeAll(b);  // {1, 2}

        System.out.println("Union: " + union);
        System.out.println("Intersection: " + intersection);
        System.out.println("Difference: " + difference);
    }
}

# Python equivalents of Java Set implementations

# --- set (equivalent to Java HashSet — unordered, unique) ---
hash_set = {5, 2, 8, 2}  # Duplicate removed: {2, 5, 8}
hash_set.add(10)
print(5 in hash_set)       # True (O(1))

# --- No direct equivalent to LinkedHashSet ---
# Use dict.fromkeys() to maintain insertion order with uniqueness
linked_set = dict.fromkeys(["Banana", "Apple", "Cherry", "Apple"])
print(list(linked_set.keys()))  # ['Banana', 'Apple', 'Cherry']

# --- SortedContainers (equivalent to Java TreeSet) ---
# from sortedcontainers import SortedSet
# tree_set = SortedSet([5, 2, 8, 1, 9])  # Sorted: [1, 2, 5, 8, 9]

# --- Set operations (built-in in Python!) ---
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}
print(a | b)    # Union: {1, 2, 3, 4, 5, 6}
print(a & b)    # Intersection: {3, 4}
print(a - b)    # Difference: {1, 2}
print(a <= b)   # Subset check: False

#include <set>
#include <unordered_set>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // --- unordered_set (equivalent to Java HashSet) ---
    unordered_set<int> hashSet = {5, 2, 8, 2}; // {5, 2, 8}
    hashSet.insert(10);
    cout << hashSet.count(5) << endl; // 1 (true, O(1))

    // --- set (equivalent to Java TreeSet — sorted) ---
    set<int> treeSet = {5, 2, 8, 1, 9}; // {1, 2, 5, 8, 9}
    cout << *treeSet.begin() << endl;   // 1 (smallest)
    cout << *treeSet.rbegin() << endl;  // 9 (largest)

    // Range query: elements >= 2 and < 9
    auto lo = treeSet.lower_bound(2);
    auto hi = treeSet.lower_bound(9);
    for (auto it = lo; it != hi; ++it)
        cout << *it << " "; // 2 5 8
    cout << endl;

    // --- Set operations ---
    set<int> a = {1, 2, 3, 4};
    set<int> b = {3, 4, 5, 6};

    vector<int> uni, inter, diff;
    set_union(a.begin(), a.end(), b.begin(), b.end(), back_inserter(uni));
    set_intersection(a.begin(), a.end(), b.begin(), b.end(), back_inserter(inter));
    set_difference(a.begin(), a.end(), b.begin(), b.end(), back_inserter(diff));

    return 0;
}

HashMap — Building a Word Frequency Counter — Watch how HashMap stores word counts: new words get inserted with count 1, while repeated words have their count incremented.

import java.util.*;

public class MapDemo {
    public static void main(String[] args) {
        // --- HashMap (default choice) ---
        Map<String, Integer> hashMap = new HashMap<>();
        hashMap.put("Alice", 95);
        hashMap.put("Bob", 87);
        hashMap.put("Charlie", 92);
        System.out.println(hashMap.get("Bob"));       // 87
        System.out.println(hashMap.containsKey("Alice")); // true
        System.out.println(hashMap.getOrDefault("Dave", 0)); // 0

        // Frequency counting pattern
        String[] words = {"cat", "dog", "cat", "bird", "dog", "cat"};
        Map<String, Integer> freq = new HashMap<>();
        for (String w : words) {
            freq.merge(w, 1, Integer::sum); // Elegant counting
        }
        System.out.println(freq); // {cat=3, bird=1, dog=2}

        // --- LinkedHashMap (insertion order) ---
        Map<String, Integer> linkedMap = new LinkedHashMap<>();
        linkedMap.put("Banana", 2);
        linkedMap.put("Apple", 5);
        linkedMap.put("Cherry", 3);
        System.out.println(linkedMap); // {Banana=2, Apple=5, Cherry=3}

        // --- TreeMap (sorted by key) ---
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("Charlie", 92);
        treeMap.put("Alice", 95);
        treeMap.put("Bob", 87);
        System.out.println(treeMap);           // {Alice=95, Bob=87, Charlie=92}
        System.out.println(treeMap.firstKey()); // Alice
        System.out.println(treeMap.lastKey());  // Charlie
        System.out.println(treeMap.floorKey("Bob")); // Bob
        System.out.println(treeMap.headMap("Charlie")); // {Alice=95, Bob=87}

        // --- Iterating over Map ---
        for (Map.Entry<String, Integer> entry : hashMap.entrySet()) {
            System.out.println(entry.getKey() + " -> " + entry.getValue());
        }

        // Using forEach with lambda
        hashMap.forEach((key, value) -> System.out.println(key + ": " + value));
    }
}

# Python equivalents of Java Map implementations

# --- dict (equivalent to Java HashMap + LinkedHashMap) ---
# Python dicts maintain insertion order since Python 3.7
hash_map = {}
hash_map["Alice"] = 95
hash_map["Bob"] = 87
hash_map["Charlie"] = 92
print(hash_map.get("Bob"))        # 87
print("Alice" in hash_map)        # True
print(hash_map.get("Dave", 0))    # 0 (default)

# Frequency counting (using Counter — cleanest)
from collections import Counter
words = ["cat", "dog", "cat", "bird", "dog", "cat"]
freq = Counter(words)
print(freq)  # Counter({'cat': 3, 'dog': 2, 'bird': 1})

# Frequency counting (manual — like Java)
freq2 = {}
for w in words:
    freq2[w] = freq2.get(w, 0) + 1

# --- SortedDict (equivalent to Java TreeMap) ---
# from sortedcontainers import SortedDict
# tree_map = SortedDict({"Charlie": 92, "Alice": 95, "Bob": 87})

# --- Iterating over dict ---
for key, value in hash_map.items():
    print(f"{key} -> {value}")

#include <map>
#include <unordered_map>
#include <string>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    // --- unordered_map (equivalent to Java HashMap) ---
    unordered_map<string, int> hashMap;
    hashMap["Alice"] = 95;
    hashMap["Bob"] = 87;
    hashMap["Charlie"] = 92;
    cout << hashMap["Bob"] << endl; // 87
    cout << (hashMap.count("Alice") > 0) << endl; // 1 (true)

    // Frequency counting
    vector<string> words = {"cat", "dog", "cat", "bird", "dog", "cat"};
    unordered_map<string, int> freq;
    for (const auto& w : words) {
        freq[w]++;  // Auto-initializes to 0, then increments
    }
    // freq: {cat:3, dog:2, bird:1}

    // --- map (equivalent to Java TreeMap — sorted by key) ---
    map<string, int> treeMap;
    treeMap["Charlie"] = 92;
    treeMap["Alice"] = 95;
    treeMap["Bob"] = 87;
    cout << treeMap.begin()->first << endl;  // Alice (smallest)
    cout << treeMap.rbegin()->first << endl; // Charlie (largest)

    // Iterating (sorted order)
    for (const auto& [key, val] : treeMap) {
        cout << key << " -> " << val << endl;
    }

    return 0;
}

PriorityQueue (Min-Heap) — Insert and Poll Operations — Watch how a min-heap maintains the smallest element at the top through bubble-up on insert and sink-down on removal.

import java.util.*;

public class QueueDemo {
    public static void main(String[] args) {
        // --- ArrayDeque as Queue (FIFO) ---
        Queue<String> queue = new ArrayDeque<>();
        queue.offer("Task A");
        queue.offer("Task B");
        queue.offer("Task C");
        System.out.println(queue.peek());  // Task A (front)
        System.out.println(queue.poll());  // Task A (removed)
        System.out.println(queue.poll());  // Task B (removed)
        System.out.println(queue);         // [Task C]

        // --- ArrayDeque as Stack (LIFO) ---
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(10);
        stack.push(20);
        stack.push(30);
        System.out.println(stack.peek());  // 30 (top)
        System.out.println(stack.pop());   // 30 (removed)
        System.out.println(stack.pop());   // 20 (removed)

        // --- PriorityQueue (Min-Heap) ---
        PriorityQueue<Integer> minHeap = new PriorityQueue<>();
        minHeap.add(30);
        minHeap.add(10);
        minHeap.add(50);
        minHeap.add(20);
        System.out.println(minHeap.peek()); // 10 (minimum)
        System.out.println(minHeap.poll()); // 10 (removed)
        System.out.println(minHeap.poll()); // 20 (next minimum)

        // --- PriorityQueue (Max-Heap) ---
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());
        maxHeap.add(30);
        maxHeap.add(10);
        maxHeap.add(50);
        System.out.println(maxHeap.peek()); // 50 (maximum)

        // --- PriorityQueue with custom comparator ---
        PriorityQueue<int[]> taskQueue = new PriorityQueue<>(
            (a, b) -> a[0] - b[0]  // Sort by priority (first element)
        );
        taskQueue.offer(new int[]{3, 1}); // priority 3, task 1
        taskQueue.offer(new int[]{1, 2}); // priority 1, task 2
        taskQueue.offer(new int[]{2, 3}); // priority 2, task 3
        System.out.println(Arrays.toString(taskQueue.poll())); // [1, 2] (highest priority)
    }
}

# Python equivalents of Java Queue/Deque/PriorityQueue

# --- deque as Queue (FIFO) ---
from collections import deque
queue = deque()
queue.append("Task A")    # enqueue
queue.append("Task B")
queue.append("Task C")
print(queue[0])            # Task A (peek front)
print(queue.popleft())     # Task A (dequeue)
print(queue.popleft())     # Task B

# --- list as Stack (LIFO) or deque ---
stack = []
stack.append(10)   # push
stack.append(20)
stack.append(30)
print(stack[-1])    # 30 (peek top)
print(stack.pop())  # 30 (pop)

# --- heapq (Min-Heap — equivalent to Java PriorityQueue) ---
import heapq
min_heap = []
heapq.heappush(min_heap, 30)
heapq.heappush(min_heap, 10)
heapq.heappush(min_heap, 50)
heapq.heappush(min_heap, 20)
print(min_heap[0])          # 10 (peek min)
print(heapq.heappop(min_heap))  # 10 (remove min)
print(heapq.heappop(min_heap))  # 20

# --- Max-Heap (negate values) ---
max_heap = []
heapq.heappush(max_heap, -30)
heapq.heappush(max_heap, -10)
heapq.heappush(max_heap, -50)
print(-max_heap[0])         # 50 (peek max)

#include <queue>
#include <stack>
#include <iostream>
#include <functional>
using namespace std;

int main() {
    // --- queue (FIFO — equivalent to Java ArrayDeque as Queue) ---
    queue<string> q;
    q.push("Task A");
    q.push("Task B");
    q.push("Task C");
    cout << q.front() << endl;  // Task A
    q.pop();                    // Remove Task A
    cout << q.front() << endl;  // Task B

    // --- stack (LIFO) ---
    stack<int> st;
    st.push(10);
    st.push(20);
    st.push(30);
    cout << st.top() << endl;   // 30
    st.pop();                   // Remove 30
    cout << st.top() << endl;   // 20

    // --- priority_queue (Max-Heap by default in C++) ---
    priority_queue<int> maxPQ;
    maxPQ.push(30);
    maxPQ.push(10);
    maxPQ.push(50);
    maxPQ.push(20);
    cout << maxPQ.top() << endl;  // 50 (max)
    maxPQ.pop();                  // Remove 50

    // --- Min-Heap ---
    priority_queue<int, vector<int>, greater<int>> minPQ;
    minPQ.push(30);
    minPQ.push(10);
    minPQ.push(50);
    cout << minPQ.top() << endl;  // 10 (min)

    return 0;
}

Collections.sort + binarySearch — Sort Then Search — Watch the array get sorted by TimSort, then see binary search find a target value in O(log n) time.

import java.util.*;

public class CollectionsUtilDemo {
    public static void main(String[] args) {
        List<Integer> nums = new ArrayList<>(Arrays.asList(5, 2, 8, 1, 9, 3));

        // --- Sorting ---
        Collections.sort(nums);                    // [1, 2, 3, 5, 8, 9]
        Collections.sort(nums, Comparator.reverseOrder()); // [9, 8, 5, 3, 2, 1]
        Collections.sort(nums);                    // Back to [1, 2, 3, 5, 8, 9]

        // --- Binary Search ---
        int idx = Collections.binarySearch(nums, 8);  // 4
        int missing = Collections.binarySearch(nums, 4); // -4 (not found)
        System.out.println("Index of 8: " + idx);      // 4
        System.out.println("Search for 4: " + missing); // -4

        // --- Min, Max, Frequency ---
        System.out.println("Max: " + Collections.max(nums)); // 9
        System.out.println("Min: " + Collections.min(nums)); // 1

        List<Integer> withDups = Arrays.asList(1, 2, 2, 3, 3, 3);
        System.out.println("Freq of 3: " + Collections.frequency(withDups, 3)); // 3

        // --- Reverse, Shuffle, Swap ---
        Collections.reverse(nums);              // [9, 8, 5, 3, 2, 1]
        Collections.shuffle(nums);              // Random order
        Collections.swap(nums, 0, nums.size() - 1); // Swap first and last

        // --- Immutable collections ---
        List<String> immutable = Collections.unmodifiableList(
            Arrays.asList("A", "B", "C")
        );
        // immutable.add("D"); // Throws UnsupportedOperationException!

        // --- Java 9+ List.of / Map.of ---
        List<String> imm2 = List.of("X", "Y", "Z");    // Immutable
        Map<String, Integer> imm3 = Map.of("a", 1, "b", 2); // Immutable
    }
}

# Python equivalents of Java Collections utility methods
import random
from bisect import bisect_left, insort

nums = [5, 2, 8, 1, 9, 3]

# --- Sorting ---
nums.sort()                        # [1, 2, 3, 5, 8, 9]
nums.sort(reverse=True)            # [9, 8, 5, 3, 2, 1]
nums.sort()                        # [1, 2, 3, 5, 8, 9]

# --- Binary Search (bisect module) ---
idx = bisect_left(nums, 8)         # 4
found = idx < len(nums) and nums[idx] == 8  # True

# --- Min, Max ---
print(max(nums))                   # 9
print(min(nums))                   # 1

# --- Reverse, Shuffle ---
nums.reverse()                     # [9, 8, 5, 3, 2, 1]
random.shuffle(nums)               # Random order

# --- Frequency ---
with_dups = [1, 2, 2, 3, 3, 3]
print(with_dups.count(3))          # 3

# --- Immutable (tuple) ---
immutable = tuple(["A", "B", "C"])
# immutable[0] = "X"  # TypeError!

#include <vector>
#include <algorithm>
#include <numeric>
#include <random>
#include <iostream>
using namespace std;

int main() {
    vector<int> nums = {5, 2, 8, 1, 9, 3};

    // --- Sorting ---
    sort(nums.begin(), nums.end());       // {1, 2, 3, 5, 8, 9}
    sort(nums.begin(), nums.end(), greater<int>()); // {9, 8, 5, 3, 2, 1}
    sort(nums.begin(), nums.end());       // {1, 2, 3, 5, 8, 9}

    // --- Binary Search ---
    bool found = binary_search(nums.begin(), nums.end(), 8); // true
    auto it = lower_bound(nums.begin(), nums.end(), 8);      // Iterator to 8
    int idx = distance(nums.begin(), it);                     // 4

    // --- Min, Max ---
    cout << *max_element(nums.begin(), nums.end()) << endl; // 9
    cout << *min_element(nums.begin(), nums.end()) << endl; // 1

    // --- Reverse, Shuffle ---
    reverse(nums.begin(), nums.end());    // {9, 8, 5, 3, 2, 1}
    random_device rd;
    mt19937 gen(rd());
    shuffle(nums.begin(), nums.end(), gen); // Random

    // --- Count ---
    vector<int> dups = {1, 2, 2, 3, 3, 3};
    cout << count(dups.begin(), dups.end(), 3) << endl; // 3

    // --- Sum ---
    int total = accumulate(nums.begin(), nums.end(), 0);

    return 0;
}