目录
循环链表的基本概念
循环链表是一种特殊的链表, 和普通链表的不同是它的尾节点的next指向了头结点
这样做的好处是从任何一个节点开始都能找到其他所有节点, 当然,不能保证时间复杂度较优
循环链表一般也有两种: 单循环链表和双循环链表, 其实也就是有没有prior前驱指针的区别
这里就仅以单循环链表为例了:
注意: 空的单循环链表头结点的next指向头结点(他自己)
题外话: 记得王道有一个很坑的题:
问一个单循环链表的头结点为head, 如果head->next->next=head, 那么这个链表的长度是多少?
答案是0或者1, 原因一想只知道,但是很容易认为长度就是1[哭]
算法时间复杂度
和普通单链表几乎没有区别
- 找到某个索引的节点: O(n), (不能随机访问,只能从头开始找)
- 在头部/尾部插入节点: O(1)
- 在中间某位置插入节点: O(n) (因为需要找到节点的位置)
- 删除第一个结点(如果有头指针或者尾指针): O(1)
- 删除最后一个节点 (不管是否有尾指针): O(n)
- 删除中间某位置的节点: O(n) (也是因为需要找到节点位置)
这里有一个值的注意的点:
因为是循环链表, 所以尾指针比头指针有用, 两者可以不用同时有, 只要有尾指针就行了
但是如果是要删除最后一个节点, 两个指针都不好使了(需要的是指向倒数第二个节点的指针)
但是这时可以使用循环双链表(操作性能性能最优的链表)
C语言实现
循环单链表
/**
* @file circular_linked_list.c
* @author xiaoxiao (you@domain.com)
* @brief 循环单链表
* @version 0.1
* @date 2022-03-04
*
* @copyright Copyright (c) 2022
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
struct Node * next;
int data;
}Node;
typedef Node* PNode;
/**
* @brief 初始化表头(无数据)
*
* @return PNode 表头
*/
PNode initalList(){
// 表头不存储数据
// 最后一个节点的指针指向头结点,表示为空
PNode pHead = (PNode) malloc(sizeof(Node));
pHead -> next = pHead;
return pHead;
}
/**
* @brief 在尾部插入一个元素
*
* @param pHead 链表头
* @param data 数据值
*/
void insertInTail(PNode pHead, int data){
PNode pCurrent = pHead;
while(pCurrent -> next != pHead){
pCurrent = pCurrent -> next;
}
pCurrent -> next = (PNode)(malloc(sizeof(Node)));
pCurrent -> next -> next = pHead;
pCurrent -> next -> data = data;
}
/**
* @brief 在任意索引插入一个元素
* index=1是在表头后面(第一个元素)插入
*
* @param pHead 链表头
* @param index 索引
* @param data 数据值
*/
bool insertByIndex(PNode pHead, int index, int data){
PNode pCurrent = pHead;
int i = 1;
do{
if(i == index){
PNode pNewNode = (PNode) malloc (sizeof(Node)); // 新节点
pNewNode -> data = data;
pNewNode -> next = pCurrent -> next;
pCurrent -> next = pNewNode;
return true;
}
pCurrent = pCurrent -> next;
i ++;
}while(pCurrent != pHead);
printf("索引大于链表长度+1,无法插入\n");
return false;
}
/**
* @brief 删除尾部元素
*
* @param pHead 链表头
*/
bool deleteTail(PNode pHead){
if(pHead -> next == pHead){
printf("链表为空, 不能删除\n");
return false;
}
PNode pCurrent = pHead;
PNode pPrev = NULL;
while(pCurrent -> next != pHead){
pPrev = pCurrent;
pCurrent = pCurrent -> next;
}
pPrev -> next = pHead;
free(pCurrent);
return true;
}
bool deleteByIndex(PNode pHead, int index){
PNode pCurrent = pHead;
for(int i = 1; i < index; i++){
if(pCurrent -> next != pHead){
pCurrent = pCurrent -> next;
}
else{
printf("索引大于链表长度,无法删除\n");
return false;
}
// pCurrent是要删除的前一个节点
}
if(pCurrent -> next == pHead){ // 这就是最后一个节点
printf("索引大于链表长度, 无法插入\n");
return false;
}
PNode pNext = pCurrent -> next -> next;
free(pCurrent -> next);
pCurrent -> next = pNext;
return true;
}
/**
* @brief 打印链表
*
* @param pHead 链表头
*/
void printList(PNode pHead){
if(pHead -> next == pHead){
printf("空链表无法打印");
return;
}
PNode pCurrent = pHead -> next;
printf("打印链表: ");
while(pCurrent != pHead){
printf("%d ", pCurrent -> data);
pCurrent = pCurrent -> next;
}
}
int main(){
printf("----------------\n");
PNode pHead = initalList();
insertInTail(pHead, 2);
deleteByIndex(pHead, 1);
insertByIndex(pHead, 1, 3);
deleteTail(pHead);
printList(pHead);
printf("\n----------------\n");
return 0;
}循环双链表
/**
* @file double_circular_linked_list.c
* @author xiaoxiao (you@domain.com)
* @brief 循环双链表
* @version 0.1
* @date 2022-03-04
*
* @copyright Copyright (c) 2022
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
typedef struct Node {
struct Node * prior; // 前驱结点
struct Node * next; // 后继节点
int data;
}Node;
typedef Node* PNode;
/**
* @brief 初始化表头(无数据)
*
* @return PNode 表头
*/
PNode initalList(){
// 表头不存储数据
// 最后一个节点的两个指针都指向头结点,表示为空链表
PNode pHead = (PNode) malloc(sizeof(Node));
pHead -> next = pHead;
pHead -> prior = pHead;
return pHead;
}
/**
* @brief 在尾部插入一个元素
*
* @param pHead 链表头
* @param data 数据值
*/
void insertInTail(PNode pHead, int data){
PNode pCurrent = pHead;
while(pCurrent -> next != pHead){
pCurrent = pCurrent -> next;
}
// ppCurrent是原链表最后一个节点
pCurrent -> next = (PNode)(malloc(sizeof(Node)));
pCurrent -> next -> next = pHead;
pCurrent -> next -> prior = pCurrent;
pHead -> prior = pCurrent -> next; // 头结点的前驱指针指向最后一个节点
pCurrent -> next -> data = data;
}
/**
* @brief 在任意索引插入一个元素
* index=1是在表头后面(第一个元素)插入
*
* @param pHead 链表头
* @param index 索引
* @param data 数据值
*/
bool insertByIndex(PNode pHead, int index, int data){
PNode pCurrent = pHead;
int i = 1;
do{
if(i == index){
PNode pNewNode = (PNode) malloc (sizeof(Node)); // 新节点
pNewNode -> prior = pCurrent;
pNewNode -> next = pCurrent -> next;
pCurrent -> next -> prior = pNewNode;
pCurrent -> next = pNewNode;
pNewNode -> data = data;
return true;
}
pCurrent = pCurrent -> next;
i ++;
}while(pCurrent != pHead);
printf("索引大于链表长度+1,无法插入\n");
return false;
}
/**
* @brief 删除尾部元素
*
* @param pHead 链表头
*/
bool deleteTail(PNode pHead){
if(pHead -> next == pHead){
printf("链表为空, 不能删除\n");
return false;
}
PNode pCurrent = pHead;
while(pCurrent -> next != pHead){
pCurrent = pCurrent -> next;
}
pCurrent -> prior -> next = pHead; // 尾结点的上一个节点(新的尾结点)后驱指向头结点
pHead -> prior = pCurrent -> prior; // 头结点的前驱指向尾结点的上一个节点
free(pCurrent);
return true;
}
bool deleteByIndex(PNode pHead, int index){
if(pHead -> next = pHead){
printf("空链表无法删除\n");
return false;
}
PNode pCurrent = pHead -> next;
for(int i = 1; i < index; i++){
if(pCurrent -> next != pHead){
pCurrent = pCurrent -> next;
}
else{
printf("索引大于链表长度,无法删除\n");
return false;
}
}
// pCurrent是要删除的节点
pCurrent -> next -> prior = pCurrent -> prior;
pCurrent -> prior -> next = pCurrent -> next;
free(pCurrent);
return true;
}
/**
* @brief 打印链表
*
* @param pHead 链表头
*/
void printList(PNode pHead){
if(pHead -> next == pHead){
printf("空链表无法打印\n");
return;
}
PNode pCurrent = pHead -> next;
printf("打印链表: ");
while(pCurrent != pHead){
printf("%d ", pCurrent -> data);
pCurrent = pCurrent -> next;
}
printf("\n");
}
int main(){
printf("----------------\n");
PNode pHead = initalList();
insertInTail(pHead, 2);
insertByIndex(pHead, 1, 3);
deleteTail(pHead);
printList(pHead);
printf("----------------\n");
return 0;
}