一、双向链表的结构
注意：双向链表又称带头双向循环链表
这⾥的“带头”跟前⾯我们说的“头节点”是两个概念，实际前⾯的在单链表阶段称呼不严
谨，但是为了同学们更好的理解就直接称为单链表的头节点。
带头链表⾥的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这⾥“放哨 的”
“哨兵位”存在的意义： 遍历循环链表避免死循环。
双向链表每个节点储存一个有效数据+前驱指针+后继指针
二、. 双向链表的实现
2.1 创建&初始化
2.2.1 List.h
#pragma once typedef struct ListNode { int val; struct ListNode* next; struct ListNode* prev; }LTNode; //初始化 LTNode* LTInit();
2.2.2 List.c
#define _CRT_SECURE_NO_WARNINGS #include"List.h" #include<stdlib.h> #include<assert.h> #include<stdio.h> LTNode* LTInit()//哨兵位初始化 { LTNode* head = (LTNode*)malloc(sizeof(LTNode)); head->val = -1; head->next = head->prev =head; return head; }
2.2.3 text.c
#define _CRT_SECURE_NO_WARNINGS #include"List.h" #include<stdio.h> int main() { LTNode* head; head=LTInit(); return 0; }
代码运行测试：
2.2尾插&头插
分析：
尾插
1.往d3节点的后面插入数据叫做尾插
2.往哨兵位head之前插入数据也叫尾插
头插
在哨兵位和头节点之间插入
2.2.1 List.h
//尾插 //1.往d3节点的后面插入数据叫做尾插 2.往哨兵位head之前插入数据也叫尾插 void LTPushBack(LTNode* head, int x); //打印 void LTPrint(LTNode* head); //头插 void LTPushFront(LTNode* head, int x);
2.2.2 List.c
//创建新节点 LTNode* Listbuynode(int x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); node->val = x; node->next = node->prev = NULL; return node; } void LTPushBack(LTNode* head, int x) { LTNode* node = Listbuynode(x); //对新节点进行操作 node->next = head; node->prev = head->prev; //对原来的尾节点和哨兵位进行操作 head->prev->next = node; head->prev = node; } void LTPrint(LTNode* head) { assert(head); LTNode* pcur = head->next; while (pcur != head) { printf("%d->", pcur->val); pcur = pcur->next; } printf("\n"); } void LTPushFront(LTNode* head, int x) { LTNode* node = Listbuynode(x); //对新节点进行操作 node->next = head->next; node->prev = head; //对哨兵位和头节点进行操作 head->next->prev = node; head->next = node; }
2.2.3 text.c
#define _CRT_SECURE_NO_WARNINGS #include"List.h" #include<stdio.h> int main() { LTNode* head; head=LTInit(); LTPushBack(head, 1); LTPushBack(head, 2); LTPushBack(head, 3); LTPushFront(head,4);//4->1->2->3 LTPrint(head); return 0; }
2.3 头删&尾删
2.3.1 List.h
//尾删 void LTPopBack(LTNode* head); //头删 void LTPopFront(LTNode* head);
2.3.2 List.c
void LTPopBack(LTNode* head) { //链表为空不能删除 assert(head); assert(head->next != head); //将尾节点进行保存 LTNode* del = head->prev; //连接次尾节点和哨兵位 del->prev->next = head; head->prev = del->prev; free(del); del = NULL; } void LTPopFront(LTNode* head) { //链表为空不能删除 assert(head); assert(head->next != head); //将头节点进行保存 LTNode* del = head->next; //连接哨兵位和次头节点 head->next = del->next; del->next->prev = head; free(del); del = NULL; }
2.3.3 text.c
#define _CRT_SECURE_NO_WARNINGS #include"List.h" #include<stdio.h> int main() { LTNode* head; head=LTInit(); LTPushBack(head, 1); LTPushBack(head, 2); LTPushBack(head, 3); LTPushFront(head, 4); LTPrint(head);//4->1->2->3 LTPopFront(head); LTPrint(head);//1->2->3 LTPopBack(head); LTPrint(head);1->2 return 0; }
2.4 查找数据&在pos节点后插入数据&删除pos节点
2.4.1 List.h
//在pos位置之后插入数据 void LTInsert(LTNode* pos, int x); //删除pos节点 void LTErase(LTNode* pos); //查找数据 LTNode* LTFind(LTNode* head, int x);
2.4.2 List.c
void LTInsert(LTNode* pos, int x) { assert(pos); LTNode* node = Listbuynode(x); //先处理新节点 node->prev = pos; node->next = pos->next; //在处理前后节点 pos->next = node; node->next->prev = node; } LTNode* LTFind(LTNode* head, int x) { assert(head); assert(head->next!=head); LTNode* pcur = head->next; while (pcur != head) { if (pcur->val == x) { return pcur; } pcur = pcur->next; } return NULL; } void LTErase(LTNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; }
2.4.3 text.c
#define _CRT_SECURE_NO_WARNINGS #include"List.h" #include<stdio.h> int main() { LTNode* head; head=LTInit(); LTPushBack(head, 1); LTPushBack(head, 2); LTPushBack(head, 3); LTPushBack(head, 4); //LTPopBack(head); //LTPrint(head); //LTPopBack(head); LTNode* find = LTFind(head, 4); LTInsert(find, 11); LTPrint(head);//1->2->3->4->11 LTErase(find);//1->2->3->11 LTPrint(head); return 0; }
2.5 销毁
若销毁接口用二级指针接受，传哨兵位指针的地址，那么可以改变哨兵位（指针指向）,使哨兵位指向NULL;
若销毁接口用一级指针接受，传一级指针（哨兵位指针），传过去的形参（是指针存储的地址），不能够改变指针的指向，在对形参操作，可以释放哨兵位指向的地址空间（形参的值为空间地址），但是不能改变实参指针的指向（实参依然指向原来被释放的地址空间），需要手动将实参置为NULL.
简而言之，若需要改变一级指针指向，需要传二级指针。
前面都是用一级指针传参，为了保持接口的一致性，我们用一级指针传参
2.5.1 List.h
1. //销毁 2. void LTDestroy(LTNode* phead);
2.5.2 List.c
void LTDestroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; LTNode* next = pcur->next; while (pcur != phead) { free(pcur); pcur = next; next = next->next; } free(phead); phead = NULL; }
2.5.3 text.c
#define _CRT_SECURE_NO_WARNINGS #include"List.h" #include<stdio.h> int main() { LTNode* head; head=LTInit(); LTPushBack(head, 1); LTPushBack(head, 2); LTPushBack(head, 3); LTPushFront(head, 4); /*LTPrint(head); LTPopFront(head);*/ LTPrint(head); //LTPopBack(head); //LTPrint(head); //LTPopBack(head); LTNode* find = LTFind(head, 4); /*LTInsert(find, 11);*/ LTErase(find); LTPrint(head); LTDestroy(head); head = NULL; return 0; }
2.6 完整代码
2.6.1 List.h
#pragma once typedef struct ListNode { int val; struct ListNode* next; struct ListNode* prev; }LTNode; //初始化 LTNode* LTInit(); //销毁 void LTDestroy(LTNode* phead); //尾插 //1.往d3节点的后面插入数据叫做尾插 2.往哨兵位head之前插入数据也叫尾插 void LTPushBack(LTNode* head, int x); //打印 void LTPrint(LTNode* head); //头插 void LTPushFront(LTNode* head, int x); //尾删 void LTPopBack(LTNode* head); //头删 void LTPopFront(LTNode* head); //在pos位置之后插入数据 void LTInsert(LTNode* pos, int x); //删除pos节点 void LTErase(LTNode* pos); //查找数据 LTNode* LTFind(LTNode* head, int x);
2.6.2 List.c
#define _CRT_SECURE_NO_WARNINGS #include"List.h" #include<stdlib.h> #include<assert.h> #include<stdio.h> LTNode* LTInit()//哨兵位初始化 { LTNode* head = (LTNode*)malloc(sizeof(LTNode)); head->val = -1; head->next = head->prev =head; return head; } //创建新节点 LTNode* Listbuynode(int x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); node->val = x; node->next = node->prev = NULL; return node; } void LTPushBack(LTNode* head, int x) { LTNode* node = Listbuynode(x); //对新节点进行操作 node->next = head; node->prev = head->prev; //对原来的尾节点和哨兵位进行操作 head->prev->next = node; head->prev = node; } void LTPrint(LTNode* head) { assert(head); LTNode* pcur = head->next; while (pcur != head) { printf("%d->", pcur->val); pcur = pcur->next; } printf("\n"); } void LTPushFront(LTNode* head, int x) { LTNode* node = Listbuynode(x); //对新节点进行操作 node->next = head->next; node->prev = head; //对哨兵位和头节点进行操作 head->next->prev = node; head->next = node; } void LTPopBack(LTNode* head) { //链表为空不能删除 assert(head); assert(head->next != head); //将尾节点进行保存 LTNode* del = head->prev; //连接次尾节点和哨兵位 del->prev->next = head; head->prev = del->prev; free(del); del = NULL; } void LTPopFront(LTNode* head) { //链表为空不能删除 assert(head); assert(head->next != head); //将头节点进行保存 LTNode* del = head->next; //连接哨兵位和次头节点 head->next = del->next; del->next->prev = head; free(del); del = NULL; } void LTInsert(LTNode* pos, int x) { assert(pos); LTNode* node = Listbuynode(x); //先处理新节点 node->prev = pos; node->next = pos->next; //在处理前后节点 pos->next = node; node->next->prev = node; } LTNode* LTFind(LTNode* head, int x) { assert(head); assert(head->next!=head); LTNode* pcur = head->next; while (pcur != head) { if (pcur->val == x) { return pcur; } pcur = pcur->next; } return NULL; } void LTErase(LTNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; } void LTDestroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; LTNode* next = pcur->next; while (pcur != phead) { free(pcur); pcur = next; next = next->next; } free(phead); phead = NULL; }
2.6.3 text.c
#define _CRT_SECURE_NO_WARNINGS #include"List.h" #include<stdlib.h> #include<assert.h> #include<stdio.h> LTNode* LTInit()//哨兵位初始化 { LTNode* head = (LTNode*)malloc(sizeof(LTNode)); head->val = -1; head->next = head->prev =head; return head; } //创建新节点 LTNode* Listbuynode(int x) { LTNode* node = (LTNode*)malloc(sizeof(LTNode)); node->val = x; node->next = node->prev = NULL; return node; } void LTPushBack(LTNode* head, int x) { LTNode* node = Listbuynode(x); //对新节点进行操作 node->next = head; node->prev = head->prev; //对原来的尾节点和哨兵位进行操作 head->prev->next = node; head->prev = node; } void LTPrint(LTNode* head) { assert(head); LTNode* pcur = head->next; while (pcur != head) { printf("%d->", pcur->val); pcur = pcur->next; } printf("\n"); } void LTPushFront(LTNode* head, int x) { LTNode* node = Listbuynode(x); //对新节点进行操作 node->next = head->next; node->prev = head; //对哨兵位和头节点进行操作 head->next->prev = node; head->next = node; } void LTPopBack(LTNode* head) { //链表为空不能删除 assert(head); assert(head->next != head); //将尾节点进行保存 LTNode* del = head->prev; //连接次尾节点和哨兵位 del->prev->next = head; head->prev = del->prev; free(del); del = NULL; } void LTPopFront(LTNode* head) { //链表为空不能删除 assert(head); assert(head->next != head); //将头节点进行保存 LTNode* del = head->next; //连接哨兵位和次头节点 head->next = del->next; del->next->prev = head; free(del); del = NULL; } void LTInsert(LTNode* pos, int x) { assert(pos); LTNode* node = Listbuynode(x); //先处理新节点 node->prev = pos; node->next = pos->next; //在处理前后节点 pos->next = node; node->next->prev = node; } LTNode* LTFind(LTNode* head, int x) { assert(head); assert(head->next!=head); LTNode* pcur = head->next; while (pcur != head) { if (pcur->val == x) { return pcur; } pcur = pcur->next; } return NULL; } void LTErase(LTNode* pos) { assert(pos); pos->prev->next = pos->next; pos->next->prev = pos->prev; free(pos); pos = NULL; } void LTDestroy(LTNode* phead) { assert(phead); LTNode* pcur = phead->next; LTNode* next = pcur->next; while (pcur != phead) { free(pcur); pcur = next; next = next->next; } free(phead); phead = NULL; }
三、顺序表和双向链表的优缺点分析
不同点 |
顺序表 | 链表（单链表） |
存储空间上 |
物理上一定连续 | 逻辑上连续，但物理上不⼀定连续 |
随机访问 |
⽀持O(1） |
不支持，O(n) |
任意位置插⼊或者删除元素 |
可能需要搬移元素，效率低O(N) |
只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 |
没有容量的概念 |
应⽤场景 |
元素⾼效存储+频繁访问 |
任意位置插⼊和删除频繁 |
