Picking a data structure is picking which operation gets cheap. Chọn cấu trúc dữ liệu là chọn thao tác nào rẻ.

Eight structures, four operations each. None is fastest at everything; each one makes a few operations cheap and charges you for the rest. Tám cấu trúc, mỗi cấu trúc bốn thao tác. Không cấu trúc nào nhanh ở mọi thứ; mỗi cái làm vài thao tác trở nên rẻ và bắt bạn trả giá ở phần còn lại.

Array
Linked List
Stack
Queue
Hash Map
BST
Heap
Trie

What the letters cost, in stepsCác chữ cái Big-O tốn bao nhiêu bước

Slide n to see how many steps each operation takes. Bars are on a log scale: one notch is ten times more work. Kéo n để xem mỗi thao tác tốn bao nhiêu bước. Thanh đo theo thang log: mỗi nấc là gấp mười lần công việc.

ItemsSố phần tử 1,000,000 Show worst case (hash collisions, unbalanced tree) Xem trường hợp xấu nhất (va chạm hash, cây lệch)

AccessTruy cập

SearchTìm kiếm

InsertChèn

DeleteXoá

Trie assumes key length L = 10. Pale-red bars mark a cost that only appears in the worst case. Trie giả định độ dài khoá L = 10. Thanh màu đỏ nhạt là chi phí chỉ xuất hiện ở trường hợp xấu nhất.

Which one do I need?Mình cần cái nào?

Answer the first box honestly before reading the list below it.Trả lời thật lòng ô đầu tiên trước khi đọc danh sách bên dưới.

First: maybe you need none of themTrước hết: có thể bạn không cần cái nào

Small data (under a few thousand items): a built-in array and a linear scan is usually just as fast, thanks to cache.Dữ liệu nhỏ (dưới vài nghìn phần tử): mảng có sẵn cộng quét tuyến tính thường nhanh không kém, nhờ cache.
Read once: stream it and keep only the number you need.Chỉ đọc một lần: đọc dạng stream, chỉ giữ con số cần tính.
Many lookups, rare changes: sort once, then binary search.Tra nhiều, ít thay đổi: sắp xếp một lần rồi tìm nhị phân.
Large, long-lived, shared: use a database with an index instead of building one in memory.Lớn, cần lưu lâu, nhiều người dùng: dùng cơ sở dữ liệu có index thay vì tự dựng trong bộ nhớ.

I fetch items by position, “the i-th one”Tôi lấy phần tử theo vị trí, “phần tử thứ i”Array
I look things up by key, equality onlyTôi tra theo khoá, chỉ so sánh bằngHash Map
…and I also need min, max, ranges or sorted order…và còn cần min, max, khoảng hoặc thứ tự sắp xếpBalanced BST
I search by string prefixTôi tìm theo tiền tố chuỗiTrie
I keep taking the smallest or most urgent itemTôi liên tục lấy phần tử nhỏ nhất hoặc gấp nhấtHeap
Newest first: last opened, first closedMới nhất trước: mở sau, đóng trướcStack
Oldest first: first come, first servedCũ nhất trước: đến trước, phục vụ trướcQueue
I insert and unlink constantly at a spot I already holdTôi chèn và gỡ liên tục tại vị trí đã cầm sẵnLinked List

The eight structuresTám cấu trúc

Numbered as in the original cheatsheet. Colour shows the family, explained at the bottom of the page.Đánh số theo cheatsheet gốc. Màu thể hiện họ cấu trúc, giải thích ở cuối trang.

Array

LinearTuyến tính

Elements side by side in memory. Index math gives instant access; inserting in the middle shifts everything after it.Các phần tử nằm sát nhau trong bộ nhớ. Tính địa chỉ cho truy cập tức thì; chèn vào giữa thì mọi phần tử phía sau phải dịch.

accesstruy cậpO(1)

searchtìmO(n)

insertchènO(n)

deletexoáO(n)

Use forDùng cho: Paged lists, pixel and audio buffers, sorted data for binary search.Danh sách phân trang, bộ đệm pixel và âm thanh, dữ liệu đã sắp để tìm nhị phân.
GainĐược: O(1) by index, fastest scans, near-zero overhead.O(1) theo chỉ số, quét nhanh nhất, gần như không tốn bộ nhớ phụ.
LoseMất: O(n) insert and delete away from the end; growth causes latency spikes.Chèn/xoá không ở cuối tốn O(n); lúc mở rộng gây độ trễ tăng vọt.

Trades mid-sequence insert and delete for O(1) indexed access and cache-fast scans.Đổi chi phí chèn/xoá ở giữa lấy truy cập O(1) theo chỉ số và tốc độ quét nhờ cache.

Sign:Dấu hiệu: you think “the i-th element”.bạn nghĩ “phần tử thứ i”.

Correction: append and pop at the end of a dynamic array are O(1) amortized, not O(n).Đính chính: thêm/xoá ở cuối mảng động là O(1) khấu hao, không phải O(n).

Linked List

LinearTuyến tính

Nodes linked by pointers. Re-pointing is instant; getting to the right node means walking the chain.Các nút nối với nhau bằng con trỏ. Đổi con trỏ thì tức thì; còn đi tới đúng nút thì phải lần theo cả chuỗi.

accesstruy cậpO(n)

searchtìmO(n)

insertchènO(1)

deletexoáO(1)

Use forDùng cho: LRU caches (with a hash map), kernel lists, allocator free lists.LRU cache (đi cùng hash map), danh sách trong kernel, free list của bộ cấp phát.
GainĐược: O(1) insert/unlink at a held node, no resizing, stable node pointers.Chèn/gỡ O(1) tại nút đang cầm, không mở rộng, con trỏ tới nút luôn đúng.
LoseMất: A cache miss per hop, 8–16 bytes of pointers per node, no binary search.Mỗi bước nhảy một lần trượt cache, 8–16 byte con trỏ mỗi nút, không tìm nhị phân được.

Trades random access and cache locality for O(1) insert and delete at a node you already hold.Đổi truy cập ngẫu nhiên và cache locality lấy chèn/xoá O(1) tại nút đã cầm sẵn.

Sign:Dấu hiệu: you already hold a reference to where the change happens.bạn đã cầm sẵn tham chiếu tới chỗ cần sửa.

Correction: O(1) delete holds only at the head or a held node in a doubly linked list. Deleting by value is O(n).Đính chính: xoá O(1) chỉ đúng ở đầu, hoặc tại nút đang cầm trong danh sách liên kết đôi. Xoá theo giá trị là O(n).

Stack

Ordering ruleQuy tắc thứ tự

Last in, first out. Everything happens at the top, usually the end of an array.Vào sau, ra trước. Mọi thứ diễn ra ở đỉnh, thường là cuối một mảng.

topđỉnhO(1)

searchtìmO(n)

pushpushO(1)

poppopO(1)

Use forDùng cho: Undo, bracket matching, iterative DFS, the call stack.Undo, kiểm tra ngoặc, DFS bằng vòng lặp, call stack.
GainĐược: O(1) everything, a narrow interface that is hard to misuse.Mọi thao tác O(1), giao diện hẹp khó dùng sai.
LoseMất: No reach into the middle; deep recursion hits stack limits.Không chạm được phần giữa; đệ quy sâu đụng giới hạn stack.

Trades access to any element for O(1) operations and an interface that is hard to misuse.Đổi khả năng chạm vào phần tử bất kỳ lấy thao tác O(1) và giao diện khó dùng sai.

Sign:Dấu hiệu: whatever opened last must close first.thứ mở sau cùng phải đóng trước tiên.

Correction: “Access O(1)” means the top only. Arbitrary access is not part of a stack.Đính chính: “Truy cập O(1)” chỉ là phần tử ở đỉnh. Truy cập tuỳ ý không thuộc về stack.

Queue

Ordering ruleQuy tắc thứ tự

First in, first out. A ring buffer moves two indices instead of shifting elements.Vào trước, ra trước. Ring buffer chỉ dịch hai chỉ số thay vì dịch phần tử.

frontđầuO(1)

searchtìmO(n)

enqueuevàoO(1)

dequeueraO(1)

Use forDùng cho: BFS, background jobs, producer–consumer buffers, rate-limit windows.BFS, hàng đợi công việc nền, bộ đệm producer–consumer, cửa sổ rate limit.
GainĐược: O(1) both ends, fair ordering, backpressure when bounded.O(1) ở hai đầu, công bằng theo thứ tự, có backpressure khi giới hạn kích thước.
LoseMất: No priorities; unbounded queues hide slow consumers until memory runs out.Không có ưu tiên; queue không giới hạn che giấu bên tiêu thụ chậm tới khi hết RAM.

Trades priority and arbitrary access for fair arrival-order processing at O(1).Đổi quyền ưu tiên và truy cập tuỳ ý lấy sự công bằng theo thứ tự đến với chi phí O(1).

Sign:Dấu hiệu: first come, first served.đến trước, phục vụ trước.

Watch out: list.pop(0) and array.shift() are O(n). Use a deque.Cẩn thận: list.pop(0) và array.shift() là O(n). Hãy dùng deque.

Hash Map

HashedBăm

A hash function turns the key into a bucket index, so you jump straight to it. Collisions still force a short scan.Hàm băm biến khoá thành chỉ số bucket, nên nhảy thẳng tới chỗ cần tìm. Va chạm vẫn buộc phải quét một đoạn ngắn.

getđọcO(1)*

containscó khôngO(1)*

putghiO(1)*

removexoáO(1)*

Use forDùng cho: Caches, frequency counts, de-duplication, id-to-record indexes, hash joins.Cache, đếm tần suất, khử trùng lặp, index id sang bản ghi, hash join.
GainĐược: Average O(1) on everything; turns many O(n²) loops into O(n).Trung bình O(1) mọi thao tác; biến nhiều vòng lặp O(n²) thành O(n).
LoseMất: No order or ranges; worst case O(n); rehash spikes; extra memory.Không có thứ tự hay khoảng; xấu nhất O(n); độ trễ tăng vọt khi băm lại; tốn bộ nhớ.

Trades ordering and worst-case guarantees for average O(1) lookup by key.Đổi thứ tự và đảm bảo trường hợp xấu nhất lấy tra cứu theo khoá trung bình O(1).

Sign:Dấu hiệu: you only ask “is X here?” or “what is X?”, by equality.bạn chỉ hỏi “có X không?” hoặc “X là gì?”, bằng phép so sánh bằng.

Correction: the original says “no scanning, ever”. Collisions do scan; adversarial keys can push every operation to O(n).Đính chính: ảnh gốc ghi “không bao giờ phải quét”. Va chạm thì vẫn quét; khoá được tính sẵn để va chạm có thể đẩy mọi thao tác lên O(n).

Balanced BSTBST cân bằng

TreeCây

Smaller keys left, larger right. Each comparison discards half the tree, and rotations keep the height near log₂n.Khoá nhỏ hơn bên trái, lớn hơn bên phải. Mỗi lần so sánh loại nửa cây, các phép xoay giữ chiều cao khoảng log₂n.

findtìm khoáO(log n)

rangekhoảngO(log n)

insertchènO(log n)

deletexoáO(log n)

Use forDùng cho: Sorted maps, date-range queries, leaderboards with rank, “next event after t”.Sorted map, truy vấn theo khoảng ngày, bảng xếp hạng có thứ hạng, “sự kiện kế tiếp sau t”.
GainĐược: Guaranteed O(log n), sorted traversal, floor/ceiling/min/max.O(log n) có đảm bảo, duyệt có thứ tự, floor/ceiling/min/max.
LoseMất: Slower than hashing on average, pointer-heavy, hard to implement correctly.Trung bình chậm hơn hash map, nhiều con trỏ, khó cài đúng.

Trades a hash map’s average speed for sorted order and a worst-case O(log n) guarantee.Đổi tốc độ trung bình của hash map lấy thứ tự sắp xếp và đảm bảo O(log n) ở trường hợp xấu nhất.

Sign:Dấu hiệu: you need “less than”, “greater than” or “between”.bạn cần “nhỏ hơn”, “lớn hơn” hoặc “trong khoảng”.

Correction: only self-balancing trees (AVL, red-black) give O(log n). A plain BST fed sorted data is O(n).Đính chính: chỉ cây tự cân bằng (AVL, red-black) mới cho O(log n). BST thường gặp dữ liệu đã sắp xếp là O(n).

Heap

TreeCây

Every parent is no larger than its children, so the minimum sits at the root. The whole tree lives in a flat array.Nút cha không lớn hơn nút con, nên phần tử nhỏ nhất luôn ở gốc. Cả cây nằm gọn trong một mảng phẳng.

peek minxem minO(1)

searchtìmO(n)

insertchènO(log n)

pop minlấy minO(log n)

Use forDùng cho: Priority queues, Dijkstra and A*, top-k, k-way merge, event-loop timers.Priority queue, Dijkstra và A*, top-k, gộp k danh sách, timer trong event loop.
GainĐược: Instant min, O(log n) updates, no pointers, O(n) heapify.Min tức thì, cập nhật O(log n), không con trỏ, heapify O(n).
LoseMất: Searching is O(n); no full order; arbitrary delete needs a position index.Tìm kiếm O(n); không có thứ tự đầy đủ; xoá tuỳ ý cần bảng vị trí.

Trades full order and searchability for the top-priority item in O(1) at O(log n) per update.Đổi thứ tự đầy đủ và khả năng tìm kiếm lấy phần tử ưu tiên nhất trong O(1), cập nhật O(log n).

Sign:Dấu hiệu: you keep asking “what is most urgent right now?” while data keeps arriving.bạn liên tục hỏi “cái gì gấp nhất lúc này?” trong khi dữ liệu vẫn đổ vào.

Correction: “delete” on the cheatsheet means pop-min. The original diagram (0 under 1) shows a bubble-up mid-swap, not a valid heap.Đính chính: “xoá” trong ảnh gốc là lấy min. Hình gốc (0 nằm dưới 1) là bubble-up đang đổi chỗ dở, chưa phải heap hợp lệ.

Trie

TreeCây

A prefix tree: each edge is a character, shared prefixes share a path. Cost depends on key length, not on how many keys you store.Cây tiền tố: mỗi cạnh là một ký tự, các tiền tố chung dùng chung đường đi. Chi phí phụ thuộc độ dài khoá, không phụ thuộc số khoá đang lưu.

prefixtiền tốO(L)

wordtìm từO(L)

insertchènO(L)

deletexoáO(L)

Use forDùng cho: Autocomplete, IP longest-prefix routing, URL routers, spell-check.Autocomplete, định tuyến IP theo tiền tố dài nhất, router URL, kiểm tra chính tả.
GainĐược: O(L) regardless of n, native prefix queries, lexicographic order.O(L) bất kể n, truy vấn tiền tố tự nhiên, có thứ tự từ điển.
LoseMất: Very memory-hungry, cache-unfriendly, slower than a hash set for exact match.Rất tốn bộ nhớ, kém thân thiện với cache, khớp chính xác thì chậm hơn hash set.

Trades memory for O(L) prefix queries that do not slow down as the dataset grows.Đổi bộ nhớ lấy truy vấn tiền tố O(L) không chậm đi khi dữ liệu lớn lên.

Sign:Dấu hiệu: your question starts with “which keys begin with…”.câu hỏi của bạn bắt đầu bằng “những khoá nào bắt đầu bằng…”.

Note: listing all matches for a prefix costs extra time proportional to the number of results.Lưu ý: liệt kê mọi kết quả khớp tiền tố tốn thêm thời gian tỷ lệ với số kết quả.

Trade-offs beyond Big-OĐánh đổi ngoài Big-O

The step meter above covers speed. These columns decide the rest of the choice.Bảng đếm bước ở trên nói về tốc độ. Các cột dưới đây quyết định phần còn lại của lựa chọn.

StructureCấu trúc	Keeps sorted orderGiữ thứ tự sắp xếp	Worst-case guaranteeĐảm bảo xấu nhất	Cache friendlinessThân thiện cache	Memory overheadBộ nhớ phụ
Array	Only if you maintain itChỉ khi tự giữ	Yes, except growthCó, trừ lúc mở rộng	ExcellentRất tốt	Very lowRất thấp
Linked List	NoKhông	YesCó	PoorKém	HighCao
Stack	Not applicableKhông áp dụng	YesCó	GoodTốt	LowThấp
Queue	Not applicableKhông áp dụng	YesCó	Good (ring buffer)Tốt (ring buffer)	LowThấp
Hash Map	NoKhông	No, O(n)Không, O(n)	MediumTrung bình	MediumTrung bình
Balanced BSTBST cân bằng	YesCó	YesCó	PoorKém	HighCao
Heap	Top element onlyChỉ phần tử đỉnh	YesCó	GoodTốt	Very lowRất thấp
Trie	Yes, lexicographicCó, theo từ điển	YesCó	PoorKém	Very highRất cao

Common mistakesSai lầm thường gặp

Each of these passes code review and only shows up when n gets large.Mỗi lỗi dưới đây đều lọt qua code review và chỉ lộ ra khi n đủ lớn.

MistakeSai lầm	Why it is wrongVì sao sai	FixSửa thế nào
Linked list because “insert is O(1)”Dùng linked list vì “chèn O(1)”	Finding the spot is O(n), with a cache miss per stepTìm vị trí mất O(n), mỗi bước một lần trượt cache	Dynamic array, unless you already hold the nodeMảng động, trừ khi đã cầm sẵn nút
`list.pop(0)` / `array.shift()` as a queuelàm queue	Every dequeue shifts the whole arrayMỗi lần lấy ra dịch cả mảng	`collections.deque`, ring bufferring buffer
`x in list` inside a looptrong vòng lặp	Silently O(n²)Âm thầm thành O(n²)	Build a set once, before the loopDựng set một lần trước vòng lặp
Hand-written, unbalanced BSTTự viết BST không cân bằng	Sorted input turns it into a line, O(n)Dữ liệu đã sắp biến cây thành đường thẳng, O(n)	`TreeMap`, `std::map`, `sortedcontainers`
Re-sorting everything to get the top 10Sắp xếp lại toàn bộ để lấy top 10	O(n log n) each time for 10 itemsO(n log n) mỗi lần chỉ để lấy 10 phần tử	Size-k heap, `heapq.nlargest`Heap kích thước k, `heapq.nlargest`
Relying on hash map iteration orderDựa vào thứ tự duyệt của hash map	An implementation detail that changes between languages and versionsChi tiết cài đặt, khác nhau giữa ngôn ngữ và phiên bản	Sort keys first, or use a sorted mapSắp khoá trước, hoặc dùng sorted map
Mutable objects as hash keysĐối tượng thay đổi được làm khoá hash	Mutate it after insert and it is lostSửa sau khi chèn là mất luôn	Immutable keys: strings, numbers, tuplesKhoá bất biến: chuỗi, số, tuple
Unbounded queues and cachesQueue và cache không giới hạn	A slow consumer grows memory until the process diesBên tiêu thụ chậm làm RAM tăng tới khi tiến trình chết	Set a limit and a policy for when it is fullĐặt giới hạn và chính sách khi đầy

Three things to rememberBa câu cần nhớ

Start from the operation you call most; the structure is whatever makes that one cheap.Bắt đầu từ thao tác bạn gọi nhiều nhất; cấu trúc đúng là cái làm thao tác đó rẻ.
Big-O is growth, not speed. On small data, a plain array and the cache usually win.Big-O là tốc độ tăng, không phải tốc độ chạy. Với dữ liệu nhỏ, một mảng đơn giản và cache thường thắng.
Read the fine print: average, amortized, balanced, at a known node. That is where systems fall over.Đọc kỹ điều kiện kèm theo: trung bình, khấu hao, cân bằng, tại nút đã biết. Hệ thống sập chính ở những chỗ đó.