线性表之链表
导航1、带头双向循环链表介绍2、结构体及接口函数定义3、接口函数实现3.1 头结点初始化3.2 结点动态内存申请3.3 双向链表尾插3.4 双向链表尾删3.5 双向链表头插3.6 双向链表头删3.7 双向链表查找3.8 在pos位置前插入3.9 删除pos位置的结点3.10 打印双向链表3.11 销毁双向链表 4、顺序表和链表的区别5、结语
导航
1、带头双向循环链表介绍
在上一篇博客我们讲述了链表的概念和结构,还实现了无头单向非循环链表接口写法,那么这一章节,我们来实现另一种常用的链表组成结构——带头双向循环链表。
如果对前面的链表基本概念还是不了解,可以看作者的上一篇博客:
线性表中链表介绍及无头单向非循环链表接口实现
2、结构体及接口函数定义
首先是结构体的定义
代码如下:
typedef int LTDateType;typedef struct ListNode{LTDateType data;//结点存储元素struct ListNode* next;//下一结点指针struct ListNode* prev;//上一结点指针}LTNode;
然后就是接口函数的定义
代码如下:
void ListInit(LTNode* phead);//哨兵位头结点初始化LTNode* BuyListNode(LTDateType x);//动态申请结点void ListPushBack(LTNode* phead, LTDateType x);//双向链表尾插void ListPopBack(LTNode* phead);//双向链表尾删void ListPushFront(LTNode* phead, LTDateType x);//双向链表头插void ListPopFront(LTNode* phead);//双向链表头删LTNode* ListFind(LTNode* phead, LTDateType x);//双向链表查找void ListInsert(LTNode* pos, LTDateType x);//在pos位置前插入void ListErase(LTNode* pos);//删除pos位置的结点void ListPrint(LTNode* phead);//打印双向链表void ListDestroy(LTNode* phead);//销毁双向链表
3、接口函数实现
在上一篇博客中我们讲到不带头的单非循环链表存在一定缺陷,就是无法访问上一结点,但是这一节讲的带头双向循环链表就很好的弥补了这一缺点,带头双向循环链表看来比单链表结构要复杂很多,但其实实现起来要比单链表更简单,更高效;下面我们就来实现带头双向循环链表的接口函数吧!
3.1 头结点初始化
头结点初始化(ListInit)
首先是我们的头结点的定义,它是不存放数据的,起到一个哨兵的作用
代码如下:
void ListInit(LTNode* phead){// 哨兵位头结点LTNode* phead = (LTNode*)malloc(sizeof(LTNode));phead->next = phead;phead->prev = phead;return phead;}
第一步当然是先使用malloc函数申请内存空间,然后就是两个指针的建立,尾部指针指向头结点头部,头部指针指向头结点尾部,返回带头结点,头结点初始化完成。
3.2 结点动态内存申请
结点动态内存申请(BuyListNode)
这个函数和上一篇中的单链表的函数类似
代码如下:
LTNode* BuyListNode(LTDateType x){LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->next = NULL;newnode->prev = NULL;return newnode;}
第一步也是先使用malloc函数申请内存空间,然后就是初始化这个结点的操作,将元素插入,两个指针指向空,返回新结点,完成结点初始化操作。
3.3 双向链表尾插
双向链表尾插(ListPushBack)
代码如下:
void ListPushBack(LTNode* phead, LTDateType x){assert(phead);LTNode* tail = phead->prev;LTNode* newnode = BuyListNode(x);tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;}
这里我们先是把phead的上一级指针赋给tail
再将要插入的元素赋给临时结点newnode
接着将tail的下一级指针指向newnode
再将newnode上一级指针指向tail
newnode下一级指针指向被插入结点phead
最后将phead的上一级指针再指向newnode完成尾插操作
3.4 双向链表尾删
双向链表尾删(ListPopBack)
代码如下:
void ListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);//防止链表中无元素继续删除的断言LTNode* tail = phead->prev;phead->prev = tail->prev;tail->prev->next = phead;free(tail);}
上述代码中第二个断言是为了防止链表中无元素继续删除
这里我们也是先把phead的上一级指针赋给tail
再将tail的上一级指针赋给phead的上一级指针
也就是指向要删除结点的上一结点
最后将要删除结点的前一个结点的下一级指针指向头结点
然后释放掉tail的内存空间完成尾删
3.5 双向链表头插
双向链表头插(ListPushFront)
代码如下:
void ListPushFront(LTNode* phead, LTDateType x){assert(phead);LTNode* newnode = BuyListNode(x);LTNode* next = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = next;next->prev = newnode;}
这里我们先和尾插一样将要插入的元素值赋给临时结点newnode
将phead下一级指针赋给临时结点next
再将newnode赋给phead下一级指针
也就是把phead的尾部指针指向newnode
把phead赋给newnode的上一级指针
再将next赋给newnode的下一级指针
最后把newnode赋给next的上一级指针,完成头插
3.6 双向链表头删
双向链表头删(ListPopFront)
代码如下:
void ListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);//防止链表中无元素继续删除的断言LTNode* next = phead->next;LTNode* nextNext = next->next;phead->next = nextNext;nextNext->prev = phead;free(next);}
和尾删一样这里的第二个断言也是为了防止链表中无元素继续删除
头删的第一步就是将phead的下一级指针赋给next
再将next的下一级指针赋给nextNext
再将nextNext赋给phead的下一级指针
最后将phead赋给nextNext的上一指针
把next的内存空间释放完成头删
3.7 双向链表查找
双向链表查找(ListFind)
代码如下:
LTNode* ListFind(LTNode* phead, LTDateType x){assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;}
这里的查找就是使用一个while循环遍历链表找到某节点的data符合要查找的值
找到了便返回结点,如果遍历一遍没找到,则返回空(NULL)。
3.8 在pos位置前插入
pos位置前插入(ListInsert)
代码如下:
void ListInsert(LTNode* pos, LTDateType x){assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyListNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;}
插入函数的实现首先创建第一个临时结点posPrev
把pos的上一级指针赋给posPrev
将要插入的元素x赋给newnode
再将newnode赋给posPrev的下一级指针
再将posPrev赋给newnode的上一级指针
再将pos赋给newnode的下一级指针
最后将再将newnode赋给pos的上一级指针完成插入操作
在这里我们可以利用ListInsert函数将前面的尾插和头插进行同义替换
双向链表尾插(ListPushBack)同义替换
代码如下:
void ListPushBack(LTNode* phead, LTDateType x){assert(phead);ListInsert(phead, x);}
双向链表头插(ListPushFront)同义替换
代码如下:
void ListPushFront(LTNode* phead, LTDateType x){assert(phead);ListInsert(phead->next, x);}
3.9 删除pos位置的结点
删除pos位置的结点(ListErase)
代码如下:
void ListErase(LTNode* pos){assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;posPrev->next = posNext;posNext->prev = posPrev;free(pos);pos = NULL;}
首先将pos的上一级指针赋给posPrev
再将将pos的下一级指针赋给posNext
再将posNext赋给posPrev下一级指针
最后把posPrev赋给posNext上一级指针
将pos内存空间释放,使pos等于空(NULL),完成删除。
同样的,我们也可以利用这个ListErase函数对尾删和头删进行同义替换
双向链表尾删(ListPopBack)同义替换
代码如下:
void ListPopBack(LTNode* phead){assert(phead);assert(phead->next != phead);ListErase(phead->prev);}
双向链表头删(ListPopFront)同义替换
代码如下:
void ListPopFront(LTNode* phead){assert(phead);assert(phead->next != phead);ListErase(phead->next);}
3.10 打印双向链表
打印双向链表(ListPrint)
代码如下:
void ListPrint(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){printf("%d ", cur->data);cur = cur->next;}printf("\n");}
这里的打印操作同样是利用while循环进行一遍遍历打印输出
3.11 销毁双向链表
销毁双向链表(ListDestroy)
代码如下:
void ListDestroy(LTNode* phead){assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);phead = NULL;}
和打印函数原理一样,只不过这里是再进行遍历的同时进行逐个删除
最后将phead内存空间释放,令phead等于空(NULL)完成链表销毁操作。在这里最后讲一下断言,在之前的单链表那一节的接口函数都有,写断言是为了让代码更健壮
一旦出现了编译错误,我们可以立马排查出问题出在哪里,这是一个不错的代码习惯
带头双向循环链表接口代码可能不是那么好理解,但是实现起来时,却更方便,所以带头双向循环链表对于我们来说是非常必要的知识点!
4、顺序表和链表的区别
特征 | 顺序表 | 链表 |
---|---|---|
存储空间 | 物理上一定连续 | 逻辑上连续物理上不一定连续 |
随机访问 | 支持:O(1) | 不支持:O(N) |
任意位置插入或删除元素 | 可能需要搬移元素,效率低O(N) | 只需修改指针指向 |
插入 | 动态顺序表,空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
缓存利用率 | 高 | 低 |
5、结语
顺序表到这一篇就结束了,这里的带头双向循环链表可能在代码体现上不是那么容易理解,这需要我们不断的去进行学习和实操,如果知识光看,在数据结构这门课的学习上是不会有提高的,最重要的还是练习!!!
制作不易,如有不正之处敬请指出,感谢大家的来访,UU们的观看是我坚持下去的动力,在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!不要忘了一键三连呦!