🌟一、面试官让你十分钟内实现带头双向循环链表
对于刚学链表的小白来说十分钟内实现一个带头双向循环链表是有点困难的，那有什么办法可以完成这个任务呢？别担心下面教你一步来实现。
🌟二、对链表的清晰认知
对于实现这个链表，首先结构是必须要写的，然后是初始化，而最重要的一个地方就是LTInsert(在pos位置之前插入)和LTErase(删除pos位置的值) 最后我们在头插 尾插 头删 尾删中复用就可以了最后再加上一个释放链表
🌟三、根据上述步骤简单实现
🌏3.1结构:
#define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int LTDataType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDataType data; }LTNode; LTNode* LTInit(); void LTPrint(LTNode* phead); void LTPushFront(LTNode* phead,LTDataType x); void LTPushBack(LTNode* phead,LTDataType x); void LTPopFront(LTNode* phead); void LTPopBack(LTNode* phead); LTNode* LTFind(LTNode* phead, LTDataType x); void LTInsert(LTNode* pos, LTDataType x); void LTErase(LTNode* pos); void LTDestroy(LTNode* phead);
🌏3.2查找(LTFind)+LTErase+LTInsert：
不太懂这部分代码的宝贝可以看上一章
【数据结构】- 几个步骤教你认识并实现一个链表之带头(哨兵位)双向循环链表(上)
【数据结构】- 几个步骤教你认识并实现一个链表之带头(哨兵位)双向循环链表(中)
//LTFind LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //LTInsert void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyLTNode(x); LTNode* Prev = pos->prev; Prev->next = newnode; newnode->prev = Prev; pos->prev = newnode; newnode->next = pos; } //LTErase void LTErase(LTNode* pos) { LTNode* Prev = pos->prev; LTNode* Next = pos->next; Prev->next = Next; Next->prev = Prev; free(pos); }
🌏3.3头插：
💫3.3.1代码：
void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead->next , x); }
🌏3.4尾插：
💫3.4.1代码：
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead, x); }
🌏3.5头删：
💫3.5.1代码：
void LTPopFront(LTNode* phead) { assert(phead); LTErase(phead->next); }
🌏3.6尾删：
💫3.6.1代码：
void LTPopBack(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTErase(phead->prev); }
🌏3.7释放链表：
void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); }
🌟四、完整代码
//List.h #define _CRT_SECURE_NO_WARNINGS 1 #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<stdbool.h> typedef int LTDataType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDataType data; }LTNode; LTNode* LTInit(); void LTPrint(LTNode* phead); void LTPushFront(LTNode* phead,LTDataType x); void LTPushBack(LTNode* phead,LTDataType x); void LTPopFront(LTNode* phead); void LTPopBack(LTNode* phead); LTNode* LTFind(LTNode* phead, LTDataType x); void LTInsert(LTNode* pos, LTDataType x); void LTErase(LTNode* pos); void LTDestroy(LTNode* phead); //List.c #define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" bool LTEmpty(LTNode* phead) { assert(phead); return phead->next == phead; } LTNode* BuyLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail"); } 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 LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next; printf("guard<==>"); while (phead != cur) { printf("%d==>", cur->data); cur = cur->next; } printf("\n"); } LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = BuyLTNode(x); LTNode* Prev = pos->prev; Prev->next = newnode; newnode->prev = Prev; pos->prev = newnode; newnode->next = pos; } void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead->next , x); } void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead, x); } void LTErase(LTNode* pos) { LTNode* Prev = pos->prev; LTNode* Next = pos->next; Prev->next = Next; Next->prev = Prev; free(pos); } void LTPopFront(LTNode* phead) { assert(phead); LTErase(phead->next); } void LTPopBack(LTNode* phead) { assert(phead); assert(!LTEmpty(phead)); LTErase(phead->prev); } void LTDestroy(LTNode* phead) { assert(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"List.h" void TestList() { LTNode* plist = LTInit(); //LTPushFront(plist, 1); //LTPushFront(plist, 2); //LTPushFront(plist, 3); //LTPushFront(plist, 4); LTPushBack(plist, 1); LTPushBack(plist, 2); LTPushBack(plist, 3); LTPushBack(plist, 4); LTPrint(plist); /*LTNode* pos = LTFind(plist,1); if (pos) { LTInsert(pos, 30); } LTPrint(plist);*/ /*LTNode* pos = LTFind(plist, 3); if (pos) { LTErase(pos, 30); } LTPrint(plist);*/ //LTPopFront(plist); //LTPopFront(plist); //LTPrint(plist); LTPopBack(plist); LTPopBack(plist); LTPrint(plist); } int main() { TestList(); return 0; }
😽总结
😽总体来说上面这种代码是比较优化的同时不会花费太多时间，简单易懂
😽Ending,今天的链表之带头双向循环链表(下)的内容就到此结束啦~，如果后续想了解更多，就请关注我吧
