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