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.
TL;DR
Module này trả lời một câu hỏi đơn giản nhưng hay bị trả lời sai: khi nào chọn array, khi nào chọn linked list, khi nào chọn stack/queue? Câu trả lời không nằm ở O(n) — mà nằm ở cache locality, memory footprint, và access pattern. Từ array nguyên thuỷ 40 MB đến LinkedList 400 MB cho cùng 10 triệu số nguyên — khoảng cách 10x đến từ thiết kế bộ nhớ, không phải thuật toán.
Vì sao cần module này
Big-O che giấu constant factor. Tutorial dạy LinkedList.add() là O(1) và ArrayList.add() là amortized O(1) — nghe có vẻ tương đương. Nhưng production Java hầu như không dùng LinkedList vì cache miss khiến sum 10 triệu phần tử qua linked list chậm hơn array 25 lần dù cùng O(n).
Module này đào sâu cơ chế bên dưới từng cấu trúc — layout bộ nhớ, cache behavior, grow strategy — để bạn chọn đúng cấu trúc cho từng bài toán production, không chỉ cho bài DSA.
Sau module này bạn sẽ
- Compare mảng tĩnh, mảng động và danh sách liên kết theo truy cập / chèn / xoá và bộ nhớ
- Implement stack, queue, deque, circular buffer và hàng đợi ưu tiên bằng pseudocode
- Explain vì sao cache locality khiến mảng nhanh hơn danh sách liên kết dù cùng O(n)
- Design cấu trúc kết hợp (LRU cache = hash map + danh sách liên kết đôi; ring buffer SPSC)
Bản đồ module
graph TD
START(["Bắt đầu"])
A01["Bài 01<br/>Array vs ArrayList<br/>— bộ nhớ & boxing"]
A02["Bài 02<br/>Linked list<br/>— singly & doubly"]
A03["Bài 03<br/>Stack<br/>— LIFO & call stack"]
A04["Bài 04<br/>Queue & Deque<br/>— FIFO & hai đầu"]
A05["Bài 05<br/>Circular buffer<br/>— ring & SPSC"]
A06["Bài 06<br/>Priority Queue<br/>— heap intro"]
A07["Bài 07<br/>Mini-challenge<br/>LRU Cache"]
A08["Bài 08<br/>Case study<br/>LMAX Disruptor"]
A09["Bài 09<br/>Tổng kết & cheat sheet"]
START --> A01 --> A02 --> A03 --> A04 --> A05 --> A06 --> A07 --> A08 --> A09Lộ trình học
| Bài | Chủ đề | Điểm cốt lõi |
|---|---|---|
| 01 | Array vs ArrayList | 40 MB vs 234 MB — boxing overhead, capacity vs size |
| 02 | Linked list | Cache miss 25x — khi nào O(1) insert thực sự quan trọng |
| 03 | Stack | LIFO — call stack, undo, balanced brackets |
| 04 | Queue & Deque | FIFO — BFS, sliding window, monotonic deque |
| 05 | Circular buffer | Ring + modulo trick — O(1) enqueue/dequeue, SPSC lock-free |
| 06 | Priority Queue | Min-heap intro — dijkstra, task scheduling |
| 07 | Mini-challenge LRU | HashMap + DoublyLinkedList — O(1) get & put |
| 08 | Case study Disruptor | Pre-alloc + false sharing padding — 25M+ ops/s |
| 09 | Tổng kết | Cheat sheet, glossary, pitfall, self-assessment |
Cách học hiệu quả
Đọc pseudocode, đừng chạy code. Các bài dùng pseudocode ngôn-ngữ-trung-lập — keyword điều khiển English (if / while / for), identifier English, chú thích tiếng Việt. Mục tiêu là nắm tư tưởng, không phải copy-paste vào IDE.
Tập trung vào "vì sao", không chỉ "cái gì". Mỗi bài có section "Cơ chế bên dưới" giải thích layout bộ nhớ, cache behavior, grow strategy. Đây là phần quan trọng nhất — đọc kỹ trước self-check.
Làm mini-challenge trước khi xem lời giải. Bài 07 (LRU Cache) yêu cầu implement đầy đủ. Tự viết pseudocode trước, sau đó so sánh với lời giải để thấy sự khác biệt trong xử lý edge case.
Prerequisites: Module 1 (Big-O, amortized analysis, cache locality) — bài 08 Case Study Disruptor sẽ reference trực tiếp bài 03 + 04 + 07 của Module 1.
Bài tiếp theo: Array vs ArrayList
Bài này có giúp bạn hiểu bản chất không?
Hỏi đáp về bài này
Chưa có câu hỏi
Có gì chưa rõ trong bài? Đặt câu hỏi đầu tiên — câu trả lời từ cộng đồng giúp bạn (và người sau).
Đặt câu hỏi đầu tiên