code

#include <bits/stdc++.h>
using namespace std;

//1.Khai báo cấu trúc danh sách liên kết đôi
struct Node {
    int data;
    struct Node *next;
    struct Node *previous;
};
struct List {
    Node *head, *tail;
};

//2.Khởi tạo danh sách
void CreateList (List &l) { //các thao tác tạo, thêm, xóa thì phải truyền tham chiếu &
    l.head= l.tail=nullptr; //chưa tạo node nào nên danh sách sẽ null
}

//3.Khởi tạo node

Node *CreateNode (int x) { //x là dữ liệu đưa vào data
    //Cấp phát động cho node mới
    Node *p= new Node;

    //Khởi tạo giá trị ban đầu
    p->data= x; //Lưu dữ liệu vào data
    p->next= nullptr;
    p->previous= nullptr;
    // node vừa tạo chưa thêm vào danh sách nên chưa liên kết với phần tử nào cả nên phần liên kết gán bằng NULL

    return p;
}

//4.Thêm node mới

void AddTail (List &l, Node *p) {
    if (l.head == nullptr)
    {
        l.head = l.tail = p;
    }
    else //Ngược lại,
    {
        l.tail->next= p; //Trỏ liên kết sau tail vào p
        p->previous= l.tail;//Trỏ liên kết trước p vào tail
        l.tail= p; //Gán tail bằng node mới p
    }
}

//5. Nhập dữ liệu
void InputList (List &l, int n) {
    for(int i=1; i<=n; i++) {
        //Nhập dữ liệu cho x
        int x;//Khai báo biến x sau mỗi vòng for
        cout<<"Nhap gia tri node thu "<<i<<": ";
        cin>>x;
        //Tạo và truyền data vào node
        Node *p= CreateNode(x); //Hàm CreateNode trả về p
        //Thêm node vừa tạo vào cuối danh sách
        AddTail(l, p);
    }
}

//6. Xuất dữ liệu
void OutputList(List l)
{
    cout<<"Danh sach la: ";
    for(Node *i= l.head; i!= nullptr; i=i->next){ //Khởi tạo con trỏ p chạy từ đầu đến đuôi (null)
        cout<<i->data<<"  ";
    }
}


//7. Xóa node

//a. Xóa ở đầu
void DeleteHead(List &l){
    //Nếu rỗng, list rỗng
    if (l.head == nullptr)      l.tail= nullptr;
    else {
        Node *temp= l.head;//Trỏ temp vào head gốc
        l.head=l.head->next;//Đẩy head sang node next
        l.head->previous= nullptr; //Node trước head mới là NULL
        delete temp;
    }
}

//b. Xóa ở cuối

void DeleteTail(List &l){
    Node *temp;
        if(l.tail!= nullptr){
            temp= l.tail;
            l.tail= l.tail->previous;
            l.tail->next= nullptr;
            delete temp;
            if ( l.head == nullptr) l.tail = nullptr;
        }
}

//c. Xóa node p nằm sau node q
void DeleteNode(List &l, Node *q){
    Node *p;
    p = q->next;
    q -> next = p -> next;
    if ( p == l.tail ) l.tail = q;
    else p -> next -> previous = q;
    delete p;
}

//d. Xóa tự do
void DeleteAtK(List &l, int dataK){
    if(dataK==l.head->data)
        DeleteHead(l);
    else if(dataK==l.tail->data)
        DeleteTail(l);
    else for(Node *k=l.head; k!= l.tail; k=k->next){
            if(dataK==k->next->data)
                DeleteNode(l, k-1);
        }

}

int main() {
    List l{};
    CreateList(l);
    int n, a;
    cout<<"\nNhap so phan tu (node) muon tao: ";
    cin>>n;
    InputList(l, n);
    OutputList(l);

    int dataK;
    cout<<"\nNhap node can xoa:";
    cin>>dataK;
    DeleteAtK(l, dataK);
    cout<<"\nDanh sach sau khi xoa: ";
    OutputList(l);
    return 0;
}