【数据结构】双链表的定义和操作

1.双链表的定义

双链表是一种常见的数据结构，它由一系列节点组成，每个节点包含两个指针，一个指向前一个节点，另一个指向后一个节点。与单链表不同的是，双链表的节点可以双向访问，因此可以在任意位置快速插入、删除和查找元素。

2.双链表的创建和初始化

创建一个双链表需要定义一个结构体，包含数据域和前后指针域。初始化时要注意将头结点的前后指针均指向 NULL。

struct DNode {
    int data;  //数据域
    struct DNode *prior;  //前驱指针域
    struct DNode *next;   //后继指针域
};

struct DNode *createList() {
    struct DNode *head = (struct DNode*)malloc(sizeof(struct DNode));
    head->prior = NULL;
    head->next = NULL;
    return head;
}

定义结构体struct DNode表示双向链表的节点。
该节点包括三个成员变量：
int data表示节点的数据域，可以存储整数类型的数据。
struct DNode *prior表示指向前一个节点的指针域。
struct DNode *next表示指向后一个节点的指针域。

在createList函数内部，首先通过malloc函数动态分配了一块内存，大小为一个struct DNode结构体的大小。然后将分配的内存强制转换为struct DNode*类型，并将其赋值给head指针变量，作为链表的头节点。

3.双链表的插入节点操作

在插入节点时，需要将新节点插入到某个节点之前或之后，通过修改前后指针实现。具体操作分为两步，先将新节点的前后指针赋值，然后修改它前后节点的指针。需要注意判断特殊情况，如插入到空链表、插入到头结点等。

void insertNode(struct DNode *p, int data) {
    if (p == NULL) return;
    struct DNode *newNode = (struct DNode*)malloc(sizeof(struct DNode));
    newNode->data = data;
    newNode->prior = p;
    newNode->next = p->next;
    if (p->next != NULL) p->next->prior = newNode;
    p->next = newNode;
}

函数insertNode接受两个参数：指向双向链表结点的指针p和要插入的数据data。

如果p不为空，则创建一个新的双向链表结点newNode，通过malloc函数动态分配内存。然后，将新节点的data字段设置为传入的data值。再将新节点的prior字段设置为指向p，将新节点的next字段设置为指向p->next。

检查p的下一个结点是否为空，如果不为空，则将下一个结点的prior字段指向新节点newNode。最后将p的next指针指向新结点newNode，完成插入操作。这样，插入操作就将新节点插入到了链表中p结点之后的位置。

4.双链表的删除节点操作

在删除节点时，需先找到要删除的节点，然后修改前后节点的指针。在执行 free 操作后，需要将指针置为 NULL，避免出现野指针。

void deleteNode(struct DNode *p) {
    if (p == NULL) return;
    p->prior->next = p->next;
    if (p->next != NULL) p->next->prior = p->prior;
    free(p);
    p = NULL;
}

如果p不为空，将p结点的前驱结点的next指针指向p结点的后继结点，断开p结点与前后结点的连接。即p->prior->next = p->next。

检查p结点的后继结点是否为空，如果不为空，则将后继结点的前驱指针指向p结点的前驱结点，断开p结点与后继结点的连接。即p->next->prior = p->prior。

使用free函数释放了指针p指向的内存，将p结点从链表中删除。

将指针p设置为NULL，确保不再引用已经删除的结点。

5.双链表的查找节点操作

查找节点时，可以采用遍历的方法进行查找。需要注意判断特殊情况，如链表为空等。

struct DNode *findNode(struct DNode *head, int data) {
    if (head == NULL) return NULL;
    struct DNode *p = head->next;
    while (p != NULL) {
        if (p->data == data) return p;
        p = p->next;
    }
    return NULL;
}

如果head不为空，代码将p指针初始化为head结点的下一个结点，即head->next。

使用while循环遍历链表，如果指针p指向的结点的data字段等于要查找的数据data，则直接返回该结点的指针p，表示查找成功。

如果没有查找到要找的数据，即p到达链表结尾指针为NULL，则返回NULL，表示查找失败。

6.双链表的更新节点操作

更新节点操作与单链表类似，具体步骤为先查找要更新的节点，然后修改其数据域的值即可。

void updateNode(struct DNode *p, int newData) {
    if (p != NULL) {
        p->data = newData;
    }
}

首先检查指针p是否为空，如果不为空，则将指针p所指向的结点的data字段更新为新的数据newData。如果结点p为空，则不进行任何操作。

7.完整代码

#include <stdio.h>
#include <stdlib.h>

//双链表结构体定义
struct DNode {
    int data;  //数据域
    struct DNode *prior;  //前驱指针域
    struct DNode *next;   //后继指针域
};

//创建双链表
struct DNode *createList() {
    struct DNode *head = (struct DNode*)malloc(sizeof(struct DNode));
    head->prior = NULL;
    head->next = NULL;
    return head;
}

//插入节点
void insertNode(struct DNode *p, int data) {
    if (p == NULL) return;
    struct DNode *newNode = (struct DNode*)malloc(sizeof(struct DNode));
    newNode->data = data;
    newNode->prior = p;
    newNode->next = p->next;
    if (p->next != NULL) p->next->prior = newNode;
    p->next = newNode;
}

//删除节点
void deleteNode(struct DNode *p) {
    if (p == NULL) return;
    p->prior->next = p->next;
    if (p->next != NULL) p->next->prior = p->prior;
    free(p);
    p = NULL;
}

//查找节点
struct DNode *findNode(struct DNode *head, int data) {
    if (head == NULL) return NULL;
    struct DNode *p = head->next;
    while (p != NULL) {
        if (p->data == data) return p;
        p = p->next;
    }
    return NULL;
}

//更新节点
void updateNode(struct DNode *p, int newData) {
    if (p != NULL) {
        p->data = newData;
    }
}

//遍历双链表
void traverseList(struct DNode *head) {
    if (head == NULL) return;
    struct DNode *p = head->next;
    while (p != NULL) {
        printf("%d ", p->data);
        p = p->next;
    }
    printf("\n");
}

//测试双链表
int main() {
    struct DNode *head = createList();  //创建链表

    //插入节点
    insertNode(head, 1);
    insertNode(head, 2);
    insertNode(head, 3);
    insertNode(head, 4);

    traverseList(head);  //遍历链表

    struct DNode *p = findNode(head, 2);  //查找节点
    if (p != NULL) {
        printf("Found node: %d\n", p->data);
        updateNode(p, 5);  //更新节点
        printf("After updated, the list is:\n");
        traverseList(head);  //遍历链表
    }

    deleteNode(findNode(head, 3)); //删除节点
    printf("After deleted, the list is:\n");
    traverseList(head);  //遍历链表

    return 0;
}

输出结果如下：