Data structure (cấu trúc dữ liệu) là cách tổ chức và lưu trữ dữ liệu trong bộ nhớ sao cho có thể truy cập và sửa đổi một cách hiệu quả. Abstract data type (ADT) là mô hình logic — các thao tác và hành vi của chúng — độc lập với cách nó được hiện thực.
ADT mô tả thao tác nào tồn tại; data structure quyết định chúng được lưu trữ và chạy nhanh đến đâu.
ADT: Stack → push, pop, peek (hành vi LIFO)
Implementations: → dựa trên array HOẶC dựa trên linked list
ADT: List → get(i), insert, remove
Implementations: → dynamic array HOẶC linked list
# Cả hai đều thỏa mãn ADT "Stack", nhưng có hồ sơ chi phí khác nhau
stack = [] # stack dựa trên list
stack.append(10) # push -> amortized O(1)
top = stack[-1] # peek -> O(1)
stack.pop() # pop -> O(1)
| Mối quan tâm | Câu hỏi cần đặt ra |
|---|---|
| Mẫu truy cập | Truy cập ngẫu nhiên hay tuần tự? |
| Thay đổi | Chèn/xóa ở giữa thường xuyên? |
| Thứ tự | Sắp xếp, FIFO, LIFO, hay không có? |
| Tra cứu | Theo index hay theo key? |
Lựa chọn đúng là cái mà các thao tác phổ biến của nó rẻ cho khối lượng công việc của bạn.
Chọn sai cấu trúc biến một thao tác O(1) thành O(n), điều này có thể khiến code chậm hơn hàng nghìn lần ở quy mô lớn.
Tư duy theo ADT cho phép bạn lập luận về hành vi trước, sau đó hoán đổi hiện thực về sau mà không cần viết lại bên gọi (caller).