1. Array (Mảng)
- Là gì: Tập hợp các phần tử nằm liên tiếp nhau trong bộ nhớ, cùng kiểu dữ liệu.
- Truy cập: Dựa vào chỉ số (index), rất nhanh (O(1)).
- Nhược điểm: Kích thước cố định, khó thêm/xóa giữa mảng.
- Ứng dụng:
- Lưu danh sách sản phẩm, điểm số, chuỗi ký tự.
- Là nền tảng của các cấu trúc khác như Stack, Queue.
Ví dụ: int[] arr = {1, 2, 3, 4} → arr[0] là 1
2. Linked List (Danh sách liên kết)
- Là gì: Gồm các phần tử (node), mỗi node chứa dữ liệu + con trỏ đến node kế tiếp.
- Ưu điểm: Thêm/xóa linh hoạt, không cần dịch chuyển phần tử.
- Nhược điểm: Truy cập chậm (O(n)), không truy cập trực tiếp được như mảng.
- Ứng dụng:
- Tạo Stack, Queue
- Undo/Redo (mỗi bước là 1 node)
- Danh sách playlist nhạc
Ví dụ: 1 → 2 → 3 → 4 → null
3. Stack (Ngăn xếp – LIFO)
- Là gì: Cấu trúc vào sau ra trước (Last In – First Out).
- Chỉ thao tác trên đỉnh (top): push (thêm), pop (lấy ra).
- Ứng dụng:
- Quay lui (backtracking)
- Undo thao tác (word, photoshop)
- Duyệt cây đệ quy
Ví dụ:
- Đặt đĩa chồng lên nhau: Lấy ra phải lấy từ trên xuống
- Code:
push(1), push(2), pop()→ ra 2
4. Queue (Hàng đợi – FIFO)
- Là gì: Cấu trúc vào trước ra trước (First In – First Out).
- Có hai đầu: enqueue (thêm vào cuối), dequeue (lấy từ đầu).
- Ứng dụng:
- Xử lý yêu cầu: hàng chờ in, gọi điện
- Hệ điều hành: lập lịch CPU
- BFS (duyệt đồ thị theo chiều rộng)
- Ví dụ:
- Xếp hàng mua vé: người đến trước được phục vụ trước
- Hệ thống xử lý yêu cầu (server, in ấn)
- BFS trong thuật toán tìm đường
5. Hash Table / Hash Map
- Là gì: Lưu trữ dữ liệu dưới dạng (key, value) với key được mã hóa thành hash
- Ưu điểm: Tìm kiếm/truy cập cực nhanh (~O(1))
- Nhược điểm: Dễ xung đột hash nếu không xử lý tốt
- Ứng dụng:
- Từ điển
- Cache dữ liệu (như Redis)
- Đếm tần suất xuất hiện (đếm từ, ký tự)
- Ví dụ:
- Từ điển:
"cat" → "con mèo" hashMap.put("id123", "Nguyễn Văn A")- Tra cứu dữ liệu (từ điển, danh bạ)
- Đếm số lần xuất hiện
- Caching (Redis dùng dạng này)
6. Binary Tree (Cây nhị phân)
- Là gì: Cấu trúc dạng cây, mỗi node có tối đa 2 con (trái & phải)
- Ứng dụng:
- Cây tìm kiếm nhị phân (Binary Search Tree – BST)
- Lưu trữ phân cấp như thư mục
- Cây biểu thức toán học
- Tìm kiếm/log tìm kiếm nhanh hơn danh sách
- Cây biểu thức toán học
- Tổ chức dữ liệu dạng phân cấp
- Tìm kiếm nhanh (cây tìm kiếm nhị phân – BST)
7. Heap (Đống)
- Là gì: Cây nhị phân đặc biệt:
- Ứng dụng:
- Hàng đợi ưu tiên (Priority Queue)
- Thuật toán Dijkstra
- Heap Sort
- Lấy k phần tử lớn/nhỏ nhất
- Ví dụ:
- Hàng đợi bệnh viện: người ưu tiên cao được xử lý trước dù đến sau
- Hàng đợi ưu tiên (Priority Queue)
- Thuật toán tìm K phần tử lớn nhất/nhỏ nhất
- Dùng trong
heap sort
8. Graph (Đồ thị)
- Là gì: Gồm tập đỉnh (node) và tập cạnh (edge) biểu diễn mối quan hệ giữa các đỉnh
- Có thể là: có hướng / vô hướng, có trọng số / không trọng số
- Ứng dụng:
- Mạng xã hội (user kết nối user)
- Google Maps (đường đi giữa điểm A-B)
- Gợi ý kết bạn, sản phẩm
- Ví dụ:
- User A kết bạn với B và C → graph có 3 node, 2 cạnh nối A-B và A-C
- Mạng xã hội
- Hệ thống giao thông
- Tìm đường (Google Maps)
- Gợi ý kết bạn (Facebook)
Tóm tắt nhanh:
| Cấu trúc | Dùng khi nào? | Ứng dụng thực tế |
|---|---|---|
| Array | Truy cập nhanh, dữ liệu cố định | Danh sách sản phẩm |
| Linked List | Dữ liệu thay đổi linh hoạt | Undo/Redo |
| Stack | Quay lui, xử lý lùi | Undo, duyệt đệ quy |
| Queue | Xử lý theo lượt | Lập lịch in, xử lý task |
| Hash Map | Tìm kiếm cực nhanh | Từ điển, đếm từ, cache |
| Binary Tree | Tìm kiếm nhanh, tổ chức phân cấp | Cây thư mục, phân loại |
| Heap | Ưu tiên xử lý | Priority Queue, top K |
| Graph | Mối quan hệ giữa các đối tượng | Mạng xã hội, định tuyến |
Be First to Comment