Cấu trúc dữ liệu là gì?What Are Data Structures?

Thuộc bộ kiến thức Data Structures & Algorithms Roadmap.

Tổng quan

Data structure là cách tổ chức và lưu trữ dữ liệu trong máy tính sao cho có thể sử dụng nó một cách hiệu quả. Định nghĩa đó chính xác nhưng khô khan. Có một cách nói hữu ích hơn: data structure là một thỏa thuận bạn ký với cái máy. Bạn đồng ý sắp xếp dữ liệu theo một kiểu nhất định, và đổi lại một số thao tác trở nên rẻ — đồng thời, không tránh khỏi, một số thao tác khác trở nên đắt. Không có cấu trúc nào làm mọi thứ đều nhanh. Chọn một cấu trúc chính là chọn xem bạn quan tâm đến những thao tác nào.

Hãy xét một trường hợp cụ thể. Bạn có một triệu bản ghi user và cần trả lời câu hỏi “user X có nằm trong tập này không?” một trăm nghìn lần. Lưu chúng trong một array thường thì mỗi câu trả lời tốn một lần quét lên tới một triệu phép so sánh — tổng cộng 10¹¹ phép toán, mất vài phút CPU. Lưu chúng trong hash table thì mỗi câu trả lời tốn khoảng một lần tính hash và một lần chạm vào memory — tổng cộng 10⁵ phép toán, vài mili giây. Cùng dữ liệu, cùng câu hỏi, cùng cái máy, cùng lập trình viên. Thứ duy nhất thay đổi là cách sắp xếp, và nó mua về tốc độ nhanh hơn năm bậc độ lớn. Đó là toàn bộ lý lẽ cho việc học data structures.

Đây cũng là lý do roadmap đặt data structures trước algorithms. Thuật toán là một chuỗi các bước, nhưng chi phí của mỗi bước phụ thuộc vào dữ liệu đang nằm trong cái gì. Thuật toán Dijkstra là O(V²) với array và O((V + E) log V) với binary heap — thuật toán không đổi, cấu trúc bên dưới nó mới đổi. Bạn không thể lập luận gì về chi phí thuật toán cho tới khi biết cấu trúc của mình tính giá bao nhiêu cho mỗi thao tác, và đó là lý do mọi ghi chú trong phần này đều đi kèm bảng complexity của cấu trúc.

Kiến thức nền tảng

Chính xác thì data structure là gì

Một data structure có ba phần, và bỏ qua bất kỳ phần nào cũng sẽ dẫn tới rối rắm về sau:

1. Một cách bố trí (layout) — dữ liệu nằm vật lý trong memory như thế nào. Các ô liền kề? Các node rải rác trên heap được nối bằng pointer? Một bảng bucket kích thước cố định?
2. Một tập thao tác — bạn được phép làm gì với nó: insert, delete, search, lấy phần tử nhỏ nhất, duyệt theo thứ tự sắp xếp.
3. Invariant — những tính chất luôn đúng ở giữa các thao tác, và các thao tác phải bảo toàn chúng. “Node cha của heap luôn ≤ các node con.” “Cây con trái của BST chỉ chứa key nhỏ hơn.” “Load factor của hash table không bao giờ vượt 0.75.” Invariant chính là thứ khiến các thao tác nhanh; duy trì nó chính là cái giá của các thao tác.

Phần thứ ba là phần người ta hay bỏ qua, và nó lại là phần quan trọng. Mọi cấu trúc trong phần này thực chất đều là một invariant cộng với bộ máy giữ cho nó luôn đúng. Một khi đã nắm được invariant, bạn thường có thể tự suy lại ra code.

Abstract data type và implementation

Abstract data type (ADT) mô tả một cấu trúc làm cái gì — các thao tác của nó và ý nghĩa của chúng — mà không nói bằng cách nào. Implementation là một cấu trúc cụ thể cung cấp các thao tác đó. Sự phân biệt này quan trọng vì một ADT thường có nhiều implementation với hiệu năng khác nhau rất xa:

ADT	Hứa hẹn điều gì	Implementation phổ biến	Đánh đổi
List	Dãy có thứ tự, truy cập theo vị trí	Dynamic array, doubly linked list	Array: index O(1), chèn giữa O(n). List: index O(n), chèn O(1) nếu đã có node
Stack	LIFO: push, pop, peek	Dynamic array, linked list	Array nhanh hơn (cache); list không bao giờ phải resize
Queue	FIFO: enqueue, dequeue	Circular buffer, linked list, hai stack	Circular buffer là O(1) và thân thiện cache nhưng dung lượng cố định
Map / Dictionary	Tra cứu key → value	Hash table, balanced BST, skip list	Hash: O(1) trung bình, không có thứ tự. BST: O(log n) worst case, nhưng duyệt sorted và range query được
Set	Kiểm tra thành viên	Hash set, tree set, bitset	Đánh đổi giống Map; dùng bitset nếu key là số nguyên nhỏ và dày
Priority Queue	Lấy/xóa phần tử cực trị	Binary heap, pairing heap, sorted array	Heap: insert và extract O(log n), peek O(1)
Graph	Đỉnh và cạnh	Adjacency list, adjacency matrix	List: bộ nhớ O(V + E). Matrix: bộ nhớ O(V²) nhưng kiểm tra cạnh O(1)

Lợi ích thực tế: viết thuật toán dựa trên ADT thì sau này bạn có thể thay implementation mà không phải viết lại thuật toán. Một routine tìm đường đi ngắn nhất chỉ gọi push, pop_min và neighbours sẽ chạy với bất kỳ priority queue nào và bất kỳ cách biểu diễn graph nào. Đây chính là nguyên lý abstraction từ ./01-programming-fundamentals-and-pseudocode.md, được áp dụng.

# Một ADT (Stack), hai implementation, interface giống hệt nhau.

class ArrayStack:
    """Stack dựa trên dynamic array. Thân thiện cache, push amortized O(1)."""
    def __init__(self):
        self._items = []

    def push(self, x):
        self._items.append(x)          # amortized O(1); O(n) ở bước resize

    def pop(self):
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()       # O(1) — xóa ở cuối

    def peek(self):
        return self._items[-1]

    def __len__(self):
        return len(self._items)


class LinkedStack:
    """Stack dựa trên singly linked list. Push O(1) thật sự, không bao giờ resize,
    nhưng mỗi node là một lần cấp phát heap riêng."""
    class _Node:
        __slots__ = ("value", "next")
        def __init__(self, value, next):
            self.value = value
            self.next = next

    def __init__(self):
        self._head = None
        self._size = 0

    def push(self, x):
        self._head = self._Node(x, self._head)   # O(1), luôn luôn
        self._size += 1

    def pop(self):
        if self._head is None:
            raise IndexError("pop from empty stack")
        node = self._head
        self._head = node.next
        self._size -= 1
        return node.value

    def peek(self):
        return self._head.value

    def __len__(self):
        return self._size


def check_balanced(text, stack):
    """Chạy được với cả hai implementation — nó chỉ dùng ADT."""
    pairs = {")": "(", "]": "[", "}": "{"}
    for ch in text:
        if ch in "([{":
            stack.push(ch)
        elif ch in pairs:
            if len(stack) == 0 or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0


assert check_balanced("([]{})", ArrayStack()) is True
assert check_balanced("([)]", LinkedStack()) is False

Hai cách bố trí memory nền tảng

Gần như mọi cấu trúc đều được xây trên một trong hai cách sắp xếp memory, và hầu hết khác biệt hiệu năng giữa chúng đều truy ngược về lựa chọn này.

Liền kề (contiguous) — một khối memory duy nhất, các phần tử nằm ở những offset cố định. Địa chỉ của phần tử i là base + i * item_size, tính được bằng một phép nhân và một phép cộng, nên indexing là O(1). Vì các phần tử nằm sát nhau, một lần nạp cache line kéo về được vài phần tử cùng lúc, khiến việc duyệt tuần tự cực nhanh trong thực tế — thường nhanh gấp 5–10 lần so với cùng số lần truy cập rải rác, dù cả hai đều là O(n) dưới mô hình RAM.

Liên kết (linked) — các phần tử là những lần cấp phát riêng biệt, mỗi phần tử giữ một pointer trỏ tới phần tử kế tiếp. Không có phép tính số học nào tìm ra phần tử i; bạn phải đi bộ từ head, nên indexing là O(n). Nhưng chèn giữa hai node chỉ là hai lần ghi pointer — không dời dữ liệu, không cấp phát lại — nên nó là O(1) khi bạn đã nắm sẵn tham chiếu tới vị trí đó.

Liền kề (array):  một lần cấp phát, chỉ số tính được
  index:      0     1     2     3     4
            +-----+-----+-----+-----+-----+
            |  10 |  20 |  30 |  40 |  50 |
            +-----+-----+-----+-----+-----+
  address:  1000  1008  1016  1024  1032        addr(i) = 1000 + 8*i

Liên kết (singly linked list): nhiều lần cấp phát, nằm rải rác
  head
   |
   v
 +------+----+     +------+----+     +------+----+
 |  10  | *--|---->|  20  | *--|---->|  30  | \  |
 +------+----+     +------+----+     +------+----+
  @0x7f2a            @0x91c4           @0x4e08     (không tính được địa chỉ)

Mọi thứ còn lại đều là biến thể hoặc tổ hợp của hai cái này. Hash table là một array liền kề gồm các bucket, mà mỗi bucket có thể là một chuỗi liên kết. B-tree là một cây gồm các node liền kề, có kích thước khớp một page trên đĩa. deque là một linked list gồm các block liền kề. Biết một cấu trúc thuộc về nửa nào của sơ đồ trên là bạn đã đoán được phần lớn bảng complexity của nó trước khi đọc.

Vì sao data structures quan trọng — đo đạc chứ không khẳng định suông

Roadmap nói data structures “tăng hiệu năng” và “giảm độ phức tạp của code”. Cả hai đều đúng, nhưng ý thứ hai bị đánh giá thấp. Đây là cùng một nhiệm vụ được viết hai lần:

# Nhiệm vụ: từ một luồng event, báo cáo ID event đầu tiên bị lặp lại.

# Phiên bản 1 — dùng list làm tập "đã thấy". Đúng, và là bậc hai.
def first_repeat_list(events):
    seen = []
    for e in events:
        if e in seen:          # quét tuyến tính O(len(seen)) ở mọi vòng lặp
            return e
        seen.append(e)
    return None                # tổng cộng: O(n^2)

# Phiên bản 2 — dùng set làm tập "đã thấy". Cùng hình dạng, nhưng tuyến tính.
def first_repeat_set(events):
    seen = set()
    for e in events:
        if e in seen:          # O(1) trung bình — một lần hash, một lần chạm bucket
            return e
        seen.add(e)
    return None                # tổng cộng: O(n)

Hai function dài bằng nhau và dễ đọc như nhau. Với n = 100_000 event phân biệt, cái đầu tốn hàng chục giây còn cái sau tốn vài phần trăm giây. Bài học ở đây là quyết định về hiệu năng được đưa ra bởi đúng một từ — [] so với set() — và không có lượng vi tối ưu nào bên trong thân vòng lặp có thể lấy lại được khoảng chênh đó. Chọn cấu trúc chính là việc tối ưu; phần còn lại là nhiễu.

Ý về sự đơn giản của code cũng là thật. Thử viết “tìm k phần tử nhỏ nhất của một luồng” mà không có heap, hoặc “kiểm tra xem thêm cạnh này có tạo ra chu trình không” mà không có disjoint set. Làm được, nhưng code dài gấp ba và mọc thêm vài bug lệch một đơn vị. Cấu trúc đúng không chỉ chạy nhanh hơn; nó làm cho thuật toán đúng trở nên hiển nhiên.

Khái niệm chính

Phân loại

Vài trục phân loại đáng gọi tên vì chúng xuất hiện liên tục:

• Tuyến tính vs phi tuyến. Cấu trúc tuyến tính sắp xếp phần tử thành một dãy, mỗi phần tử có một phần tử trước và một phần tử sau: array, linked list, stack, queue. Cấu trúc phi tuyến cho phép quan hệ phân nhánh: tree (phân cấp), graph (mạng lưới tùy ý), heap.
• Tĩnh vs động. Cấu trúc tĩnh có kích thước cố định quyết định lúc tạo (array trong C, ring buffer dung lượng cố định). Cấu trúc động co giãn lúc chạy (list của Python, linked list, phần lớn các loại cây). Động thì tiện hơn; tĩnh thì dễ dự đoán hơn và thường nhanh hơn vì không có bước resize.
• Liền kề vs liên kết — sự phân đôi về memory layout ở trên.
• Có thứ tự vs không thứ tự. Việc duyệt có cho ra một thứ tự có ý nghĩa không? Hash table cho bạn lookup O(1) nhưng không có thứ tự; balanced BST tốn O(log n) nhưng tặng kèm duyệt sorted và range query. Đây là lý do phổ biến nhất để trả giá dùng tree thay vì hash table.
• Đồng nhất vs không đồng nhất. Các phần tử có bắt buộc cùng kiểu không? Chủ yếu là chuyện của ngôn ngữ — array trong C là đồng nhất, list trong Python thì không — nhưng nó có hệ quả memory thật: một array đồng nhất gồm số nguyên 64-bit là một khối byte đặc, trong khi list Python chứa số nguyên lại là một array các pointer trỏ tới những object được cấp phát riêng lẻ, và đó là lý do numpy tồn tại.

Các data structure cơ bản

Năm cái này là vốn từ vựng. Mọi thứ phức tạp hơn đều được xây từ chúng.

Array (./04-arrays.md) — một khối liền kề chứa các phần tử cùng kiểu, định vị bằng chỉ số nguyên. Truy cập ngẫu nhiên trong thời gian hằng số là điểm mạnh định danh của nó; cái giá là chèn hoặc xóa ở bất kỳ đâu ngoài vị trí cuối đều phải dời phần đuôi. Dynamic array (list của Python, vector của C++, slice của Go) bổ sung khả năng tự lớn lên bằng cách cấp phát lại sang khối lớn hơn, thao tác này là O(n) ở bước resize nhưng amortized O(1) cho mỗi lần append vì mỗi lần resize đều nhân đôi dung lượng nên rất hiếm khi xảy ra.

Linked list (./05-linked-lists.md) — các node nằm rải rác trong memory, mỗi node giữ một giá trị và một pointer trỏ tới node kế tiếp (và trỏ tới node trước nữa, trong doubly linked list). Chèn và xóa ở một vị trí đã biết là O(1) mà không phải dời gì. Cái giá là có thật và thường bị xem nhẹ: không truy cập ngẫu nhiên được, mỗi phần tử tốn thêm một lần cấp phát và một pointer, và hành vi cache rất tệ. Trong thực tế, dynamic array thắng linked list ở phần lớn workload; linked list chỉ thắng khi bạn phải nối/cắt liên tục tại những vị trí đã nắm sẵn, hoặc khi bạn cần tham chiếu ổn định tới phần tử qua các lần thay đổi.

Stack (./06-stacks-and-queues.md) — LIFO (vào sau, ra trước). Chỉ phần tử mới nhất là chạm tới được. Instance quan trọng nhất của nó lại không phải cái bạn viết ra: đó là call stack mà mỗi lời gọi function đẩy một frame lên, và đó là lý do đệ quy không có điểm dừng sinh ra stack overflow. Stack cũng là động cơ của việc tính biểu thức, backtracking (./21-backtracking.md), DFS phiên bản lặp, và lịch sử undo.

Queue (./06-stacks-and-queues.md) — FIFO (vào trước, ra trước). Phần tử rời đi theo thứ tự đến. Queue mô hình hóa mọi thứ phải xếp hàng: lập lịch tác vụ, đệm request, hàng đợi in ấn, breadth-first search. Cài đặt đúng thì nó là một circular buffer trên array; cài đặt sai thì nó là một list Python với pop(0), tốn O(n) mỗi lần dequeue và âm thầm biến thuật toán tuyến tính thành bậc hai. Hãy dùng collections.deque.

Hash table (./07-hash-tables.md) — lưu các cặp key-value trong một array các bucket, dùng hash function để biến key thành chỉ số bucket. Insert, delete và lookup O(1) ở average case khiến nó là cấu trúc hữu dụng phổ quát nhất từng tồn tại, và là câu trả lời mặc định cho “tôi cần tra cứu theo tên”. Các lưu ý: worst case tụt xuống O(n) khi nhiều key va chạm, nó ngốn nhiều memory hơn bản thân dữ liệu (bảng được cố tình để trống một phần), và nó không cho bạn thứ tự nào cả.

Cấu trúc	Truy cập theo chỉ số	Search	Insert	Delete	Bộ nhớ	Worst case có khác?
Static array	O(1)	O(n), O(log n) nếu đã sorted	không có (cố định)	không có	O(n)	không
Dynamic array	O(1)	O(n)	O(1) amortized ở cuối, O(n) ở chỗ khác	O(n) (O(1) ở cuối)	O(n)	có — một lần append là O(n) khi nó kích hoạt resize
Singly linked list	O(n)	O(n)	O(1) ở head hoặc tại node đã nắm	O(1) tại node đã nắm, ngược lại O(n)	O(n) + 1 pointer/phần tử	không
Doubly linked list	O(n)	O(n)	O(1) tại node đã nắm	O(1) tại node đã nắm	O(n) + 2 pointer/phần tử	không
Stack	không có	O(n)	O(1) push	O(1) pop	O(n)	dựa trên array: O(n) khi resize
Queue (circular buffer)	không có	O(n)	O(1) enqueue	O(1) dequeue	O(n)	dựa trên array: O(n) khi resize
Hash table	không có	O(1) trung bình	O(1) trung bình	O(1) trung bình	O(n) (có phần dư)	có — O(n) nếu mọi key đều va chạm

Các data structure phức tạp

Nhóm này giải quyết những bài toán mà năm cấu trúc cơ bản không kham nổi, nhìn chung bằng cách áp đặt thêm cấu trúc và trả giá lúc sửa đổi.

Tree (./10-tree-data-structures.md) — một hệ phân cấp: một root, mỗi node có không hoặc nhiều con, không có chu trình. Tree mô hình hóa mọi thứ lồng nhau — file system, DOM document, sơ đồ tổ chức, cú pháp đã parse. Binary search tree bổ sung một invariant về thứ tự (mọi thứ bên trái nhỏ hơn, mọi thứ bên phải lớn hơn) khiến search, insert và delete là O(h) với h là chiều cao.

Balanced tree (./11-balanced-and-multiway-trees.md) — vấn đề của BST thường là h có thể suy biến thành n: đổ dữ liệu đã sorted vào và bạn nhận được một linked list khoác áo cây, với thao tác O(n). AVL tree, red-black tree và B-tree bổ sung cơ chế cân bằng lại để đảm bảo h = O(log n). Riêng B-tree dùng node rộng, cỡ đúng bằng một page trên đĩa, và đó chính xác là lý do nó là cấu trúc đứng sau gần như mọi index của database — xem ../../postgresql-dba/vi/08-indexing-strategies.md.

Heap (./12-heaps-and-priority-queues.md) — một cây nhị phân với invariant yếu hơn BST: mọi node cha đều ≤ (hoặc ≥) các con của nó, không có ràng buộc thứ tự giữa các anh em. Chính sự yếu ớt đó là điểm mấu chốt — nó rẻ đến mức duy trì được insert và extract-min trong O(log n) còn peek-min là O(1), và toàn bộ cây có thể nhồi vào một array liền kề mà không cần pointer nào. Nó là implementation tiêu chuẩn của priority queue và là động cơ bên trong Dijkstra, A*, heapsort và k-way merge.

Graph (./13-graph-data-structures.md) — các đỉnh nối với nhau bằng cạnh, không ràng buộc hình dạng: cho phép chu trình, cho phép nhiều đường đi, cho phép các mảnh rời rạc. Tree là trường hợp đặc biệt của một graph liên thông không có chu trình. Graph mô hình hóa mọi loại mạng lưới — đường sá, quan hệ xã hội, phụ thuộc package, máy trạng thái — và mang theo họ thuật toán phong phú nhất trong roadmap này (./14-shortest-path-algorithms.md, ./15-minimum-spanning-trees.md).

Trie (./17-advanced-tree-structures.md) — một cây được đánh key theo tiền tố chuỗi, trong đó đường đi từ root ghép lại thành key. Lookup tốn O(m) theo độ dài key thay vì O(log n) theo số lượng key, và truy vấn theo tiền tố (“mọi từ bắt đầu bằng pre”) thì miễn phí. Đây là thứ đứng sau autocomplete và bảng định tuyến IP.

Disjoint set / union-find (./16-disjoint-set-union-find.md) — theo dõi một phân hoạch các phần tử thành các nhóm và trả lời “hai phần tử này có cùng nhóm không?” trong thời gian gần như hằng số. Interface nhỏ, đòn bẩy khổng lồ: nó là thứ khiến thuật toán MST Kruskal và bài toán connectivity động trở nên khả thi.

Cấu trúc	Search	Insert	Delete	Bảo đảm thêm	Bộ nhớ
BST (cân bằng)	O(log n)	O(log n)	O(log n)	duyệt sorted, range query, predecessor/successor	O(n)
BST (mất cân bằng, worst)	O(n)	O(n)	O(n)	vẫn có, nhưng không đảm bảo thời gian	O(n)
B-tree (bậc b)	O(log_b n)	O(log_b n)	O(log_b n)	ít lần đọc đĩa — node khớp một page	O(n)
Binary heap	O(n) (key bất kỳ)	O(log n)	O(log n) extract-min	peek-min O(1), build từ array O(n)	O(n), không pointer
Trie (bảng chữ cái cỡ s, key dài m)	O(m)	O(m)	O(m)	tìm theo tiền tố, thứ tự từ điển	O(n · m · s) worst
Graph — adjacency list	O(deg v) kiểm tra cạnh	O(1) thêm cạnh	O(deg v)	duyệt hàng xóm hiệu quả	O(V + E)
Graph — adjacency matrix	O(1) kiểm tra cạnh	O(1)	O(1)	graph dày, thuật toán ma trận	O(V²)
Disjoint set	O(α(n)) find	O(α(n)) union	không có	α(n) ≤ 4 với mọi n thực tế	O(n)

Chọn cấu trúc: bắt đầu từ các thao tác

Phương pháp đáng tin cậy không phải là học thuộc các bảng trên, mà là viết ra những thao tác mà workload của bạn thật sự thực hiện, kèm tần suất ước lượng, rồi đọc bảng để tìm cấu trúc làm cho các thao tác thường xuyên trở nên rẻ.

Bạn cần gì	Dùng gì	Vì sao
Truy cập theo chỉ số vào dãy kích thước cố định, duyệt nhiều	Array	truy cập O(1), hành vi cache tốt nhất
Tra cứu theo key, không quan tâm thứ tự	Hash table	O(1) trung bình
Tra cứu theo key và duyệt theo thứ tự sắp xếp, hoặc range query	Balanced BST / skip list	hash table không làm được range
Liên tục lấy phần tử nhỏ nhất/lớn nhất, xen kẽ với insert	Heap	peek O(1), cập nhật O(log n)
Thêm/xóa ở cả hai đầu	Deque (collections.deque)	O(1) cả hai đầu
Xử lý theo thứ tự đến	Queue	FIFO
Undo, backtracking, lồng nhau	Stack	LIFO
So khớp tiền tố trên chuỗi	Trie	O(m), tiền tố là bản chất
Thành viên nhóm / tính liên thông	Disjoint set	union và find gần như hằng số
Quan hệ giữa các thực thể	Graph	mọi thứ khác đều là trường hợp đặc biệt

Hai quy tắc kinh nghiệm tiết kiệm thời gian. Thứ nhất, nếu dữ liệu vừa memory và bạn không có yêu cầu về thứ tự, hãy thử hash table trước — nó đúng một cách đáng ngạc nhiên, và cũng là thứ rẻ nhất để thay đổi về sau. Thứ hai, nếu dữ liệu không vừa memory thì câu trả lời thường là B-tree hoặc LSM tree, vì mô hình chi phí đổi từ “số phép toán CPU” sang “số lần đọc đĩa”, và những cấu trúc có node cao và mảnh sẽ thua đậm (../../backend/vi/10-database-design-and-scaling.md).

Đây không phải chuyện hàn lâm — đây là thứ tạo nên công cụ bạn đang dùng

Mọi cấu trúc trong phần này đều đang chịu lực trong phần mềm bạn dùng hằng ngày:

Ở đâu	Cấu trúc	Mục đích
Database index	B-tree / B+ tree	lookup O(log n) với ít lần đọc đĩa (../../postgresql-dba/vi/08-indexing-strategies.md)
Redis / Memcached	Hash table (+ skip list cho sorted set)	tra key O(1) (../../backend/vi/11-caching.md)
LRU cache	Hash table + doubly linked list	lookup O(1) và cập nhật độ mới O(1)
Thư mục trong filesystem	B-tree, hash table	phân giải tên nhanh
Git	DAG các commit, Merkle tree các object	lịch sử và địa chỉ hóa theo nội dung
Compiler	AST (tree), symbol table (hash), CFG (graph)	parsing, xác định scope, tối ưu
OS scheduler	Heap hoặc red-black tree các task đang chờ chạy	chọn task kế tiếp theo độ ưu tiên
Router mạng	Trie trên các tiền tố IP	longest-prefix match ở tốc độ đường truyền
Kiểm tra chính tả, autocomplete	Trie, DAWG	tìm theo tiền tố và tìm mờ
Undo trong editor	Stack (hoặc hai stack nếu có redo)	lịch sử LIFO

Các built-in của Python thực chất là gì

Python giấu implementation sau những cái tên thân thiện, và sự lệch pha đó gây ra lỗi complexity thật sự. Hãy nắm bảng ánh xạ:

Kiểu Python	Cấu trúc thật sự	Cần cẩn thận
list	Dynamic array chứa pointer	insert(0, x) và pop(0) là O(n); in là O(n)
dict	Hash table open addressing, giữ thứ tự chèn từ 3.7	worst case O(n); key phải hashable
set / frozenset	Hash table không có phần value	các lưu ý giống dict
tuple	Array kích thước cố định	bất biến nên hashable — dùng làm key của dict được
collections.deque	Doubly linked list gồm các block cố định	O(1) ở cả hai đầu; truy cập giữa là O(n)
heapq (trên một list)	Binary min-heap trong array	không có max-heap sẵn — hãy đảo dấu key
bisect (trên list đã sorted)	Binary search	search là O(log n) nhưng insort chèn vẫn O(n)
str	Array bất biến các code point	dựng chuỗi bằng += trong vòng lặp là O(n²); dùng "".join()

Standard library không có sẵn balanced tree, linked list, trie hay graph. sortedcontainers là câu trả lời bên thứ ba thường dùng cho ordered map.

Best Practices

• Chọn cấu trúc từ hồ sơ thao tác, không phải từ thói quen. Viết ra những thao tác nào chạy trong vòng lặp nóng và chạy bao nhiêu lần, rồi mới chọn. Câu hỏi “cấu trúc nào tốt nhất?” không có đáp án; câu hỏi “cấu trúc nào làm ba thao tác này rẻ?” thì luôn có.
• Ghi invariant vào docstring của class. Mọi cấu trúc đều là một invariant cộng với code duy trì nó. Viết nó ra sẽ bắt được bug ngay lúc bạn đang viết các method và ghi lại ý đồ tốt hơn nhiều so với mô tả các field.
• Lập trình dựa trên ADT, không dựa trên implementation. Hãy phụ thuộc vào push/pop/neighbours, đừng phụ thuộc vào việc nó tình cờ là một list. Khi đó, đổi linked list sang array, hay đổi adjacency matrix sang list, chỉ là sửa một dòng.
• Dùng standard library trong production; tự viết từ đầu một lần, để học. Tự cài hash table dạy bạn về hash table. Đưa bản tự viết lên production thay cho dict là đưa bug lên production. Nhưng phải biết built-in tốn bao nhiêu — toàn bộ mục đích của việc học cơ chế là để dự đoán được cái giá.
• Cảnh giác với các thao tác tuyến tính ẩn. list.pop(0), x in some_list, del arr[0], += chuỗi trong vòng lặp, và list.insert(0, x) đều trông như hằng số nhưng không phải. Chỉ cần một trong số đó nằm trong vòng lặp là bạn đã có nguyên nhân phổ biến nhất của một chương trình vô tình bậc hai.
• Đừng vội với tới cấu trúc phức tạp khi cấu trúc đơn giản chưa chậm một cách đo được. Với n = 50, quét tuyến tính một array thắng hash table — ít lệnh hơn, không phải hash, hành vi cache hoàn hảo. Lớp complexity mô tả tốc độ tăng trưởng, không mô tả tốc độ trên input nhỏ (./03-algorithmic-complexity.md).
• Tính cả memory, không chỉ thời gian. Một adjacency matrix cho 100 000 đỉnh cần 10¹⁰ ô và sẽ không vừa vào đâu cả. Một hash table chứa n phần tử thường chiếm gấp 2–3 lần dữ liệu thô. Bộ nhớ là ràng buộc thật mà các bảng complexity hay khiến bạn quên mất.
• Khi thứ tự có thể trở nên quan trọng về sau, hãy ưu tiên tree. Gắn thêm range query vào hash table đồng nghĩa với thay luôn cấu trúc. Trả O(log n) thay vì O(1) ngay từ đầu thường rẻ hơn cuộc viết lại đó.

Tài liệu tham khảo

• roadmap.sh — Data Structures & Algorithms
• Data structure — Wikipedia
• Abstract data type — Wikipedia
• Big-O Cheat Sheet — common data structure operations
• VisuAlgo — visualising data structures and algorithms
• CLRS — Introduction to Algorithms, Part III: Data Structures
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• Python Documentation — Data Structures tutorial
• Python Documentation — collections module
• Python Wiki — TimeComplexity of built-in types

# One ADT (Stack), two implementations, identical interface.

class ArrayStack:
    """Stack backed by a dynamic array. Cache-friendly, amortized O(1) push."""
    def __init__(self):
        self._items = []

    def push(self, x):
        self._items.append(x)          # amortized O(1); O(n) on the resize step

    def pop(self):
        if not self._items:
            raise IndexError("pop from empty stack")
        return self._items.pop()       # O(1) — removes from the end

    def peek(self):
        return self._items[-1]

    def __len__(self):
        return len(self._items)


class LinkedStack:
    """Stack backed by a singly linked list. True O(1) push, never resizes,
    but every node is a separate heap allocation."""
    class _Node:
        __slots__ = ("value", "next")
        def __init__(self, value, next):
            self.value = value
            self.next = next

    def __init__(self):
        self._head = None
        self._size = 0

    def push(self, x):
        self._head = self._Node(x, self._head)   # O(1), always
        self._size += 1

    def pop(self):
        if self._head is None:
            raise IndexError("pop from empty stack")
        node = self._head
        self._head = node.next
        self._size -= 1
        return node.value

    def peek(self):
        return self._head.value

    def __len__(self):
        return self._size


def check_balanced(text, stack):
    """Works with either implementation — it only uses the ADT."""
    pairs = {")": "(", "]": "[", "}": "{"}
    for ch in text:
        if ch in "([{":
            stack.push(ch)
        elif ch in pairs:
            if len(stack) == 0 or stack.pop() != pairs[ch]:
                return False
    return len(stack) == 0


assert check_balanced("([]{})", ArrayStack()) is True
assert check_balanced("([)]", LinkedStack()) is False

Contiguous (array):  one allocation, indices computable
  index:      0     1     2     3     4
            +-----+-----+-----+-----+-----+
            |  10 |  20 |  30 |  40 |  50 |
            +-----+-----+-----+-----+-----+
  address:  1000  1008  1016  1024  1032        addr(i) = 1000 + 8*i

Linked (singly linked list): many allocations, scattered
  head
   |
   v
 +------+----+     +------+----+     +------+----+
 |  10  | *--|---->|  20  | *--|---->|  30  | \  |
 +------+----+     +------+----+     +------+----+
  @0x7f2a            @0x91c4           @0x4e08     (no address arithmetic possible)

# Task: from a stream of events, report the first event ID that repeats.

# Version 1 — list as a "seen" collection. Correct, and quadratic.
def first_repeat_list(events):
    seen = []
    for e in events:
        if e in seen:          # O(len(seen)) linear scan on every iteration
            return e
        seen.append(e)
    return None                # total: O(n^2)

# Version 2 — set as a "seen" collection. Same shape, linear.
def first_repeat_set(events):
    seen = set()
    for e in events:
        if e in seen:          # O(1) average — one hash, one probe
            return e
        seen.add(e)
    return None                # total: O(n)