Bài 15. Cấu trúc dữ liệu danh sách liên kết và ứng dụng SVIP

1. Cấu trúc danh sách liên kết

Danh sách liên kết (linked list) cũng gọi là danh sách móc nối, gồm các phần tử gọi là nút (node).

Một nút có hai thành phần: phần Data chứa dữ liệu, phần liên kết gọi là Next.

Phần Next (chứa địa chỉ của nút liền kề) trong một nút là con trỏ Next (kí hiệu mũi tên "→" thể hiện Next đang trỏ vào cái gì), con trỏ cho phép truy cập trực tiếp đến một địa chỉ ô nhớ cụ thể.

Đuôi danh sách là nút cuối cùng trong danh sách được thể hiện bằng hình vẽ Next trỏ đến Null (con trỏ Tail trỏ đến nút đuôi).

Đầu danh sách được Head trỏ đến nút đầu tiên trong danh sách.

So với mảng, các nút danh sách liên kết không được lưu trữ thành một khối liên tục liền kề mà có thể nằm rải rác, tách rời nhau trong bộ nhớ.

Các nút trong danh sách liên kết không có chỉ số. Phép lặp duyệt tuần tự từng nút: A, B, C, D của danh sách liên kết sử dụng một con trỏ curr (current) chỉ vào nút đang xét, thực hiện như sau:

+ curr= Head bắt đầu từ Head để truy cập nút A;

+ curr= A.Next để truy cập nút B; curr= B.Next để truy cập nút C;...

+ Kết thúc khi gặp curr = Null tức là ở tình huống curr= D.Next.

a) Thêm nút vào đầu danh sách

Nút mới thêm thành nút đầu tiên. Gọi nút mới là E.

• Cho E.Next trỏ đến nút A: gán E.Next = Head.
• Cho Head trỏ đến nút E: Head → E.

b) Thêm nút vào cuối danh sách

Nối thêm nút mới vào cuối danh sách, nó trở thành nút cuối cùng. Con trỏ Tail trỏ đến nút cuối cùng của danh sách. Chú ý rằng phải sửa lại, cho Tail trỏ vào E. Thời gian thực hiện phép thêm nút vào cuối danh sách là O(1), không phụ thuộc độ dài danh sách.

c) Thêm nút vào giữa danh sách

Thêm nút vào sau nút B, thời gian thực hiện phép thêm nút vào giữa danh sách là O(1), không phụ thuộc độ dài danh sách.

Gỡ bỏ nút B, ghi lưu con trỏ để truy cập nút C: tmp = B.Next, tức là tmp → C. Cho B.Next trỏ đến nút đứng sau C (là nút D): B.Next =C.Next.

Sử dụng tmp để giải phóng phần bộ nhớ dành cho C.

Thời gian thực hiện gỡ bỏ là O(1), không phụ thuộc vào độ dài danh sách.

Thời gian thực hiện các phép toán của danh sách liên kết

• Phép tìm kiếm tuần tự có độ phức tạp là O(n) với n là số nút của danh sách.
• Các thao tác thêm nút, gỡ bỏ nút dù ở bất cứ vị trí nào thì thời gian thực hiện đều là O(1).
• Tốn thêm chỗ để lưu trữ thành phần Next.

2. Một số kiểu danh sách đặc biệt và ứng dụng của danh sách liên kết

Danh sách liên kết phát huy ưu điểm trong những trường hợp thường xuyên phải:

• Thêm phần tử, gỡ bỏ phần tử ở bất cứ vị trí nào trong danh sách;
• Độ dài danh sách thay đổi nhanh và nhiều trong quá trình sử dụng.

Một số bài toán thực tế cần mô hình hoá một mạng lưới (điện, đường giao thông,...) hay một cấu trúc phân cấp hình cây (tổ chức hành chính, cây gia phả,...) thì không thể dùng một danh sách. Việc thể hiện mối liên kết giữa các nút (điểm giao cắt) phải cho phép cập nhật các thay đổi một cách linh hoạt.