Sự khác biệt giữa Mảng và Danh sách liên kết

Mảng so với 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 thức để dễ dàng khai báo các mảng và các phần tử truy cập trong các mảng. Danh sách liên kết, danh sách liên kết đơn 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 yếu 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.

Hiển thị 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 chỉ số 0 đến 4. Một thuộc tính quan trọng của mảng là toàn bộ mảng được phân bổ thà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ó đượ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. Nhưng, 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 số lượng chúng ta đã phân bổ. Vì vậy, một lượng đáng kể bộ nhớ thực sự bị lãng phí. Mặt khác, nếu mảng đủ lớn, thì không đủ lớn, chương trình sẽ bị sập.

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 trong khối bộ nhớ riêng 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 dưới dạng liên kết trong một chuỗi. Mỗi phần tử trong danh sách được 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 giữ 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.

Hình 3: Phần tử của 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 yếu 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ữ một giá trị null trong trường tiếp theo của nó. Bất kỳ yếu tố nào trong danh sách đều có thể được truy cập bằng cách bắt đầu ở đầu và theo con trỏ tiếp theo cho đến khi bạn đáp ứng được yếu tố cần thiết.

Mặc dù các mảng và danh sách được liên kết tương tự nhau theo nghĩa là cả hai đều được sử dụng để lưu trữ bộ sưu tập các phần tử, chúng phải chịu sự khác biệt do các chiến lược mà chúng 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ó dưới dạng 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ì danh sách được liên kết phân bổ bộ nhớ cho các thành phần của nó một cách riêng biệt, 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 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 đơn giản so với cách bạn truy cập trực tiếp các phần tử trong một mảng bằng chỉ mục của nó.