Cấu trúc tuyến tính

Array vs ArrayList — Khi nào primitive thắng wrapper

int[] dùng 40 MB cho 10 triệu phần tử; ArrayList<Integer> dùng gần 480 MB — chênh lệch 12 lần. Bài này phân biệt int[], Integer[], Arrays.asList(), List.of(), và ArrayList — biết khi nào pick gì cho production.

Linked list — Vì sao production Java gần như không dùng LinkedList

Tutorial DSA dạy LinkedList.add() là O(1) — nghe tương đương ArrayList. Nhưng grep production codebase: hầu như không ai dùng LinkedList mới. Bài này giải thích cơ chế linked list, vì sao Big-O không nói hết, và những trường hợp hiếm hoi linked list thực sự thắng.

Stack — LIFO từ chồng đĩa đến JVM call stack

Mở browser, click 5 link liên tiếp, bấm Back: page xuất hiện theo thứ tự ngược lại. Bài này phân biệt khi nào pick stack thay queue/list, cách Java implement đúng với ArrayDeque, và pitfall production khi dùng java.util.Stack legacy.

Queue & Deque — FIFO scheduler, sliding window, và ArrayDeque thay LinkedList

Queue là cấu trúc dữ liệu nền tảng của thread pool, BFS, message broker, và OS scheduler. Bài này phân biệt 4 biến thể queue trong Java, giải thích vì sao ArrayDeque thay thế LinkedList, và trình bày pattern sliding window dùng monotonic deque đạt O(n).

Circular buffer — Ring queue cho hot path & log buffer

ArrayList shift O(n) khi đầy, LinkedList có cache miss và GC pressure cao. Circular buffer giải bài toán giữ N event gần nhất với O(1) enqueue và auto-evict oldest — xương sống của log system, audio DSP, và LMAX Disruptor.

PriorityQueue — Top-K, scheduler, Dijkstra cần queue thứ tự

ArrayList scan max là O(n) mỗi lần — với 1 triệu task và 1000 lookup/giây, đây là bottleneck rõ ràng. PriorityQueue dùng binary heap để đảm bảo O(log n) insert và O(log n) extract-min. Bài này giới thiệu API, pattern top-K, và use case thực tế.

Mini-challenge — Implement LRU Cache thủ công (không dùng LinkedHashMap)

Implement LRU Cache đạt O(1) cho cả get và put bằng cách kết hợp HashMap và Doubly Linked List từ đầu — pattern mà Caffeine, Redis, và Linux page cache đều dùng.

Case Study: LMAX Disruptor — Vì sao ring buffer thắng BlockingQueue 10x

LMAX Exchange cần xử lý hơn 6 triệu order mỗi giây với p99 latency dưới 1ms. BlockingQueue chuẩn JDK chỉ đạt 5 triệu ops/s. Bài này phân tích bốn kỹ thuật Disruptor dùng để đạt 25M+ ops/s: ring buffer pre-allocated, sequence counter, cache-line padding, và wait strategy không dùng lock.