前言

提示：本系列文章均使用Visual Studio 2019编程，编程语言为c语言。

一、循环链表

（一）定义

将单链表的终端结点的指针端由空指针改为指向头结点，这样就让整个单链表形成一个循环，这时头尾相连的单链表就称为单循环链表，即循环链表，下图的head，即为头指针。

将循环链表和单链表相比较，其实就在循环的判断条件上差别，单链表判断是否为空（p!=null 或 p->null!=null），循环链表是否等于头结点(p!=head 或 p->next!=head)。

（二）尾指针

事实上我们不用头指针，而改用指向终端结点的尾指针来表示循环链表，这样就使查找开始结点和终端结点就很方便。

我们通过一张图，进一步了解其尾指针的作用：

二、双向链表

（一）定义

在单链表结构中，结点只有一个指向后继的指针域next，若要查找某个结点只能顺着单链表寻找它的后继结点，为了能够高效地查找一个结点，我们只需从头指针出发查找其前驱，即我们增加一个指向其直接前驱的指针域prior，这样我们就构成了一个双向链表。其中第一个结点的前趋结点为NULL，最后一个结点的后继结点也为NULL。

即，数据域为data数据，存储一个数据元素的信息；prior指针域为前驱指针域，用于存储其直接前驱存储地址的信息；next指针域为后继指针域，用于存储其后继存储地址的信息。

（二）代码

1.双向单链表的建立

分别定义数据域，前驱指针域以及后继指针域。

typedef char DataType;
typedef struct dunode
{
  DataType data;         //数据域
  struct dunode *prior;   //前驱指针域
  struct dunode *next;    //后继指针域
}DuLinkList;

2.双向单链表的插入

若要将新结点s（x为其值）插入到双向链表中两个结点o、p之间，即在p结点之前插入结点s，首先我们应该将要插入的新结点s的前驱指针域指向结点p的前一个结点o，将结点o的后继指针域指向要插入的新结点s，然后将结点s的后继指针域指向p结点，并将结点p的前驱指针域指向结点s。

void InsertList(InsertElem *p,DataType x)
{
   InsertElem *s;
   s=(InsertElem *)malloc(sizeof(InsertElem));  //生成新结点s
   s->data=x;
   s->prior=p->prior;     //也可写成s->prior=o
   p->prior->next=s;      //也可写成o->next=s
   s->next=p;
   p->prior=s;            //也可写成o=s
}

3.双向链表的删除

若要删除表中的结点p，我们首先应该将结点p的前一个结点的后继指针域指向结点p的后继指针域，将结点p后一个结点的前驱指针域指向结点p的后继指针域，然后释放结点p的空间。

void DeleteElem(DeleteList *p,DataType *x)
{
  *x=p->data;
  p->prior->next=p->next;
  p->next->prior=p->prior;
  free(p);
}

总结

以上就是本次的笔记内容，本文介绍了循环链表、双向链表的各项操作，笔记若有错误，还望指出！！！