Cấu trúc dữ liệu: Array & Linked List

🎯 Bộ nhớ máy tính tổ chức thế nào?

Array và Linked List là hai cách tổ chức bộ nhớ cơ bản nhất. Mọi CTDL phức tạp hơn (Stack, Queue, Graph...) đều xây dựng trên 2 thằng này.

1. Array (Mảng) - "Nhà Liền Kề"

Các phần tử nằm sát nhau trong RAM. Địa chỉ ô nhớ liên tiếp (0x01, 0x02, 0x03...).

Thao tác	Độ phức tạp	Giải thích
Truy cập (Read)	O(1) - Siêu nhanh	Vì máy tính tính được ngay địa chỉ: Addr = Start + Index * Size. A[1000] mất đúng 1 tích tắc.
Chèn/Xóa (Insert/Delete)	O(N) - Chậm	Nếu bạn chèn 1 số vào đầu mảng, bạn phải dịch chuyển (Shift) toàn bộ N phần tử phía sau lùi lại 1 bước. Rất tốn công.

Nhược điểm chí mạng: Kích thước cố định (Static). Khai báo mảng 100 phần tử thì chỉ dùng được 100. Muốn thêm phải tạo mảng mới to hơn rồi copy sang.

2. Linked List (Danh sách liên kết) - "Trò chơi tìm kho báu"

Các phần tử nằm rải rác khắp nơi trong RAM. Mỗi phần tử (Node) cầm một mảnh giấy (Pointer) ghi địa chỉ của thằng tiếp theo.

Thao tác	Độ phức tạp	Giải thích
Truy cập (Read)	O(N) - Chậm	Muốn tìm phần tử thứ 100, bạn phải đi từ Head, hỏi thằng 1, thằng 1 chỉ thằng 2... cứ thế lần mò đến thằng 100.
Chèn/Xóa (Insert/Delete)	O(1) - Siêu nhanh	Muốn chèn B vào giữa A và C? Chỉ cần bảo A trỏ vào B, B trỏ vào C. Không cần dịch chuyển ai cả. (Giả sử bạn đã đứng ở vị trí A).

Ưu điểm: Kích thước động (Dynamic). Thích thêm bao nhiêu cũng được miễn là còn RAM.