只有一个节点的时候，把头指针和尾指针都指向自己，形成了一个环形，通常把这种链表叫作双向循环链表
多个节点形成环形
双向循环链表主要分为三部分
-
前项指针
-
后项指针
-
数据域
-
第一个节点的前项指针指向最后一个节点，最后一个节点的后项指针指向第一个节点
#include创建节点#include #include typedef struct Node { int data; //数据域 struct Node* front; //前项指针 struct Node* tail; //后项指针 }NODE,*LPNODE,*LPDLIST;
把用户的数据变成一个结构体变量
LPNODE createNode(int data)
{
//申请内存
LPNODE newNode = (LPDLIST)malloc(sizeof(NODE));
//断言处理
assert(newNode);
//前项指针、后项指针置为空
newNode->front = NULL;
newNode->tail = NULL;
//给数据做初始化
newNode->data = data;
return newNode;
}
创建链表
-
描述链表最初的状态，创建一个不带数据的链表，链表就是结构体变量和结构体变量连接在一起
-
需要一个表头，由于是环形，如果没有表头不方便表示，创建一个表头起区分作用。创建无头链表也可以，但是也需要有一个节点表示这个链表
LPDLIST createList()
{
LPDLIST headNode = (LPDLIST)malloc(sizeof(NODE)); //头节点 做动态内存申请
assert(headNode);
headNode->front = headNode; //头指针指向自身 尾指针指向自身 数据不做处理
headNode->tail = headNode;
return headNode;
}
头插法
创建新节点做插入四步操作，不需要考虑空的情况，不存在空的情况，注意插入的顺序一定是先连后断
先求出来表头 headNode->tail
①原来链表的尾节点的前项指针指向新节点
②新节点的前项指针指向原来链表
③原来链表的后项指针指向新节点
④新节点的后项指针指向原来链表的尾节点
//要插入的链表 插入的数据
void push_front(LPDLIST headNode,int data)
{
//创建新节点
LPNODE newNode = createNode(data);
//就算只有一个节点、只有一个表头headNode->tail不可能为空 直接做连接就可以了
headNode->tail->front = newNode;
newNode->front = headNode;
newNode->tail = headNode->tail;
headNode->tail = newNode;
}
//测试代码
LPDLIST list = createList();
push_front(list, 1); //1
push_front(list, 2); //2 1
printByFront(list); //1 2 通过前项指针做打印 从后往前
printByTail(list); //2 1 通过后项指针做打印 从前往后
打印链表
可以通过前项指针去做打印，也可以通过后项指针去做打印
通过前项指针做打印可以通过前项指针去做打印，由于是环形，所以打印条件不太一样，不可能用空来做判定。环形的结束状态就是跑一圈又回到自己这个位置，我们可以从第二个节点开始打印，如果不等于头节点就一直做打印
void printByFront(LPDLIST headNode)
{
//头节点的前项指针就是最后一个节点
LPNODE pmove = headNode->front;
//最后一个不等于头节点
while (pmove != headNode)
{
//打印数据
printf("%dt", pmove->data);
pmove = pmove->front;
}
printf("n");
}
通过后项指针做打印
void printByTail(LPDLIST headNode)
{
LPNODE pmove = headNode->tail;
while (pmove != headNode)
{
printf("%dt", pmove->data);
pmove = pmove->tail;
}
printf("n");
}
尾插法
错误的画法，指针的方向反，两个指针指向同一个位置
先求出来表尾 headNode->front
①原来链表的尾节点的后项指针指向新节点
②新节点的后项指针指向原来链表的第一个节点
③新节点的前项指针指向原来链表的尾节点
④原来链表的第一个节点的前项指针指向新节点
void push_back(LPDLIST headNode, int data)
{
//创建新节点
LPNODE newNode = createNode(data);
headNode->front->tail = newNode;
newNode->tail = headNode;
newNode->front = headNode->front;
headNode->front = newNode;
}
//测试代码
push_back(list, 888);
printByTail(list); //2 1 888
printByFront(list); //888 2 1
在指定位置前做插入
找指定位置，定义一个移动的指针从第一个节点开始找，头节点不用找，找一个环形代表没找到
void push_appoin(LPDLIST headNode, int posData, int data)
{
//前驱节点置为头节点
LPNODE preNode = headNode;
//从第一个节点开始找
LPNODE curNode = headNode->tail;
//1.当前节点不等于头节点表示没有形成一个环形 2.当前节点的数据不等于指定数据
while (curNode != headNode&&curNode->data!=posData)
{
//并排往下走
preNode = curNode;
curNode = preNode->tail;
}
//分析结果做插入
if (curNode == headNode)
{
printf("未找到指定位置,无法插入!n");
}
else
{
//找到了 创建一个新节点做插入
LPNODE newNode = createNode(data);
//tail指向
preNode->tail = newNode;
newNode->tail = curNode;
//front指向
curNode->front = newNode;
newNode->front = preNode;
}
}
//测试代码
push_appoin(list, 888, 666);
printByTail(list); //2 1 666 888
printByFront(list); //888 666 2 1
push_appoin(list, 2, 999);
printByFront(list); //999 2 1 666 888
printByTail(list); //2 1 666 888 999
头删法
①头节点的下一个指向要删除节点的下一个
②要删除节点的下一个的前项指针指向头节点
void pop_front(LPDLIST headNode)
{
//头指针、尾指针指向自己 这个链表就是空的
if (headNode==NULL||headNode->front == headNode)
{
printf("链表为空无法删除!n");
}
else
{
//保存头部的下一个
LPNODE nextNode = headNode->tail;
//连接
headNode->tail = nextNode->tail;
nextNode->tail->front = headNode;
//释放
free(nextNode);
//置空
nextNode = NULL;
}
}
//测试代码
pop_front(list);
printByTail(list); //2 1 666 888
printByFront(list); //888 666 1 2
尾删法
①最后一个节点的前一个节点的后项指针指向头节点
②头节点的前项指针指向最后一个节点的前一个节点
void pop_back(LPDLIST headNode)
{
if (headNode == NULL || headNode->front == headNode)
{
printf("链表为空无法删除!n");
}
else
{
//保存尾部的上一个
LPNODE backNode = headNode->front;
backNode->front->tail = headNode;
headNode->front = backNode->front;
//释放
free(backNode);
//置空
backNode = NULL;
}
}
//测试代码
pop_back(list);
printByTail(list); //2 1 666
printByFront(list); //666 1 2
