在上篇文章数据结构2——单链表中，我们了解了什么是链表，以及单链表的实现，接着上篇文章，本篇文章介绍一下比单链表更常用的链表——双向循环链表。 
1.双向链表的实现
1.1节点
单链表的节点存的有数据域和一个指向下一个节点后继指针，因此单链表只能单向遍历。
要想实现双向遍历，就需要在节点里增加一个指向前一个节点的前驱指针。
typedef int DLTDataType; typedef struct DListNode { DLTDataType data; struct DListNode* prev;//前继指针 struct DListNode* next;//后继指针 }DLTNode;
1.2 初始化节点
//初始化节点函数实现 DLTNode* DLTInit() { DLTNode* phead = BuyDLTNode(-1); phead->next = phead; phead->prev = phead; return phead; }
1.3 动态开辟新节点
//开辟新节点函数实现 DLTNode* BuyDLTNode(DLTDataType x) { DLTNode* node = (DLTNode*)malloc(sizeof(DLTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = NULL; node->prev = NULL; return node; }
1.4 遍历链表
void DLTPrint(DLTNode* phead) { assert(phead); printf("phead <-> "); DLTNode* cur = phead->next; while (cur != phead) { printf("%d <-> ", cur->data); cur = cur->next; } printf("\n"); }
1.5 查找
//查找 DLTNode* DLTFind(DLTNode* phead, DLTDataType x) { assert(phead); DLTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; }
1.6 插入
1.尾插
//尾插函数实现 void DLTPushBack(DLTNode* phead, DLTDataType x) { assert(phead); //①常规写法 DLTNode* tail = phead->prev; DLTNode* newnode = BuyDLTNode(x); newnode->prev = tail; tail->next = newnode; newnode->next = phead; phead->prev = newnode; //②复用 DLTInsert //DLTInsert(phead, x); }
2. 头插
//头插函数实现 void DLTPushFront(DLTNode* phead, DLTDataType x) { assert(phead); //①常规写法 DLTNode* newnode = BuyDLTNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; //②复用DLTInsert //DLTInsert(phead->next, x); }
3.在pos之前插入
//在pos之前插入 void DLTInsert(DLTNode* pos, DLTDataType x) { assert(pos); DLTNode* posPrev = pos->prev; DLTNode* newnode = BuyDLTNode(x); posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; }
1.7 删除
1. 尾删
//尾删函数实现 void DLTPopBack(DLTNode* phead) { assert(phead); assert(phead->next != phead);//检查链表是否为空 //①常规写法 DLTNode* tail = phead->prev; DLTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; //②复用DLTErase //DLTErase(phead->prev); }
2. 头删
//头删函数实现 void DLTPopFront(DLTNode* phead) { assert(phead); assert(phead->next != phead); //①常规写法 DLTNode* first = phead->next; DLTNode* second = first->next; free(first); phead->next = second; second->prev = phead; //②复用DLTErase //DLTErase(phead->next); }
3.删除pos位置
//删除pos位置 void DLTErase(DLTNode* pos) { assert(pos); DLTNode* posPrev = pos->prev; DLTNode* posNext = pos->next; free(pos); posPrev->next = posNext; posNext->prev = posPrev; }
1.8 其他函数
1. 链表长度
//链表长度 int DLTSize(DLTNode* phead) { assert(phead); int size = 0; DLTNode* cur = phead->next; while (cur != phead) { ++size; cur = cur->next; } return size; }
2. 销毁链表
//销毁函数 void DLTDestory(DLTNode* phead) { assert(phead); DLTNode* cur = phead->next; while (cur != phead) { DLTNode* next = cur->next; free(cur); cur = next; } free(phead); }
1.9 测试
int main() { DLTNode* plist = DLTInit(); DLTPushBack(plist, 1); DLTPushBack(plist, 2); DLTPushBack(plist, 3); DLTPushBack(plist, 4); DLTPushBack(plist, 5); DLTPrint(plist); DLTPushFront(plist, 10); DLTPushFront(plist, 11); DLTPushFront(plist, 12); DLTPrint(plist); DLTDestory(plist); plist = NULL; return 0; }
2.顺序表和链表的比较
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定 连续 |
| 随机访问 | 支持O(1) | 不支持O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低 O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要 扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
*源代码
DLish.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> typedef int DLTDataType; typedef struct DListNode { DLTDataType data; struct DListNode* prev;//前继指针 struct DListNode* next;//后继指针 }DLTNode; //开辟新节点函数声明 DLTNode* BuyDLTNode(DLTDataType x); //初始化节点函数声明 DLTNode* DLTInit(); //遍历函数声明 void DLTPrint(DLTNode* phead); //尾插函数声明 void DLTPushBack(DLTNode* phead, DLTDataType x); //头插函数声明 void DLTPushFront(DLTNode* phead, DLTDataType x); //尾删函数声明 void DLTPopBack(DLTNode* phead); //头删函数声明 void DLTPopFront(DLTNode* phead); //链表长度 int DLTSize(DLTNode* phead); //查找 DLTNode* DLTFind(DLTNode* phead, DLTDataType x); //在pos之前插入 void DLTInsert(DLTNode* pos, DLTDataType x); //删除pos位置 void DLTErase(DLTNode* pos); //销毁函数 void DLTDestory(DLTNode* phead);
DLish.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "DList.h" //开辟新节点函数实现 DLTNode* BuyDLTNode(DLTDataType x) { DLTNode* node = (DLTNode*)malloc(sizeof(DLTNode)); if (node == NULL) { perror("malloc fail"); exit(-1); } node->data = x; node->next = NULL; node->prev = NULL; return node; } //初始化节点函数实现 DLTNode* DLTInit() { DLTNode* phead = BuyDLTNode(-1); phead->next = phead; phead->prev = phead; return phead; } //遍历函数实现 void DLTPrint(DLTNode* phead) { assert(phead); printf("phead <-> "); DLTNode* cur = phead->next; while (cur != phead) { printf("%d <-> ", cur->data); cur = cur->next; } printf("\n"); } //尾插函数实现 void DLTPushBack(DLTNode* phead, DLTDataType x) { assert(phead); //①常规写法 DLTNode* tail = phead->prev; DLTNode* newnode = BuyDLTNode(x); newnode->prev = tail; tail->next = newnode; newnode->next = phead; phead->prev = newnode; //②复用 DLTInsert //DLTInsert(phead, x); } //头插函数实现 void DLTPushFront(DLTNode* phead, DLTDataType x) { assert(phead); //①常规写法 DLTNode* newnode = BuyDLTNode(x); newnode->next = phead->next; phead->next->prev = newnode; phead->next = newnode; newnode->prev = phead; //②复用DLTInsert //DLTInsert(phead->next, x); } //尾删函数实现 void DLTPopBack(DLTNode* phead) { assert(phead); assert(phead->next != phead);//检查链表是否为空 //①常规写法 DLTNode* tail = phead->prev; DLTNode* tailPrev = tail->prev; free(tail); tailPrev->next = phead; phead->prev = tailPrev; //②复用DLTErase //DLTErase(phead->prev); } //头删函数实现 void DLTPopFront(DLTNode* phead) { assert(phead); assert(phead->next != phead); //①常规写法 DLTNode* first = phead->next; DLTNode* second = first->next; free(first); phead->next = second; second->prev = phead; //②复用DLTErase //DLTErase(phead->next); } //链表长度 int DLTSize(DLTNode* phead) { assert(phead); int size = 0; DLTNode* cur = phead->next; while (cur != phead) { ++size; cur = cur->next; } return size; } //查找 DLTNode* DLTFind(DLTNode* phead, DLTDataType x) { assert(phead); DLTNode* cur = phead->next; while (cur != phead) { if (cur->data == x) { return cur; } cur = cur->next; } return NULL; } //在pos之前插入 void DLTInsert(DLTNode* pos, DLTDataType x) { assert(pos); DLTNode* posPrev = pos->prev; DLTNode* newnode = BuyDLTNode(x); posPrev->next = newnode; newnode->prev = posPrev; newnode->next = pos; pos->prev = newnode; } //删除pos位置 void DLTErase(DLTNode* pos) { assert(pos); DLTNode* posPrev = pos->prev; DLTNode* posNext = pos->next; free(pos); posPrev->next = posNext; posNext->prev = posPrev; } //销毁函数 void DLTDestory(DLTNode* phead) { assert(phead); DLTNode* cur = phead->next; while (cur != phead) { DLTNode* next = cur->next; free(cur); cur = next; } free(phead); }
test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "DList.h" int main() { DLTNode* plist = DLTInit(); DLTPushBack(plist, 1); DLTPushBack(plist, 2); DLTPushBack(plist, 3); DLTPushBack(plist, 4); DLTPushBack(plist, 5); DLTPrint(plist); DLTPushFront(plist, 10); DLTPushFront(plist, 11); DLTPushFront(plist, 12); DLTPrint(plist); DLTDestory(plist); plist = NULL; DLTPrint(plist); return 0; }
