双向链表的定义，初始化，插入和删除

双向链表是一种数据结构，每个节点有两个指针，分别指向前一个节点和后一个节点。它相比于单向链表可以双向遍历，插入和删除操作可以更加方便地实现。

定义：

struct ListNode{
    int val;
    ListNode *prev;
    ListNode *next;
    ListNode(int x): val(x), prev(nullptr), next(nullptr){}
};

初始化：

ListNode *head = nullptr;
ListNode *tail = nullptr;

插入：
- 在链表头部插入节点

if(head == nullptr){
    head = new ListNode(val);
    tail = head;
} else {
    ListNode *new_node = new ListNode(val);
    new_node->next = head;
    head->prev = new_node;
    head = new_node;
}

- 在链表尾部插入节点

if(head == nullptr){
    head = new ListNode(val);
    tail = head;
} else {
    ListNode *new_node = new ListNode(val);
    tail->next = new_node;
    new_node->prev = tail;
    tail = new_node;
}

- 在指定位置插入节点

ListNode *new_node = new ListNode(val);
ListNode *cur = head;
while(cur != nullptr && cur->val != insert_val){
    cur = cur->next;
}
if(cur == nullptr){
    // 没有找到对应的节点，插入失败
    delete new_node;
} else {
    new_node->prev = cur->prev;
    new_node->next = cur;
    cur->prev->next = new_node;
    cur->prev = new_node;
}

删除：
- 删除链表头部节点

if(head == nullptr) return;
ListNode *temp = head;
head = head->next;
if(head == nullptr){
    tail = nullptr;
} else {
    head->prev = nullptr;
}
delete temp;

- 删除链表尾部节点

if(tail == nullptr) return;
ListNode *temp = tail;
tail = tail->prev;
if(tail == nullptr){
    head = nullptr;
} else {
    tail->next = nullptr;
}
delete temp;

- 删除指定节点

ListNode *cur = head;
while(cur != nullptr && cur->val != delete_val){
    cur = cur->next;
}
if(cur == nullptr){
    // 没有找到对应的节点，删除失败
} else {
    cur->prev->next = cur->next;
    if(cur->next != nullptr){
        cur->next->prev = cur->prev;
    } else {
        tail = cur->prev;
    }
    delete cur;
}