C++双向链表实现方法详解

• 节点结构包含 data、next 和 prev 指针
• 链表类维护 head 和 tail 指针，也可只用 head 实现，但维护 tail 可提升尾部操作效率

#include 
using namespace std;
// 定义节点结构
struct ListNode {
int data;
ListNode next;
ListNode prev;
ListNode(int val) : data(val), next(nullptr), prev(nullptr) {}
};
// 双向链表类
class DoublyLinkedList {
private:
ListNode head;
ListNode tail;
public:
DoublyLinkedList() : head(nullptr), tail(nullptr) {}
// 在链表末尾插入节点
void push_back(int val) {
    ListNode* newNode = new ListNode(val);
    if (!head) {
        head = tail = newNode;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
}

// 在链表头部插入节点
void push_front(int val) {
    ListNode* newNode = new ListNode(val);
    if (!head) {
        head = tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
}

// 删除指定值的节点
bool remove(int val) {
    ListNode* curr = head;
    while (curr) {
        if (curr->data == val) {
            if (curr->prev) {
                curr->prev->next = curr->next;
            } else {
                head = curr->next;  // 当前是头节点
            }

            if (curr->next) {
                curr->next->prev = curr->prev;
            } else {
                tail = curr->prev;  // 当前是尾节点
            }

            delete curr;
            return true;
        }
        curr = curr->next;
    }
    return false;  // 未找到
}

// 打印链表（正向）
void print_forward() {
    ListNode* curr = head;
    while (curr) {
        cout << curr->data << " ";
        curr = curr->next;
    }
    cout << endl;
}

// 打印链表（反向）
void print_backward() {
    ListNode* curr = tail;
    while (curr) {
        cout << curr->data << " ";
        curr = curr->prev;
    }
    cout << endl;
}

// 析构函数：释放所有节点内存
~DoublyLinkedList() {
    ListNode* curr = head;
    while (curr) {
        ListNode* next = curr->next;
        delete curr;
        curr = next;
    }
}
};

插入操作：
• push_back 在尾部添加，需更新 tail 指针
• push_front 在头部添加，需更新 head 指针

删除操作：

• 需处理四种情况：唯一节点、头节点、尾节点、中间节点
• 注意指针判空，避免访问非法内存

遍历方向：

• 从 head 开始 next 遍历为正向
• 从 tail 开始 prev 遍历为反向

int main() {
    DoublyLinkedList dll;
    dll.push_back(1);
    dll.push_back(2);
    dll.push_front(0);
    dll.print_forward();   // 输出: 0 1 2
    dll.print_backward();  // 输出: 2 1 0
dll.remove(1);
dll.print_forward();   // 输出: 0 2

return 0;
}