Mảng so với Danh sách được Liên kết
Mảng là cấu trúc dữ liệu được sử dụng phổ biến nhất để lưu trữ tập hợp các phần tử. Hầu hết các ngôn ngữ lập trình đều cung cấp các phương thức để dễ dàng khai báo mảng và truy cập các phần tử trong mảng. Danh sách được liên kết, chính xác hơn là danh sách được liên kết đơn lẻ, cũng là một cấu trúc dữ liệu có thể được sử dụng để lưu trữ tập hợp các phần tử. Nó được tạo thành từ một chuỗi các nút và mỗi nút có một tham chiếu đến nút tiếp theo trong chuỗi.
Được thể hiện trong hình 1, là một đoạn mã thường được sử dụng để khai báo và gán giá trị cho một mảng. Hình 2 mô tả một mảng trông như thế nào trong bộ nhớ.
Đoạn mã trên xác định một mảng có thể lưu trữ 5 số nguyên và chúng được truy cập bằng cách sử dụng các chỉ số từ 0 đến 4. Một thuộc tính quan trọng của mảng là toàn bộ mảng được cấp phát như một khối bộ nhớ duy nhất và mỗi phần tử có không gian riêng. trong mảng. Khi một mảng được xác định, kích thước của nó sẽ được cố định. Vì vậy, nếu bạn không chắc chắn về kích thước của mảng tại thời điểm biên dịch, bạn sẽ phải xác định một mảng đủ lớn để ở bên an toàn. Tuy nhiên, hầu hết thời gian chúng ta thực sự sẽ sử dụng số lượng phần tử ít hơn chúng ta đã phân bổ. Vì vậy, một lượng bộ nhớ đáng kể thực sự bị lãng phí. Mặt khác, nếu “mảng đủ lớn” không thực sự đủ lớn, chương trình sẽ bị lỗi.
Một danh sách liên kết phân bổ bộ nhớ cho các phần tử của nó một cách riêng biệt trong khối bộ nhớ riêng của nó và cấu trúc tổng thể có được bằng cách liên kết các phần tử này như các liên kết trong một chuỗi. Mỗi phần tử trong danh sách liên kết có hai trường như trong Hình 3. Trường dữ liệu chứa dữ liệu thực được lưu trữ và trường tiếp theo chứa tham chiếu đến phần tử tiếp theo trong chuỗi. Phần tử đầu tiên của danh sách được liên kết được lưu trữ dưới dạng phần đầu của danh sách được liên kết.
| dữ liệu | tiếp theo |
Hình 3: Phần tử của Danh sách được Liên kết
Hình 4 mô tả một danh sách được liên kết với ba phần tử. Mỗi phần tử lưu trữ dữ liệu của nó và tất cả các phần tử ngoại trừ phần tử cuối cùng lưu trữ một tham chiếu đến phần tử tiếp theo. Phần tử cuối cùng giữ giá trị null trong trường tiếp theo của nó. Bất kỳ phần tử nào trong danh sách đều có thể được truy cập bằng cách bắt đầu từ đầu và theo sau con trỏ tiếp theo cho đến khi bạn đáp ứng phần tử được yêu cầu.
Mặc dù các mảng và danh sách được liên kết giống nhau theo nghĩa cả hai đều được sử dụng để lưu trữ tập hợp các phần tử, chúng có sự khác biệt do chiến lược mà chúng sử dụng để cấp phát bộ nhớ cho các phần tử của nó. Mảng phân bổ bộ nhớ cho tất cả các phần tử của nó như một khối duy nhất và kích thước của mảng phải được xác định trong thời gian chạy. Điều này sẽ làm cho các mảng hoạt động kém hiệu quả trong các tình huống mà bạn không biết kích thước của mảng tại thời điểm biên dịch. Vì một danh sách được liên kết phân bổ bộ nhớ cho các phần tử của nó một cách riêng biệt, nó sẽ hiệu quả hơn nhiều trong các tình huống mà bạn không biết kích thước của danh sách tại thời điểm biên dịch. Khai báo và truy cập các phần tử trong danh sách được liên kết sẽ không dễ dàng so với cách bạn truy cập trực tiếp vào các phần tử trong một mảng bằng cách sử dụng các chỉ số của nó.
