Sự khác biệt giữa Danh sách liên kết đơn và Danh sách liên kết đôi

Danh sách liên kết đơn so với danh sách liên kết đô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 đượ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ột danh sách liên kế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. Một danh sách liên kết đôi chứa một chuỗi các nút trong đó mỗi nút chứa tham chiếu đến nút tiếp theo cũng như đến nút trước đó.

Danh sách liên kết đơn

Mỗi phần tử trong danh sách liên kết đơn có hai trường như 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 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 2 mô tả một danh sách liên kết đơn 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.

Danh sách liên kết đôi

Mỗi phần tử trong danh sách được liên kết đôi có ba trường như trong Hình 3. Tương tự như danh sách liên kết đơn, trường dữ liệu giữ 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. 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 liên kết đôi với ba yếu tố. Tất cả các yếu tố trung gian lưu trữ các tham chiếu đến các yếu 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 và phần tử đầu tiên trong danh sách giữ giá trị null trong trường trước đó. Danh sách liên kết đôi có thể được chuyển tiếp bằng cách theo dõi 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 đôi?

Mỗi phần tử trong danh sách liên kết đơn có 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 được liên kết đôi 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 liên kết đôi đòi hỏi nhiều không gian hơn cho mỗi thành phần 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 đôi cho phép thao tác dễ dàng hơn vì nó cho phép đi qua danh sách theo hướng tiến và lùi.