Tag: data-structures

Pick the Right Structure:Match the Job to the Data Layout

A decision guide for the data-structures series: given the hot operation, which layout and which JDK type — with links to every post in the series.

Data Structures

Quadtrees and k-d Trees:Space as a Tree Instead of a Nested Loop

Spatial trees split the plane so range and nearest-neighbor queries skip whole regions. Quadtrees cut into four boxes; k-d trees alternate axis splits.

Data Structures

Suffix Arrays:Substring Search Without a Full Suffix Tree

A suffix array is the sorted list of a string’s suffixes as start indices. Binary search finds substrings; a short section contrasts the heavier suffix tree.

Data Structures

Treaps:BST Order Plus Heap Priority

A treap is a BST on keys and a heap on random priorities. Rotations restore heap order so the shape stays balanced in expectation without color bits.

Data Structures

Splay Trees:Move What You Touch to the Root

A splay tree is a BST that rotates the accessed node to the root. Recently used keys get cheap; amortized O(log n) without storing balance factors.

Data Structures

LRU Cache:Hash Map Plus Doubly Linked List as One Machine

Least-recently-used eviction is O(1) only when a hash map points at nodes of a doubly linked list. How the two layouts share the work, and LinkedHashMap as the JDK shortcut.

Data Structures

Bloom Filters:Maybe-Yes, Definitely-No, and Why False Positives Are the Point

A Bloom filter is a bit array plus k hashes. It can say definitely not in the set, or maybe yes. False positives are the trade for tiny memory — never a false negative.

Data Structures

Skip Lists:Layers of Express Lanes Instead of Rotations

A skip list is a layered linked list where higher levels skip ahead. Expected O(log n) search without tree rotations — Redis and ConcurrentSkipListMap use this idea.

Data Structures

Fenwick Trees:Prefix Updates When a Segment Tree Is More Tree Than You Need

A Fenwick tree (BIT) stores prefix aggregates in an array using least-significant-bit jumps. Point update and prefix query in O(log n) with less machinery than a segment tree.

Data Structures

Segment Trees:Range Queries Without Rescanning the Array

A segment tree stores aggregates of array ranges in a binary tree of intervals. Point update and range query in O(log n) without walking the whole slice each time.

Data Structures

Union-Find:Connected Components Without Building a Graph

Disjoint sets with find and union: path compression and union by rank so “are these two in the same component?” stays nearly O(1) without storing an adjacency list.

Data Structures

Tries:Prefix Search Without Scanning Every String

A trie stores strings by shared prefixes. Autocomplete and dictionary lookup become a walk down characters — not a scan of every word.

Data Structures

Graphs:Adjacency List, Matrix, Directed and Weighted — Pick the Layout First

A graph is vertices and edges. Adjacency list vs matrix, directed vs undirected, weighted vs not — choose the representation before you think about an algorithm.

Data Structures

Heaps:Priority in O(log n) Without Sorting the Whole Collection

A binary heap is a complete tree in an array that keeps the next-best element at the root. Min vs max, PriorityQueue in the JDK, and why you will hear Fibonacci heap without implementing one.

Data Structures

B-Trees:Wide Nodes for Disk (and Why Databases Do Not Use BSTs)

A B-tree packs many keys per node so one disk page is one hop. Why databases and filesystems use this shape, and how B+ trees keep values in the leaves.

Data Structures

Red-Black Trees:The Shape Behind `TreeMap` and `TreeSet`

A red-black tree is a BST painted with color rules that keep height logarithmic without AVL’s strict balance. Why TreeMap and TreeSet use this shape.

Data Structures

AVL Trees:Height Balance When You Need Strict Guarantees

An AVL tree is a BST that rebalances on insert and delete so height stays O(log n). Balance factors, rotations, and when the extra strictness is worth it versus red-black.

Data Structures

Binary Search Trees:Ordered Trees That Go Lopsided Under Sorted Input

A BST keeps left < node < right so search is O(height). Why already-sorted inserts become a linked list, and what that does to the bill.

Data Structures

Binary Trees:Shape, Traversals, and What “Balanced” Even Means

A binary tree is a hierarchical layout: left, right, parent. Height vs size, preorder inorder postorder and level-order as operations of the shape, and what balanced actually promises.

Data Structures

Sets:Uniqueness Without Scanning the List

The set ADT is unique membership. HashSet delivers it with a hash table; List.contains is a scan. When TreeSet belongs instead, and what you lose (order).

Data Structures

Hash Tables:Buckets, Collisions, and When `HashMap` Lies About O(1)

How hashing maps a key to a bucket, what chaining and open addressing do with collisions, and why HashMap is expected O(1) — not a law of physics.

Data Structures

Deque:Both Ends Without Two Structures

A double-ended queue lets you push and pop at both ends in O(1). How ArrayDeque delivers that in the JDK, and when a deque is a stack, a queue, or a sliding window.

Data Structures

Queue:FIFO, Circular Buffers, and Why a Naive Array Queue Rotates

FIFO as an ADT: enqueue, dequeue, and why a naive array queue slides or wastes space — and how a circular buffer (ring) fixes both.

Data Structures

Stack:Undo, Parse, and Call Frames Are the Same Shape

LIFO as an ADT: push, pop, peek, and why undo, brace matching, and the call stack are the same layout — implemented with ArrayDeque, not java.util.Stack.

Data Structures

Linked Lists:Singly, Doubly, and Circular Without Losing the Head

How node-and-pointer lists make splice cheap when you already hold the node, why get(i) walks, and how singly, doubly, and circular variants differ.

Data Structures

Dynamic Arrays:Amortized Growth Without Pretending Append Is Always O(1)

How ArrayList grows by doubling, why append is amortized O(1) not a guarantee on the next call, and when a fixed array is the honest choice.

Data Structures

Arrays:Why Index `i` Is Free and Insert in the Middle Is Not

How a contiguous array makes index i O(1), why insert and delete in the middle slide everything, and how a 2D matrix is still the same layout.

Data Structures

Data Structures Roadmap:What to Learn from Arrays to Tries

A beginner-to-advanced path through data structures: glossary, Big-O literacy, a JDK map, and a living index of every post in this series.