Khóa học C++ từ cơ bản đến nâng cao

#include <iostream> // Cần cho việc nhập xuất

// Định nghĩa cấu trúc của một Node
struct Node {
    int data;   // Dữ liệu lưu trữ trong node
    Node* next; // Con trỏ tới node tiếp theo
    Node* prev; // Con trỏ tới node trước đó

    // Constructor tiện lợi để khởi tạo node mới
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

#include <iostream>

// Định nghĩa cấu trúc của một Node (như trên)
struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

// Định nghĩa lớp DoublyLinkedList để quản lý danh sách
class DoublyLinkedList {
private:
    Node* head; // Con trỏ tới nút đầu tiên
    Node* tail; // Con trỏ tới nút cuối cùng

public:
    // Constructor: Khởi tạo danh sách rỗng
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    // Destructor: Giải phóng bộ nhớ khi đối tượng DoublyLinkedList bị hủy
    ~DoublyLinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current; // Giải phóng bộ nhớ của node hiện tại
            current = next;  // Di chuyển tới node tiếp theo
        }
        head = nullptr; // Đảm bảo head và tail là nullptr sau khi giải phóng
        tail = nullptr;
        cout << "\nDa giai phong bo nho danh sach." << endl;
    }

    // --- Các phương thức thao tác sẽ được thêm vào đây ---

    // Phương thức hiển thị danh sách (duyệt xuôi)
    void displayForward() const {
        Node* current = head;
        cout << "Danh sach (xuoi): ";
        while (current != nullptr) {
            cout << current->data;
            if (current->next != nullptr) {
                cout << " <-> ";
            }
            current = current->next;
        }
        cout << endl;
    }

    // Phương thức hiển thị danh sách (duyệt ngược)
    void displayBackward() const {
        Node* current = tail; // Bắt đầu từ tail
        cout << "Danh sach (nguoc): ";
        while (current != nullptr) {
            cout << current->data;
            if (current->prev != nullptr) { // Sử dụng prev để di chuyển ngược
                cout << " <-> ";
            }
            current = current->prev;
        }
        cout << endl;
    }

    // --- Các phương thức chèn và xóa sẽ được thêm vào sau ---
};

// Thêm vào trong class DoublyLinkedList:
void insertAtHead(int val) {
    Node* newNode = new Node(val); // 1. Tạo nút mới

    if (head == nullptr) { // Trường hợp danh sách rỗng
        head = newNode;
        tail = newNode; // Nút đầu tiên cũng là nút cuối cùng
    } else { // Trường hợp danh sách không rỗng
        newNode->next = head; // 2. Nút mới trỏ tới head hiện tại
        head->prev = newNode; // 3. Head hiện tại trỏ ngược về nút mới
        head = newNode;       // 4. Cập nhật head là nút mới
    }
    cout << "Da chen " << val << " vao dau danh sach." << endl;
}

// Thêm vào trong class DoublyLinkedList:
void insertAtTail(int val) {
    Node* newNode = new Node(val); // 1. Tạo nút mới

    if (tail == nullptr) { // Trường hợp danh sách rỗng (giống insertAtHead)
        head = newNode;
        tail = newNode;
    } else { // Trường hợp danh sách không rỗng
        newNode->prev = tail; // 2. Nút mới trỏ ngược về tail hiện tại
        tail->next = newNode; // 3. Tail hiện tại trỏ tới nút mới
        tail = newNode;       // 4. Cập nhật tail là nút mới
    }
    cout << "Da chen " << val << " vao cuoi danh sach." << endl;
}

// Thêm vào trong class DoublyLinkedList:
void insertAfterNode(Node* prevNode, int val) {
    // 1. Kiểm tra nếu prevNode không hợp lệ (nullptr)
    if (prevNode == nullptr) {
        cout << "Loi: prevNode khong duoc la nullptr." << endl;
        return;
    }

    // 2. Tạo nút mới
    Node* newNode = new Node(val);

    // 3. Thiết lập con trỏ next và prev cho nút mới
    newNode->next = prevNode->next; // Nút mới trỏ tới nút mà prevNode đang trỏ tới
    newNode->prev = prevNode;       // Nút mới trỏ ngược về prevNode

    // 4. Cập nhật con trỏ next của prevNode
    prevNode->next = newNode;

    // 5. Cập nhật con trỏ prev của nút đứng SAU nút mới (nếu có)
    if (newNode->next != nullptr) {
        newNode->next->prev = newNode;
    } else {
        // Nếu newNode->next là nullptr, tức là newNode được chèn vào cuối danh sách
        tail = newNode; // Cập nhật tail là nút mới
    }
    cout << "Da chen " << val << " sau node co data = " << prevNode->data << "." << endl;
}

// Để sử dụng insertAfterNode, bạn cần tìm được con trỏ đến prevNode.
// Cần thêm phương thức tìm kiếm hoặc truy cập node.
// Tạm thời, ta có thể tìm thủ công hoặc thêm phương thức search.
// Ví dụ đơn giản phương thức search để minh họa:
Node* search(int val) const {
    Node* current = head;
    while (current != nullptr) {
        if (current->data == val) {
            return current; // Trả về con trỏ tới node nếu tìm thấy
        }
        current = current->next;
    }
    return nullptr; // Trả về nullptr nếu không tìm thấy
}

// Thêm vào trong class DoublyLinkedList:
void deleteNode(Node* nodeToDelete) {
    // 1. Kiểm tra nếu nodeToDelete không hợp lệ (nullptr) hoặc danh sách rỗng
    if (head == nullptr || nodeToDelete == nullptr) {
        cout << "Khong the xoa. Danh sach rỗng hoặc node xoa la nullptr." << endl;
        return;
    }

    // 2. Xử lý các con trỏ của nút đứng trước và nút đứng sau nodeToDelete

    // Nếu có nút trước nodeToDelete
    if (nodeToDelete->prev != nullptr) {
        nodeToDelete->prev->next = nodeToDelete->next;
    } else {
        // Nếu nodeToDelete là head, cập nhật head
        head = nodeToDelete->next;
    }

    // Nếu có nút sau nodeToDelete
    if (nodeToDelete->next != nullptr) {
        nodeToDelete->next->prev = nodeToDelete->prev;
    } else {
        // Nếu nodeToDelete là tail, cập nhật tail
        tail = nodeToDelete->prev;
    }

    // 3. Giải phóng bộ nhớ của nodeToDelete
    cout << "Da xoa node co data = " << nodeToDelete->data << "." << endl;
    delete nodeToDelete;
}

// Ví dụ về cách xóa theo giá trị (cần sử dụng search trước)
void deleteByValue(int val) {
    Node* nodeToDelete = search(val); // Tìm node cần xóa
    if (nodeToDelete != nullptr) {
        deleteNode(nodeToDelete); // Gọi phương thức xóa node dựa trên con trỏ
    } else {
        cout << "Khong tim thay node co data = " << val << " de xoa." << endl;
    }
}

#include <iostream>

// --- Cấu trúc Node ---
struct Node {
    int data;
    Node* next;
    Node* prev;
    Node(int val) : data(val), next(nullptr), prev(nullptr) {}
};

// --- Lớp DoublyLinkedList ---
class DoublyLinkedList {
private:
    Node* head;
    Node* tail;

public:
    DoublyLinkedList() : head(nullptr), tail(nullptr) {}

    ~DoublyLinkedList() {
        Node* current = head;
        while (current != nullptr) {
            Node* next = current->next;
            delete current;
            current = next;
        }
        head = nullptr;
        tail = nullptr;
        cout << "\nDa giai phong bo nho danh sach." << endl;
    }

    // Phương thức chèn vào đầu
    void insertAtHead(int val) {
        Node* newNode = new Node(val);
        if (head == nullptr) {
            head = newNode;
            tail = newNode;
        } else {
            newNode->next = head;
            head->prev = newNode;
            head = newNode;
        }
        cout << "Da chen " << val << " vao dau danh sach." << endl;
    }

    // Phương thức chèn vào cuối
    void insertAtTail(int val) {
        Node* newNode = new Node(val);
        if (tail == nullptr) {
            head = newNode;
            tail = newNode;
        } else {
            newNode->prev = tail;
            tail->next = newNode;
            tail = newNode;
        }
        cout << "Da chen " << val << " vao cuoi danh sach." << endl;
    }

     // Phương thức tìm kiếm node theo giá trị
    Node* search(int val) const {
        Node* current = head;
        while (current != nullptr) {
            if (current->data == val) {
                return current;
            }
            current = current->next;
        }
        return nullptr;
    }

    // Phương thức chèn sau một node cho trước
    void insertAfterNode(Node* prevNode, int val) {
        if (prevNode == nullptr) {
            cout << "Loi: prevNode khong duoc la nullptr." << endl;
            return;
        }
        Node* newNode = new Node(val);
        newNode->next = prevNode->next;
        newNode->prev = prevNode;
        prevNode->next = newNode;
        if (newNode->next != nullptr) {
            newNode->next->prev = newNode;
        } else {
            tail = newNode;
        }
        cout << "Da chen " << val << " sau node co data = " << prevNode->data << "." << endl;
    }

    // Phương thức xóa node (dựa trên con trỏ)
    void deleteNode(Node* nodeToDelete) {
        if (head == nullptr || nodeToDelete == nullptr) {
            cout << "Khong the xoa. Danh sach rỗng hoặc node xoa la nullptr." << endl;
            return;
        }

        if (nodeToDelete->prev != nullptr) {
            nodeToDelete->prev->next = nodeToDelete->next;
        } else { // Xoa head
            head = nodeToDelete->next;
        }

        if (nodeToDelete->next != nullptr) {
            nodeToDelete->next->prev = nodeToDelete->prev;
        } else { // Xoa tail
            tail = nodeToDelete->prev;
        }

        cout << "Da xoa node co data = " << nodeToDelete->data << "." << endl;
        delete nodeToDelete;

        // Cập nhật head/tail nếu danh sách trở nên rỗng sau khi xóa
        if (head == nullptr) {
             tail = nullptr;
        }
    }

    // Phương thức xóa node theo giá trị
    void deleteByValue(int val) {
        Node* nodeToDelete = search(val);
        if (nodeToDelete != nullptr) {
            deleteNode(nodeToDelete);
        } else {
            cout << "Khong tim thay node co data = " << val << " de xoa." << endl;
        }
    }


    // Phương thức hiển thị danh sách (duyệt xuôi)
    void displayForward() const {
        Node* current = head;
        cout << "Danh sach (xuoi): ";
        if (current == nullptr) {
             cout << "rong";
        }
        while (current != nullptr) {
            cout << current->data;
            if (current->next != nullptr) {
                cout << " <-> ";
            }
            current = current->next;
        }
        cout << endl;
    }

    // Phương thức hiển thị danh sách (duyệt ngược)
    void displayBackward() const {
        Node* current = tail;
        cout << "Danh sach (nguoc): ";
         if (current == nullptr) {
             cout << "rong";
        }
        while (current != nullptr) {
            cout << current->data;
            if (current->prev != nullptr) {
                cout << " <-> ";
            }
            current = current->prev;
        }
        cout << endl;
    }

}; // Kết thúc class DoublyLinkedList

// --- Hàm main để chạy thử ---
int main() {
    // 1. Khởi tạo danh sách
    DoublyLinkedList dll;
    cout << "Khoi tao danh sach rong." << endl;
    dll.displayForward();

    // 2. Chen vao dau
    cout << "\n--- Chen vao dau ---" << endl;
    dll.insertAtHead(10); // DSLK: 10
    dll.insertAtHead(20); // DSLK: 20 <-> 10
    dll.insertAtHead(5);  // DSLK: 5 <-> 20 <-> 10
    dll.displayForward();
    dll.displayBackward();

    // 3. Chen vao cuoi
    cout << "\n--- Chen vao cuoi ---" << endl;
    dll.insertAtTail(30); // DSLK: 5 <-> 20 <-> 10 <-> 30
    dll.insertAtTail(40); // DSLK: 5 <-> 20 <-> 10 <-> 30 <-> 40
    dll.displayForward();
    dll.displayBackward();

    // 4. Chen sau mot node cho truoc (sau node 20)
    cout << "\n--- Chen sau node 20 ---" << endl;
    Node* node20 = dll.search(20);
    if (node20 != nullptr) {
        dll.insertAfterNode(node20, 25); // DSLK: 5 <-> 20 <-> 25 <-> 10 <-> 30 <-> 40
        dll.displayForward();
        dll.displayBackward();
    } else {
         cout << "Khong tim thay node 20 de chen sau." << endl;
    }

    // 5. Xoa node theo gia tri
    cout << "\n--- Xoa node theo gia tri ---" << endl;
    dll.deleteByValue(10); // Xoa node 10 (o giua)
    dll.displayForward();
    dll.deleteByValue(5);  // Xoa node 5 (head)
    dll.displayForward();
    dll.deleteByValue(40); // Xoa node 40 (tail)
    dll.displayForward();
    dll.deleteByValue(100); // Xoa node khong ton tai
    dll.displayForward();

    // DSLK hien tai: 20 <-> 25 <-> 30

    // Chen them de test xoa cac truong hop khac
    cout << "\n--- Chen lai de test xoa ---" << endl;
    dll.insertAtHead(1); // DSLK: 1 <-> 20 <-> 25 <-> 30
    dll.insertAtTail(50); // DSLK: 1 <-> 20 <-> 25 <-> 30 <-> 50
    dll.displayForward();

    cout << "\n--- Xoa het danh sach ---" << endl;
    dll.deleteByValue(25); // Xoa node 25 (o giua)
    dll.displayForward(); // DSLK: 1 <-> 20 <-> 30 <-> 50
    dll.deleteByValue(1); // Xoa head
    dll.displayForward(); // DSLK: 20 <-> 30 <-> 50
    dll.deleteByValue(50); // Xoa tail
    dll.displayForward(); // DSLK: 20 <-> 30
    dll.deleteByValue(20); // Xoa head moi
    dll.displayForward(); // DSLK: 30
    dll.deleteByValue(30); // Xoa node cuoi cung
    dll.displayForward(); // DSLK: rong


    // Khi doi tuong dll ra khoi pham vi cua main, destructor ~DoublyLinkedList() se tu dong duoc goi
    // de giai phong bo nho.

    return 0;
}