阅读量:0
双链表的概念和结构
双链表的全称叫做：带头双向循环链表
它的结构示意图如下
注意：这⾥的“带头”跟前⾯我们说的单链表的“头结点”是两个概念，实际前⾯的在单链表阶段称呼不严谨，但是为了读者们更好的理解就直接称为单链表的头结点。
带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的”也可以认为是用来占位置滴！！！
双链表的实现
首先先在结构体当中输入需要的数据，则有如下的数据是需要的
结构体中的数据
typedef int LTDataType;//方便对数据类型进行统一的替换 typedef struct ListNode ListNode;//对结构体的名称重新命名交ListNode struct ListNode { LTDataType data; ListNode* next; ListNode* prev; }; 则上面的图可以变成这样
双链表新结点的创建及双链表的初始化
ListNode* LTBuyNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));//一个结构体的大小 if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = newnode->prev = newnode; return newnode;//返回头结点 }链表的初始化需要一个创建的新的结点作为哨兵位
//void LTInit(ListNode** pphead) //{ // //创建一个头结点即“哨兵位” // *pphead = LTBuyNode(-1); //} ListNode* LTInit() { ListNode* phead = LTBuyNode(-1); return phead; } //上面是两种初始化的方法 //第一种需要传递一个二级指针 在上面的代码当中，我们只需要创建一个头结点来保证第一个“头”存在即可。
插入
第一个参数传一级还是二级，要看phead指向的结点会不会改变
如果发生改变，那么pphead的改变要影响实参，传二级
如果不发生改变，pphead不会影响实参，传一级
双链表的尾插
//尾插 void LTPushBack(ListNode* phead, LTDataType x) { assert(phead); //创建需要插入的结点 //上面初始化的newnode是头结点，这个newnode是尾插的结点 ListNode* newnode = LTBuyNode(x); newnode->next = phead; newnode->prev = phead->prev; phead->prev->next = newnode; phead->prev = newnode; }
上面的顺序是不能改变的，否则无法让新结点找到原来链表的位置
这边测试一下我们的尾插代码依次插入1 2 3 4
双链表的头插
//头插 void LTPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* newnode = LTBuyNode(x); newnode->next = phead->next; newnode->prev = phead; phead->next->prev = newnode; phead->next = newnode; }头插和尾插是类似的 ，不过有一个特殊的地方
头插是头插在哨兵位和第一个真正的结点中间
同样的，上面的顺序位置是不能改变的
测试头插代码
这个代码是在上面尾插代码基础上的操作
双链表的尾删
//尾删 void LTPopBack(ListNode* phead) { assert(phead); assert(!Empty(phead)); ListNode* del = phead->prev; ListNode* prev = del->prev; prev->next = phead; phead->prev = prev; free(del); del = NULL; }
这边仍然是在尾插的基础上的操作
这边我们进行了五次尾删，所以代码assert断言了！
将一次尾删注释，下面就是尾删的效果
双链表的头删
//头删 void LTPopFront(ListNode* phead) { assert(phead); assert(!Empty(phead)); ListNode* del = phead->next; del->next->prev = phead; phead->next = del->next; free(del); del = NULL; }
这个仍然是在尾插的基础上操作的，如果继续删除，跟上面的情况一样assert断言报错
以上就是最基础的增删 ，下面开始加大难度！
双链表中查找数据pos
//找相同数据 ListNode* LTFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* pcur = phead->next; while (pcur != phead) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; }
这边我们查找的是数据3，所以我们可以找到
这个在链表中没有数据6，所以我们没有找到相关的数据
在pos之后插入结点
这个和尾插以及头插其实是类似的，这里主要是寻找到pos结点，然后插入想要的数据
//在pos之后插入结点 void LTInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = LTBuyNode(x); newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode; pos->next = newnode; }在3的后面插入数据10
删除pos结点
//删除指定位置节点 void LTErase(ListNode* pos) { assert(pos); // pos->prev pos pos->next pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; } 
双链表的销毁
这里我们提供了两种的销毁方法，两种方法基本是类似的
//销毁 void LTDesTroy(ListNode** pphead) { assert(pphead && *pphead); ListNode* pcur = (*pphead)->next; while (pcur != *pphead) { ListNode* next = pcur->next; free(pcur); pcur = next; } //销毁哨兵位结点 free(*pphead); *pphead = NULL; pcur = NULL; } //为了更好的记忆，我们让销毁也传递一级指针 void LTDesTroy2(ListNode* phead)//传一级，需要手动将plist置为NULL { assert(phead); ListNode* pcur = phead->next; while (pcur != phead) { ListNode* next = pcur->next; free(pcur); pcur = next; } free(phead); phead = pcur = NULL; }最后我们将双向链表的源码附上
list.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int LTDataType; typedef struct ListNode ListNode; struct ListNode { LTDataType data; ListNode* next; ListNode* prev; }; ListNode* LTBuyNode(LTDataType x); //为了保存接口的一致性 // //初始化 //void LTInit(ListNode** pphead); ListNode* LTInit(); // void LTPrint(ListNode* phead); bool Empty(ListNode* phead); //插入 //第一个参数传一级还是二级，要看phead指向的结点会不会改变 //如果发生改变，那么pphead的改变要影响实参，传二级 //如果不发生改变，pphead不会影响实参，传一级 //尾插 void LTPushBack(ListNode* phead, LTDataType x); //头插 void LTPushFront(ListNode* phead, LTDataType x); //尾删 void LTPopBack(ListNode* phead); //头删 void LTPopFront(ListNode* phead); //在pos之后插入结点 void LTInsert(ListNode* pos, LTDataType x); //删除指定位置的结点 void LTErase(ListNode* pos); //找数据 ListNode* LTFind(ListNode* phead, LTDataType x); //销毁 void LTDesTroy(ListNode** pphead); void LTDesTroy2(ListNode* phead);//传一级，需要手动将plist置为NULLList.c
#include"List.h" ListNode* LTBuyNode(LTDataType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc fail!"); exit(1); } newnode->data = x; newnode->next = newnode->prev = newnode; return newnode; } //初始化 //void LTInit(ListNode** pphead) //{ // //创建一个头结点即“哨兵位” // *pphead = LTBuyNode(-1); //} ListNode* LTInit() { ListNode* phead = LTBuyNode(-1); return phead; } //打印 void LTPrint(ListNode* phead) { ListNode* pcur = phead->next; while (pcur != phead) { printf("%d->", pcur->data); pcur = pcur->next; } printf("\n"); } bool Empty(ListNode* phead) { assert(phead); return phead->next == phead; } //尾插 void LTPushBack(ListNode* phead, LTDataType x) { assert(phead); //创建需要插入的结点 ListNode* newnode = LTBuyNode(x); newnode->next = phead; newnode->prev = phead->prev; phead->prev->next = newnode; phead->prev = newnode; } //头插 void LTPushFront(ListNode* phead, LTDataType x) { assert(phead); ListNode* newnode = LTBuyNode(x); newnode->next = phead->next; newnode->prev = phead; phead->next->prev = newnode; phead->next = newnode; } //尾删 void LTPopBack(ListNode* phead) { assert(phead); assert(!Empty(phead)); ListNode* del = phead->prev; ListNode* prev = del->prev; prev->next = phead; phead->prev = prev; free(del); del = NULL; } //头删 void LTPopFront(ListNode* phead) { assert(phead); assert(!Empty(phead)); ListNode* del = phead->next; del->next->prev = phead; phead->next = del->next; free(del); del = NULL; } //找相同数据 ListNode* LTFind(ListNode* phead, LTDataType x) { assert(phead); ListNode* pcur = phead->next; while (pcur != phead) { if (pcur->data == x) { return pcur; } pcur = pcur->next; } return NULL; } //在pos之后插入结点 void LTInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = LTBuyNode(x); newnode->next = pos->next; newnode->prev = pos; pos->next->prev = newnode; pos->next = newnode; } //删除指定位置节点 void LTErase(ListNode* pos) { assert(pos); // pos->prev pos pos->next pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; } //销毁 void LTDesTroy(ListNode** pphead) { assert(pphead && *pphead); ListNode* pcur = (*pphead)->next; while (pcur != *pphead) { ListNode* next = pcur->next; free(pcur); pcur = next; } //销毁哨兵位结点 free(*pphead); *pphead = NULL; pcur = NULL; } void LTDesTroy2(ListNode* phead) { assert(phead); ListNode* pcur = phead->next; while (pcur != phead) { ListNode* next = pcur->next; free(pcur); pcur = next; } free(phead); phead = pcur = NULL; }test.c
#include"List.h" void test() { 创建双向链表变量 //ListNode* plist = NULL; //LTInit(&plist); ListNode* plist = LTInit(); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPrint(plist); ListNode* pos = LTFind(plist, 3); LTInsert(pos, 10); LTPrint(plist); pos = LTFind(plist, 3); LTErase(pos); LTPrint(plist); /*LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist); LTPopFront(plist); LTPrint(plist);*/ /*LTPushFront(plist, 1); LTPrint(plist); LTPushFront(plist, 2); LTPrint(plist); LTPushFront(plist, 3); LTPrint(plist); LTPushFront(plist, 4); LTPrint(plist);*/ /*LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist); LTPopBack(plist); LTPrint(plist);*/ /*if (pos == NULL) { printf("没有找到\n"); } else { printf("找到了\n"); }*/ LTDesTroy(&plist); //LTDesTroy2(plist); //plist = NULL; } int main() { test(); return 0; }