Common Data Structures in Java: Arrays, Lists, Queues, Stacks, Sets, Maps, Trees, and Heaps

Arrays are contiguous memory blocks that store elements of the same type. They provide O(1) get and set operations but O(N) add and remove operations. In Java, the primitive type Array represents an array, while ArrayList builds on an internal array and automatically expands when capacity is exceeded.

Linked lists are non‑contiguous structures where each node points to the next, allowing O(1) add and remove but O(N) get and set operations. Java’s LinkedList implements this structure.

Queues are FIFO linear collections. In Java, LinkedList implements Deque and can serve as a double‑ended queue, while PriorityQueue adds element priority ordering.

Stacks are LIFO structures. Java’s legacy Stack class is thread‑safe but inefficient; modern code prefers Deque (e.g., ArrayDeque ) to implement stack behavior.

Sets store unique elements. Java provides HashSet (based on HashMap ), LinkedHashSet (preserves insertion order), and TreeSet (sorted via a red‑black tree, implements SortedSet ).

Hash tables (maps) associate keys with values. Java’s HashMap is the standard implementation; Hashtable adds synchronization but is slower. For concurrency, ConcurrentHashMap is preferred. Sorted maps include TreeMap , while LinkedHashMap preserves insertion order and WeakHashMap uses weak references for keys.

Trees are hierarchical structures with a root node and sub‑trees. They are widely used (e.g., red‑black trees in OS kernels, B+ trees in databases, syntax trees in compilers). Java’s TreeSet and TreeMap are typical examples.

Binary trees have at most two children per node. Important properties include node count per level (≤ 2^(i‑1)), depth‑related node limits, and relationships for array‑based storage (parent at ⌊i/2⌋, left child at 2i, right child at 2i+1). Complete and full binary trees are special cases.

Binary Search Trees (BST) maintain the invariant that left‑subtree keys are smaller and right‑subtree keys are larger or equal to the node’s key. They support O(log n) search, insertion, and deletion on average, but can degrade to O(n) if unbalanced.

AVL trees are self‑balancing BSTs where the height difference between left and right sub‑trees of any node is at most 1. Balancing is achieved via rotations: single rotations for “left‑left” and “right‑right” cases, double rotations for “left‑right” and “right‑left”. The following method returns a node’s height, a key part of the balance check:

private int height(Node t){
    return t == null ? -1 : t.height;
}

Heaps are complete binary trees stored in arrays. In a max‑heap each parent ≥ its children; in a min‑heap each parent ≤ its children. The array index relationships (parent at ⌊(i‑1)/2⌋, left child at 2i+1, right child at 2i+2) enable efficient priority‑queue operations and heap sort.

Overall, the article provides a concise reference for Java developers to choose appropriate data structures based on performance characteristics and usage scenarios.