What are Data Structures? — Specification & Reference¶

List<E> list = new ArrayList<>();      // Dynamic array
List<E> list = new LinkedList<>();     // Doubly linked list

// Add
list.add(e);                           // Append: O(1) amortized
list.add(index, e);                    // Insert at index: O(n) for ArrayList
list.addAll(collection);               // Append all: O(k)

// Remove
list.remove(index);                    // By index: O(n) for ArrayList
list.remove(object);                   // By value (first occurrence): O(n)
list.clear();                          // Remove all: O(n)

// Access
list.get(index);                       // O(1) ArrayList, O(n) LinkedList
list.set(index, e);                    // O(1) ArrayList, O(n) LinkedList
list.indexOf(e);                       // First index: O(n)
list.contains(e);                      // Membership: O(n)

// Info
list.size();                           // O(1)
list.isEmpty();                        // O(1)

// Iterate
for (E e : list) { ... }
list.forEach(e -> { ... });
list.iterator();
list.listIterator();                   // Bidirectional

// Convert
list.toArray();                        // To Object[]
list.toArray(new String[0]);          // To typed array
list.subList(from, to);               // View (not copy)

// Sort
list.sort(Comparator.naturalOrder());
Collections.sort(list);

Set<E> set = new HashSet<>();          // O(1) add/remove/contains, unordered
Set<E> set = new LinkedHashSet<>();    // O(1) operations, insertion-ordered
Set<E> set = new TreeSet<>();          // O(log n) operations, sorted

// Add
set.add(e);                            // Returns false if already present

// Remove
set.remove(e);
set.clear();

// Query
set.contains(e);
set.size();
set.isEmpty();

// Set operations
set.addAll(other);                     // Union
set.retainAll(other);                  // Intersection
set.removeAll(other);                  // Difference
set.containsAll(other);               // Subset check

// Iterate
for (E e : set) { ... }

Map<K, V> map = new HashMap<>();       // O(1), unordered
Map<K, V> map = new LinkedHashMap<>(); // O(1), insertion-ordered
Map<K, V> map = new TreeMap<>();       // O(log n), sorted by key

// Insert/Update
map.put(key, value);                   // Returns previous value or null
map.putIfAbsent(key, value);          // Only if key not present
map.putAll(otherMap);
map.merge(key, value, (v1, v2) -> v1 + v2); // Merge with function

// Access
map.get(key);                          // Returns null if missing
map.getOrDefault(key, defaultVal);    // Returns default if missing

// Remove
map.remove(key);
map.remove(key, expectedValue);       // Conditional remove

// Query
map.containsKey(key);
map.containsValue(value);             // O(n)
map.size();
map.isEmpty();

// Views
map.keySet();                          // Set<K>
map.values();                          // Collection<V>
map.entrySet();                        // Set<Map.Entry<K,V>>

// Iterate
for (Map.Entry<K, V> entry : map.entrySet()) {
    entry.getKey();
    entry.getValue();
}
map.forEach((k, v) -> { ... });

// Compute
map.compute(key, (k, v) -> newValue);
map.computeIfAbsent(key, k -> expensiveComputation(k));
map.computeIfPresent(key, (k, v) -> v + 1);

// Queue (FIFO)
Queue<E> queue = new LinkedList<>();
Queue<E> queue = new ArrayDeque<>();   // Preferred (faster, no null elements)

queue.offer(e);        // Add to tail: O(1). Returns false if full (bounded).
queue.poll();          // Remove from head: O(1). Returns null if empty.
queue.peek();          // View head: O(1). Returns null if empty.
queue.add(e);          // Like offer, but throws on full.
queue.remove();        // Like poll, but throws on empty.
queue.element();       // Like peek, but throws on empty.

// Deque (double-ended)
Deque<E> deque = new ArrayDeque<>();

deque.offerFirst(e);   // Add to front: O(1)
deque.offerLast(e);    // Add to back: O(1)
deque.pollFirst();     // Remove from front: O(1)
deque.pollLast();      // Remove from back: O(1)
deque.peekFirst();     // View front: O(1)
deque.peekLast();      // View back: O(1)

// Use as Stack
deque.push(e);         // = addFirst(e)
deque.pop();           // = removeFirst()
deque.peek();          // = peekFirst()

PriorityQueue<E> pq = new PriorityQueue<>();                  // Min-heap (natural order)
PriorityQueue<E> pq = new PriorityQueue<>(Comparator.reverseOrder()); // Max-heap

pq.offer(e);           // Add: O(log n)
pq.poll();             // Remove min/max: O(log n)
pq.peek();             // View min/max: O(1)
pq.size();
pq.contains(e);        // O(n) — not O(log n)!
pq.remove(e);          // O(n) — linear scan

// Java
new ArrayList<>().get(0);     // IndexOutOfBoundsException
new ArrayDeque<>().poll();    // null (no exception)
new ArrayDeque<>().remove();  // NoSuchElementException
new HashMap<>().get("x");     // null (no exception)

import java.util.TreeMap;
import java.util.Map;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, Integer> scores = new TreeMap<>();
        scores.put("Charlie", 85);
        scores.put("Alice", 92);
        scores.put("Bob", 78);
        scores.put("Diana", 95);

        // Sorted iteration (by key)
        for (Map.Entry<String, Integer> entry : scores.entrySet()) {
            System.out.printf("%s: %d%n", entry.getKey(), entry.getValue());
        }
        // Alice: 92, Bob: 78, Charlie: 85, Diana: 95

        // Navigation methods
        System.out.println("First: " + scores.firstKey());          // Alice
        System.out.println("Last: " + scores.lastKey());            // Diana
        System.out.println("Floor of 'Cat': " + scores.floorKey("Cat")); // Charlie
        System.out.println("Ceiling of 'Cat': " + scores.ceilingKey("Cat")); // Charlie

        // Range view
        Map<String, Integer> range = scores.subMap("Bob", true, "Diana", false);
        System.out.println("Range [Bob, Diana): " + range); // {Bob=78, Charlie=85}
    }
}

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeExample {
    public static void main(String[] args) {
        // As a Stack (LIFO)
        Deque<String> stack = new ArrayDeque<>();
        stack.push("first");
        stack.push("second");
        stack.push("third");
        System.out.println(stack.pop());  // third
        System.out.println(stack.pop());  // second

        // As a Queue (FIFO)
        Deque<String> queue = new ArrayDeque<>();
        queue.offer("first");
        queue.offer("second");
        queue.offer("third");
        System.out.println(queue.poll()); // first
        System.out.println(queue.poll()); // second
    }
}