C++实现一个双向链表

#include using namespace std;

// 双向链表节点结构体 struct ListNode { int val; ListNode *prev; // 前驱指针 ListNode *next; // 后继指针 ListNode(int x) : val(x), prev(NULL), next(NULL) {} };

// 双向链表类定义 class LinkedList { private: ListNode *head; // 头结点指针 ListNode *tail; // 尾节点指针 int size; // 链表长度 public: // 构造函数 LinkedList() { head = NULL; tail = NULL; size = 0; }

// 插入节点
void insertNode(int val) {
    ListNode *newNode = new ListNode(val); // 创建一个新节点
    if (head == NULL) { // 如果链表为空
        head = newNode;
        tail = newNode;
    }
    else {
        tail->next = newNode; // 在尾节点后插入新节点
        newNode->prev = tail; // 新节点的前驱指向尾节点
        tail = newNode; // 更新尾节点指针
    }
    size++; // 更新链表长度
}

// 删除节点
void deleteNode(int val) {
    ListNode *p = head;
    while (p) {
        if (p->val == val) { // 找到要删除的节点
            if (p == head) { // 如果要删除的节点是头结点
                head = p->next;
                if (head) head->prev = NULL; // 更新新的头结点的前驱指针
            }
            else if (p == tail) { // 如果要删除的节点是尾节点
                tail = p->prev;
                if (tail) tail->next = NULL; // 更新新的尾节点的后继指针
            }
            else { // 如果要删除的节点不是头结点也不是尾节点
                p->prev->next = p->next;
                p->next->prev = p->prev;
            }
            delete p; // 释放内存
            size--; // 更新链表长度
            return;
        }
        p = p->next;
    }
}

// 打印链表
void printList() {
    ListNode *p = head;
    while (p) {
        cout << p->val << " ";
        p = p->next;
    }
    cout << endl;
}

// 获取链表长度
int getSize() {
    return size;
}

};

int main() { LinkedList list; list.insertNode(1); list.insertNode(2); list.insertNode(3); list.insertNode(4); list.insertNode(5); list.printList(); // 输出：1 2 3 4 5 list.deleteNode(3); list.printList(); // 输出：1 2 4 5 cout << "链表长度：" << list.getSize() << endl; // 输出：4 return 0; }