Danh sách liên kết: nút, con trỏ, xóa và đảo danh sách

Node, head và next là gì?

Mỗi nút của danh sách liên kết đơn gồm một giá trị và một đường dẫn tới nút kế tiếp. Trong C++, đường dẫn thường biểu diễn bằng Node*. Trong Python, nó là tham chiếu tới đối tượng Node hoặc None. Biến head giữ nút đầu tiên; danh sách rỗng có head bằng nullptr hoặc None.

Khác với vector của C++ và list có sẵn của Python, các nút không cần nằm cạnh nhau trong bộ nhớ. Khi đọc phần tử tiếp theo, chương trình phải theo liên kết next. Bạn không thể từ head nhảy thẳng tới nút thứ một triệu chỉ bằng phép tính địa chỉ. Hãy phân biệt list có sẵn của Python, vốn là mảng động, với danh sách Node tự cài trong bài.

Đọc độ phức tạp cho đúng điều kiện

Thêm một nút ngay sau nút p đã biết chỉ cần đổi vài liên kết, có chi phí O(1). Nhưng tìm p theo chỉ số hoặc giá trị có thể tốn O(n). Nếu gộp cả hai bước vào một hàm “chèn tại vị trí i”, không được quảng cáo toàn hàm O(1) chỉ vì thao tác nối ở cuối ngắn.

Với danh sách đơn, xóa một nút bất kỳ thường cần biết nút đứng trước nó. Chỉ có con trỏ tới nút cần xóa chưa đủ để xử lý mọi trường hợp, đặc biệt nút cuối. Danh sách liên kết đôi thêm prev để đi ngược, đổi lại tốn thêm bộ nhớ liên kết và phải cập nhật cả hai chiều.

Những ưu điểm này không có nghĩa linked list luôn nhanh hơn mảng. Mỗi nút cần cấp phát và lưu con trỏ, trong khi duyệt mảng thường thuận lợi hơn cho bộ nhớ đệm. Chọn theo thao tác thật sự cần dùng, không chỉ theo tên cấu trúc.

Xóa mọi nút có giá trị cho trước bằng nút giả

Giả sử cần xóa giá trị 2 khỏi [1, 2, 3, 2, 4]. Nếu chỉ sửa liên kết từ nút trước, trường hợp nút đầu cũng bằng 2 sẽ cần nhánh riêng. Một nút giả dummy đặt trước head giúp mọi nút thật đều có một nút đứng trước để xử lý thống nhất.

Giữ prev ở nút đứng trước vị trí đang xét. Nếu prev.next có giá trị cần xóa, nối prev.next tới nút tiếp nữa. Trong C++, giải phóng nút vừa bỏ bằng delete sau khi đã giữ các liên kết cần thiết. Không tăng prev ở nhánh này, vì nút mới đứng sau prev có thể cũng cần xóa. Nếu không xóa, mới tiến prev sang nút tiếp theo.

Sau vòng lặp trả dummy.next, vì head cũ có thể đã bị bỏ. Nút giả chỉ hỗ trợ xử lý biên, không phải phần tử kết quả. Bản C++ dùng dummy là biến cục bộ nhưng chỉ trả con trỏ tới nút thật, không trả địa chỉ của chính dummy.

Đảo danh sách với ba tham chiếu

Muốn đảo 1 → 3 → 4, ta cần biến next của 1 thành rỗng, next của 3 thành 1 và next của 4 thành 3. Dùng prev đại diện phần đã đảo, head đại diện phần chưa xử lý và sau giữ nút kế tiếp trước khi sửa.

Mỗi lượt: lưu sau = head.next, đổi head.next = prev, rồi chuyển prev tới head và head tới sau. Khi head rỗng, prev là đầu mới. Bất biến này giúp bạn không bị mất phần đuôi: phần chưa xử lý luôn còn được giữ trong sau hoặc head trước khi đường nối cũ bị ghi đè.

#include <iostream>
#include <vector>
using namespace std;
struct Node {int val;Node* next;Node(int v,Node* p=nullptr):val(v),next(p){}};
Node* tao(const vector<int>& a) {
    Node* head=nullptr;
    for(auto it=a.rbegin();it!=a.rend();++it)head=new Node(*it,head);
    return head;
}
Node* xoa_gia_tri(Node* head,int val) {
    Node dummy(0,head);Node* prev=&dummy;
    while(prev->next) {
        Node* cur=prev->next;
        if(cur->val==val){prev->next=cur->next;delete cur;}
        else prev=cur;
    }
    return dummy.next;
}
Node* dao(Node* head) {
    Node* prev=nullptr;
    while(head){Node* sau=head->next;head->next=prev;prev=head;head=sau;}
    return prev;
}
int main() {
    int n,val=2;vector<int>a={1,2,3,2,4};
    if(cin>>n>>val){a.resize(n);for(int&x:a)cin>>x;}
    Node* head=dao(xoa_gia_tri(tao(a),val));
    while(head){cout<<head->val<<' ';Node* sau=head->next;delete head;head=sau;}
    cout<<'\n';
}

class Node:
    def __init__(self, val, next_node=None):
        self.val, self.next = val, next_node

def tao(a):
    head=None
    for x in reversed(a):
        head=Node(x,head)
    return head

def xoa_gia_tri(head,val):
    dummy=Node(0,head)
    prev=dummy
    while prev.next:
        if prev.next.val==val:
            prev.next=prev.next.next
        else:
            prev=prev.next
    return dummy.next

def dao(head):
    prev=None
    while head:
        sau=head.next
        head.next=prev
        prev,head=head,sau
    return prev

if __name__=='__main__':
    import sys
    d=list(map(int,sys.stdin.read().split()))
    a,val=(d[2:2+d[0]],d[1]) if d else ([1,2,3,2,4],2)
    p=dao(xoa_gia_tri(tao(a),val))
    ans=[]
    while p:
        ans.append(p.val)
        p=p.next
    print(*ans)

Không nhập dữ liệu, tệp chạy ví dụ và in 4 3 1. Để thử khác, nhập n, giá trị cần xóa, rồi n số. Chương trình dựng danh sách, xóa mọi nút mang giá trị đó và đảo phần còn lại. Cuối cùng bản C++ giải phóng các nút kết quả khi in. Hàm xử lý liên kết chạy O(n) thời gian và O(1) bộ nhớ phụ; phần dựng dữ liệu và các nút vẫn cần O(n) bộ nhớ.

Các ca biên và lỗi mất liên kết

Thử danh sách rỗng, một nút, mọi nút cùng giá trị cần xóa, chỉ nút đầu bị xóa và hai nút cần xóa đứng liền nhau. Để đối chiếu nhanh trên dữ liệu nhỏ, bạn có thể lọc bỏ giá trị và đảo ngược trên một mảng thường rồi so sánh kết quả với danh sách liên kết. Kiểm tra thêm rằng đảo ngược hai lần liên tiếp sẽ khôi phục đúng thứ tự ban đầu.

Chu trình và con trỏ nhanh chậm

Các hàm trong bài giả định danh sách hữu hạn, không có chu trình. Nếu nút cuối trỏ lại một nút trước, vòng duyệt tới nullptr sẽ không dừng. Thuật toán Floyd dùng một con trỏ đi một bước và một con trỏ đi hai bước; nếu gặp nhau thì có chu trình. Đây là bài mở rộng, không phải cách sửa tùy tiện hàm đảo đang dùng.

Khi làm phỏng vấn, nên nói rõ đầu vào có thể có chu trình hay không. Tương tự, nếu nhiều head cùng trỏ tới chung một đoạn đuôi, việc sửa liên kết từ một head có thể ảnh hưởng head khác. Các ví dụ tạo danh sách độc lập, nên không gặp chia sẻ nút như vậy.

Luyện ngay trên Big-O Coding

Bài xóa nút miễn phí áp dụng trực tiếp dummy. Tiếp theo luyện đảo danh sách và phát hiện chu trình để hiểu khác biệt giữa đổi liên kết và chỉ đổi thứ tự các giá trị.

Câu hỏi thường gặp

Nguồn tham khảo

• Open Data Structures: SLList
• Python: Data model, objects and references
• cppreference: delete expression