Mục lục
Sự khác biệt lớn nhất của mảng với danh sách liên kết chính là cấu trúc của chúng. Mảng là cấu trúc dữ liệu dựa trên các chỉ mục, mỗi phần tử trong mảng đều có mối liên kết với một chỉ mục. Mặc khác, danh sách liên kết lại dựa trên sự tham chiếu(references) mỗi node chứa 2 thành phần chính là data và con trỏ trỏ đến phần tử tiếp theo.
Bảng so sánh
| Thuộc tính so sánh | Mảng | Danh sách liên kết |
| Cấu trúc | Tập hợp cố định số lượng dữ liệu. | Tập hợp không cố định số lượng phần tử. |
| Số lượng |
Được chỉ định lúc khởi tạo. Độ lớn của mảng không tự động co giãn theo số lượng phần tử. |
Không cần chỉ định số lượng phần tử. Độ lớn của danh sách liên kết tự động co giãn theo số lượng phần tử. |
| Phân bổ lưu trữ |
Vị trí lưu của các phần tử được quyết định trong quá trình compile time. |
Vị trí lưu các phần tử được quyết định trong quá trình run time. |
|
Thứ tự lưu trữ |
Được lưu trữ liên tiếp. |
Được lưu trữ random. |
|
Truy cập |
Có thể truy cập trực tiếp hoặc ngẫu nhiên dựa vào chỉ mục. |
Truy cập tuần tự. |
|
Thêm xoá |
Chậm, phải dịch chuyển các phần tử để phủ lấp phần tử được thêm, xoá. |
Nhanh, có thể xoá trực tiếp phần tử cần xoá mà không cần dịch chuyển các phần tử khác. Nhưng phải tốn thời gian duyệt tuần tự đến phần tử cần thêm, xoá. |
|
Tìm kiếm |
Có thể áp dụng linear search hoặc binary search | Chỉ có thể áp dụng linear search. |
|
Sử dụng menory |
Không hiệu quả | Hiệu quả |
Kết luận
Mảng và danh sách liên kết đều là những cấu trúc dự liệu thường được dùng trong các chương trình. Tuy nhiên chúng có đều có những thế mạnh và hạn chế của chúng trong từng trường hợp cụ thể. Chúng ta cần phải nắm bắt vấn đề của mình mà sử dụng đúng cấu trúc dữ liệu.