Java Data Structures
A highly-scannable architectural cheat sheet for developers and technical interviews.
1. Linear vs. Non-Linear: The Core Division
Data Structure Classification Hierarchy
┌───────────────────────┐
│ Data Structures │
└───────────┬───────────┘
│
┌───────────────┴───────────────┐
▼ ▼
┌────────────────────┐ ┌────────────────────┐
│ Linear (Seq) │ │ Non-Linear │
└──────────┬─────────┘ └──────────┬─────────┘
│ │
┌──────┴──────┐ ┌──────┴──────┐
▼ ▼ ▼ ▼
[Static] [Dynamic] [Trees] [Graphs]
(Array) (Queue, Stack) (BST) (Network)
Linear Structures
Sequential
- Elements are arranged sequentially where each element connects directly to its adjacent neighbors.
- Static Sizing: Memory allocation is fixed at compile time (e.g., standard Array).
- Dynamic Sizing: Memory scales randomly during runtime to optimize space complexity (e.g., Queue, Stack, Linked List).
Non-Linear Structures
Hierarchical
Interconnected
- Elements are not placed sequentially and can link to multiple other components.
- Trees: Connects elements using a parent-child hierarchy (e.g., Binary Search Tree).
- Graphs: Complex network vertices linked together by non-linear edges.
2. Deep-Dive: Java's Core Collection Implementations
ArrayList
Linear
Dynamic
Not Thread-Safe
- Inherits AbstractList and implements the List interface.
- Initializes with a set size, then grows or shrinks automatically.
- Supports fast, constant-time O(1) random index access.
- Cannot store primitives directly (requires wrappers like Integer).
LinkedList
Linear
Doubly-Linked
O(N) Random Access
- Internally backed by a doubly linked list structure.
- Offers fast O(1) node insertions and deletions.
- Requires sequential traversal, yielding slower random access times.
Vector
Linear
Synchronized
Slow Performance
- Maintains strict insertion order but is thread-safe due to synchronized methods.
- Iterators are fail-fast; concurrent modifications immediately throw ConcurrentModificationException.
- Throws IllegalArgumentException on negative initial sizing, and NullPointerException on null payloads.
Stack
LIFO
Synchronized
Legacy
- Under the hood, extends the legacy Vector class.
- Implements Serializable, Cloneable, Iterable, Collection, List, and RandomAccess.
ArrayDeque
LIFO/FIFO
High-Speed
No Nulls
- Implements both Queue and Deque.
- Unbounded capacity that resizes dynamically; strictly prohibits null values.
- Consistently outpaces Stack (when using LIFO) and LinkedList (when using FIFO).
PriorityQueue
Heaps
O(Log N)
No Nulls
- Sorts elements dynamically according to natural order or a provided Comparator.
- The head of the queue is always the lowest-valued element.
- Requires elements to be comparable. Provides O(log n) add/poll speeds.
3. Set Implementations
HashSet
Hash Table
O(1)
Allows Null
- Backed by a hashtable (internally a HashMap).
- Prevents duplicate values; provides fast constant-time performance.
- Does not preserve insertion order (placements rely strictly on element hashes).
LinkedHashSet
Hash Table
Linked List
Preserves Order
- Extends HashSet while maintaining a running doubly linked list of entries.
- Maintains a predictable, strict insertion order.
TreeSet
Red-Black Tree
O(Log N)
No Nulls
- Stores unique elements inside a self-balancing binary search tree.
- Automatically sorts stored values in ascending order.
- Attempting to insert a null value immediately throws NullPointerException due to sorting comparison logic.
4. Mapping Your Data: The Java Map Family
Map Interface Implementations
┌───────────────────────────────┐
│ Map Interface │
└───────────────┬───────────────┘
│
┌────────────────────────┬────────────┴───────────┬────────────────────────┐
▼ ▼ ▼ ▼
┌──────────────┐ ┌──────────────┐ ┌──────────────┐ ┌──────────────┐
│ HashMap │ │LinkedHashMap │ │ TreeMap │ │ Hashtable │
├──────────────┤ ├──────────────┤ ├──────────────┤ ├──────────────┤
│ Hash Table │ │ Double-Link │ │ Red-Black │ │ Hash Table │
│ Constant O(1)│ │ Keeps Order │ │ Sorted Keys │ │ Synchronized │
│ 1 Null Key │ │ Predictable │ │ No Null Keys │ │ No Nulls │
└──────────────┘ └──────────────┘ └──────────────┘ └──────────────┘
HashMap
Hash Table
O(1)
1 Null Key
- Stores key-value mappings with no guaranteed iteration ordering.
- Supports up to one null key and multiple null values.
- Offers instant O(1) performance for simple lookup and write operations.
LinkedHashMap
Hash Table
Linked List
Insertion Order
- Integrates a doubly-linked list across hash buckets.
- Maintains key-value pairs in the exact order they were inserted.
TreeMap
Red-Black Tree
O(Log N)
No Null Keys
- Sorts keys naturally or via a custom Comparator.
- Prohibits null keys (throws NullPointerException), though null values are fine.
- Provides structured O(log n) operations for map search, insert, and delete.
Hashtable
Hash Table
Synchronized
No Nulls
- A legacy, fully thread-safe key-value data structure.
- Strictly prohibits both null keys and null values (throws NullPointerException on both).
- Much slower than HashMap due to heavy synchronization overhead (consider ConcurrentHashMap for modern concurrent mapping).
5. Cheat Sheet: Comparison at a Glance
| Structure Class | Insertion Order? | Sorted? | Allows Null? | Thread Safe? | Best For... |
|---|---|---|---|---|---|
| ArrayList | Yes | No | Yes | No | Fast index-based random access, standard list tracking. |
| LinkedList | Yes | No | Yes | No | Frequent head/tail list updates (insertions/deletions). |
| Vector | Yes | No | Yes | Yes | Legacy multi-threaded codebase operations. |
| Stack | Yes (LIFO) | No | Yes | Yes | Basic Last-In-First-Out execution patterns. |
| ArrayDeque | Yes (FIFO/LIFO) | No | No | No | Lightweight, high-speed stack/queue processing. |
| PriorityQueue | No | Yes | No | No | Dynamic priority scheduling, finding min/max tasks. |
| HashSet | No | No | Yes | No | Deduplication tasks where element order does not matter. |
| LinkedHashSet | Yes | No | Yes | No | Enforcing uniqueness while retaining sequence details. |
| TreeSet | No | Yes | No | No | Handling massive datasets of sorted information quickly. |
| HashMap | No | No | Yes (1 Key) | No | General purpose Key-Value indexing with O(1) lookups. |
| LinkedHashMap | Yes | No | Yes (1 Key) | No | Caching architectures (LRU) and keeping track of order. |
| TreeMap | No | Yes | No Keys | No | Structured sorted sorting keys and executing range searches. |
| Hashtable | No | No | No | Yes | Legacy thread-safe mapping (replaced by ConcurrentHashMap). |
Comments
Post a Comment