双链表

双链表定义

双链表在结点结构体中包含两个指针：

• 一个指针指向下一个结点位置
• 另一个指针指向前一个结点位置

struct Node {
    int data;
    Node* prev;  // 前驱结点指针
    Node* next;  // 后继结点指针
};

双向链表操作

头插法

1. 将新结点的next指针指向原首结点
2. 将原首结点的prev指针指向新结点
3. 将链表指针list指向新结点

尾插法

1. 找到尾结点位置
2. 让尾结点的next指针指向新结点
3. 让新结点的prev指针指向尾结点

中间插入法

1. 将新结点的prev指针指向临时指针（插入位置前结点）
2. 将新结点的next指针指向临时指针的next结点
3. 将临时指针的next指针指向新结点
4. 将新结点下一个结点的prev指针指向新结点

删除结点

删除首结点：

1. 将list指针更新到首结点的下一个结点
2. 释放原首结点
3. 将新首结点的prev指针置空

删除非首结点：

1. 将前结点的next指针指向被删结点的下一个结点
2. 将被删结点下一个结点的prev指针指向前结点
3. 释放被删结点

void deleteNode(Node*& head, Node* delNode) {
    if(head == nullptr || delNode == nullptr) return;
    
    // 情况1：删除首结点
    if(head == delNode) {
        head = delNode->next;
        if(head != nullptr) head->prev = nullptr;
    }
    // 情况2：删除中间或尾结点
    else {
        if(delNode->prev != nullptr) 
            delNode->prev->next = delNode->next;
        if(delNode->next != nullptr) 
            delNode->next->prev = delNode->prev;
    }
    
    delete delNode;
}

算法练习平台

• 牛客网：https://www.nowcoder.com/
• 力扣：https://leetcode.cn/

作业

将双向链表和单链表封装成模板类，实现以下功能：

template <typename T>
class DoublyLinkedList {
private:
    struct Node {
        T data;
        Node* prev;
        Node* next;
        Node(T val) : data(val), prev(nullptr), next(nullptr) {}
    };
    
    Node* head;
    Node* tail;
    size_t size;
    
public:
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    // 插入操作
    void push_front(T val);
    void push_back(T val);
    void insert(size_t pos, T val);
    
    // 删除操作
    void pop_front();
    void pop_back();
    void erase(size_t pos);
    
    // 访问操作
    T& front();
    T& back();
    T& at(size_t pos);
    
    // 容量操作
    size_t length() const { return size; }
    bool empty() const { return size == 0; }
    
    // 遍历操作
    void traverse() const;
    
    ~DoublyLinkedList() {
        while(head) {
            Node* temp = head;
            head = head->next;
            delete temp;
        }
    }
};