题解 | #【模板】链表#

链表用了双指针的节点，如果用单指针，在插入的时候可以利用两个指针来遍历列表，因为需要插入的位置是在找到的位置之前。

#include <iostream>
using namespace std;
struct node {
    int data = 0;
    node* pfront = nullptr;
    node* prear = nullptr;
};
class linked_list {
  private:
    node* head = new node;
  public:
    void insert(int x, int y) {
        node* tmp = new node; // new一个节点
        tmp->data = y;
        node* p = head;
        bool find = false;
        // 找值为x的节点
        while (p->prear != nullptr) {
            p = p->prear;
            if (p->data == x) {
                find = true;
                break;
            }
        }
        // 插入tmp
        if (find == true) {
            node* front = p->pfront;
            front->prear = tmp;
            tmp->pfront = front;
            p->pfront = tmp;
            tmp->prear = p;
        } else { // 包含了空链表的情况
            p->prear = tmp;
            tmp->pfront = p;
        }
    }
    void del(int x) {
        node* p = head;
        while (p->prear != nullptr) {
            p = p->prear;
            if (p->data == x) {
                if (p->prear != nullptr) {
                    p->pfront->prear = p->prear;
                    p->prear->pfront = p->pfront; // 非后一个节点时，需要设置后一个节点的pfront指针
                } else {
                    p->pfront->prear = p->prear; 
                }
                free(p); // 释放p的空间
                break;
            }
        }
    }
    void show() {
        if (head->prear == nullptr)
            cout << "NULL";
        else {
            node* p = head;
            while (p->prear != nullptr) {
                p = p->prear;
                cout << p->data << ' ';
            }
        }
    }
};
int main() {
    int n, x, y;
    cin >> n;
    linked_list ll;
    for (int i = 0; i < n; i++) {
        string op;
        cin >> op;
        if (op == "insert") {
            cin >> x >> y;
            ll.insert(x, y);
        } else if (op == "delete") {
            cin >> x;
            ll.del(x);
        }
    }
    ll.show();
    return 0;
}