C++ 双链表学习笔记教程

1. 双链表的概念

双链表（Doubly Linked List）是一种常见的线性数据结构，与单链表不同的是，双链表中的每个节点不仅包含指向下一个节点的指针，还包含一个指向其前一个节点的指针。这种结构使得双链表可以双向遍历，在某些操作上比单链表更加灵活。

双链表的节点通常包含三部分：

• 数据域：存储节点的数据
• 前驱指针（prev）：指向当前节点的前一个节点
• 后继指针（next）：指向当前节点的后一个节点

2. 双链表节点的定义

在C++中，我们可以使用结构体来定义双链表的节点：

// 双链表节点结构体
struct Node {
    int data;       // 数据域
    Node* prev;     // 前驱指针
    Node* next;     // 后继指针
    
    // 构造函数
    Node(int val) : data(val), prev(nullptr), next(nullptr) {}
};

3. 双链表类的设计

我们可以设计一个双链表类来封装双链表的各种操作：

class DoublyLinkedList {
private:
    Node* head;  // 头指针
    Node* tail;  // 尾指针
    int size;    // 链表长度
    
public:
    // 构造函数
    DoublyLinkedList() : head(nullptr), tail(nullptr), size(0) {}
    
    // 析构函数
    ~DoublyLinkedList();
    
    // 插入操作
    void insertAtHead(int val);       // 在头部插入
    void insertAtTail(int val);       // 在尾部插入
    void insertAtPosition(int val, int pos);  // 在指定位置插入
    
    // 删除操作
    void deleteAtHead();              // 删除头部节点
    void deleteAtTail();              // 删除尾部节点
    void deleteAtPosition(int pos);   // 删除指定位置节点
    void deleteByValue(int val);      // 删除指定值的节点
    
    // 查找操作
    Node* find(int val);              // 查找指定值的节点
    
    // 遍历操作
    void printForward();              // 从头到尾遍历
    void printBackward();             // 从尾到头遍历
    
    // 其他操作
    int getSize() const { return size; }  // 获取链表长度
    bool isEmpty() const { return size == 0; }  // 判断链表是否为空
    void clear();                     // 清空链表
};

4. 双链表成员函数的实现

下面我们来实现双链表类中的各个成员函数：

// 析构函数
DoublyLinkedList::~DoublyLinkedList() {
    clear();
}

// 在头部插入节点
void DoublyLinkedList::insertAtHead(int val) {
    Node* newNode = new Node(val);
    
    if (isEmpty()) {
        // 链表为空时，头指针和尾指针都指向新节点
        head = tail = newNode;
    } else {
        newNode->next = head;
        head->prev = newNode;
        head = newNode;
    }
    size++;
}

// 在尾部插入节点
void DoublyLinkedList::insertAtTail(int val) {
    Node* newNode = new Node(val);
    
    if (isEmpty()) {
        // 链表为空时，头指针和尾指针都指向新节点
        head = tail = newNode;
    } else {
        tail->next = newNode;
        newNode->prev = tail;
        tail = newNode;
    }
    size++;
}

// 在指定位置插入节点
void DoublyLinkedList::insertAtPosition(int val, int pos) {
    if (pos < 0 || pos > size) {
        cout << "Invalid position!" << endl;
        return;
    }
    
    if (pos == 0) {
        insertAtHead(val);
        return;
    }
    
    if (pos == size) {
        insertAtTail(val);
        return;
    }
    
    Node* newNode = new Node(val);
    Node* current = head;
    
    // 移动到要插入位置的前一个节点
    for (int i = 0; i < pos - 1; i++) {
        current = current->next;
    }
    
    newNode->next = current->next;
    newNode->prev = current;
    current->next->prev = newNode;
    current->next = newNode;
    
    size++;
}

// 删除头部节点
void DoublyLinkedList::deleteAtHead() {
    if (isEmpty()) {
        cout << "List is empty!" << endl;
        return;
    }
    
    Node* temp = head;
    
    if (size == 1) {
        head = tail = nullptr;
    } else {
        head = head->next;
        head->prev = nullptr;
    }
    
    delete temp;
    size--;
}

// 删除尾部节点
void DoublyLinkedList::deleteAtTail() {
    if (isEmpty()) {
        cout << "List is empty!" << endl;
        return;
    }
    
    Node* temp = tail;
    
    if (size == 1) {
        head = tail = nullptr;
    } else {
        tail = tail->prev;
        tail->next = nullptr;
    }
    
    delete temp;
    size--;
}

// 删除指定位置节点
void DoublyLinkedList::deleteAtPosition(int pos) {
    if (isEmpty()) {
        cout << "List is empty!" << endl;
        return;
    }
    
    if (pos < 0 || pos >= size) {
        cout << "Invalid position!" << endl;
        return;
    }
    
    if (pos == 0) {
        deleteAtHead();
        return;
    }
    
    if (pos == size - 1) {
        deleteAtTail();
        return;
    }
    
    Node* current = head;
    
    // 移动到要删除的节点
    for (int i = 0; i < pos; i++) {
        current = current->next;
    }
    
    current->prev->next = current->next;
    current->next->prev = current->prev;
    
    delete current;
    size--;
}

// 删除指定值的节点
void DoublyLinkedList::deleteByValue(int val) {
    if (isEmpty()) {
        cout << "List is empty!" << endl;
        return;
    }
    
    Node* current = head;
    
    // 查找要删除的节点
    while (current != nullptr && current->data != val) {
        current = current->next;
    }
    
    if (current == nullptr) {
        cout << "Value not found!" << endl;
        return;
    }
    
    // 如果是头节点
    if (current == head) {
        deleteAtHead();
        return;
    }
    
    // 如果是尾节点
    if (current == tail) {
        deleteAtTail();
        return;
    }
    
    // 中间节点
    current->prev->next = current->next;
    current->next->prev = current->prev;
    
    delete current;
    size--;
}

// 查找指定值的节点
Node* DoublyLinkedList::find(int val) {
    Node* current = head;
    
    while (current != nullptr) {
        if (current->data == val) {
            return current;
        }
        current = current->next;
    }
    
    return nullptr;  // 未找到
}

// 从头到尾遍历
void DoublyLinkedList::printForward() {
    if (isEmpty()) {
        cout << "List is empty!" << endl;
        return;
    }
    
    Node* current = head;
    cout << "Forward traversal: ";
    
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->next;
    }
    
    cout << endl;
}

// 从尾到头遍历
void DoublyLinkedList::printBackward() {
    if (isEmpty()) {
        cout << "List is empty!" << endl;
        return;
    }
    
    Node* current = tail;
    cout << "Backward traversal: ";
    
    while (current != nullptr) {
        cout << current->data << " ";
        current = current->prev;
    }
    
    cout << endl;
}

// 清空链表
void DoublyLinkedList::clear() {
    Node* current = head;
    Node* next;
    
    while (current != nullptr) {
        next = current->next;
        delete current;
        current = next;
    }
    
    head = tail = nullptr;
    size = 0;
}

5. 双链表的使用示例

下面是一个使用双链表的示例程序，展示了如何创建双链表并使用其各种功能：

6. 双链表的时间复杂度分析

7. 双链表的优缺点

优点

1. 可以双向遍历，灵活性更高
2. 已知节点的情况下，删除操作效率高（无需从头查找前驱节点）
3. 在头部和尾部的插入删除操作效率高

缺点

1. 每个节点需要额外的空间存储前驱指针，内存消耗更大
2. 实现比单链表复杂，需要同时维护prev和next指针

8. 双链表的应用场景

1. 需要频繁进行双向遍历的场景
2. 需要在两端都进行插入删除操作的场景（如实现双端队列）
3. 某些高级数据结构的基础，如红黑树、B+树等
4. 浏览器的前进后退功能实现
5. 文本编辑器中的光标移动实现

通过学习双链表，我们可以更好地理解链表这种数据结构的特性，为学习更复杂的数据结构打下基础。双链表的实现虽然比单链表稍复杂，但提供了更多的灵活性，在很多实际场景中都有广泛应用。