Sự khác nhau giữa mảng và danh sách liên kết?

Mảng và danh sách liên kết đều là cấu trúc dự liệu phổ biến trong ngôn ngữ lập trình. Dưới đây là các điểm khác nhau giữa mảng và danh sách liên kết

Mảng Danh sách liên kết
Vùng nhớ của các phần tử trong mảng được sắp xếp liên tục nhau Vùng nhớ của các phần tử trong danh sách liên kết được sắp xếp tùy ý (do hệ điều hành). Các phần tử lưu 1 con trỏ trỏ tới phần tử tiếp theo.
Truy cập tới phần tử trong mảng là truy cập trực tiếp dựa vào chỉ số (ví dụ: a[0], a[1], a[2],…, a[n]) Cần phải duyệt tuần tự khi muốn truy cập tới phần tử trong danh sách liên kết.
  •  Kích thước của mảng là hằng số, không thay đổi khi chạy chương trình
  • Sử dụng mảng không tối ưu được bộ nhớ. Có thể thừa hoặc thiếu bộ nhớ khi xóa hoặc chèn phần tử vào mảng
  •  Kích thước của danh sách liên kết có thể thay đổi khi chạy chương trình.
  • Sử dụng danh sách liên kết tối ưu được bộ nhớ. Vùng nhớ được cấp phát thêm khi cần chèn thêm phần tử mới, vùng nhớ được free khi xóa phần tử.

1 Comment on Sự khác nhau giữa mảng và danh sách liên kết?

Leave a Reply