小工具知识网

当前位置: 首页 > 行业知识 > 数据结构:5、链表之双向链表

行业知识

数据结构:5、链表之双向链表

2026-11-16 12:12:14 来源:互联网转载

一、什么是双向链表

如下��这样有一个哨兵位作为头,然后每个节点中存着数据,和next、prev两个指针,这两个指针一个记录下一个节点的地址,一个记录上一个节点的地址,这样就可以组成一个循环的链表,废话不多说直接开始代码演示,文章末尾附上全部代码。

二、双向链表的代码实现 

1、结构体定义,类型重定义

首先肯定是要顶一个结构体,为了方便后续代码的编写,所以这里直接重定义了,如LTNode是链表结构体的定义,而LTDatetype就是把int重定义,也方便后续代码的更改与维护。

typedef int LTDatetype;typedef struct LTNode{LTDatetype data;struct LTNode* next;struct LTNode* prev;}LTNode;

2、双向链表的初始化

这个是初始化,也相当于链表创建时申请的哨兵位,代码如下,这里是直接申请了一个新的节点,并且把下一个节点的地址存入哨兵位的next,尾的地址存入哨兵位的prev,因为只有一个节点所以结构如图。

LTNode* LTInit()//双向链表初始化{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;}

3、双向链表的打印、地址申请与LTEmpty

首先是打印,这个直接遍历打印一边,当cur和head一样时就退出,这个cur就是哨兵位的下一个节点,申请地址没啥好说的就是直接用malloc申请地址,直接返回,LTEmpty这个函数,这里是利用c语言的bool量库函数,直接定义的,当head的下一个节点等于head就是相当于空链表,所以没法删除,直接返回就是个bool量,可以直接用断言函数去进行判定。

void LTPrintf(LTNode* phead)//双向链表打印{LTNode* cur = phead->next;printf("哨兵位->");while (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("\n");}LTNode* BuyLTNode(LTDatetype x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}bool LTEmpty(LTNode* phead){assert(phead);return phead->next == phead;}

4、双向链表的尾插与尾删

这个尾插直接就是把申请一个节点,因为哨兵位存着尾部的地址就可以直接访问尾部不需要遍历,把新节点的地址给哨兵位的prev,新节点的next就是哨兵位的地址,新节点的prev就是之前的尾,之前的尾的next就是新节点的地址,这样就创建好了,具体示例如图,图是手工画的可能有点抽象,尾删原理也差不多,找到尾,和尾上一个,直接把地址交换下,free掉尾就可以了,代码运行结果如图,依次删除直至删空,在删除这时就会因为断言程序停下来。

void LTPushBack(LTNode* phead, LTDatetype x)//双向链表尾插{assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;phead->prev = newnode;newnode->next = phead;newnode->prev = tail;}void LTPopBack(LTNode* phead)//双向链表尾删{assert(phead);assert(!LTEmpty(phead));LTNode* tail = phead->prev;LTNode* cur = tail->prev;cur->next = phead;phead->prev = cur;free(tail);}

5、 双向链表的头插与头删

与上文中的尾插和尾删原理差不多,只不过是之前是连接在尾部,这里是连接在哨兵位的后面,也就是把哨兵位的next换成新节点,原来头的prev换成新节点,新节点的next是原来的头,prev是哨兵位,同理删除也就是把哨兵位的next换成头的下一个节点的地址,把下一个节点的prev换成哨兵位,代码如下,代码运行结果如下,和上文一样,一个一个删,再看看空是否能断言停止。

void LTPushFront(LTNode* phead, LTDatetype x)//双向链表头插{assert(phead);LTNode* head = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;head->prev = newnode;newnode->next = head;newnode->prev = phead;}void LTPopFront(LTNode* phead)//双向链表头删{assert(phead);assert(!LTEmpty(phead));LTNode* head = phead->next;LTNode* next = head->next;next->prev = phead;phead->next = next;free(head);}

6、查找、在任意位置修改与删除 

这个就是查找数据在哪个位置,然后返回这个位置的地址,直接遍历就可以,而在任意位置删除,就是根据查找的数据的地址后,直接在这个地址前加入一个数据,删除就是直接删除这个数据所在的节点,也就是直接free,插入原理和之前差不多,就是找到pos的前一位,因为pos这个节点中就存有这个地址,所以就可以直接使用,然后创建新节点,链接就可以了,删除就是找到os的前后位,因为pos这个节点中就存有这两个地址,所以直接把这两个节点连接然后free掉这就可以,代码如下,程序运行示例图如下。

LTNode* LTFind(LTNode* phead,LTDatetype x){LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}void LTInsert(LTNode* pos, LTDatetype x)//在pos位置前插入数据{assert(pos);LTNode* cur = pos->prev;LTNode* newnode = BuyLTNode(x);cur->next = newnode;pos->prev = newnode;newnode->next = pos;newnode->prev = cur;}void LTErase(LTNode* pos)//删除pos位置的数据{assert(pos);LTNode* prev = pos->prev;LTNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);}

7、释放内存

这个一定要写就是在链表运行结束时把链表释放掉,要不然容易造成内存泄漏,直接遍历然后free,最后free掉头,在主函里在置空这个指针,代码如下。

void LTDestory(LTNode* phead)//释放内存{LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}

 8、LTIsert与LTErase函数的使用技巧

在这个函数写完后,头插尾插,头删尾删完全可以用这个函数代替,代码和运行示例如下。

void LTPushBack(LTNode* phead, LTDatetype x)//双向链表尾插{assert(phead);/*LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;phead->prev = newnode;newnode->next = phead;newnode->prev = tail;*/LTInsert(phead, x);}void LTPushFront(LTNode* phead, LTDatetype x)//双向链表头插{assert(phead);/*LTNode* head = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;head->prev = newnode;newnode->next = head;newnode->prev = phead;*/LTInsert(phead->next, x);}void LTPopBack(LTNode* phead)//双向链表尾删{assert(phead);assert(!LTEmpty(phead));/*LTNode* tail = phead->prev;LTNode* cur = tail->prev;cur->next = phead;phead->prev = cur;free(tail);*/LTErase(phead->prev);}void LTPopFront(LTNode* phead)//双向链表头删{assert(phead);assert(!LTEmpty(phead));/*LTNode* head = phead->next;LTNode* next = head->next;next->prev = phead;phead->next = next;free(head);*/LTErase(phead->next);}

头插头删 

尾插尾删

三、代码附图 

LT.h

#pragma once#include #include #include #include typedef int LTDatetype;typedef struct LTNode{LTDatetype data;struct LTNode* next;struct LTNode* prev;}LTNode;LTNode* BuyLTNode(LTDatetype x);LTNode* LTInit();//双向链表初始化LTNode* LTFind(LTNode* phead,LTDatetype x);//双向链表查找bool LTEmpty(LTNode* phead);//判断是链表是否为空链表void LTPrintf(LTNode* phead);//双向链表打印void LTPushBack(LTNode* phead,LTDatetype x);//双向链表尾插void LTPushFront(LTNode* phead, LTDatetype x);//双向链表头插void LTPopBack(LTNode* phead);//双向链表尾删void LTPopFront(LTNode* phead);//双向链表头删void LTInsert(LTNode* pos, LTDatetype x);//在pos位置前插入数据void LTErase(LTNode* pos);//删除pos位置的数据void LTDestory(LTNode* phead);//释放内存

 LT.c

#define _CRT_SECURE_NO_WARNINGS 1#include "LT.h"LTNode* BuyLTNode(LTDatetype x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}LTNode* LTInit()//双向链表初始化{LTNode* phead = BuyLTNode(-1);phead->next = phead;phead->prev = phead;return phead;}void LTPrintf(LTNode* phead)//双向链表打印{LTNode* cur = phead->next;printf("哨兵位->");while (cur != phead){printf("%d->", cur->data);cur = cur->next;}printf("\n");}bool LTEmpty(LTNode* phead){assert(phead);return phead->next == phead;}void LTPushBack(LTNode* phead, LTDatetype x)//双向链表尾插{assert(phead);/*LTNode* tail = phead->prev;LTNode* newnode = BuyLTNode(x);tail->next = newnode;phead->prev = newnode;newnode->next = phead;newnode->prev = tail;*/LTInsert(phead, x);}void LTPushFront(LTNode* phead, LTDatetype x)//双向链表头插{assert(phead);/*LTNode* head = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;head->prev = newnode;newnode->next = head;newnode->prev = phead;*/LTInsert(phead->next, x);}void LTPopBack(LTNode* phead)//双向链表尾删{assert(phead);assert(!LTEmpty(phead));/*LTNode* tail = phead->prev;LTNode* cur = tail->prev;cur->next = phead;phead->prev = cur;free(tail);*/LTErase(phead->prev);}void LTPopFront(LTNode* phead)//双向链表头删{assert(phead);assert(!LTEmpty(phead));/*LTNode* head = phead->next;LTNode* next = head->next;next->prev = phead;phead->next = next;free(head);*/LTErase(phead->next);}LTNode* LTFind(LTNode* phead,LTDatetype x){LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}void LTInsert(LTNode* pos, LTDatetype x)//在pos位置前插入数据{assert(pos);LTNode* cur = pos->prev;LTNode* newnode = BuyLTNode(x);cur->next = newnode;pos->prev = newnode;newnode->next = pos;newnode->prev = cur;}void LTErase(LTNode* pos)//删除pos位置的数据{assert(pos);LTNode* prev = pos->prev;LTNode* next = pos->next;prev->next = next;next->prev = prev;free(pos);}void LTDestory(LTNode* phead)//释放内存{LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);}

 test.c

#define _CRT_SECURE_NO_WARNINGS 1#include "LT.h"void LTTest1(){LTNode* LT = LTInit();LTPushBack(LT, 1);LTPushBack(LT, 2);LTPushBack(LT, 3);LTPushBack(LT, 4);LTPushBack(LT, 5);LTPushBack(LT, 6);LTPrintf(LT);LTErase(LT);LT = NULL;}void LTTest2(){LTNode* LT = LTInit();LTPushFront(LT, 1);LTPushFront(LT, 2);LTPushFront(LT, 3);LTPushFront(LT, 4);LTPushFront(LT, 5);LTPushFront(LT, 6);LTPrintf(LT);LTErase(LT);LT = NULL;}void LTTest3(){LTNode* LT = LTInit();LTPushBack(LT, 1);LTPushBack(LT, 2);LTPushBack(LT, 3);LTPushBack(LT, 4);LTPushBack(LT, 5);LTPushBack(LT, 6);LTPrintf(LT);LTPopBack(LT);LTPrintf(LT);LTPopBack(LT);LTPrintf(LT);LTPopBack(LT);LTPrintf(LT);LTPopBack(LT);LTPrintf(LT);LTPopBack(LT);LTPrintf(LT);LTPopBack(LT);LTPrintf(LT);LTPopBack(LT);LTPrintf(LT);LTErase(LT);LT = NULL;}void LTTest4(){LTNode* LT = LTInit();LTPushFront(LT, 1);LTPushFront(LT, 2);LTPushFront(LT, 3);LTPushFront(LT, 4);LTPushFront(LT, 5);LTPushFront(LT, 6);LTPrintf(LT);LTPopFront(LT);LTPrintf(LT);LTPopFront(LT);LTPrintf(LT);LTPopFront(LT);LTPrintf(LT);LTPopFront(LT);LTPrintf(LT);LTPopFront(LT);LTPrintf(LT);LTPopFront(LT);LTPrintf(LT);LTPopFront(LT);LTPrintf(LT);LTErase(LT);LT = NULL;}void LTTest5(){LTNode* LT = LTInit();LTPushFront(LT, 1);LTPushFront(LT, 2);LTPushFront(LT, 3);LTPushFront(LT, 4);LTPushFront(LT, 5);LTPushFront(LT, 6);LTPrintf(LT);LTNode* pos = LTFind(LT, 3);LTInsert(pos, 30);LTPrintf(LT);LTErase(LT);LT = NULL;}void LTTest6(){LTNode* LT = LTInit();LTPushFront(LT, 1);LTPushFront(LT, 2);LTPushFront(LT, 3);LTPushFront(LT, 4);LTPushFront(LT, 5);LTPushFront(LT, 6);LTPrintf(LT);LTNode* pos = LTFind(LT, 3);LTInsert(pos, 30);LTPrintf(LT);LTErase(pos);LTPrintf(LT);LTErase(LT);LT = NULL;}int main(){LTTest3();return 0;}

上一篇:终结战场哪里有极地服务器?

下一篇:地球服务器崩溃怎么办?