什么是單循環鏈表，數據結構 2-3-3 循環鏈表

一、概念

循環鏈表是在一般鏈表的基礎上，對鏈表的尾結點做改動，讓其的next指針不指向NULL，而是改為指向頭結點，從而讓整個鏈表形成一個環。

二、定義

定義與一般鏈表沒區別

三、代碼實現

循環鏈表可以分成循環單鏈表和循環雙鏈表，與不循環的代碼的區別在于增加刪減節點時對前驅后繼的修改。

初始化時，頭結點的next指針不再指向空而是換為指向自己。

使用頭插法時，單循環鏈表與不循環沒有區別，因為每次增加的節點相當于在鏈表的中間，并沒有影響到后面的節點。雙循環鏈表也是一個道理。

什么是單循環鏈表、使用尾插法則有小小的變動，因為插入的節點在尾部，所以要插入的節點的next指針指向的要換成head頭結點。

//單循環鏈表尾插法
void buttominsert(int n)
{for(int i=0;i<n;i++){struct LNode *temp;temp=(struct LNode*)malloc(sizeof(struct LNode));scanf("%d",&temp->num);temp->next=head;L->next=temp;L=L->next;head->num++;}
}
//雙循環鏈表尾插法
void buttominsert(int n)
{for(int i=0;i<n;i++){struct LNode *temp;temp=(struct LNode*)malloc(sizeof(struct LNode));scanf("%d",&temp->num);temp->next=head;temp->pre=L;L->next=temp;L=L->next;head->num++;}
}

除此之外，在遍歷鏈表時到表尾的條件也要做出修改，因為最后一個節點的next不再是空而是head。其余部分上實現起來和一般的單鏈表雙鏈表沒什么區別，主要還是因為變化根本就不大，修改的就只有最后一個節點而已。直接上手擼代碼。

//循環單鏈表
#include<bits/stdc++.h>
using namespace std;
struct LNode{int num;struct LNode *next;
};
struct LNode *head;//頭結點 
struct LNode *L;//尾結點 
void init()
{head=(struct LNode*)malloc(sizeof(struct LNode));L=head;head->next=head;head->num=0;
}
void print()
{struct LNode *out;out=head->next;while(out!=head){printf("%d ",out->num);out=out->next;}printf("\n");printf("The length of the list is %d\n",head->num);
}
void headinsert(int n)
{for(int i=0;i<n;i++){struct LNode *temp;temp=(struct LNode*)malloc(sizeof(struct LNode));scanf("%d",&temp->num);temp->next=head->next;head->next=temp;head->num++;}
} 
void buttominsert(int n)
{for(int i=0;i<n;i++){struct LNode *temp;temp=(struct LNode*)malloc(sizeof(struct LNode));scanf("%d",&temp->num);temp->next=head;L->next=temp;L=L->next;head->num++;}
}
int search(int tar)
{int cnt=0;struct LNode *temp;temp=head->next;while(temp!=head){if(temp->num==tar)return cnt;cnt++;temp=temp->next;}return -1;
}
bool insert(int tar,int num)
{if(tar<0||tar>head->num)return false;struct LNode *temp;temp=(struct LNode*)malloc(sizeof(struct LNode));temp->num=num;struct LNode *p=head;while(tar--)p=p->next;temp->next=p->next;p->next=temp;head->num++;return true;
}
bool Delete(int tar)
{if(tar<0||tar>=head->num)return false;struct LNode *p,*q;p=head;while(tar--)p=p->next;q=p->next;p->next=p->next->next;free(q);head->num--;return true;
}
void delmode()
{int tar;printf("Input the location that you want to delete:");scanf("%d",&tar);if(!Delete(tar-1))printf("Delete failed\n");elseprintf("Delete succeed\n");
}
void insmode()
{int tar,num;printf("Input the location and num that you want to insert:");scanf("%d %d",&tar,&num);if(!insert(tar-1,num))printf("Insert failed\n");elseprintf("Insert succeed\n");
}
void seamode()
{int tar;printf("Input the number you want to search:");scanf("%d",&tar);int ans=search(tar);if(ans==-1)printf("Find failed\n");elseprintf("The target is at the %d\n",ans+1);
}
int main()
{init();int n,tar,num,choice=-1;printf("Input the amount of elements:");scanf("%d",&n);buttominsert(n);//headinsert(n);print();while(choice!=0){printf("1-delete\n");printf("2-insert\n");printf("3-show\n");printf("4-search\n");printf("0-exit\n");printf("Choice the function you want:");scanf("%d",&choice);switch(choice){case 1:delmode();break;case 2:insmode();break;case 3:print();break;case 4:seamode();break;case 0:break;default:printf("input error!");break;}	}	return 0;} 

//循環雙鏈表
#include<bits/stdc++.h>
using namespace std;
struct LNode{int num;struct LNode *next;struct LNode *pre; 
};
struct LNode *head;//頭結點 
struct LNode *L;//尾結點 
void init()
{head=(struct LNode*)malloc(sizeof(struct LNode));L=head;head->next=head;head->pre=head;head->num=0;
}
void print()
{struct LNode *out;out=head->next;while(out!=head){printf("%d ",out->num);out=out->next;}printf("\n");printf("The length of the list is %d\n",head->num);
}
void headinsert(int n)
{for(int i=0;i<n;i++){struct LNode *temp;temp=(struct LNode*)malloc(sizeof(struct LNode));scanf("%d",&temp->num);temp->next=head->next;temp->pre=head;head->next=temp;head->num++;}
} 
void buttominsert(int n)
{for(int i=0;i<n;i++){struct LNode *temp;temp=(struct LNode*)malloc(sizeof(struct LNode));scanf("%d",&temp->num);temp->next=head;temp->pre=L;L->next=temp;L=L->next;head->num++;}
}
int search(int tar)
{int cnt=0;struct LNode *temp;temp=head->next;while(temp!=head){if(temp->num==tar)return cnt;cnt++;temp=temp->next;}return -1;
}
bool insert(int tar,int num)
{if(tar<0||tar>head->num)return false;struct LNode *temp;temp=(struct LNode*)malloc(sizeof(struct LNode));temp->num=num;struct LNode *p=head;while(tar--)p=p->next;temp->next=p->next;temp->pre=p;p->next->next->pre=temp;p->next=temp;head->num++;return true;
}
bool Delete(int tar)
{if(tar<0||tar>=head->num)return false;struct LNode *p,*q;p=head;while(tar--)p=p->next;q=p->next;p->next=p->next->next;p->next->pre=p;free(q);head->num--;return true;
}
void delmode()
{int tar;printf("Input the location that you want to delete:");scanf("%d",&tar);if(!Delete(tar-1))printf("Delete failed\n");elseprintf("Delete succeed\n");
}
void insmode()
{int tar,num;printf("Input the location and num that you want to insert:");scanf("%d %d",&tar,&num);if(!insert(tar-1,num))printf("Insert failed\n");elseprintf("Insert succeed\n");
}
void seamode()
{int tar;printf("Input the number you want to search:");scanf("%d",&tar);int ans=search(tar);if(ans==-1)printf("Find failed\n");elseprintf("The target is at the %d\n",ans+1);
}
int main()
{init();int n,tar,num,choice=-1;printf("Input the amount of elements:");scanf("%d",&n);buttominsert(n);//headinsert(n);print();while(choice!=0){printf("1-delete\n");printf("2-insert\n");printf("3-show\n");printf("4-search\n");printf("0-exit\n");printf("Choice the function you want:");scanf("%d",&choice);switch(choice){case 1:delmode();break;case 2:insmode();break;case 3:print();break;case 4:seamode();break;case 0:break;default:printf("input error!");break;}	}	return 0;} 

四、優缺點分析

因為循環鏈表是個環，所以頭結點的意義會稍微有點模糊，因為從任意一個節點都可以訪問到全部節點，所以從這個角度看，頭結點的意義會不那么明顯，除此之外，頭指針也可以取消，只留一個尾指針即可，這是因為其循環的緣故，尾指針的下一個就成了頭指針所指向的頭結點，這樣操作起來就更加高效。若設的是頭指針，對表尾進行操作需要 O(n）的時間復雜度，而若設的是尾指針 next 即為頭指針， 對于表頭與表尾進行操 作都只需要 O(1）的時間復雜度。