c++双向链表操作示例(创建双向链、双向链表中查找数据、插入数据等)

创建双向链表示例

创建双向链表需要实现以下几个步骤：

1. 定义双向链表节点结构体 Node，包含 data 数据项和 prev、next 指针分别指向前驱节点和后继节点。
2. 定义双向链表结构体 LinkedList，包含头节点 head 和尾节点 tail，以及链表长度 size。
3. 实现 LinkedList 的构造函数，初始化头节点和尾节点，并将 head 和 tail 的 prev 和 next 指向彼此。
4. 实现 LinkedList 的 insertAtTail() 方法，在链表尾部插入节点。
5. 实现 LinkedList 的 insertAtHead() 方法，在链表头部插入节点。
6. 实现 LinkedList 的 removeItem() 方法，删除指定节点。

以下是一个完整的 C++ 双向链表示例代码：

#include<iostream>

// 双向链表节点结构体
struct Node {
    int data;
    Node *prev;
    Node *next;
};

// 双向链表结构体
class LinkedList {
    private:
        Node *head;
        Node *tail;
        int size;

    public:
        // 构造函数
        LinkedList() {
            head = new Node();
            tail = new Node();
            head->next = tail;
            tail->prev = head;
            size = 0;
        }

        // 在链表尾部插入节点
        void insertAtTail(int value) {
            Node *node = new Node();
            node->data = value;
            node->prev = tail->prev;
            node->next = tail;
            tail->prev->next = node;
            tail->prev = node;
            size++;
        }

        // 在链表头部插入节点
        void insertAtHead(int value) {
            Node *node = new Node();
            node->data = value;
            node->prev = head;
            node->next = head->next;
            head->next->prev = node;
            head->next = node;
            size++;
        }

        // 删除指定节点
        void removeItem(Node *node) {
            node->prev->next = node->next;
            node->next->prev = node->prev;
            delete node;
            size--;
        }

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

int main() {
    // 创建双向链表并在尾部插入数据
    LinkedList list;
    list.insertAtTail(1);
    list.insertAtTail(2);
    list.insertAtTail(3);
    list.insertAtTail(4);

    // 遍历打印链表中的数据
    Node *currNode = list.head->next;
    while(currNode != list.tail) {
        std::cout << currNode->data << " ";
        currNode = currNode->next;
    }
    std::cout << std::endl;
    return 0;
}

双向链表中查找数据和插入数据示例

双向链表中查找数据和插入数据有多种方式，以下列举其中两种方法：

方法一：遍历查找和插入

遍历双向链表查找节点和插入节点是最基础的方法。遍历链表时从头节点开始向后遍历，直到找到目标节点或遍历到链表尾部。

以下是具体实现代码：

// 查找指定值的节点
Node *findItem(LinkedList &list, int value) {
    Node *currNode = list.head->next;
    while(currNode != list.tail) {
        if(currNode->data == value) {
            return currNode;
        }
        currNode = currNode->next;
    }
    return nullptr;
}

// 在指定值的节点后插入新节点
void insertAfter(LinkedList &list, int value, int newValue) {
    Node *currNode = list.head->next;
    while(currNode != list.tail) {
        if(currNode->data == value) {
            Node *newNode = new Node();
            newNode->data = newValue;
            newNode->prev = currNode;
            newNode->next = currNode->next;
            currNode->next->prev = newNode;
            currNode->next = newNode;
            list.size++;
            break;
        }
        currNode = currNode->next;
    }
}

方法二：使用哈希表优化查找和插入

使用哈希表优化查找和插入是一个常见的优化方法，可以在 O(1) 的时间复杂度内完成节点的查找和插入。

以下代码展示了如何使用 unordered_map（哈希表）实现快速查找和插入：

#include <unordered_map>

// 保存链表节点指针的哈希表
std::unordered_map<int, Node *> hashMap;

// 初始化哈希表
void initHashMap(LinkedList &list) {
    Node *currNode = list.head->next;
    while(currNode != list.tail) {
        hashMap[currNode->data] = currNode;
        currNode = currNode->next;
    }
}

// 查找指定值的节点
Node *findItem(LinkedList &list, int value) {
    if(hashMap.find(value) != hashMap.end()) {
        return hashMap[value];
    }
    return nullptr;
}

// 在指定值的节点后插入新节点
void insertAfter(LinkedList &list, int value, int newValue) {
    Node *currNode = findItem(list, value);
    if(currNode != nullptr) {
        Node *newNode = new Node();
        newNode->data = newValue;
        newNode->prev = currNode;
        newNode->next = currNode->next;
        currNode->next->prev = newNode;
        currNode->next = newNode;
        hashMap[newValue] = newNode;
        list.size++;
    }
}

以上两种方法根据实际场景进行选择，有时更基础的遍历法可能性能更高。