Danh sách được liên kết đơn lẻ so với Danh sách được liên kết kép
Danh sách được liên kết là một cấu trúc dữ liệu tuyến tính được sử dụng để lưu trữ một tập hợp dữ liệu. 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ột danh sách được liên kết đơn lẻ đượ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. Một danh sách được liên kết kép chứa một chuỗi các nút trong đó mỗi nút chứa một tham chiếu đến nút tiếp theo cũng như đến nút trước đó.
Danh sách liên kết Singly
Mỗi phần tử trong danh sách được liên kết đơn lẻ có hai trường như thể hiện trong Hình 1. 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.
Hình 2 mô tả một danh sách được liên kết đơn lẻ 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ó. 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à theo con trỏ tiếp theo cho đến khi bạn đáp ứng phần tử được yêu cầu.
Danh sách được liên kết gấp đôi
Mỗi phần tử trong danh sách liên kết kép có ba trường như trong Hình 3. Tương tự như danh sách được liên kết đơn lẻ, trường dữ liệu giữ dữ liệu thực tế được lưu trữ và trường tiếp theo giữ tham chiếu đến phần tử tiếp theo trong chuỗi. Ngoài ra, trường trước đó giữ tham chiếu đến phần tử trước đó 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 4 mô tả một danh sách được liên kết kép với ba phần tử. Tất cả các phần tử trung gian lưu trữ các tham chiếu đến các phần tử đầu tiên và trước đó. Phần tử cuối cùng trong danh sách giữ giá trị null trong trường tiếp theo của nó và phần tử đầu tiên trong danh sách giữ giá trị null trong trường trước đó. Danh sách được liên kết kép có thể được duyệt qua bằng cách đi theo các tham chiếu tiếp theo trong mỗi phần tử và tương tự có thể được chuyển ngược lại bằng cách sử dụng các tham chiếu trước đó trong mỗi phần tử.
Sự khác biệt giữa Danh sách liên kết đơn và Danh sách liên kết kép là gì?
Mỗi phần tử trong danh sách liên kết đơn chứa một tham chiếu đến phần tử tiếp theo trong danh sách, trong khi mỗi phần tử trong danh sách liên kết kép chứa các tham chiếu đến phần tử tiếp theo cũng như phần tử trước đó trong danh sách. Danh sách được liên kết kép yêu cầu nhiều không gian hơn cho mỗi phần tử trong danh sách và các thao tác cơ bản như chèn và xóa phức tạp hơn vì chúng phải xử lý hai tham chiếu. Nhưng danh sách liên kết kép cho phép thao tác dễ dàng hơn vì nó cho phép duyệt qua danh sách theo hướng tiến và lùi.
