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

Module 2 — Cấu trúc tuyến tính: tổng quan

Array, ArrayList, LinkedList, Stack, Queue, Deque, Circular buffer — khi nào chọn cái nào và vì sao. Bản đồ 8 bài của module.

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

int[] dùng 40 MB; ArrayList<Integer> dùng 234 MB — gấp 6 lần cho 10 triệu phần tử. Bài phân biệt array và danh sách động, khi nào chọn cái nào cho production.

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

LinkedList.add() là O(1) nhưng production Java gần như không dùng. Bài giải thích cơ chế, constant factor cache miss, và khi nào linked list thực sự thắng.

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

Bấm Back trên browser: page xuất hiện ngược lại — đó là stack. Bài phân biệt khi nào pick stack thay queue, cách implement đúng, và pitfall dùng java.util.Stack legacy.

Queue & Deque — FIFO, sliding window, ArrayDeque thay LinkedList

Queue là nền tảng thread pool, BFS, OS scheduler. Bài phân biệt 4 biến thể, vì sao ArrayDeque thắng LinkedList, và sliding window monotonic deque đạt O(n).

Circular buffer — Ring queue cho hot path & log buffer

Circular buffer giải bài giữ N event gần nhất với O(1) enqueue và auto-evict oldest — không alloc, không shift. 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 tốn O(n) — bottleneck rõ với 1 triệu task. Bài giới thiệu PriorityQueue, binary heap, sift-up/sift-down O(log n), và pattern top-K.

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à DoublyLinkedList từ đầu — pattern mà Caffeine, Redis, và Linux page cache đều dùng.

Case Study: LMAX Disruptor — Ring buffer thắng BlockingQueue 10x

LMAX cần 6M order/giây, p99 dưới 1ms. Bài phân tích 4 kỹ thuật Disruptor đạt 25M+ ops/s: ring buffer, sequence counter, cache-line padding, lock-free wait.

Module 2 — Tổng kết: cheat sheet cấu trúc tuyến tính

Cheat sheet Big-O, memory footprint, glossary 13 thuật ngữ, 5 pitfall tổng hợp, self-assessment 4 outcome, và lộ trình tiếp theo.