双向链表的头尾指针逆序操作实现

引言

双向链表是一种常见的链式数据结构，它在插入和删除节点时能够保持O(1)的时间复杂度优势。双向链表不仅可以通过前驱节点访问下一个节点，还可以通过后继节点反向访问上一个节点。本文将详细介绍如何通过头尾指针逆序操作来实现双向链表的基本功能。

双向链表的结构

在开始讨论具体的逆序操作之前，首先需要了解双向链表的基本结构。每个节点包含三个部分：数据域、前驱指针和后继指针。前驱指针指向当前节点的前一个节点，后继指针指向当前节点的下一个节点。

typedef struct Node {
    int data;
    struct Node *prev;  // 前驱指针
    struct Node *next;  // 后继指针
} Node, *NodePtr;

头尾指针逆序操作

初始化头尾指针

在双向链表的初始化过程中，设置一个虚拟节点作为链表的头部，并且用两个指针分别指向这个虚拟节点和最后一个节点。

struct LinkedList {
    NodePtr head;  // 指向头节点
    NodePtr tail;  // 指向尾节点
};

添加操作

在进行插入或删除等操作时，可以通过调整头尾指针来实现逆序操作。以添加元素为例，在链表末尾追加一个新节点的操作中：

创建新节点。
更新尾指针的 next 指针指向新节点，并设置新节点的 prev 为尾指针。
将新节点设为新的尾节点。

void appendNode(struct LinkedList *list, int data) {
    NodePtr newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = NULL;
    newNode->prev = list->tail;

    if (list->head == list->tail) {  // 如果链表为空
        list->head = newNode;
    } else {
        list->tail->next = newNode;  // 将尾节点的下一个节点指向新节点
    }

    list->tail = newNode;  // 更新尾指针
}

删除操作

在删除节点时，可以通过调整头尾指针来实现逆序。例如删除链表末尾元素的操作：

检查是否为空。
更新尾指针的前驱节点的 next 置为NULL，并将其设为新的尾节点。

void deleteNode(struct LinkedList *list) {
    if (list->head == list->tail) {  // 如果链表只有一个元素
        free(list->head);
        list->head = NULL;
        list->tail = NULL;
    } else {
        NodePtr nodeToDel = list->tail;  // 要删除的节点
        list->tail = list->tail->prev;   // 将尾指针向前移动一位
        if (list->tail != NULL) {        // 非空情况下的操作
            list->tail->next = NULL;
        }
        free(nodeToDel);
    }
}

逆序操作

要实现双向链表的逆序，可以通过遍历链表并调整每个节点的前驱和后继指针来实现。具体步骤如下：

遍历整个链表。
对于每一个节点，交换其 prev 和 next 指针指向的对象。

void reverseList(struct LinkedList *list) {
    NodePtr current = list->head;
    while (current != NULL) {
        // 交换当前节点的前后继指针
        NodePtr temp = current->prev;
        current->prev = current->next;
        current->next = temp;

        if (current == list->tail) {  // 更新头尾指针，注意是临时的指向对象，不是变量本身
            break;
        }

        current = current->prev;    // 继续遍历
    }

    NodePtr tmp = list->head;  // 拷贝当前头部给尾部
    list->tail = list->head;
    list->head = tmp;          // 交换头尾指针指向的对象
}

结论

通过上述方法，可以灵活地对双向链表进行逆序操作。这种操作不仅适用于简单的逆序功能实现，还可以应用于其他需要逆序处理的场景中。在实际应用中，根据具体需求，可以通过调整头尾指针或节点间的指针关系来满足不同的操作要求。