一、链表的八种结构
我们已经知道链表可以有以下三种分法
而这三种结构又可以排列组合，形成八种结构
其中我们最常见的就是无头单向非循环链表和带头双向循环链表
1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了
二、带头双向循环链表的实现
1.链表的定义
对于这个链表，我们需要使用两个指针来控制，一个是前驱指针，一个是后继指针
typedef int LTDateType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDateType data; }ListNode;
2.链表的接口定义
如下代码所示，是我们需要实现的接口
//链表的初始化 ListNode* ListCreat(); //链表的打印 void ListPrint(ListNode* phead); //链表的尾插 void ListPushBack(ListNode* phead, LTDateType x); //链表的头插 void ListPushFront(ListNode* phead, LTDateType x); //链表是否为空 bool ListEmpty(ListNode* phead); //链表的尾删 void ListPopBack(ListNode* phead); //链表的头删 void ListPopFront(ListNode* phead); //链表的查找 ListNode* ListFind(ListNode* phead, LTDateType x); //链表在pos前面的插入 void ListInsert(ListNode* pos, LTDateType x); //链表在pos位置处的删除 void ListErase(ListNode* pos); //链表的销毁 void ListDestroy(ListNode* phead);
3.接口的具体实现
1.链表的初始化
ListNode* BuyListNode(LTDateType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } //链表的初始化 ListNode* ListCreat() { ListNode* phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; }
如上代码所示，对于这个初始化，他与单链表不同，单链表其实是没有必要去专门做一个初始化函数的。但同时我们需要传二级指针来解决一些问题
对于双向带头循环链表，我们就有必要设置一个初始化函数了。
我们有两种思路去构建这个函数
一种是在主函数中直接定义一个指针，然后通过传这个指针的地址去构建。但是这样我们就需要传二级指针了。
另外一种是我们可以利用返回值，这样我们就直接避免了传参数了。
2.链表的打印
//链表的打印 void ListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next; printf("<=head=>"); while (cur != phead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); }
如上代码所示，链表的打印与单链表的打印是一样的，没有什么太大的区别，我们可以利用printf来更加形象的表达双向循环的意思
3.链表的尾插
//链表的尾插 void ListPushBack(ListNode* phead, LTDateType x) { assert(phead); ListNode* newnode = BuyListNode(x); ListNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; }
对于尾插就比单链表简单多了，因为有了头节点，我们就不需要处理是否为空的状态了
4.链表的头插
//链表的头插 void ListPushFront(ListNode* phead, LTDateType x) { assert(phead); ListNode* newnode = BuyListNode(x); ListNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; }
头插和尾插基本上是非常类似的，这也得益于这种链表结构基本是无死角的
5.链表的头删尾删以及是否为空
//链表是否为空 bool ListEmpty(ListNode* phead) { assert(phead); return phead->next == phead; } //链表的尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(!ListEmpty(phead)); ListNode* tail = phead->prev; ListNode* tailPrev = tail->prev; phead->prev = tailPrev; tailPrev->next = phead; free(tail); tail = NULL; } //链表的头删 void ListPopFront(ListNode* phead) { assert(phead); assert(!ListEmpty(phead)); ListNode* first = phead->next; ListNode* firstNext = first->next; phead->next = firstNext; firstNext->prev = phead; free(first); first = NULL; }
对于头删和尾删其实也是一致的思路，我们只需要改变结点即可，值得注意的是，我们需要判断链表是否为空， 如果为空肯定不可以删除
6.链表的查找
//链表的查找 ListNode* ListFind(ListNode* phead,LTDateType x) { assert(phead); assert(!ListEmpty(phead)); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
这个也是比较简单的，他的思路与单链表的是一样的
7.链表在pos位置之前插入
//链表在pos前面的插入 void ListInsert(ListNode* pos, LTDateType x) { assert(pos); ListNode* newnode = BuyListNode(x); ListNode* prev = pos->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; }
这个的话，我们更能体会到他相对于单链表的优势了。我们只需要pos位置即可。然后思路和头插尾插是一致的
8.链表在pos位置的删除
//链表在pos位置处的删除 void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; }
对于删除，也是与头删尾删思路一致的
9.链表的销毁
//链表的销毁 void ListDestroy(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; }
对于链表的销毁思路与单链表也是一致的，只需要循环遍历即可
三、带头双向循环链表的完整代码
List.h
#pragma once #include<stdio.h> #include<malloc.h> #include<assert.h> #include<stdbool.h> typedef int LTDateType; typedef struct ListNode { struct ListNode* prev; struct ListNode* next; LTDateType data; }ListNode; //链表的初始化 ListNode* ListCreat(); //链表的打印 void ListPrint(ListNode* phead); //链表的尾插 void ListPushBack(ListNode* phead, LTDateType x); //链表的头插 void ListPushFront(ListNode* phead, LTDateType x); //链表是否为空 bool ListEmpty(ListNode* phead); //链表的尾删 void ListPopBack(ListNode* phead); //链表的头删 void ListPopFront(ListNode* phead); //链表的查找 ListNode* ListFind(ListNode* phead, LTDateType x); //链表在pos前面的插入 void ListInsert(ListNode* pos, LTDateType x); //链表在pos位置处的删除 void ListErase(ListNode* pos); //链表的销毁 void ListDestroy(ListNode* phead);
List.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" ListNode* BuyListNode(LTDateType x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc"); return NULL; } newnode->data = x; newnode->next = NULL; newnode->prev = NULL; return newnode; } //链表的初始化 ListNode* ListCreat() { ListNode* phead = BuyListNode(-1); phead->next = phead; phead->prev = phead; return phead; } //链表的打印 void ListPrint(ListNode* phead) { assert(phead); ListNode* cur = phead->next; printf("<=head=>"); while (cur != phead) { printf("%d<=>", cur->data); cur = cur->next; } printf("\n"); } //链表的尾插 void ListPushBack(ListNode* phead, LTDateType x) { assert(phead); ListNode* newnode = BuyListNode(x); ListNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } //链表的头插 void ListPushFront(ListNode* phead, LTDateType x) { assert(phead); ListNode* newnode = BuyListNode(x); ListNode* first = phead->next; phead->next = newnode; newnode->prev = phead; newnode->next = first; first->prev = newnode; } //链表是否为空 bool ListEmpty(ListNode* phead) { assert(phead); return phead->next == phead; } //链表的尾删 void ListPopBack(ListNode* phead) { assert(phead); assert(!ListEmpty(phead)); ListNode* tail = phead->prev; ListNode* tailPrev = tail->prev; phead->prev = tailPrev; tailPrev->next = phead; free(tail); tail = NULL; } //链表的头删 void ListPopFront(ListNode* phead) { assert(phead); assert(!ListEmpty(phead)); ListNode* first = phead->next; ListNode* firstNext = first->next; phead->next = firstNext; firstNext->prev = phead; free(first); first = NULL; } //链表的查找 ListNode* ListFind(ListNode* phead,LTDateType x) { assert(phead); assert(!ListEmpty(phead)); ListNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //链表在pos前面的插入 void ListInsert(ListNode* pos, LTDateType x) { assert(pos); ListNode* newnode = BuyListNode(x); ListNode* prev = pos->prev; prev->next = newnode; newnode->prev = prev; newnode->next = pos; pos->prev = newnode; } //链表在pos位置处的删除 void ListErase(ListNode* pos) { assert(pos); ListNode* prev = pos->prev; ListNode* next = pos->next; prev->next = next; next->prev = prev; free(pos); pos = NULL; } //链表的销毁 void ListDestroy(ListNode* phead) { assert(phead); ListNode* cur = phead->next; while (cur != phead) { ListNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; }
Test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" void TestList1() { ListNode* plist = ListCreat(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPrint(plist); ListPushFront(plist, 6); ListPushFront(plist, 7); ListPushFront(plist, 8); ListPushFront(plist, 9); ListPushFront(plist, 10); ListPrint(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPopBack(plist); ListPrint(plist); ListPopFront(plist); ListPopFront(plist); ListPopFront(plist); ListPopFront(plist); ListPrint(plist); } void TestList2() { ListNode* plist = ListCreat(); ListPushBack(plist, 1); ListPushBack(plist, 2); ListPushBack(plist, 3); ListPushBack(plist, 4); ListPushBack(plist, 5); ListPrint(plist); ListNode* pos = ListFind(plist, 3); (pos->data) *= 10; ListPrint(plist); ListInsert(pos, 20); ListPrint(plist); ListErase(pos); ListPrint(plist); } int main() { //TestList1(); TestList2(); return 0; }
四、顺序表和链表的区别
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持，O(1) | 不支持，O(N) |
| 任意位置插入或删除元素 | 可能需要搬移元素，效率低，O(N) | 只需要改变指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
如上表所示，是顺序表和链表的区别
在这里我们需要注意缓存利用率这个东西。
对于我们的顺序表/链表，想要实现他的数据访问、遍历、修改等
这些数据是由cpu来进行访问的。
也就是这些访问的指令都是cpu执行的。从而访问打印等操作。这时候cpu就需要去访问内存
而cpu其实是不能直接访问内存的，这是因为cpu太快了，内存太慢了
为了解决这个问题，就有了三级缓存，即cpu高速缓存这个东西。
也就是说cpu会先访问缓存，最高级的缓存再次缓存其实就是命中。
在计算机中有一个局部性原理，在访问某个位置的数据的时候，大概率要访问后面的数据。因此他就会将这个数据后面的数据也顺便加载进去。
这时候由于顺序表是连续的，后面的都直接被命中了。所以他的缓存利用率高
而链表他访问某个数据的时候也会加载一长段，但是后面的不一定会用。所以就会浪费，也会导致缓存污染。所以缓存利用率低。也就是他不仅没有起到正向作用，反而起到了反向作用。
本节内容到此位置
如果对你有帮助的话，不要忘记点赞加收藏哦！！！
