双向链表基本操作详解（附C语言完整代码）

掌握了双向链表的创建方法后，你可能会思考如何操作已建立的双向链表。例如，如何添加数据、删除节点、查找元素，或直接修改某个节点的值。本节将深入讲解双向链表的基本操作，涵盖添加、删除、查找与修改等核心功能。

为便于讲解，我们继续使用上一节创建好的双向链表作为基础，其结构如图1所示：

图1 双向链表结构示意图

双向链表添加节点

向双向链表添加数据时，根据插入位置的不同，通常可归纳为三种情况来处理。

1) 添加至表头

将新元素插入表头时，只需构建新节点与原表头之间的双向关系即可。假设新节点名为temp，原表头节点为head，两步操作即可完成：

temp->next=head; head->prior=temp;再将head指向temp，使其成为新的表头。

例如，将新元素7插入链表表头，具体过程如图2所示：

图2 向双向链表表头插入新元素

2) 添加至表的中间位置

与单链表插入类似，在双向链表中间位置插入节点需完成两个步骤，如图3所示：

新节点先与其直接后继节点建立双向关系；然后新节点的直接前驱再与其建立双向关系。

图3 向双向链表中间位置插入数据元素

3) 添加至表尾

表尾插入的逻辑与表头对称，步骤如下（如图4所示）：

首先找到链表的最后一个节点；然后将新节点与最后一个节点建立双向链接。

图4 向双向链表尾部添加数据元素

综合以上三种情况，可编写双向链表添加数据的C语言代码。参考实现如下：

data = data;\n temp->prior = NULL;\n temp->next = NULL;\n //插入到链表头，要特殊考虑\n if (add == 1) {\n temp->next = head;\n head->prior = temp;\n head = temp;\n }\n else {\n int i;\n Line* body = head;\n //找到要插入位置的前一个结点\n for (i = 1; i < add - 1; i++) {\n body = body->next;\n //只要 body 不存在，表明插入位置输入错误\n if (!body) {\n printf(\"插入位置有误！\\n\");\n return head;\n }\n }\n //判断条件为真，说明插入位置为链表尾，实现第 2 种情况\n if (body && (body->next == NULL)) {\n body->next = temp;\n temp->prior = body;\n }\n else {\n //第 2 种情况的具体实现\n body->next->prior = temp;\n temp->next = body->next;\n body->next = temp;\n temp->prior = body;\n }\n }\n return head;\n}","heightLimit":true,"margin":true,"id":"Tk9BD"}">

双向链表删除节点

删除节点的思路与添加类似，同样分为三种情况。

1) 删除表头结点

删除表头节点的过程如图5所示：

图5 删除双向链表表头元素

具体步骤如下：

新建一个指针指向表头节点；断开表头节点与直接后继节点的关联，调整head指针指向，并将新表头的prior指针置为NULL；释放原表头节点占用的内存。

2) 删除表中结点

删除中间节点的过程如图6所示：

图6 删除双向链表中间节点

实现要点：

找到目标节点并用指针指向它；将目标节点从链表中摘除；释放该节点占用的内存。

3) 删除表尾结点

删除表尾节点的过程如图7所示：

图7 删除双向链表表尾节点

实现步骤：

找到表尾节点并用指针指向它；断开表尾节点与直接前驱的关联，将前驱节点的next指针置为NULL；释放表尾节点占用的内存。

双向链表删除节点的C语言实现代码如下：

data == data) {\n //删除表头结点\n if (temp->prior == NULL) {\n head = head->next;\n if (head) {\n head->prior = NULL;\n temp->next = NULL;\n }\n free(temp);\n return head;\n }\n //删除表中结点\n if (temp->prior && temp->next) {\n temp->next->prior = temp->prior;\n temp->prior->next = temp->next;\n free(temp);\n return head;\n }\n //删除表尾结点\n if (temp->next == NULL) {\n temp->prior->next = NULL;\n temp->prior = NULL;\n free(temp);\n return head;\n }\n }\n temp = temp->next;\n }\n printf(\"表中没有目标元素，删除失败\\n\");\n return head;\n}","heightLimit":true,"margin":true,"id":"FMNaj"}">

双向链表查找节点

通常情况下，双向链表与单链表一样，只维护一个头指针。因此查找指定元素的过程也与单链表类似：从头节点开始，依次遍历每个节点。

C语言实现代码如下：

data==elem) {\n return i;\n }\n i++;\n t=t->next;\n }\n //程序执行至此处，表示查找失败\n return -1;\n}","heightLimit":true,"margin":true,"id":"QpIp9"}">

双向链表更改节点

更改双向链表指定节点的数据域，本质上是先查找后修改。遍历链表找到目标节点后，直接更新其数据域即可。

实现此操作的C语言代码如下：

data == oldElem) {\n find = 1;\n break;\n }\n temp = temp->next;\n }\n //成功找到，则进行更改操作\n if (find == 1) {\n temp->data = newElem;\n return;\n }\n //查找失败，输出提示信息\n printf(\"链表中未找到目标元素，更改失败\\n\");\n}","heightLimit":true,"margin":true,"id":"U2DvC"}">

总结

以下是双向链表“增删查改”操作的完整C语言实现代码：

\n#include \ntypedef struct line {\n struct line* prior; //指向直接前趋\n int data;\n struct line* next; //指向直接后继\n}Line;\n\nLine* initLine(Line* head) {\n int i;\n Line* list = NULL;\n head = (Line*)malloc(sizeof(Line));//创建链表第一个结点（首元结点）\n head->prior = NULL;\n head->next = NULL;\n head->data = 1;\n list = head;\n for (i = 2; i <= 5; i++) {\n //创建并初始化一个新结点\n Line* body = (Line*)malloc(sizeof(Line));\n body->prior = NULL;\n body->next = NULL;\n body->data = i;\n //直接前趋结点的next指针指向新结点\n list->next = body;\n //新结点指向直接前趋结点\n body->prior = list;\n list = list->next;\n }\n return head;\n}\n\nvoid display(Line* head) {\n Line* temp = head;\n while (temp) {\n //如果该节点无后继节点，说明此节点是链表的最后一个节点\n if (temp->next == NULL) {\n printf(\"%d\\n\", temp->data);\n }\n else {\n printf(\"%d <-> \", temp->data);\n }\n temp = temp->next;\n }\n}\n\n//删除结点的函数，data为要删除结点的数据域的值\nLine* delLine(Line* head, int data) {\n Line* temp = head;\n while (temp) {\n if (temp->data == data) {\n //删除表头结点\n if (temp->prior == NULL) {\n head = head->next;\n if (head) {\n head->prior = NULL;\n temp->next = NULL;\n }\n free(temp);\n return head;\n }\n //删除表中结点\n if (temp->prior && temp->next) {\n temp->next->prior = temp->prior;\n temp->prior->next = temp->next;\n free(temp);\n return head;\n }\n //删除表尾结点\n if (temp->next == NULL) {\n temp->prior->next = NULL;\n temp->prior = NULL;\n free(temp);\n return head;\n }\n }\n temp = temp->next;\n }\n printf(\"表中没有目标元素，删除失败\\n\");\n return head;\n}\n\n//head为原双链表，elem表示被查找元素\nint selectElem(Line* head, int elem) {\n //新建一个指针t，初始化为头指针 head\n Line* t = head;\n int i = 1;\n while (t) {\n if (t->data == elem) {\n return i;\n }\n i++;\n t = t->next;\n }\n //程序执行至此处，表示查找失败\n return -1;\n}\n\n//更新函数，其中，add 表示要修改的元素，newElem 为新数据的值\nvoid amendElem(Line* p, int oldElem, int newElem) {\n Line* temp = p;\n int find = 0;\n //找到要修改的目标结点\n while (temp)\n {\n if (temp->data == oldElem) {\n find = 1;\n break;\n }\n temp = temp->next;\n }\n //成功找到，则进行更改操作\n if (find == 1) {\n temp->data = newElem;\n return;\n }\n //查找失败，输出提示信息\n printf(\"链表中未找到目标元素，更改失败\\n\");\n}\n//释放链表中结点占用的内存空间\nvoid free_line(Line* head) {\n Line* temp = head;\n while (temp) {\n head = head->next;\n free(temp);\n temp = head;\n }\n}\n\nint main()\n{\n //创建一个头指针\n Line* head = NULL;\n //调用链表创建函数\n head = initLine(head);\n printf(\"创建好的双向链表为:\\n\");\n display(head);\n\n printf(\"删除元素 2:\\n\");\n head = delLine(head, 2);\n display(head);\n\n printf(\"元素 3 的位置是：%d\\n\", selectElem(head, 3));\n \n printf(\"表中的元素 3 改为 6:\\n\");\n amendElem(head, 3, 6);\n display(head);\n\n free_line(head);\n return 0;\n}","heightLimit":true,"margin":true,"id":"9QeoO"}">

程序运行结果如下：

创建好的双向链表为:

1 <-> 2 <-> 3 <-> 4 <-> 5

删除元素 2:

1 <-> 3 <-> 4 <-> 5

元素 3 的位置是：2

表中的元素 3 改为 6:

1 <-> 6 <-> 4 <-> 5