带头双向循环链表的结构
- 注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严
谨，但是为了同学们更好的理解就直接称为单链表的头节点。 - 带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨
的” 哨兵位存在的意义：
- 遍历循环链表避免死循环。
- 每个节点有三部分内容：
- 保存数据的
val - 保存下一个节点的地址next指针
- 保存前一个节点的地址prev指针
实现双向链表
我们需要实现以下功能
头文件的定义
List.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<assert.h> // 带头+双向+循环链表增删查改实现 typedef int LTDataType; typedef struct ListNode { LTDataType _val; struct ListNode* _next; struct ListNode* _prev; }ListNode; //哨兵位初始化 ListNode* ListInit(); // 创建返回链表的头结点. ListNode* ListCreate(LTDataType* x); // 双向链表销毁 void ListDestory(ListNode* pHead); // 双向链表打印 void ListPrint(ListNode* pHead); // 双向链表尾插 void ListPushBack(ListNode* pHead, LTDataType x); // 双向链表尾删 void ListPopBack(ListNode* pHead); // 双向链表头插 void ListPushFront(ListNode* pHead, LTDataType x); // 双向链表头删 void ListPopFront(ListNode* pHead); // 双向链表查找 ListNode* ListFind(ListNode* pHead, LTDataType x); // 双向链表在pos的前面进行插入 void ListInsert(ListNode* pos, LTDataType x); // 双向链表删除pos位置的节点 void ListErase(ListNode* pos);
创建节点
- malloc一个节点，然后让新节点的next和prev赋值为空，将值给了val，最后返回空间
ListNode* ListCreate(LTDataType* x) { ListNode* newnode = (ListNode*)malloc(sizeof(ListNode)); if (newnode == NULL) { perror("malloc fail!\n"); exit(-1); } newnode->_val = x; newnode->_next = NULL; newnode->_prev = NULL; return newnode;
哨兵位初始化
- 这里我们初始化成
-1代表是哨兵位，然后让前驱指针和next指针指向自己
ListNode* ListInit() { ListNode* pHead = ListCreate(-1); pHead->_next = pHead; pHead->_prev = pHead; return pHead; }
尾插
void ListPushBack(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* tail = pHead->_prev; ListNode* newnode = ListCreate(x); // phead tail newnode tail->_next = newnode; newnode->_prev = tail; newnode->_next = pHead; pHead->_prev = newnode;
尾删
void ListPopBack(ListNode* pHead) { assert(pHead); assert(pHead->_next != pHead); ListNode* tail = pHead->_prev; ListNode* tailprev = tail->_prev; free(tail); tailprev->_next = pHead; pHead->_prev = tailprev; }
头插
void ListPushFront(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* cur = pHead->_next; ListNode* newnode = ListCreate(x); pHead->_next = newnode; newnode->_prev = pHead; newnode->_next = cur; cur->_prev = newnode; }
头删
void ListPopFront(ListNode* pHead) assert(pHead); assert(pHead->_next != pHead); ListNode* first = pHead->_next; ListNode* second = first->_next; pHead->_next = second; second->_prev = pHead; free(first); first = NULL; }
打印
void ListPrint(ListNode* pHead) { ListNode* tail = pHead->_next; printf("哨兵位->"); while (tail != pHead) { printf("%d->", tail->_val); tail = tail->_next; } printf("NULL\n");
查找
ListNode* ListFind(ListNode* pHead, LTDataType x) { assert(pHead); ListNode* cur = pHead->_next; while (cur != pHead) { if (cur->_val == x) { return cur; } cur = cur->_next; } return NULL; }
指定位置前插入
void ListInsert(ListNode* pos, LTDataType x) { assert(pos); ListNode* newnode = ListCreate(x); ListNode* prev = pos->_prev; prev->_next = newnode; newnode->_prev = prev; pos->_prev = newnode; newnode->_next = 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 ListDestory(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<stdlib.h> #include<assert.h> #include<stdbool.h> typedef int LTDataType; typedef struct ListNode { LTDataType val; struct ListNode* next; struct ListNode* prev; }LTNode; //初始化哨兵位 LTNode* LTInit(); //创建节点 LTNode* LTcreate(LTDataType x); //销毁 void LTDestroy(LTNode* phead); //打印 void LTPrint(LTNode* phead); //判断是否为空 bool LTEmpty(LTNode* phead); //尾插 void LTPushBack(LTNode* phead, LTDataType x); //尾删 void LTPopBack(LTNode* phead); //头插 void LTPushFront(LTNode* phead, LTDataType x); //头删 void LTPopFront(LTNode* phead); //指定位置插入 void LTInsert(LTNode* pos, LTDataType x); //指定位置删除 LTNode* LTErase(LTNode* pos); //查找 LTNode* LTFind(LTNode* phead, LTDataType x);
List.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"List.h" //初始化哨兵位 LTNode* LTInit() { LTNode* phead = LTcreate(-1); phead->next = phead; phead->prev = phead; return phead; } //创建节点 LTNode* LTcreate(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode)); if (newnode == NULL) { perror("malloc fail!\n"); exit(-1); } newnode->next = NULL; newnode->prev = NULL; newnode->val = x; return newnode; } //销毁 void LTDestroy(LTNode* phead); //打印 void LTPrint(LTNode* phead) { assert(phead); printf("哨兵位<->"); LTNode* cur = phead->next; while (cur != phead) { printf("%d<->", cur->val); cur = cur->next; } printf("\n"); } //判断是否为空 bool LTEmpty(LTNode* phead) { assert(phead); return phead->val == 0; } //尾插 void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTcreate(x); LTNode* tail = phead->prev; tail->next = newnode; newnode->prev = tail; newnode->next = phead; phead->prev = newnode; } //尾删 void LTPopBack(LTNode* phead) { assert(phead); LTNode* tail = phead->prev; LTNode* tailprev = tail->prev; free(tail); tail = NULL; tailprev->next = phead; phead->prev = tailprev; } //头插 void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTNode* newnode = LTcreate(x); LTNode* cur = phead->next; phead->next = newnode; newnode->prev = phead; cur->prev = newnode; newnode->next = cur; } //头删 void LTPopFront(LTNode* phead) { assert(phead); LTNode* first = phead->next; LTNode* second = first->next; free(first); phead->next = second; second->prev = phead; } //查找 LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); LTNode* cur = phead->next; while (cur != phead) { if (cur->val == x) { return cur; } cur = cur->next; } return NULL; } //指定位置的前面插入 void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = LTcreate(x); LTNode* posprev = pos->prev; posprev->next = newnode; newnode->prev = posprev; newnode->next = pos; pos->prev = newnode; } //指定位置删除 LTNode* LTErase(LTNode* pos) { assert(pos); LTNode* posprev = pos->prev; LTNode* posnext = pos->next; free(pos); posprev->next = posnext; posprev = posprev; }
- 顺序表和双向链表的分析
| 不同点 | 顺序表 | 链表（单链表） |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
