Essential Data Structures and Algorithms in Java Apply proven problem-solving patterns to write faster and cleaner code (Joseph Su) (z-library.sk, 1lib.sk, z-lib.sk)

Page 1

(This page has no text content)

Page 2

Essential Data Structures and Algorithms in Java Apply proven problem-solving patterns to write faster and cleaner AI-native code Joseph Su

Page 3

Essential Data Structures and Algorithms in Java Copyright © 2026 Packt Publishing All rights reserved. No part of this book may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, without the prior written permission of the publisher, except in the case of brief quotations embedded in critical articles or reviews. Every effort has been made in the preparation of this book to ensure the accuracy of the information presented. However, the information contained in this book is sold without warranty, either express or implied. Neither the author, nor Packt Publishing or its dealers and distributors, will be held liable for any damages caused or alleged to have been caused directly or indirectly by this book. Packt Publishing has endeavored to provide trademark information about all of the companies and products mentioned in this book by the appropriate use of capitals. However, Packt Publishing cannot guarantee the accuracy of this information. Portfolio Director: Gebin George Relationship Lead: Srishti Seth Project Manager: K. Loganathan Content Engineer: Sujata Tripathi Technical Editor: Irfa Ansari, Aysha Nadeem Copy Editor: Sujata Tripathi Indexer: Tejal Soni Proofreader: Sujata Tripathi Production Designer: Vijay Kamble Growth Lead: Vinishka Kalra First published: July 2026 Production reference: 1290726 Published by Packt Publishing Ltd. Grosvenor House 11 St Paul's Square Birmingham B3 1RB, UK. ISBN 978-1-83588-370-9 www.packtpub.com

Page 4

To my wife and family, whose endless patience and unwavering support made this book possible. Thank you for being my constant anchor and inspiration. – Joseph Su

Page 5

Contributors About the author Joseph Su is a veteran software engineering leader, educator, and author with over 20 years of experience building high-throughput, low-latency systems for data-intensive industries. He holds a Master of Science from the Massachusetts Institute of Technology (MIT), focusing on Bayesian AI in sensor fusion, and an M.S. in Machine Learning from Georgia Tech. Alongside engineering scalable production software, Joseph has extensive experience lecturing college and graduate-level computer science courses, specializing in data structures and algorithms, and object-oriented software and web development. I would like to extend my sincere gratitude to the technical reviewers of this book, Sriram and Howard, for their time and invaluable feedback. I am also deeply grateful to the entire team at Packt for their continuous guidance and support throughout the writing process.

Page 6

About the reviewers Sriram Keerthy is a full-stack developer with over 21 years of experience. He has developed multiple large-scale distributed systems in Java ranging from Investment Banking applications to Ebook Catalog management and Digital Advertising services. Sriram has also conducted technical coding interviews for over 350 candidates during this time. I thank Joseph, my colleague and the author of this book, for entrusting me with this technical reviewer opportunity. I found Packt Publishing's process well-organized and the team was accommodating to my schedule as I worked on the technical reviews alongside my time into work, academic, family and personal things.

Page 7

(This page has no text content)

Page 8

Table of Contents Preface xxiii Free benefits with your book ................................................................................................ xxix Part 1: Introduction 1 Chapter 1: Data Structures and Algorithms 3 Technical requirements ............................................................................................................. 4 Data structures ......................................................................................................................... 5 Importance • 5 Applications • 5 File systems • 6 Data warehousing • 7 Types of data structures • 9 Linear data structures • 11 Non-linear data structures • 13 The DSA bridge to modern AI ................................................................................................... 15 The AI context • 16 Algorithmic blueprint • 16 Agentic lifecycle • 17 Input gateway • 18 Memory, context, and knowledge retrieval • 19 Reasoning • 21 Task selection and execution • 22 Routing and verification • 24 Moving to abstraction • 26 Abstract data type • 27 Java collections framework ..................................................................................................... 29 Algorithms ............................................................................................................................... 31 Why algorithms? • 31 Algorithmic performance • 32

Page 9

Algorithm analysis • 32 Algorithm 1 • 34 Algorithm 2 • 35 Complexity .............................................................................................................................. 36 Asymptotic analysis • 37 Big O notation • 38 Why big O matters • 38 Common big O examples • 38 Common big O time complexities • 40 Algebraic rules for big O analysis • 41 Rule 1: Focus on the dominant term • 41 Rule 2: Ignore multiplicative constants • 42 Rule 3: Ignore constant addition/subtraction • 42 Rule 4: Addition rule • 42 Rule 5: Division rule • 42 Summary ................................................................................................................................ 43 Part 2: Common Data Structures and Applications 45 Chapter 2: Arrays and Linked Lists 47 Arrays ...................................................................................................................................... 48 Array operations and their efficiency • 49 Resizing arrays: Expansion and contraction • 53 Amortized analysis: Resizing an array • 55 Assessing the expansion cost • 57 Vectors • 61 Types of arrays • 61 Unordered arrays • 62 Ordered arrays • 64 Linked lists .............................................................................................................................. 65 Operations and efficiency • 66 Types of linked lists • 67 ConcurrentLinkedQueue • 68 LinkedHashMap • 68 Comparing arrays and linked lists ........................................................................................... 69 Table of Contents viii

Page 10

Flexibility, access, and operations • 69 Real-world application: High-frequency logging • 69 Summary ................................................................................................................................ 70 Exercises ................................................................................................................................. 72 Exercise 1: Token window in agentic workflows • 72 Solution • 73 Exercise 2: Remove duplicates from sorted array • 74 Exercise 3: Merge two sorted lists • 74 Exercise 4: Rotate array • 75 Exercise 5: Remove linked list nodes • 76 Exercise 6: Find the middle element of a list • 76 Exercise 7: Max subarray • 77 Exercise 8: Intersection of two arrays • 77 Chapter 3: Stacks and Queues 79 What is a stack? ...................................................................................................................... 80 Example 1: Browser back-button navigation • 81 Example 2: Word processor undo/redo mechanism • 83 Abstract data type (ADT): Stack • 84 Concrete implementations • 85 Array-based stack (DynamicArrayStack) • 85 List-based stack (LinkedListStack) • 86 Performance: Linked‑based vs. array‑based stacks • 88 Memory • 90 When to use what? • 90 A stack example • 90 Thread-safe deque • 91 Queue ...................................................................................................................................... 93 What is a queue • 93 Example 1: Print spooler queue • 94 Example 2: Deferred processing and prioritization • 95 Abstract data type (ADT): Queue • 95 Concrete implementations • 96 Array-based queue (DynamicArrayQueue) • 97 Link-based queue (LinkedListQueue) • 99 ix Table of Contents

Page 11

Summary .............................................................................................................................. 100 Exercises ................................................................................................................................ 101 Exercise 1: Nested tool invocation in agentic workflows • 102 Solution • 102 Exercise 2: MinStack • 103 Exercise 3: Queue using two stacks • 104 Exercise 4: Daily temperatures: Next warmer day • 104 Exercise 5: Sliding window maximum • 105 Exercise 6: Reverse polish notation • 105 Exercise 7: Task scheduler • 106 Exercise 8: LRU cache • 107 Chapter 4: Maps and Hash Tables 109 What is a map? ...................................................................................................................... 109 Example 1: Address books • 110 Example 2: Parking garage ticketing system • 111 Abstract data type (ADT): Map ............................................................................................... 112 Concrete implementations ..................................................................................................... 114 Fundamentals of hashing ....................................................................................................... 114 What is a hash and hash function? • 115 Key properties of good hashing • 116 Why hashing amortizes to O(1)? • 117 Collision resolution techniques .............................................................................................. 119 Open addressing • 119 Linear probing • 119 Quadratic probing • 119 Closed addressing • 120 Separate chaining • 120 Hashing and the core map operations .................................................................................... 121 Examples of hashing in practice ............................................................................................. 122 Summary ............................................................................................................................... 122 Exercises ............................................................................................................................... 124 Exercise 1: HashMap-based AI agent state management • 124 Solution • 127 Exercise 2: Uniform hash function • 129 Table of Contents x

Page 12

Exercise 3: Linear probing hash map • 129 Exercise 4: Quadratic probing hash map • 131 Exercise 5: Chaining hash map • 132 Exercise 6: Hash table with open addressing • 134 Exercise 7: HashMap with load factor monitoring • 135 Exercise 8: HashMap with collision statistics • 137 Chapter 5: Trees 141 What is a tree? ........................................................................................................................ 141 Binary trees and properties .................................................................................................... 142 Java representation • 143 Binary search trees (BST) and properties .............................................................................. 144 Java representation • 146 General (n-ary) trees and properties ..................................................................................... 146 Java representation • 147 Abstract data type (ADT) ....................................................................................................... 148 N-ary tree ADT • 148 Binary tree ADT • 149 What is a traversal? ............................................................................................................... 150 Depth-first traversal ............................................................................................................... 151 Recursive methods: DFS • 151 Pre-order traversal (node, left, right) • 151 In-order traversal (left, node, right) • 152 Post-order traversal (left, right, node) • 153 Iterative methods: DFS • 153 DFS traversal complexity: recursion vs. iteration • 156 Breadth-first traversal ............................................................................................................ 156 Iterative methods: BFS • 157 BFS traversal complexity: recursion vs. iteration • 158 BFS vs. DFS ............................................................................................................................. 159 Trees in java collection framework ........................................................................................ 160 TreeMap for sorted Key-Value storage • 161 TreeSet for sorted unique elements • 162 NavigableMap interface operations • 162 NavigableSet interface range operations • 163 xi Table of Contents

Page 13

Custom tree sorting with comparator • 163 Summary .............................................................................................................................. 164 Exercises ............................................................................................................................... 166 Exercise 1: Knowledge base category search in AI • 166 Solution • 169 Exercise 2: Validate binary search tree • 172 Exercise 3: Pre-order from in-order implementation • 173 Exercise 4: Iterative post-order traversal with a single stack • 174 Exercise 5: Level-order traversal without a queue • 176 Exercise 6: Memory-efficient traversal • 178 Exercise 7: Maximum depth of binary tree • 178 Exercise 8: Binary tree side view • 179 Exercise 9: Lowest common ancestor of a binary tree • 180 Chapter 6: Priority Queues and Heaps 183 What is a priority queue? ...................................................................................................... 183 Example 1: Seat assignment on a flight • 185 Example 2: Top K elements • 185 Abstract data type (ADT): priority queue ............................................................................... 187 Order, priority, and efficiency • 187 Implementing priority queues using arrays ........................................................................... 187 Unsorted array • 188 Sorted array • 189 Complexity of unsorted array vs. sorted array • 189 The heap abstraction ............................................................................................................ 190 The shape property • 190 Implementations: Array- and Tree-based heap ...................................................................... 191 Array-based heap • 191 Tree-based heap • 192 Minimum and maximum heaps • 192 Heap operations ..................................................................................................................... 193 Heapify-up • 195 Heapify-down • 197 Complexity analysis • 198 O(insert) • 198 Table of Contents xii

Page 14

O(delete) • 198 Applications and use cases .................................................................................................... 199 Advanced heaps ................................................................................................................... 200 Heaps in java collections framework ..................................................................................... 201 PriorityQueue as heap • 203 ArrayDeque with custom heap logic • 203 TreeSet with heap-like functionality • 204 Summary .............................................................................................................................. 204 Exercises ............................................................................................................................... 206 Exercise 1: Min-Heap • 206 Solution • 207 Exercise 2: Max-Heap • 209 Exercise 3: Find the kth largest element • 211 Exercise 4: K closest points to the origin • 211 Exercise 5: Top K frequent elements • 212 Exercise 6: Merge K sorted arrays • 213 Exercise 7: Task scheduler • 214 Exercise 8: Last stone weight • 215 Chapter 7: Graphs 217 What is a graph? ..................................................................................................................... 217 Types of graphs ..................................................................................................................... 219 Undirected and directed graphs • 219 Weighted graphs • 220 Graph components ................................................................................................................ 223 Vertex • 223 Edge • 225 Vertex-to-Edge • 226 Graph representation ............................................................................................................ 228 Adjacency list • 228 Adjacency matrix • 230 Performance characteristics • 232 Choosing a graph representation • 233 When to use adjacency list • 233 When to use adjacency matrix • 233 xiii Table of Contents

Page 15

Abstract data type (ADT) – graph .......................................................................................... 234 What is a traversal? ............................................................................................................... 235 Depth-first traversal • 236 Breadth-first traversal • 239 Trade-off analysis: DFS vs. BFS • 241 Graphs in java collections framework ................................................................................... 242 HashSet for unweighted graphs • 242 Priority queue: Dijkstra's algorithm • 243 Deque: BFS implementation • 243 Stack: DFS implementation • 244 TreeMap: Ordered map operations • 244 ConcurrentHashMap: Parallel graph processing • 245 LinkedHashSet: Maintaining insertion order • 245 Summary .............................................................................................................................. 246 Exercises ............................................................................................................................... 248 Exercise 1: AI agent dependency resolution • 248 Problem • 248 Solution • 252 Complexity: O(n2) • 255 Exercise 2: Undirected weighted graph • 256 Exercise 3: Cycle detection in DAG • 257 Exercise 4: Counting connected regions • 258 Exercise 5: Can all courses be finished? • 260 Exercise 6: Shortest path with BFS • 261 Exercise 7: Number of connected components • 262 Exercise 8: Analyze graph connectivity • 263 Part 3: Practical Algorithms and Examples 267 Chapter 8: Dynamic Programming 269 What is dynamic programming? ........................................................................................... 270 Why DP Matters .................................................................................................................... 272 Classic example: 0/1 knapsack problem • 272 Core concepts and techniques ............................................................................................... 273 Recurrence relations • 273 Table of Contents xiv

Page 16

Classic example: Fibonacci sequence • 274 Bottom-up (iterative) approach • 275 Top-Down (recursive + memoization) approach • 275 Fibonacci recurrence: Overlapping and optimal substructure • 276 Memoization vs. tabulation • 276 Execution style • 277 Storage structure • 277 Complexity • 278 Space usage • 278 When to choose • 278 Classic DP illustrations ......................................................................................................... 278 Problem: Continuous sum in an integer series • 278 Intuition • 279 Solution • 280 Observation • 281 Problem: Edit distance (levenshtein) in strings • 281 Formulation • 281 Initialization • 282 Solution • 283 Observation • 286 Problem: Cheapest flight route with At-Most K stops • 287 Intuition • 287 Solution: Bottom-Up DP • 287 Solution: Top-Down DP • 289 Problem: Building a product pipeline with DP • 293 Objectives • 293 Intuition • 293 Solution • 293 DP practicals checklist .......................................................................................................... 297 Summary .............................................................................................................................. 298 Exercises .............................................................................................................................. 300 Exercise 1: Climbing stairs problem • 300 Solution • 301 Exercise 2: Maximize sum without adjacent elements • 303 Exercise 3: Coin change • 305 xv Table of Contents

Page 17

Exercise 4: Longest common subsequence • 306 Exercise 5: 0/1 knapsack • 307 Exercise 6: Word break • 308 Exercise 7: Longest increasing subsequence • 309 Exercise 8: Target sum • 310 Chapter 9: Recursion 313 Understanding recursion: patterns, mechanics, and pitfalls .................................................. 313 Recursive patterns • 314 Designing good base cases • 314 Example: Factorial • 315 Recursion vs. iteration ........................................................................................................... 316 Recursion call stack ............................................................................................................... 318 The implicit call stack: How recursion works • 319 The challenge of naive recursion (overlapping subproblems) • 320 Tail recursion ........................................................................................................................ 322 Examples • 322 Measuring complexity .......................................................................................................... 323 Analyzing merge sort • 324 Method: Recursion tree • 325 Recursive component: 2T(N/2) • 325 Non-recursive component: f(N) • 325 Recursive tree analysis of f(N) • 326 Total cost of merge sort • 326 Method: the master theorem • 326 Cost of recursive calls (aT(n/b)) • 327 Cost of non-recursive work (f(n)) • 328 Theorem summary • 329 Example 1: Merge sort • 330 Step 1: Define the recurrence relation • 330 Step 2: Identify the parameters (a, b, and f(n)) • 330 Step 3: Calculate the recursive value • 330 Step 4: Apply the master theorem • 331 Step 5: Determine the complexity • 331 Example 2: Binary search • 331 Table of Contents xvi

Page 18

Step 1: Define the recurrence relation • 331 Step 2: Identify the parameters (a, b, and f(n)) • 331 Step 3: Calculate the recursive value • 332 Step 4: Apply the master theorem • 332 Step 5: Determine the complexity • 332 Recursion in data structures ................................................................................................. 332 Binary tree depth-first search • 333 Quick sort depth-first search • 333 Recursive BFS on a graph • 333 Summary .............................................................................................................................. 334 Exercises ............................................................................................................................... 335 Exercise 1: AI prompt template expansion • 336 Example • 336 Problem • 336 Solution • 339 Exercise 2: Merge sort analysis • 341 Exercise 3: Recursion to iteration conversion • 342 Exercise 4: String permutations • 343 Exercise 5: Subset sum • 345 Exercise 6: Arithmetic expression parser • 346 Exercise 7: Binary tree traversal • 348 Exercise 8: Geometric series sum • 350 Chapter 10: Sorting 353 What is sorting? .................................................................................................................... 353 Sorting algorithm properties and trade-offs ......................................................................... 353 Stability in sorting • 354 In-place vs. out-of-place sorting • 355 In-place • 355 Out-of-place • 355 Time complexity • 356 Space complexity • 356 Classification of sorting algorithms ...................................................................................... 357 O(n²) basic comparison sorts ................................................................................................ 357 Bubble sort • 357 xvii Table of Contents

Page 19

Selection sort • 359 Insertion sort • 360 The Ω (n log n) limit ............................................................................................................. 362 The proof sketch • 362 Selection implications • 362 Advanced comparison sorts .................................................................................................. 363 Merge sort • 363 Algorithm walkthrough • 365 Quick sort • 366 The partition process • 367 Algorithm walkthrough • 367 Pivot selection: Mitigating the O(n2) Worst-Case • 368 Heap sort • 369 Heapification and extraction: The two-phase approach • 371 Algorithm walkthrough • 371 Non-comparison sorts .......................................................................................................... 372 Counting sort • 372 Radix sort • 375 Algorithm walkthrough • 377 When to use which sort ........................................................................................................ 378 Merge sort • 378 Quick sort • 378 Heap sort • 378 Counting sort • 378 Radix sort • 379 Hybrid comparison-based sorts ............................................................................................ 380 Dual-pivot quicksort • 380 The Two-pivot strategy • 380 Example • 381 Timsort • 383 Example • 383 Engineered sorts in the real world ......................................................................................... 384 Summary .............................................................................................................................. 386 Exercises ............................................................................................................................... 388 Exercise 1: RAG Re-ranking in AI • 388 Table of Contents xviii

Page 20

Solution • 391 Time complexity: O(N log N) • 392 Exercise 2: Stability analysis • 392 Exercise 3: Space complexity implementation • 395 Exercise 4: Pivot selection strategies • 397 Exercise 5: Hybrid algorithm design • 400 Exercise 6: Find the K-th largest element in an array • 403 Exercise 7: Top K frequent elements • 405 Exercise 8: Merge intervals • 407 Chapter 11: Concurrency 411 Introduction to threads and concurrent execution ............................................................... 412 Shared state • 414 Atomic operations and hardware-level guarantees • 416 Why atomic operations are necessary • 416 Hardware-level atomicity: Compare-and-Swap (CAS) • 416 Java's atomic facilities • 416 Hardware-level guarantee • 417 Mutual exclusion • 418 Synchronization • 419 Deadlock • 419 Lock interface • 420 Condition • 423 Semaphore • 424 Lock-free data structures and memory models ..................................................................... 426 Memory visibility • 426 Stacks and queues • 427 Arrays and lists • 431 Option A: Coarse-grained thread safety via synchronized wrappers • 431 Option B: Trade-offs of copy-on-write arrays • 432 Option C: Lock-free general-purpose deques • 433 Concurrent hash tables • 433 Lock-free striped word counter • 434 Collision resolution • 435 Safe and managed concurrency ............................................................................................. 436 xix Table of Contents