Cấu trúc dữ liệu Danh sách liên kết trong C++: Từ cơ bản đến ứng dụng nâng cao

Danh sách liên kết là một trong những cấu trúc dữ liệu cơ bản và quan trọng nhất trong khoa học máy tính, đóng vai trò then chốt trong quản lý bộ nhớ, triển khai thuật toán và ứng dụng thực tế. Bài viết này sẽ giới thiệu chi tiết về khái niệm, loại hình, cách triển khai bằng C++ và các tình huống ứng dụng của danh sách liên kết, giúp người đọc hiểu toàn diện về cấu trúc dữ liệu quan trọng này.

1. Khái niệm cơ bản về Danh sách liên kết

Danh sách liên kết là một cấu trúc dữ liệu tuyến tính, bao gồm một chuỗi các nút, mỗi nút chứa hai phần: phần dữ liệu và phần con trỏ. Khác với mảng, các phần tử trong danh sách liên kết không được lưu trữ liên tục trong bộ nhớ, mà được kết nối với nhau thông qua các con trỏ. Cấu trúc này cho phép thực hiện các thao tác chèn và xóa hiệu quả mà không cần di chuyển các phần tử khác.

Như hình trên cho thấy, danh sách liên kết bao gồm một chuỗi các nút, mỗi nút chứa dữ liệu và con trỏ trỏ đến nút tiếp theo. Nút đầu tiên của danh sách liên kết được gọi là nút đầu (HEAD), nút cuối cùng có con trỏ trỏ đến NULL, biểu thị sự kết thúc của danh sách.

Đặc điểm cốt lõi của Danh sách liên kết

1. Cấu trúc dữ liệu động: Danh sách liên kết có thể phát triển và thu nhỏ linh hoạt theo nhu cầu, không cần cấp phát bộ nhớ có kích thước cố định trước.
2. Cấp phát bộ nhớ không liên tục: Các nút trong danh sách liên kết có thể được lưu trữ ở bất kỳ vị trí nào trong bộ nhớ, kết nối với nhau thông qua con trỏ.
3. Hiệu quả cao khi chèn và xóa: Thời gian phức tạp cho việc chèn hoặc xóa một nút tại vị trí xác định là O(1), không cần di chuyển các phần tử khác như trong mảng.
4. Hiệu quả thấp khi truy cập ngẫu nhiên: Để truy cập phần tử thứ n trong danh sách liên kết cần phải duyệt từ đầu, thời gian phức tạp là O(n).
5. Tốn thêm bộ nhớ: Ngoài việc lưu trữ dữ liệu, mỗi nút còn cần lưu trữ con trỏ trỏ đến các nút khác.

2. Các loại Danh sách liên kết

Danh sách liên kết được phân loại thành bốn loại chính dựa trên cách kết nối giữa các nút: danh sách liên kết đơn, danh sách liên kết đôi, danh sách liên kết vòng và danh sách liên kết đôi vòng.

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

Danh sách liên kết đơn là dạng cơ bản nhất, mỗi nút chứa dữ liệu và một con trỏ trỏ đến nút tiếp theo. Con trỏ của nút cuối cùng trong danh sách trỏ đến NULL, biểu thị sự kết thúc của danh sách.

Đặc điểm:

• Chỉ có thể duyệt từ đầu đến cuối
• Mỗi nút chỉ có một con trỏ
• Chỉ có thể truy cập nút tiếp theo của nút hiện tại
• Tốn ít bộ nhớ hơn

Định nghĩa nút trong C++:

struct Nut {
    int du_lieu;     // Lưu trữ giá trị của nút
    Nut* tiep_theo;  // Trỏ đến nút tiếp theo
};

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

Trong danh sách liên kết đôi, mỗi nút chứa dữ liệu và hai con trỏ: một trỏ đến nút trước và một trỏ đến nút sau. Con trỏ prev của nút đầu tiên và con trỏ next của nút cuối cùng đều trỏ đến NULL.

Đặc điểm:

• Có thể duyệt theo hai chiều (từ đầu đến cuối hoặc từ cuối đến đầu)
• Mỗi nút có hai con trỏ
• Có thể truy cập nút trước và nút sau của nút hiện tại
• Tốn nhiều bộ nhớ hơn
• Linh hoạt hơn khi chèn và xóa

Sơ đồ cấu trúc:

NULL ← [truoc|du_lieu|sau] ⇄ [truoc|du_lieu|sau] ⇄ [truoc|du_lieu|sau] → NULL
       ↑
      dau

Định nghĩa nút trong C++:

struct Nut {
    int du_lieu;     // Lưu trữ giá trị của nút
    Nut* truoc;      // Con trỏ chỉ đến nút trước
    Nut* sau;        // Con trỏ chỉ đến nút sau
};

2.3 Danh sách liên kết vòng

Danh sách liên kết vòng là biến thể của danh sách liên kết đơn, trong đó con trỏ của nút cuối cùng không trỏ đến NULL mà trỏ đến nút đầu tiên, tạo thành một vòng tròn.

Đặc điểm:

• Không có điểm kết thúc rõ ràng
• Có thể duyệt toàn bộ danh sách từ bất kỳ nút nào
• Phù hợp cho các tình huống cần xử lý vòng lặp, như lịch luân phiên

Sơ đồ cấu trúc:

    ┌───────────────────────────┐
    ↓                           |
dau → [du_lieu|tiep_theo] → [du_lieu|tiep_theo] → [du_lieu|tiep_theo]

Định nghĩa nút trong C++:

struct Nut {
    int du_lieu;     // Lưu trữ giá trị của nút
    Nut* tiep_theo;  // Trỏ đến nút tiếp theo
};

2.4 Danh sách liên kết đôi vòng

Danh sách liên kết đôi kết hợp đặc điểm của danh sách liên kết đôi và danh sách liên kết vòng. Con trỏ prev của nút đầu tiên trỏ đến nút cuối cùng, và con trỏ next của nút cuối cùng trỏ đến nút đầu tiên.

Đặc điểm:

• Có thể duyệt vòng theo hai chiều
• Mỗi nút đều có thể truy cập nút trước và nút sau
• Không có điểm bắt đầu và kết thúc rõ ràng
• Tốn nhiều bộ nhớ nhất
• Cấu trúc linh hoạt nhất

Sơ đồ cấu trúc:

    ┌─────────────────────────────────────┐
    |                                     |
    ↓                                     ↑
[truoc|du_lieu|sau] ⇄ [truoc|du_lieu|sau] ⇄ [truoc|du_lieu|sau]
    ↑                                     |
    └─────────────────────────────────────┘

Định nghĩa nút trong C++:

struct Nut {
    int du_lieu;     // Lưu trữ giá trị của nút
    Nut* truoc;      // Con trỏ chỉ đến nút trước
    Nut* sau;        // Con trỏ chỉ đến nút sau
};

3. Triển khai Danh sách liên kết trong C++

Trong C++, chúng ta có thể sử dụng cấu trúc (struct) hoặc lớp (class) để triển khai danh sách liên kết. Dưới đây sẽ giới thiệu chi tiết cách triển khai các loại danh sách liên kết khác nhau.

3.1 Định nghĩa cấu trúc nút

Đơn vị cơ bản của danh sách liên kết là nút, trước tiên chúng ta cần định nghĩa cấu trúc của nút:

// Cấu trúc nút cho danh sách liên kết đơn
struct NutDon {
    int gia_tri;        // Lưu trữ giá trị của nút
    NutDon* ke_tiep;    // Con trỏ chỉ đến nút tiếp theo
    
    // Hàm khởi tạo mặc định
    NutDon() : gia_tri(0), ke_tiep(nullptr) {}
    
    // Hàm khởi tạo có tham số
    NutDon(int val) : gia_tri(val), ke_tiep(nullptr) {}
};

// Cấu trúc nút cho danh sách liên kết đôi
struct NutDoi {
    int gia_tri;        // Lưu trữ giá trị của nút
    NutDoi* truoc;      // Con trỏ chỉ đến nút trước
    NutDoi* sau;        // Con trỏ chỉ đến nút sau
    
    // Hàm khởi tạo mặc định
    NutDoi() : gia_tri(0), truoc(nullptr), sau(nullptr) {}
    
    // Hàm khởi tạo có tham số
    NutDoi(int val) : gia_tri(val), truoc(nullptr), sau(nullptr) {}
};

3.2 Triển khai Danh sách liên kết đơn

Dưới đây là triển khai đầy đủ cho lớp danh sách liên kết đơn, bao gồm các thao tác phổ biến như chèn, xóa, duyệt, v.v.:

// Lớp danh sách liên kết đơn
class DanhSachDon {
private:
    NutDon* dau;    // Con trỏ đầu, trỏ đến nút đầu tiên của danh sách
    
public:
    // Hàm khởi tạo
    DanhSachDon() : dau(nullptr) {}
    
    // Hàm hủy, giải phóng bộ nhớ tất cả các nút
    ~DanhSachDon() {
        NutDon* hien_tai = dau;
        while (hien_tai != nullptr) {
            NutDon* tam = hien_tai;
            hien_tai = hien_tai->ke_tiep;
            delete tam;
        }
        dau = nullptr;
    }
    
    // Chèn nút vào đầu danh sách
    void chenDau(int gia_tri) {
        // Tạo nút mới
        NutDon* nut_moi = new NutDon(gia_tri);
        
        // Nếu danh sách rỗng, nút mới là nút đầu
        if (dau == nullptr) {
            dau = nut_moi;
            return;
        }
        
        // Ngược lại, chèn nút mới vào đầu
        nut_moi->ke_tiep = dau;
        dau = nut_moi;
    }
    
    // Chèn nút vào cuối danh sách
    void chenCuoi(int gia_tri) {
        // Tạo nút mới
        NutDon* nut_moi = new NutDon(gia_tri);
        
        // Nếu danh sách rỗng, nút mới là nút đầu
        if (dau == nullptr) {
            dau = nut_moi;
            return;
        }
        
        // Tìm nút cuối cùng của danh sách
        NutDon* hien_tai = dau;
        while (hien_tai->ke_tiep != nullptr) {
            hien_tai = hien_tai->ke_tiep;
        }
        
        // Nối nút mới vào nút cuối cùng
        hien_tai->ke_tiep = nut_moi;
    }
    
    // Chèn nút vào vị trí xác định
    void chenViTri(int vi_tri, int gia_tri) {
        // Nếu vị trí là 0, tương đương chèn vào đầu
        if (vi_tri == 0) {
            chenDau(gia_tri);
            return;
        }
        
        // Tạo nút mới
        NutDon* nut_moi = new NutDon(gia_tri);
        
        // Tìm nút đứng trước vị trí cần chèn
        NutDon* hien_tai = dau;
        for (int i = 0; i < vi_tri - 1 && hien_tai != nullptr; i++) {
            hien_tai = hien_tai->ke_tiep;
        }
        
        // Nếu vị trí vượt quá độ dài danh sách hoặc danh sách rỗng
        if (hien_tai == nullptr) {
            std::cout << "Vị trí không hợp lệ" << std::endl;
            delete nut_moi;
            return;
        }
        
        // Chèn nút mới
        nut_moi->ke_tiep = hien_tai->ke_tiep;
        hien_tai->ke_tiep = nut_moi;
    }
    
    // Xóa nút ở đầu danh sách
    void xoaDau() {
        // Nếu danh sách rỗng, không thể xóa
        if (dau == nullptr) {
            std::cout << "Danh sách rỗng, không thể xóa" << std::endl;
            return;
        }
        
        // Lưu nút đầu
        NutDon* tam = dau;
        
        // Cập nhật con trỏ đầu
        dau = dau->ke_tiep;
        
        // Giải phóng bộ nhớ nút đầu cũ
        delete tam;
    }
    
    // Xóa nút ở cuối danh sách
    void xoaCuoi() {
        // Nếu danh sách rỗng, không thể xóa
        if (dau == nullptr) {
            std::cout << "Danh sách rỗng, không thể xóa" << std::endl;
            return;
        }
        
        // Nếu danh sách chỉ có một nút
        if (dau->ke_tiep == nullptr) {
            delete dau;
            dau = nullptr;
            return;
        }
        
        // Tìm nút áp chót
        NutDon* hien_tai = dau;
        while (hien_tai->ke_tiep->ke_tiep != nullptr) {
            hien_tai = hien_tai->ke_tiep;
        }
        
        // Xóa nút cuối cùng
        delete hien_tai->ke_tiep;
        hien_tai->ke_tiep = nullptr;
    }
    
    // Xóa nút ở vị trí xác định
    void xoaViTri(int vi_tri) {
        // Nếu danh sách rỗng, không thể xóa
        if (dau == nullptr) {
            std::cout << "Danh sách rỗng, không thể xóa" << std::endl;
            return;
        }
        
        // Nếu xóa nút đầu
        if (vi_tri == 0) {
            xoaDau();
            return;
        }
        
        // Tìm nút đứng trước vị trí cần xóa
        NutDon* hien_tai = dau;
        for (int i = 0; i < vi_tri - 1 && hien_tai != nullptr && hien_tai->ke_tiep != nullptr; i++) {
            hien_tai = hien_tai->ke_tiep;
        }
        
        // Nếu vị trí không hợp lệ
        if (hien_tai == nullptr || hien_tai->ke_tiep == nullptr) {
            std::cout << "Vị trí không hợp lệ" << std::endl;
            return;
        }
        
        // Lưu nút cần xóa
        NutDon* tam = hien_tai->ke_tiep;
        
        // Cập nhật liên kết
        hien_tai->ke_tiep = tam->ke_tiep;
        
        // Giải phóng bộ nhớ nút
        delete tam;
    }
    
    // Hiển thị danh sách
    void hienThi() {
        NutDon* hien_tai = dau;
        
        if (hien_tai == nullptr) {
            std::cout << "Danh sách rỗng" << std::endl;
            return;
        }
        
        std::cout << "Nội dung danh sách: ";
        while (hien_tai != nullptr) {
            std::cout << hien_tai->gia_tri << " -> ";
            hien_tai = hien_tai->ke_tiep;
        }
        std::cout << "NULL" << std::endl;
    }
    
    // Đảo ngược danh sách
    void daoNguoc() {
        NutDon* truoc = nullptr;
        NutDon* hien_tai = dau;
        NutDon* tiep_theo = nullptr;
        
        while (hien_tai != nullptr) {
            // Lưu nút tiếp theo
            tiep_theo = hien_tai->ke_tiep;
            
            // Đảo ngược con trỏ của nút hiện tại
            hien_tai->ke_tiep = truoc;
            
            // Di chuyển con trỏ
            truoc = hien_tai;
            hien_tai = tiep_theo;
        }
        
        // Cập nhật con trỏ đầu
        dau = truoc;
    }
};

3.3 Triển khai Danh sách liên kết đôi

Triển khai danh sách liên kết đôi phức tạp hơn danh sách liên kết đơn một chút vì cần duy trì hai con trỏ:

// Lớp danh sách liên kết đôi
class DanhSachDoi {
private:
    NutDoi* dau;    // Con trỏ đầu, trỏ đến nút đầu tiên của danh sách
    NutDoi* cuoi;   // Con trỏ cuối, trỏ đến nút cuối cùng của danh sách
    
public:
    // Hàm khởi tạo
    DanhSachDoi() : dau(nullptr), cuoi(nullptr) {}
    
    // Hàm hủy, giải phóng bộ nhớ tất cả các nút
    ~DanhSachDoi() {
        NutDoi* hien_tai = dau;
        while (hien_tai != nullptr) {
            NutDoi* tam = hien_tai;
            hien_tai = hien_tai->sau;
            delete tam;
        }
        dau = nullptr;
        cuoi = nullptr;
    }
    
    // Chèn nút vào đầu danh sách
    void chenDau(int gia_tri) {
        // Tạo nút mới
        NutDoi* nut_moi = new NutDoi(gia_tri);
        
        // Nếu danh sách rỗng
        if (dau == nullptr) {
            dau = nut_moi;
            cuoi = nut_moi;
            return;
        }
        
        // Chèn nút mới vào đầu
        nut_moi->sau = dau;
        dau->truoc = nut_moi;
        dau = nut_moi;
    }
    
    // Chèn nút vào cuối danh sách
    void chenCuoi(int gia_tri) {
        // Tạo nút mới
        NutDoi* nut_moi = new NutDoi(gia_tri);
        
        // Nếu danh sách rỗng
        if (cuoi == nullptr) {
            dau = nut_moi;
            cuoi = nut_moi;
            return;
        }
        
        // Chèn nút mới vào cuối
        cuoi->sau = nut_moi;
        nut_moi->truoc = cuoi;
        cuoi = nut_moi;
    }
    
    // Chèn nút vào vị trí xác định
    void chenViTri(int vi_tri, int gia_tri) {
        // Nếu vị trí là 0, tương đương chèn vào đầu
        if (vi_tri == 0) {
            chenDau(gia_tri);
            return;
        }
        
        // Tạo nút mới
        NutDoi* nut_moi = new NutDoi(gia_tri);
        
        // Tìm nút tại vị trí cần chèn
        NutDoi* hien_tai = dau;
        for (int i = 0; i < vi_tri && hien_tai != nullptr; i++) {
            hien_tai = hien_tai->sau;
        }
        
        // Nếu vị trí vượt quá độ dài danh sách, chèn vào cuối
        if (hien_tai == nullptr) {
            chenCuoi(gia_tri);
            return;
        }
        
        // Chèn nút mới
        nut_moi->sau = hien_tai;
        nut_moi->truoc = hien_tai->truoc;
        hien_tai->truoc->sau = nut_moi;
        hien_tai->truoc = nut_moi;
    }
    
    // Xóa nút ở đầu danh sách
    void xoaDau() {
        // Nếu danh sách rỗng, không thể xóa
        if (dau == nullptr) {
            std::cout << "Danh sách rỗng, không thể xóa" << std::endl;
            return;
        }
        
        // Lưu nút đầu
        NutDoi* tam = dau;
        
        // Nếu danh sách chỉ có một nút
        if (dau == cuoi) {
            dau = nullptr;
            cuoi = nullptr;
        } else {
            // Cập nhật con trỏ đầu
            dau = dau->sau;
            dau->truoc = nullptr;
        }
        
        // Giải phóng bộ nhớ nút đầu cũ
        delete tam;
    }
    
    // Xóa nút ở cuối danh sách
    void xoaCuoi() {
        // Nếu danh sách rỗng, không thể xóa
        if (cuoi == nullptr) {
            std::cout << "Danh sách rỗng, không thể xóa" << std::endl;
            return;
        }
        
        // Lưu nút cuối
        NutDoi* tam = cuoi;
        
        // Nếu danh sách chỉ có một nút
        if (dau == cuoi) {
            dau = nullptr;
            cuoi = nullptr;
        } else {
            // Cập nhật con trỏ cuối
            cuoi = cuoi->truoc;
            cuoi->sau = nullptr;
        }
        
        // Giải phóng bộ nhớ nút cuối cũ
        delete tam;
    }
    
    // Hiển thị danh sách theo chiều xuôi
    void hienThiXuoi() {
        NutDoi* hien_tai = dau;
        
        if (hien_tai == nullptr) {
            std::cout << "Danh sách rỗng" << std::endl;
            return;
        }
        
        std::cout << "Nội dung danh sách xuôi: ";
        while (hien_tai != nullptr) {
            std::cout << hien_tai->gia_tri << " <-> ";
            hien_tai = hien_tai->sau;
        }
        std::cout << "NULL" << std::endl;
    }
    
    // Hiển thị danh sách theo chiều ngược
    void hienThiNguoc() {
        NutDoi* hien_tai = cuoi;
        
        if (hien_tai == nullptr) {
            std::cout << "Danh sách rỗng" << std::endl;
            return;
        }
        
        std::cout << "Nội dung danh sách ngược: ";
        while (hien_tai != nullptr) {
            std::cout << hien_tai->gia_tri << " <-> ";
            hien_tai = hien_tai->truoc;
        }
        std::cout << "NULL" << std::endl;
    }
};

3.4 Triển khai Danh sách liên kết vòng

Triển khai danh sách liên kết vòng cần đặc biệt chú ý đến việc xử lý nút cuối:

// Lớp danh sách liên kết vòng đơn
class DanhSachVong {
private:
    NutDon* dau;    // Con trỏ đầu, trỏ đến nút đầu tiên của danh sách
    
public:
    // Hàm khởi tạo
    DanhSachVong() : dau(nullptr) {}
    
    // Hàm hủy, giải phóng bộ nhớ tất cả các nút
    ~DanhSachVong() {
        if (dau == nullptr) {
            return;
        }
        
        NutDon* hien_tai = dau->ke_tiep;
        while (hien_tai != dau) {
            NutDon* tam = hien_tai;
            hien_tai = hien_tai->ke_tiep;
            delete tam;
        }
        delete dau;
        dau = nullptr;
    }
    
    // Chèn nút vào danh sách
    void chen(int gia_tri) {
        // Tạo nút mới
        NutDon* nut_moi = new NutDon(gia_tri);
        
        // Nếu danh sách rỗng
        if (dau == nullptr) {
            dau = nut_moi;
            dau->ke_tiep = dau;  // Tự trỏ đến chính mình để tạo vòng
            return;
        }
        
        // Tìm nút cuối cùng
        NutDon* hien_tai = dau;
        while (hien_tai->ke_tiep != dau) {
            hien_tai = hien_tai->ke_tiep;
        }
        
        // Chèn nút mới
        hien_tai->ke_tiep = nut_moi;
        nut_moi->ke_tiep = dau;
    }
    
    // Xóa nút có giá trị xác định
    void xoa(int gia_tri) {
        // Nếu danh sách rỗng, không thể xóa
        if (dau == nullptr) {
            std::cout << "Danh sách rỗng, không thể xóa" << std::endl;
            return;
        }
        
        // Nếu xóa nút đầu
        if (dau->gia_tri == gia_tri) {
            // Nếu danh sách chỉ có một nút
            if (dau->ke_tiep == dau) {
                delete dau;
                dau = nullptr;
                return;
            }
            
            // Tìm nút cuối cùng
            NutDon* hien_tai = dau;
            while (hien_tai->ke_tiep != dau) {
                hien_tai = hien_tai->ke_tiep;
            }
            
            // Cập nhật liên kết
            NutDon* tam = dau;
            dau = dau->ke_tiep;
            hien_tai->ke_tiep = dau;
            
            // Giải phóng bộ nhớ
            delete tam;
            return;
        }
        
        // Tìm nút cần xóa
        NutDon* hien_tai = dau;
        while (hien_tai->ke_tiep != dau && hien_tai->ke_tiep->gia_tri != gia_tri) {
            hien_tai = hien_tai->ke_tiep;
        }
        
        // Nếu tìm thấy nút cần xóa
        if (hien_tai->ke_tiep != dau) {
            NutDon* tam = hien_tai->ke_tiep;
            hien_tai->ke_tiep = tam->ke_tiep;
            delete tam;
        } else {
            std::cout << "Không tìm thấy nút có giá trị " << gia_tri << std::endl;
        }
    }
    
    // Hiển thị danh sách
    void hienThi() {
        if (dau == nullptr) {
            std::cout << "Danh sách rỗng" << std::endl;
            return;
        }
        
        NutDon* hien_tai = dau;
        std::cout << "Nội dung danh sách vòng: ";
        do {
            std::cout << hien_tai->gia_tri << " -> ";
            hien_tai = hien_tai->ke_tiep;
        } while (hien_tai != dau);
        std::cout << "Quay về đầu" << std::endl;
    }
};

4. Các thao tác cơ bản với Danh sách liên kết

Danh sách liên kết hỗ trợ nhiều thao tác cơ bản, bao gồm chèn, xóa, duyệt và tìm kiếm.

4.1 Thao tác chèn

Thao tác chèn vào danh sách liên kết có thể chia thành ba trường hợp: chèn vào đầu, chèn vào cuối và chèn vào vị trí xác định.

Chèn vào đầu:

1. Tạo nút mới
2. Đặt con trỏ next của nút mới trỏ đến nút đầu hiện tại
3. Cập nhật con trỏ đầu trỏ đến nút mới

void chenDau(int gia_tri) {
    // Tạo nút mới
    NutDon* nut_moi = new NutDon(gia_tri);
    
    // Nếu danh sách rỗng, nút mới là nút đầu
    if (dau == nullptr) {
        dau = nut_moi;
        return;
    }
    
    // Ngược lại, chèn nút mới vào đầu
    nut_moi->ke_tiep = dau;
    dau = nut_moi;
}

Chèn vào cuối:

1. Tạo nút mới
2. Nếu danh sách rỗng, nút mới là nút đầu
3. Ngược lại, duyệt đến nút cuối cùng của danh sách
4. Đặt con trỏ next của nút cuối hiện tại trỏ đến nút mới

void chenCuoi(int gia_tri) {
    // Tạo nút mới
    NutDon* nut_moi = new NutDon(gia_tri);
    
    // Nếu danh sách rỗng, nút mới là nút đầu
    if (dau == nullptr) {
        dau = nut_moi;
        return;
    }
    
    // Tìm nút cuối cùng của danh sách
    NutDon* hien_tai = dau;
    while (hien_tai->ke_tiep != nullptr) {
        hien_tai = hien_tai->ke_tiep;
    }
    
    // Nối nút mới vào nút cuối cùng
    hien_tai->ke_tiep = nut_moi;
}

Chèn vào vị trí xác định:

1. Nếu vị trí là 0, tương đương chèn vào đầu
2. Tạo nút mới
3. Duyệt đến nút đứng trước vị trí cần chèn
4. Cập nhật con trỏ, chèn nút mới vào vị trí xác định

void chenViTri(int vi_tri, int gia_tri) {
    // Nếu vị trí là 0, tương đương chèn vào đầu
    if (vi_tri == 0) {
        chenDau(gia_tri);
        return;
    }
    
    // Tạo nút mới
    NutDon* nut_moi = new NutDon(gia_tri);
    
    // Tìm nút đứng trước vị trí cần chèn
    NutDon* hien_tai = dau;
    for (int i = 0; i < vi_tri - 1 && hien_tai != nullptr; i++) {
        hien_tai = hien_tai->ke_tiep;
    }
    
    // Nếu vị trí vượt quá độ dài danh sách, hoặc danh sách rỗng
    if (hien_tai == nullptr) {
        std::cout << "Vị trí không hợp lệ" << std::endl;
        delete nut_moi;
        return;
    }
    
    // Chèn nút mới
    nut_moi->ke_tiep = hien_tai->ke_tiep;
    hien_tai->ke_tiep = nut_moi;
}

4.2 Thao tác xóa

Thao tác xóa trong danh sách liên kết cũng có thể chia thành ba trường hợp: xóa nút đầu, xóa nút cuối và xóa nút ở vị trí xác định.

Xóa nút đầu:

1. Nếu danh sách rỗng, không thể xóa
2. Lưu nút đầu hiện tại
3. Cập nhật con trỏ đầu trỏ đến nút tiếp theo
4. Giải phóng bộ nhớ nút đầu cũ

void xoaDau() {
    // Nếu danh sách rỗng, không thể xóa
    if (dau == nullptr) {
        std::cout << "Danh sách rỗng, không thể xóa" << std::endl;
        return;
    }
    
    // Lưu nút đầu
    NutDon* tam = dau;
    
    // Cập nhật con trỏ đầu
    dau = dau->ke_tiep;
    
    // Giải phóng bộ nhớ nút đầu cũ
    delete tam;
}

Xóa nút cuối:

1. Nếu danh sách rỗng, không thể xóa
2. Nếu danh sách chỉ có một nút, xóa nút đầu và đặt con trỏ đầu bằng nullptr
3. Ngược lại, duyệt đến nút áp chót
4. Xóa nút cuối và đặt con trỏ next của nút áp chót bằng nullptr

void xoaCuoi() {
    // Nếu danh sách rỗng, không thể xóa
    if (dau == nullptr) {
        std::cout << "Danh sách rỗng, không thể xóa" << std::endl;
        return;
    }
    
    // Nếu danh sách chỉ có một nút
    if (dau->ke_tiep == nullptr) {
        delete dau;
        dau = nullptr;
        return;
    }
    
    // Tìm nút áp chót
    NutDon* hien_tai = dau;
    while (hien_tai->ke_tiep->ke_tiep != nullptr) {
        hien_tai = hien_tai->ke_tiep;
    }
    
    // Xóa nút cuối cùng
    delete hien_tai->ke_tiep;
    hien_tai->ke_tiep = nullptr;
}

Xóa nút ở vị trí xác định:

1. Nếu danh sách rỗng, không thể xóa
2. Nếu xóa nút đầu, gọi hàm xoaDau()
3. Ngược lại, duyệt đến nút đứng trước vị trí cần xóa
4. Cập nhật con trỏ, bỏ qua nút cần xóa
5. Giải phóng bộ nhớ nút cần xóa

void xoaViTri(int vi_tri) {
    // Nếu danh sách rỗng, không thể xóa
    if (dau == nullptr) {
        std::cout << "Danh sách rỗng, không thể xóa" << std::endl;
        return;
    }
    
    // Nếu xóa nút đầu
    if (vi_tri == 0) {
        xoaDau();
        return;
    }
    
    // Tìm nút đứng trước vị trí cần xóa
    NutDon* hien_tai = dau;
    for (int i = 0; i < vi_tri - 1 && hien_tai != nullptr && hien_tai->ke_tiep != nullptr; i++) {
        hien_tai = hien_tai->ke_tiep;
    }
    
    // Nếu vị trí không hợp lệ
    if (hien_tai == nullptr || hien_tai->ke_tiep == nullptr) {
        std::cout << "Vị trí không hợp lệ" << std::endl;
        return;
    }
    
    // Lưu nút cần xóa
    NutDon* tam = hien_tai->ke_tiep;
    
    // Cập nhật liên kết
    hien_tai->ke_tiep = tam->ke_tiep;
    
    // Giải phóng bộ nhớ nút
    delete tam;
}

4.3 Thao tác duyệt

Duyệt danh sách liên kết là quá trình truy cập từng nút trong danh sách, thường được sử dụng để hiển thị nội dung danh sách hoặc xử lý dữ liệu trong các nút.

void hienThi() {
    NutDon* hien_tai = dau;
    
    if (hien_tai == nullptr) {
        std::cout << "Danh sách rỗng" << std::endl;
        return;
    }
    
    std::cout << "Nội dung danh sách: ";
    while (hien_tai != nullptr) {
        std::cout << hien_tai->gia_tri << " -> ";
        hien_tai = hien_tai->ke_tiep;
    }
    std::cout << "NULL" << std::endl;
}

4.4 Thao tác tìm kiếm

Tìm kiếm trong danh sách liên kết là quá trình tìm nút có giá trị xác định, thường trả về vị trí hoặc con trỏ đến nút đó.

int timKiem(int gia_tri) {
    NutDon* hien_tai = dau;
    int vi_tri = 0;
    
    // Duyệt danh sách
    while (hien_tai != nullptr) {
        // Nếu tìm thấy giá trị, trả về vị trí
        if (hien_tai->gia_tri == gia_tri) {
            return vi_tri;
        }
        hien_tai = hien_tai->ke_tiep;
        vi_tri++;
    }
    
    // Không tìm thấy, trả về -1
    return -1;
}

5. Các thao tác nâng cao với Danh sách liên kết

Ngoài các thao tác cơ bản, danh sách liên kết còn hỗ trợ một số thao tác nâng cao như đảo ngược danh sách, phát hiện vòng lặp, tìm nút giữa và hợp nhất danh sách liên kết đã sắp xếp.

5.1 Đảo ngược danh sách liên kết

Đảo ngược danh sách liên kết là quá trình đảo ngược hướng của danh sách, làm cho nút đầu tiên trở thành nút cuối cùng và ngược lại.

void daoNguoc() {
    NutDon* truoc = nullptr;
    NutDon* hien_tai = dau;
    NutDon* tiep_theo = nullptr;
    
    while (hien_tai != nullptr) {
        // Lưu nút tiếp theo
        tiep_theo = hien_tai->ke_tiep;
        
        // Đảo ngược con trỏ của nút hiện tại
        hien_tai->ke_tiep = truoc;
        
        // Di chuyển con trỏ
        truoc = hien_tai;
        hien_tai = tiep_theo;
    }
    
    // Cập nhật con trỏ đầu
    dau = truoc;
}

5.2 Phát hiện vòng lặp

Phát hiện vòng lặp trong danh sách liên kết là kiểm tra xem có tồn tại một vòng lặp trong danh sách (tức là nút nào đó trong danh sách có con trỏ next trỏ đến một nút đứng trước nó). Một phương pháp phổ biến là thuật thuật rùa và thỏ của Floyd (phương pháp con trỏ nhanh-chậm).

bool coVong() {
    if (dau == nullptr || dau->ke_tiep == nullptr) {
        return false;
    }
    
    NutDon* cham = dau;      // Con trỏ chậm, di chuyển một bước mỗi lần
    NutDon* nhanh = dau;    // Con trỏ nhanh, di chuyển hai bước mỗi lần
    
    while (nhanh != nullptr && nhanh->ke_tiep != nullptr) {
        cham = cham->ke_tiep;          // Con trỏ chậm di chuyển một bước
        nhanh = nhanh->ke_tiep->ke_tiep;    // Con trỏ nhanh di chuyển hai bước
        
        // Nếu hai con trỏ gặp nhau, có vòng lặp
        if (cham == nhanh) {
            return true;
        }
    }
    
    // Nếu con trỏ nhanh đến cuối danh sách, không có vòng lặp
    return false;
}

5.3 Tìm nút giữa

Tìm nút giữa của danh sách liên kết cũng có thể sử dụng phương pháp con trỏ nhanh-chậm, với con trỏ nhanh di chuyển hai bước và con trỏ chậm di chuyển một bước, khi con trỏ nhanh đến cuối danh sách, con trỏ chậm sẽ ở nút giữa.

NutDon* timGiua() {
    if (dau == nullptr) {
        return nullptr;
    }
    
    NutDon* cham = dau;      // Con trỏ chậm, di chuyển một bước mỗi lần
    NutDon* nhanh = dau;    // Con trỏ nhanh, di chuyển hai bước mỗi lần
    
    // Khi con trỏ nhanh đến cuối danh sách, con trỏ chậm ở nút giữa
    while (nhanh != nullptr && nhanh->ke_tiep != nullptr) {
        cham = cham->ke_tiep;          // Con trỏ chậm di chuyển một bước
        nhanh = nhanh->ke_tiep->ke_tiep;    // Con trỏ nhanh di chuyển hai bước
    }
    
    return cham;    // Trả về nút giữa
}

5.4 Hợp nhất hai danh sách liên kết đã sắp xếp

Hợp nhất hai danh sách liên kết đã sắp xếp là quá trình kết hợp hai danh sách đã sắp xếp thành một danh sách mới vẫn được sắp xếp.

NutDon* hopHaiDanhSachDaSapXep(NutDon* l1, NutDon* l2) {
    // Tạo một nút giả làm đầu của danh sách hợp nhất
    NutDon gia(0);
    NutDon* duoi = &gia;
    
    // So sánh các nút của hai danh sách, thêm nút nhỏ hơn vào danh sách hợp nhất
    while (l1 != nullptr && l2 != nullptr) {
        if (l1->gia_tri <= l2->gia_tri) {
            duoi->ke_tiep = l1;
            l1 = l1->ke_tiep;
        } else {
            duoi->ke_tiep = l2;
            l2 = l2->ke_tiep;
        }
        duoi = duoi->ke_tiep;
    }
    
    // Thêm các nút còn lại vào danh sách hợp nhất
    if (l1 != nullptr) {
        duoi->ke_tiep = l1;
    } else {
        duoi->ke_tiep = l2;
    }
    
    return gia.ke_tiep;  // Trả về danh sách đã hợp nhất
}

6. Ứng dụng thực tế của Danh sách liên kết

Danh sách liên kết có nhiều ứng dụng thực tế, dưới đây là một số ứng dụng phổ biến.

6.1 Danh sách phát nhạc

Danh sách phát nhạc là một ứng dụng điển hình của danh sách liên kết, đặc biệt là danh sách liên kết đôi, có thể hỗ trợ phát tiếp, phát lùi, phát vòng, v.v.

// Nút chứa thông tin bài hát
struct BaiHat {
    std::string ten_bai_hat;   // Tên bài hát
    std::string ca_si;         // Ca sĩ
    int thoi_luong;            // Thời lượng (giây)
    BaiHat* truoc;             // Trỏ đến bài hát trước
    BaiHat* sau;               // Trỏ đến bài hát sau
    
    // Hàm khởi tạo
    BaiHat(const std::string& t, const std::string& c, int tl) 
        : ten_bai_hat(t), ca_si(c), thoi_luong(tl), truoc(nullptr), sau(nullptr) {}
};

// Lớp danh sách phát nhạc
class DanhSachPhatNhac {
private:
    BaiHat* hien_tai;          // Bài hát đang phát
    BaiHat* dau;               // Bài hát đầu tiên trong danh sách
    BaiHat* cuoi;              // Bài hát cuối cùng trong danh sách
    bool lap;                  // Có phát vòng không
    
public:
    // Hàm khởi tạo
    DanhSachPhatNhac() : hien_tai(nullptr), dau(nullptr), cuoi(nullptr), lap(false) {}
    
    // Thêm bài hát vào cuối danh sách phát
    void themBaiHat(const std::string& ten, const std::string& ca_si, int thoi_luong) {
        // Tạo nút mới cho bài hát
        BaiHat* bai_hat_moi = new BaiHat(ten, ca_si, thoi_luong);
        
        // Nếu danh sách phát rỗng
        if (dau == nullptr) {
            dau = bai_hat_moi;
            cuoi = bai_hat_moi;
            hien_tai = bai_hat_moi;  // Đặt bài hát hiện tại là bài hát vừa thêm
        } else {
            // Thêm bài hát mới vào cuối danh sách
            cuoi->sau = bai_hat_moi;
            bai_hat_moi->truoc = cuoi;
            cuoi = bai_hat_moi;
        }
    }
    
    // Phát bài hát tiếp theo
    void phatTiepTheo() {
        if (hien_tai == nullptr) {
            std::cout << "Danh sách phát rỗng, không có bài hát tiếp theo" << std::endl;
            return;
        }
        
        // Nếu đang ở bài hát cuối
        if (hien_tai == cuoi) {
            if (lap) {
                hien_tai = dau;  // Quay về bài hát đầu
            } else {
                std::cout << "Đây là bài hát cuối rồi" << std::endl;
                return;
            }
        } else {
            hien_tai = hien_tai->sau;
        }
        
        std::cout << "Đang phát: " << hien_tai->ten_bai_hat << " - " << hien_tai->ca_si << std::endl;
    }
    
    // Phát bài hát trước đó
    void phatTruocDo() {
        if (hien_tai == nullptr) {
            std::cout << "Danh sách phát rỗng, không có bài hát trước đó" << std::endl;
            return;
        }
        
        // Nếu đang ở bài hát đầu
        if (hien_tai == dau) {
            if (lap) {
                hien_tai = cuoi;  // Quay về bài hát cuối
            } else {
                std::cout << "Đây là bài hát đầu rồi" << std::endl;
                return;
            }
        } else {
            hien_tai = hien_tai->truoc;
        }
        
        std::cout << "Đang phát: " << hien_tai->ten_bai_hat << " - " << hien_tai->ca_si << std::endl;
    }
    
    // Đặt chế độ phát vòng
    void datCheDoLap(bool gia_tri) {
        lap = gia_tri;
    }
};

6.2 Vấn đề vòng tròn Josephus

Vấn đề vòng tròn Josephus là một bài toán cổ điển: N người đứng thành một vòng, bắt đầu từ người đầu tiên đếm số, người đếm đến số M sẽ bị loại, sau đó người tiếp theo tiếp tục đếm, cho đến khi tất cả đều bị loại. Vấn đề này có thể được giải quyết bằng danh sách liên kết vòng.

// Lớp giải quyết vấn đề Josephus
class VongTronJosephus {
private:
    NutDon* dau;    // Điểm bắt đầu của vòng
    int kich_thuoc;  // Số người trong vòng
    
public:
    // Hàm khởi tạo
    VongTronJosephus() : dau(nullptr), kich_thuoc(0) {}
    
    // Tạo vòng gồm n người
    void taoVong(int n) {
        if (n <= 0) {
            return;
        }
        
        // Tạo người đầu tiên
        dau = new NutDon(1);
        NutDon* hien_tai = dau;
        kich_thuoc = 1;
        
        // Tạo những người còn lại và tạo vòng
        for (int i = 2; i <= n; i++) {
            NutDon* nguoi_moi = new NutDon(i);
            hien_tai->ke_tiep = nguoi_moi;
            hien_tai = nguoi_moi;
            kich_thuoc++;
        }
        
        // Người cuối cùng trỏ đến người đầu tiên, tạo thành vòng
        hien_tai->ke_tiep = dau;
    }
    
    // Giải quyết vấn đề Josephus, trả về thứ tự bị loại
    std::vector<int> giaiPhap(int m) {
        std::vector<int> ket_qua;
        
        if (dau == nullptr) {
            return ket_qua;
        }
        
        NutDon* hien_tai = dau;
        NutDon* truoc = nullptr;
        
        // Tìm người cuối cùng (người trỏ đến dau)
        truoc = dau;
        while (truoc->ke_tiep != dau) {
            truoc = truoc->ke_tiep;
        }
        
        // Lặp cho đến khi tất cả đều bị loại
        while (kich_thuoc > 0) {
            // Đếm m-1 lần (vì hien_tai đã là người đầu tiên đếm)
            for (int i = 1; i < m; i++) {
                truoc = hien_tai;
                hien_tai = hien_tai->ke_tiep;
            }
            
            // Người đếm đến số m bị loại
            ket_qua.push_back(hien_tai->gia_tri);
            
            // Nếu chỉ còn một người
            if (hien_tai->ke_tiep == hien_tai) {
                delete hien_tai;
                dau = nullptr;
            } else {
                // Loại người hiện tại khỏi vòng
                truoc->ke_tiep = hien_tai->ke_tiep;
                NutDon* tam = hien_tai;
                hien_tai = hien_tai->ke_tiep;  // Người tiếp theo bắt đầu đếm
                delete tam;
            }
            
            kich_thuoc--;
        }
        
        return ket_qua;
    }
};

6.3 Đại diện đa thức

Danh sách liên kết có thể được dùng để biểu diễn đa thức, mỗi nút biểu diễn một hạng của đa thức, chứa hệ số và số mũ.

// Nút chứa thông tin hạng của đa thức
struct HangDaThuc {
    double he_so;    // Hệ số
    int so_mu;       // Số mũ
    HangDaThuc* tiep_theo;  // Trỏ đến hạng tiếp theo
    
    // Hàm khởi tạo
    HangDaThuc(double hs, int sm) : he_so(hs), so_mu(sm), tiep_theo(nullptr) {}
};

// Lớp đa thức
class DaThuc {
private:
    HangDaThuc* dau;  // Hạng đầu tiên của đa thức
    
public:
    // Hàm khởi tạo
    DaThuc() : dau(nullptr) {}
    
    // Thêm một hạng vào đa thức
    void themHang(double he_so, int so_mu) {
        // Nếu hệ số là 0, không thêm
        if (he_so == 0) {
            return;
        }
        
        // Tạo hạng mới
        HangDaThuc* hang_moi = new HangDaThuc(he_so, so_mu);
        
        // Nếu đa thức rỗng
        if (dau == nullptr) {
            dau = hang_moi;
            return;
        }
        
        // Nếu số mũ của hạng mới lớn hơn số mũ của hạng đầu, chèn vào đầu
        if (so_mu > dau->so_mu) {
            hang_moi->tiep_theo = dau;
            dau = hang_moi;
            return;
        }
        
        // Tìm vị trí chèn
        HangDaThuc* hien_tai = dau;
        while (hien_tai->tiep_theo != nullptr && hien_tai->tiep_theo->so_mu > so_mu) {
            hien_tai = hien_tai->tiep_theo;
        }
        
        // Nếu đã tồn tại hạng có cùng số mũ, hợp nhất hệ số
        if (hien_tai->so_mu == so_mu) {
            hien_tai->he_so += he_so;
            delete hang_moi;
            
            // Nếu sau khi hợp nhất hệ số là 0, xóa hạng đó
            if (hien_tai->he_so == 0) {
                if (hien_tai == dau) {
                    dau = dau->tiep_theo;
                    delete hien_tai;
                } else {
                    HangDaThuc* truoc = dau;
                    while (truoc->tiep_theo != hien_tai) {
                        truoc = truoc->tiep_theo;
                    }
                    truoc->tiep_theo = hien_tai->tiep_theo;
                    delete hien_tai;
                }
            }
        } else if (hien_tai->tiep_theo != nullptr && hien_tai->tiep_theo->so_mu == so_mu) {
            hien_tai->tiep_theo->he_so += he_so;
            delete hang_moi;
            
            // Nếu sau khi hợp nhất hệ số là 0, xóa hạng đó
            if (hien_tai->tiep_theo->he_so == 0) {
                HangDaThuc* tam = hien_tai->tiep_theo;
                hien_tai->tiep_theo = tam->tiep_theo;
                delete tam;
            }
        } else {
            // Chèn hạng mới
            hang_moi->tiep_theo = hien_tai->tiep_theo;
            hien_tai->tiep_theo = hang_moi;
        }
    }
    
    // Cộng hai đa thức
    DaThuc operator+(const DaThuc& khac) const {
        DaThuc ket_qua;
        
        // Thêm tất cả các hạng của đa thức hiện tại
        HangDaThuc* hien_tai = dau;
        while (hien_tai != nullptr) {
            ket_qua.themHang(hien_tai->he_so, hien_tai->so_mu);
            hien_tai = hien_tai->tiep_theo;
        }
        
        // Thêm tất cả các hạng của đa thức kia
        hien_tai = khac.dau;
        while (hien_tai != nullptr) {
            ket_qua.themHang(hien_tai->he_so, hien_tai->so_mu);
            hien_tai = hien_tai->tiep_theo;
        }
        
        return ket_qua;
    }
    
    // Tính giá trị của đa thức tại x
    double tinhGiaTri(double x) const {
        double ket_qua = 0.0;
        HangDaThuc* hien_tai = dau;
        
        while (hien_tai != nullptr) {
            ket_qua += hien_tai->he_so * std::pow(x, hien_tai->so_mu);
            hien_tai = hien_tai->tiep_theo;
        }
        
        return ket_qua;
    }
};

6.4 Triển khai bộ đệm LRU

Bộ đệm LRU (Least Recently Used - ít được sử dụng gần đây nhất) là một chính sách bộ đệm phổ biến, khi bộ đệm đầy sẽ xóa mục ít được sử dụng nhất. Bộ đệm LRU có thể được triển khai bằng danh sách liên kết đôi và bảng băm.

// Lớp bộ đệm LRU
class BoDemLRU {
private:
    int suc_chua;                               // Dung lượng bộ đệm
    NutDoi* dau;                               // Nút đầu (được sử dụng gần nhất)
    NutDoi* cuoi;                              // Nút cuối (ít được sử dụng gần nhất)
    std::unordered_map<int, NutDoi*> bang_bam; // Bảng băm, để tìm nút trong thời gian O(1)
    
public:
    // Hàm khởi tạo
    BoDemLRU(int sc) : suc_chua(sc), dau(nullptr), cuoi(nullptr) {}
    
    // Lấy giá trị từ bộ đệm
    int lay(int khoa) {
        // Nếu khóa không tồn tại
        if (bang_bam.find(khoa) == bang_bam.end()) {
            return -1;
        }
        
        // Lấy nút
        NutDoi* nut = bang_bam[khoa];
        int gia_tri = nut->gia_tri;
        
        // Đưa nút lên đầu danh sách (được sử dụng gần nhất)
        diLenDau(nut);
        
        return gia_tri;
    }
    
    // Đặt giá trị vào bộ đệm
    void dat(int khoa, int gia_tri) {
        // Nếu khóa đã tồn tại
        if (bang_bam.find(khoa) != bang_bam.end()) {
            // Cập nhật giá trị
            NutDoi* nut = bang_bam[khoa];
            nut->gia_tri = gia_tri;
            
            // Đưa nút lên đầu danh sách
            diLenDau(nut);
            return;
        }
        
        // Nếu bộ đệm đã đầy, xóa mục ít được sử dụng nhất (nút cuối)
        if (bang_bam.size() >= suc_chua) {
            bang_bam.erase(cuoi->gia_tri);
            
            // Nếu chỉ có một nút
            if (dau == cuoi) {
                delete dau;
                dau = nullptr;
                cuoi = nullptr;
            } else {
                NutDoi* tam = cuoi;
                cuoi = cuoi->truoc;
                cuoi->sau = nullptr;
                delete tam;
            }
        }
        
        // Tạo nút mới và thêm vào đầu danh sách
        NutDoi* nut_moi = new NutDoi(gia_tri);
        nut_moi->gia_tri = khoa;  // Sử dụng khóa làm dữ liệu của nút
        
        // Nếu danh sách rỗng
        if (dau == nullptr) {
            dau = nut_moi;
            cuoi = nut_moi;
        } else {
            nut_moi->sau = dau;
            dau->truoc = nut_moi;
            dau = nut_moi;
        }
        
        // Thêm vào bảng băm
        bang_bam[khoa] = nut_moi;
    }
    
private:
    // Đưa nút lên đầu danh sách
    void diLenDau(NutDoi* nut) {
        // Nếu nút đã là nút đầu, không cần di chuyển
        if (nut == dau) {
            return;
        }
        
        // Nếu nút là nút cuối
        if (nut == cuoi) {
            cuoi = nut->truoc;
            cuoi->sau = nullptr;
        } else {
            // Di chuyển nút khỏi vị trí hiện tại
            nut->truoc->sau = nut->sau;
            nut->sau->truoc = nut->truoc;
        }
        
        // Đưa nút vào đầu
        nut->sau = dau;
        nut->truoc = nullptr;
        dau->truoc = nut;
        dau = nut;
    }
};

7. So sánh Danh sách liên kết với các cấu trúc dữ liệu khác

Danh sách liên kết so sánh với các cấu trúc dữ liệu khác như mảng, ngăn xếp, hàng đợi, v.v. có các ưu và nhược điểm riêng.

Đặc điểm	Danh sách liên kết	Mảng
Cấp phát bộ nhớ	Động, không liên tục	Tĩnh, liên tục
Truy cập phần tử	O(n), cần duyệt	O(1), truy cập trực tiếp qua chỉ mục
Chèn/Xóa	O(1), tại vị trí xác định	O(n), cần di chuyển phần tử
Sử dụng bộ nhớ	Mỗi nút cần thêm không gian cho con trỏ	Chỉ cần lưu trữ dữ liệu
Điều chỉnh kích thước	Linh hoạt, có thể mở rộng hoặc thu nhỏ	Kích thước cố định hoặc cần cấp phát lại
Tính cục bộ của bộ nhớ đệm	Kém, các nút phân tán trong bộ nhớ

Danh sách liên kết phù hợp với các tình huống cần chèn và xóa thường xuyên, trong khi mảng phù hợp với các tình huống cần truy cập ngẫu nhiên.

8. Tổng kết và gợi ý học tập nâng cao

Danh sách liên kết là một cấu trúc dữ liệu linh hoạt, có nhiều ứng dụng rộng rãi trong quản lý bộ nhớ, triển khai thuật toán và ứng dụng thực tế. Bài viết này đã giới thiệu chi tiết về khái niệm cơ bản, loại hình, cách triển khai bằng C++ và các ứng dụng thực tế của danh sách liên kết, hy vọng sẽ giúp người đọc hiểu toàn diện về cấu trúc dữ liệu quan trọng này.

Đối với những người đọc muốn học sâu hơn về danh sách liên kết, dưới đây là một số gợi ý:

1. Thực hành là chìa khóa: Hãy tự mình triển khai các loại danh sách liên kết khác nhau và giải quyết một số bài toán kinh điển về danh sách liên kết như đảo ngược, phát hiện vòng lặp, v.v.
2. Học các thuật toán liên quan: Danh sách liên kết là nền tảng của nhiều thuật toán như sắp xếp trộn, sắp xếp topo, v.v. Học các thuật toán này sẽ giúp bạn hiểu sâu hơn về danh sách liên kết.
3. Khám phá ứng dụng thực tế: Hãy thử sử dụng danh sách liên kết trong các dự án thực tế như triển khai một bộ quản lý bộ nhớ đơn giản, hệ thống tệp, v.v.
4. Học các cấu trúc dữ liệu khác: Danh sách liên kết là nền tảng để hiểu các cấu trúc dữ liệu phức tạp hơn như cây, đồ thị. Học các cấu trúc dữ liệu này sẽ mở rộng kiến thức của bạn.
5. Đọc mã nguồn: Hãy đọc mã nguồn triển khai danh sách liên kết trong một số dự án mã nguồn mở như bộ chứa list trong STL, để học hỏi thêm các kỹ thuật và phương pháp tốt nhất.

Danh sách liên kết là một trong những cấu trúc dữ liệu cơ bản và quan trọng nhất trong khoa học máy tính, việc nắm vững nó rất quan trọng để trở thành một lập trình viên giỏi. Hy vọng bài viết này sẽ giúp bạn hiểu và ứng dụng tốt hơn danh sách liên kết.

Tham khảo

1. GeeksforGeeks. "Linked List in C++". https://www.geeksforgeeks.org/cpp-linked-list/
2. Programiz. "Linked List Data Structure". https://www.programiz.com/dsa/linked-list
3. VisuAlgo. "Linked List Visualization". https://visualgo.net/en/list