Skip to main content

Data Structure

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

Popular posts from this blog

Spring Boot 4 Ready

Spring Boot 4.x Features Explained:  Java 25, AI Agents, MCP, Resilience, gRPC & Cloud Native Evolution Building on the massive architectural shift introduced in version 3, Spring Boot 4.x bridges the gap between traditional enterprise stability and the rapid demands of modern cloud architecture and AI integration. While Spring Boot 3 introduced the foundations for GraalVM Native Images and Virtual Threads , Spring Boot 4 takes these capabilities mainstream, introduces native resilience patterns, and upgrades the underlying Spring ecosystem. Spring Boot 4 Major Theme: Modern enterprise development with cloud-native architecture, AI integration, improved resilience, better modularity, and optimized JVM performance. Table of Contents 1. Upgraded Foundation & Baselines 2. Built-in Core Resilience Features 3. First-Class Agentic AI & Model Context Protocol (MCP) 4. Native API Versioning Strategy 5. Modern...

Most questions in 2025

Java Spring Boot Senior Engineer Interview Questions & Answers A complete interview preparation guide for Senior Java Engineers, Spring Boot Developers, and Backend Technical Leads covering Java, Spring Boot, Microservices, Cloud, Database, Security, and Performance Engineering concepts. Target Audience: Senior Java Developers Spring Boot Engineers Microservice Architects Backend Technical Leads Table of Contents 1. Describe Yourself 2. RESTful APIs and Standards 3. Latest Spring Boot Version & Features 4. Java Optional 5. WebFlux Reactive Programming 6. WebFlux Retry Mechanism 7. WebFlux Pagination APIs 8. Circuit Breaker 9. Resilience Patterns 10. Rate Limiter 1. Describe Yourself A senior engineer introduction should highlight technical experience, architecture knowledge, ownership, and problem-solving capabilities. Sample Answer I am a Java backend engineer with 7+ years of experience desi...