环形链表的结构

前面我们说到，单链表结构中有一个唯一的头节点和唯一的尾节点，尾节点的指针为NULL。环形链表的结构和单链表的结构其实类似，唯一的不同就是循环链表把尾节点的指针指向了头节点，使整个链表可以形成一个真正的闭环，我们称之为环形链表或者循环链表。其具体的结构图如下:
所以环形链表的算法和单链表的算法差距不大，唯一需要注意的是在操作过程中尾节点的指针一定要及时给它指向头节点。

环形链表的定义

和单链表一样，我们在程序中声明Node类和CircleLinkedList类。Node表示节点，包含数据Data和指向下一个节点的指针Next。CircleLinkedList类封装了环形链表的相关算法，如：创建环形链表、删除链表元素、获取链表长度、插入新的节点等。

public class Node
{
    public int Data;//数据元素
    public Node Next;//指向下一个节点的指针
    public Node(int data)
    {
        this.Data = data;
    }
}
public class CircleLinkedList
{
    public Node first;//头节点指针
    public Node last;//尾指针
}

算法1:创建环形链表

创建环形链表指创建包含一组节点的单链表。如依次输入0,1,2,3,4,5来创建单链表，和单链表一样，环形链表的创建也有两种方法，前插法和后插法。 前插法是每次都将新节点作为头节点插入，每次插入的时候我们需要修改三个指针
1、尾节点指针指向新节点last.Next=ewNode。
2、新节点的指针指向原来的头节点newNode.Next=first。
3、头节点指针变量First指向新节点first=newNode。
前插法的具体操作流程如下，红色部分表示每次插入新节点时候需要调整的指针：

前插法具体代码如下：

public void InsertInHead(int data)
{
    Node newNode = new Node(data);
    newNode.Next = first;
    first = newNode;
    if (last == null)
    {
        last = newNode;
    }
    last.Next = first;
}

后插法是每次都将新节点插入到链表的尾部，每次插入的时候需要修改三个指针
1、新节点的指针指向头节点newNode.Next=first。
2、尾节点的指针指向新节点last.Next=newNode。
3、尾节点变量Last指向新节点last=newNode。
后插法的具体操作流程如下，红色矩形框代表新增的节点，红色线条表示需要调整的指针：

后插法具体代码如下：

public void InsertInLast(int data)
{
    Node newNode = new Node(data);
    if (first == null)
    {
        first = newNode;
        last = newNode;
    }
    newNode.Next = first;
    last.Next = newNode;
    last = newNode;
}

算法2：查找

循环链表的查找和数组的查找类似，但是需要注意的是，由于循环链表是连在一起的，判断一个链表遍历完成的条件不能是currentNode==null，而是currentNode.next==first。当currentNode.next==first条件成立的时候，说明我们遍历到循环链表的最后一个节点了
循环链表的查找有两种算法，一种是按照索引查找(查找链表中的第n个节点)，一种是按照值查找(查找链表中，节点值等于给定值的节点)。
按照索引查询的代码如下：

public Node GetByIndex(int index)
{
    Node currentNode = first;
    int i = 1;
    while (i != index)
    {
        currentNode = currentNode.Next;
        i++;
    }
    return currentNode;
}

按照值查找的具体代码如下：

public Node GetByData(int data)
{
    Node currentNode = first;
    while (currentNode.Next != first)
    {
        if (currentNode.Data == data)
        {
            break;
        }
        currentNode = currentNode.Next;
    }
    //如果是最后一个元素或者只有一个元素的话 需要单独比较一下
    if (currentNode.Data == data)
    {
        return currentNode;
    }
    return null;
}

算法3：删除循环链表中的节点

删除循环链表分为两种算法：按照索引删除和按照值删除。按照索引删除指删除循环链表中的第n个节点，按照值删除指的是删除环形链表中节点值等于某个给定值的节点。删除循环链表中的某个节点分为以下几种情况：
1、当环形链表只有一个节点的时候，如果第一个节点符合删除条件，直接将First和Last变量赋值为null即可first=null；last=null。
2、当删除环形链表中第一个节点的时候，需要依次变更的指针为first=first.next和last.Next=first。

3、当删除环形链表中的最后一个节点的时候，需要要变更last指针变量为last的前一个节点，前一个节点的指针指向头节点。也就是pre.Next=pre.Next.Next和last=pre;
按照索引删除删除的代码如下：

public void DeleteByIndex(int index)
{
    //删除第一个节点
    if (index == 1)
    {
        if (first.Next == first)//只有一个节点
        {
            first = null;
            last = null;
            return;
        }
        first = first.Next;
        last.Next = first;
        return;
    }

    Node currentNode = first;
    Node preNode = null;
    int i = 1;
    //找到第i个节点
    while (i != index)
    {
        preNode = currentNode;
        currentNode = currentNode.Next;
        i++;
    }

    preNode.Next = preNode.Next.Next;
    //如果是最后一个节点
    if (currentNode.Next == first)
    {
        last = preNode;
    }
}

按照值删除节点的具体代码如下：

public void DeleteByValue(int data)
{
    if (first == null)
    {
        return;
    }
    //只有一个元素
    if (first.Next == first)
    {
        if (first.Data == data)
        {
            first = null;
            last = null;
        }
        return;
    }

    Node currentNode = first;
    Node preNode = null;

    while (currentNode.Next != first)
    {
        if (currentNode.Data == data)
        {
            break;
        }
        preNode = currentNode;
        currentNode = currentNode.Next;
    }

    //没有找到要删除的节点
    if (currentNode.Data != data)
    {
        return;
    }

    //删除头节点
    if (currentNode == first)
    {
        first = first.Next;
        last.Next = first;
        return;
    }
    //删除尾节点
    if (currentNode == last)
    {
        preNode.Next = first;
        last = preNode;
        return;
    }
    //删除中间节点
    preNode.Next = currentNode.Next;
}

算法4:插入 在循环链表中插入一个元素

插入新节点分为三种情况：在链表头插入、链表中间插入、链表尾部插入。其实在创建链表的时候头插法和尾插法的示例就是在链表头部和链表尾部插入，这里就不多做说明了，现在主要说明以下在链表中间插入一个元素需要修改那些指针,主要调整两个部分的指针：NewNode.Next=current和 pre.Next=NewNode

插入元素的具体示例代码如下：

public void Insert(int index, int data)
{
    if (index == 1)
    {
        InsertInHead(data);
        return;
    }
    if (index > GetLength())
    {
        InsertInLast(data);
        return;
    }
    int i = 1;
    Node currentNode = first;
    Node preNode = null;
    while (i != index)
    {
        preNode = currentNode;
        currentNode = currentNode.Next;
        i++;
    }

    Node newNode = new Node(data);
    newNode.Next = currentNode;
    preNode.Next = newNode;
}

其他算法

除了上面几个主要的算法之外，循环链表也有获取链表长度、清空链表、链表是否为空、链表反转、链表合并等算法，这里就不给给大家一一实现了，大家可以自行实现或者查看gitee上的代码。

示例代码地址

https://gitee.com/jiamingyuanjin_admin/data_struct/blob/master/DataStruct/03CircleLinkedList.cs

总结

循环链表的优缺点和单链表的优缺点实际上基本上一样的，唯一的更多的优势是，循环链表中，从任何一个节点开始遍历，都可以完成的遍历整个链表，但是单链表只能从头节点开始才能遍历整个链表。