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