单向循环链表的概念+单向循环链表的结点插入+单向循环链表的结点删除+程序设计与笔试题分析

单向循环链表的原理与应用

思考：对于单向链表而言，想要遍历链表，则必须从链表的首结点开始进行遍历，请问有没有更简单的方案实现链表中的数据的增删改查？

回答：是有的，可以使用单向循环的链表进行设计，单向循环的链表的使用规则和普通的单向链表没有较大的区别，需要注意：单向循环链表的尾结点的指针域中必须指向链表的首结点的地址，由于带头结点的单向循环链表更加容易进行管理，所以教学以带头结点的为例：

上图所示的就是一个典型的单向循环链表的结构，可以发现单向循环链表的结构属于环形结构，链表中的最后一个结点的指针域中存储的是链表的第一个结点的地址。

为了管理单向循环链表，需要构造头结点的数据类型以及构造有效结点的数据类型，如下：

创建一个空链表，由于是使用头结点，所以就需要申请头结点的堆内存并初始化即可！

创建新结点，为新结点申请堆内存并对新结点的数据域和指针域进行初始化，操作如下：

根据情况把新结点插入到链表中，此时可以分为尾部插入、头部插入、指定位置插入：

头插

尾插

中插

根据情况可以从链表中删除某结点，此时可以分为尾部删除、头部删除、指定元素删除：

头删

尾删

中删

双向链表的原理与应用

如果想要提高单向链表或者单向循环链表的访问速度，则可以在链表中的结点中再添加一个指针域，让新添加的指针域指向当前结点的直接前驱的地址，也就意味着一个结点中有两个指针域（prev + next），也被称为双向链表（Double Linked List）。

由于带头结点更加方便用户进行数据访问，所以本次创建一条带头结点的双向不循环的链表。

创建一个空链表，由于是使用头结点，所以就需要申请头结点的堆内存并初始化即可！
创建新结点，为新结点申请堆内存并对新结点的数据域和指针域进行初始化，操作如下：
根据情况可以从链表中插入新结点，此时可以分为尾部插入、头部插入、指定位置插入：

头插
尾插
中插
（略）

根据情况可以从链表中删除某结点，此时可以分为尾部删除、头部删除、指定结点删除：

头删

//利用头删法实现结点删除
bool SencdList_Head_Delete(Node_t *HeadPointer)
{//备份头结点的地址Node_t *p =HeadPointer;//检查参数有效性if (HeadPointer == NULL){ fprintf(stderr,"SencdList HeadPointer is error,errno = %d,%s\n",errno,strerror(errno));return false;}//检查链表是否为空if (p->Next == NULL){fprintf(stderr,"SencdList is Empty,errno = %d,%s\n",errno,strerror(errno));return false;}//链表不为空，分两种情况，第一种只有一个结点，另一种有多个结点//只有一个结点if (p->Next->Next == NULL){free(p->Next);p->Next = NULL;return true;}//有多个结点else{p->Next = p->Next->Next;        //头结点的next指向新首结点p->Next->perv->Next = NULL;     //原首结点的next指向null//释放要删除的结点空间free(p->Next->perv);//更新新首结点的prevp->Next->perv = NULL;printf("Delete is  OK\n");return true;}}

尾删

//利用尾删法删除结点
bool SencdList_Tail_Delete(Node_t *TailPointer)
{//备份头结点的地址Node_t *p =TailPointer;//检查参数有效性if (TailPointer == NULL){ fprintf(stderr,"SencdList TailPointer is error,errno = %d,%s\n",errno,strerror(errno));return false;}//检查链表是否为空if (p->Next == NULL){fprintf(stderr,"SencdList TailPointer is Empty,errno = %d,%s\n",errno,strerror(errno));return false;}//如果链表不为空,有两种情况，一种为只有一个结点，另一种有多个结点//只有一个结点if (p->Next->Next == NULL)  //判断首结点的next是否指向null{free(p->Next);              //释放首结点的内存空间p->Next = NULL;             //更新头结点的指针域return true;}//有多个结点else{while (p->Next != NULL){p = p->Next; //p往后移}//循环结束p指向尾结点p->perv->Next = NULL; //新尾结点的next指向nullp->perv = NULL;       //原尾结点的prev指向null//释放尾结点空间free(p);return true;}}

中删
（略）

三、双向循环链表的原理与应用

双向循环链表与双向链表的区别：指的是双向循环链表的首结点中的prev指针成员指向链表的尾结点，并且双向循环链表的尾结点里的next指针成员指向链表的首结点，所以双向循环链表也属于环形结构。

由于带头结点更加方便用户进行数据访问，所以本次创建一条带头结点的双向循环的链表。

// 5.结构体、联合体、枚举的定义。
typedef int Data_Type_t;//结构体用来装链表的
typedef struct CirularSencdListNode
{struct CirularSencdListNode    *perv; //链表的perv指针域，指向结点的直接前驱Data_Type_t              Data; //链表的数据域struct CirularSencdListNode    *Next; //链表的next指针域,指向结点的直接后继}Node_t;

创建一个空链表，由于是使用头结点，所以就需要申请头结点的堆内存并初始化即可！

//创建新的链表（头结点）
Node_t* CirularSencdList_Create(void)
{//为链表申请堆空间Node_t *Pragmar = (Node_t*)calloc(1,sizeof(Node_t));//检查参数有效性if (Pragmar == NULL){fprintf(stderr,"CirularSencdList Create is error,errno = %d,%s\n",errno,strerror(errno));exit(-1);}//链表的初始化Pragmar->Next = Pragmar; //记录next指针域Pragmar->perv = Pragmar; //记录prev指针域printf("CirularSencdList Create is OK\n");return Pragmar;}

创建新结点，为新结点申请堆内存并对新结点的数据域和指针域进行初始化，操作如下：

//创建新的结点
Node_t* CirularSencdList_NewNode(Data_Type_t Data )
{//为链表申请堆空间Node_t *NewNode = (Node_t*)calloc(1,sizeof(Node_t));//检查参数有效性if (NewNode == NULL){fprintf(stderr,"CirularSencdList Create is error,errno = %d,%s\n",errno,strerror(errno));exit(-1);}//链表的初始化NewNode->Data = Data; //记录数据域NewNode->Next = NewNode; //记录next指针域NewNode->perv = NewNode; //记录prev指针域printf("NewNode Create is OK\n");return NewNode;}

根据情况可以从链表中插入新结点，此时可以分为尾部插入、头部插入、指定位置插入：
头插

//头插法为链表插入结点
bool CirularSencdList_HeadInsert(Node_t *HeadPointer,Data_Type_t Data)
{//备份头结点的地址Node_t *p =HeadPointer;Node_t *p_cur =HeadPointer->Next;//检查参数有效性if (HeadPointer == NULL){ fprintf(stderr,"CirularSencdList HeadPointer is error,errno = %d,%s\n",errno,strerror(errno));return false;}//创建新结点并初始化Node_t * NewNode = CirularSencdList_NewNode(Data);//检查链表是否为空if (p->Next == HeadPointer){p->Next = NewNode;printf("insert is ok\n");return true;}//如果链表不为空p->Next->perv->Next = NewNode;  //尾结点的next指向新结点NewNode->perv  = p->Next->perv; //新结点的prev指向尾结点NewNode->Next =p->Next;         //新结点的next指向原首结点p->Next->perv = NewNode;        //原首结点的prev指向新结点p->Next = NewNode;              //更新头结点的指针域return true;}

尾插

//尾插法为链表插入结点
bool CirularSencdList_Tail_Insert(Node_t *TailPointer,Data_Type_t Data)
{//备份头结点的地址Node_t *p =TailPointer;//检查参数有效性if (TailPointer == NULL){ fprintf(stderr,"CirularSencdList TailPointer is error,errno = %d,%s\n",errno,strerror(errno));return false;}//创建新结点并初始化Node_t * NewNode = CirularSencdList_NewNode(Data);//检查链表是否为空if (p->Next == TailPointer){p->Next = NewNode;return true;}//如果链表不为空p->Next->perv->Next = NewNode; //原尾结点的next指向新结点NewNode->perv =p->Next->perv;  //新结点的prev指向原尾结点NewNode->Next = p->Next;       //新结点的next指向首结点p->Next->perv = NewNode;       //首结点的prev指向新结点return true;}

根据情况可以从链表中删除某结点，此时可以分为尾部删除、头部删除、指定结点删除：
头删

//利用头删法实现结点删除
bool CirularSencdList_Head_Delete(Node_t *HeadPointer)
{//备份头结点的地址Node_t *p =HeadPointer;//检查参数有效性if (HeadPointer == NULL){ fprintf(stderr,"CirularSencdList HeadPointer is error,errno = %d,%s\n",errno,strerror(errno));return false;}//检查链表是否为空if (p->Next == HeadPointer){fprintf(stderr,"CirularSencdList is Empty,errno = %d,%s\n",errno,strerror(errno));return false;}//链表不为空有两种情况，一种为只有一个结点，另一种有多个结点//只有一个结点if (p->Next->Next == p->Next)  //判断首结点的next是否指向首结点本身{p->Next->Next = NULL;     //首结点的next指向nullp->Next->perv = NULL;     //首结点的prev指向nullfree(p->Next);            //释放首结点p->Next = HeadPointer;    //更新头结点的指针域return true;}else{p->Next = p->Next->Next;             //更新头结点的指针域p->Next->perv = p->Next->perv->perv; //新首结点的prev指向尾结点p->Next->perv->Next->Next = NULL;    //原首结点的next指向nullp->Next->perv->Next->perv = NULL;    //原首结点的prev指向null//释放原首结点的内存空间free(p->Next->perv->Next);p->Next->perv->Next = p->Next;       //尾结点的next指向新首结点}printf("Delete is  OK\n");return true;}

尾删

//利用尾删法删除结点
bool CirularSencdList_Tail_Delete(Node_t *TailPointer)
{//备份头结点的地址Node_t *p =TailPointer;//检查参数有效性if (TailPointer == NULL){ fprintf(stderr,"CirularSencdList TailPointer is error,errno = %d,%s\n",errno,strerror(errno));return false;}//检查链表是否为空if (p->Next == TailPointer){fprintf(stderr,"CirularSencdList TailPointer is Empty,errno = %d,%s\n",errno,strerror(errno));return false;}//如果链表不为空,有两种情况，第一种是只有一个结点，另一种是有多个结点//只有一个结点if (p->Next->Next == p->Next)  //判断首结点的next是否指向自身{p->Next->Next = NULL;      //首结点的next指向nullp->Next->perv = NULL;      //首结点的prev指向null//释放首结点的内存空间free(p->Next); //更新头结点的指针域            p->Next = TailPointer;return true;}//有多个结点    p->Next->perv =p->Next->perv->perv;p->Next->perv->Next->Next = NULL;p->Next->perv->Next->perv = NULL;//释放尾结点空间free(p->Next->perv->Next);p->Next->perv->Next = p->Next;return true;}