上篇文章简述讲解了链表的基本概念并且实现了无头单向不循环链表：https://developer.aliyun.com/article/1400244?spm=a2c6h.13148508.setting.14.1dab4f0eLraDPx
今天给大家带来带头双向循环链表的实现：
一.项目文件规划
头文件DoubleList.h:用来基础准备（常量定义，typedef），链表表的基本框架，函数的声明
源文件DoubleList.h:用来各种功能函数的具体实现
源文件test.c:用来测试功能是否有问题，进行基本功能的使用
二.基本结构及功能一览(DoubleList.h)
结构体定义
#include<stdio.h> #include<assert.h> #include<stdlib.h> typedef int LTDataType; typedef struct ListNode { struct ListNode* next;//下一个节点 struct ListNode* prev;//上一个节点 LTDataType val;//数据 }LTNode;
接口功能一览
LTNode* LTInit();//初始化 void LTPrint(LTNode* phead);//打印数据 void LTPushBack(LTNode* phead, LTDataType x);//尾插 void LTPopBack(LTNode* phead);//尾删 void LTPushFront(LTNode* phead, LTDataType x);//头插 void LTPopFront(LTNode* phead);//头删 LTNode* LTFind(LTNode* phead, LTDataType x);//查找 void LTInsert(LTNode* pos, LTDataType x);//在pos前插入 void LTErase(LTNode* pos);//删除pos void LTDestroy(LTNode* phead);//销毁
三.各功能接口具体实现
1.创建节点
因为后面尾插，头插，插入，初始化都要用到创建新节点，所以抽出来作为一个函数
LTNode* CreateLTNode(LTDataType x) { LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));//动态开辟 if (newnode == NULL) { perror("malloc"); return -1; } newnode->val = x; newnode->next = NULL; newnode->prev = NULL; return newnode; }
2.初始化
1.第一种：返回动态开辟的地址（不会销毁）
LTNode* LTInit() { LTNode* a =CreateLTNode(-1); a->next = a;//一开始一个节点时，下一个和上一个都指向自己 a->prev = a;// return a; }
2.第二种：传入二级指针（要直接改变头节点的值）
void LTInit(LTNode** pphead) { *pphead = CreateLTNode(-1); (*pphead)->next = *pphead; (*pphead)->prev = *pphead; }
这两种皆可
void LTPrint(LTNode* phead) { assert(phead); LTNode* cur = phead->next;//头结点数据无效，不需要打印 while (cur != phead) { printf("%d ", cur->val); cur = cur->next; } printf("\n"); }
4.尾插
void LTPushBack(LTNode* phead, LTDataType x)//无有效节点也适用 { assert(phead); LTNode* newnode = CreateLTNode(x); LTNode* tail = phead->prev; // phead tail newnode 位置展示 newnode->next = phead; phead->prev = newnode; newnode->prev = tail; tail->next = newnode; }
5.尾删
void LTPopBack(LTNode* phead)//只有一个有效节点也适用 { assert(phead); LTNode* tail = phead->prev; LTNode* pretail = tail->prev; // phead pretail tail 位置展示 free(tail); tail = NULL; phead->prev = pretail; pretail->next = phead; }
6.头插
void LTPushFront(LTNode* phead, LTDataType x)//无有效节点也适用 { assert(phead); LTNode* newnode = CreateLTNode(x); //phead newnode firest tail 位置展示 newnode->next = phead->next; phead->next->prev = newnode; newnode->prev = phead; phead->next = newnode; }
7.头删
void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead);//只有哨兵位时不能删 LTNode* first = phead->next; LTNode* second = first->next; //phead first second tail 位置展示 free(first); first = NULL; phead->next = second; second->prev = phead; }
8.查找
LTNode* LTFind(LTNode* phead, LTDataType x) { assert(phead); assert(phead->next != phead);//只有哨兵位时没必要查 LTNode* cur = phead->next; while (cur != phead) { if (cur->val == x) { return cur; } cur = cur->next; } return NULL; }
9.插入pos前
void LTInsert(LTNode* pos, LTDataType x) { assert(pos); LTNode* newnode = CreateLTNode(x); LTNode* pre = pos->prev; //pre newnode pos tail 位置展示 pre->next = newnode; newnode->prev = pre; newnode->next = pos; pos->prev = newnode; }
- 将前一个节点
pre的next指针指向新节点newnode - 将新节点
newnode的prev指针指向前一个节点pre - 将新节点
newnode的next指针指向指定节点pos - 将指定节点
pos的prev指针指向新节点newnode
10.删除pos位置
void LTErase(LTNode* pos) { assert(pos); LTNode* pre = pos->prev; LTNode* next = pos->next; //pre pos next tail 位置展示 pre->next = next; next->prev = pre; free(pos); pos = NULL; }
11.销毁
因为每个节点时malloc动态开辟出来的，要把每个节点都依次销毁
void LTDestroy(LTNode* phead) { assert(phead); LTNode* cur = phead->next; while (cur->next != phead) { LTNode* next = cur->next; free(cur); cur = next; } free(phead); phead = NULL; }
四.利用插入和删除改变“两插两删”（快速写出链表）
void LTPushBack(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead, x);//尾插就是在phead前插入 } void LTPopBack(LTNode* phead) { assert(phead); assert(phead->next != phead); LTErase(phead->prev); } void LTPushFront(LTNode* phead, LTDataType x) { assert(phead); LTInsert(phead->next, x);//头插就是插入到phead的下一个 } void LTPopFront(LTNode* phead) { assert(phead); assert(phead->next != phead); LTErase(phead->next); }
那这次就先到这里啦！两种常见的链表都已经实现完毕，接下来大概率是栈和队列了，感谢大家支持
