双向链表的操作介绍

什么是双向链表？

双向链表是一种线性数据结构，它不仅允许你从一个节点移动到另一个节点（通常是从前一个节点指向后一个节点），还允许在两个方向上进行遍历。每个节点包含三个部分：数据域、前驱指针和后继指针。

双向链表的基本操作

1. 插入操作

插入到链表头部

在双向链表的头部插入一个新节点，首先需要找到头结点，并将新节点的 prev 指向空，同时 next 指向头结点；然后更新头结点的 prev 指针指向这个新节点。

Node* insertHead(Node* head, int value) {
    Node* newNode = new Node(value);
    if (head == NULL) { // 空链表情况
        head = newNode;
        return head;
    }
    newNode->next = head;
    head->prev = newNode;
    head = newNode; 
    return head;
}

插入到链表尾部

在双向链表的尾部插入一个新节点，首先需要找到尾结点，并将新节点的 next 指向空；然后更新尾结点的 next 指针指向这个新节点。

Node* insertTail(Node* tail, int value) {
    Node* newNode = new Node(value);
    if (tail == NULL) { // 空链表情况
        return newNode;
    }
    tail->next = newNode;
    newNode->prev = tail; 
    return newNode;
}

插入到指定位置

在双向链表的某个特定节点之前插入一个新节点，首先找到目标节点的前驱结点；然后更新相应指针。

Node* insertAfter(Node* prev, int value) {
    Node* newNode = new Node(value);
    if (prev == NULL) { // 无前驱节点的情况（即插入到头部）
        newNode->next = head;
        return newNode;
    }
    newNode->next = prev->next;
    prev->next = newNode;
    newNode->prev = prev; 
    return newNode;
}

2. 删除操作

删除指定位置的节点

找到目标节点，更新前后节点之间的指针关系。

Node* deleteNode(Node* node) {
    if (node == NULL || node->next == NULL) { // 要删除的是尾部或仅有一个节点的情况
        return NULL;
    }
    Node* prev = node->prev, * next = node->next; 
    prev->next = next;
    next->prev = prev;
    delete node;
    return head;
}

3. 遍历操作

正向遍历

从头结点开始，通过 next 指针依次访问每个节点。

void printForward(Node* head) {
    Node* curr = head;
    while (curr != NULL) {
        cout << curr->value << " ";
        curr = curr->next;
    }
}

反向遍历

从尾结点开始，通过 prev 指针依次访问每个节点。

void printReverse(Node* tail) {
    Node* curr = tail;
    while (curr != NULL) {
        cout << curr->value << " ";
        curr = curr->prev;
    }
}

4. 查找操作

查找特定值的节点

从头结点开始，依次遍历查找指定值的节点。

Node* findNode(Node* head, int value) {
    Node* curr = head;
    while (curr != NULL && curr->value != value) {
        curr = curr->next;
    }
    return curr; // 返回找到的节点或NULL表示未找到
}

以上就是双向链表的一些基本操作。通过这些操作，可以灵活地管理和访问双向链表中的数据元素。