[数据结构]链表之循环链表

目录

基本概念和操作：

实现方法和原理:

应用场景和使用注意事项:

算法和复杂度分析：

与其他数据结构的比较：

PS：如有错漏之处，敬请指正

---

基本概念和操作：

循环链表是一种特殊的链表结构，其最后一个节点指向第一个节点，形成了一个循环，这样从表中的任一节点触发都可以找到表中其他节点。循环链表可以分为单向循环链表和双向循环链表两种类型。以下为带头节点的循环单链表示意图。

对循环链表来说，有的时候指针改为尾指针会使操作更简单，下图是带尾指针的循环单链表示意图。

从上图的示意图可以看出，用循环表表示线性表的逻辑关系与单链表的表示方法一样，不同的是最后一个元素的next的值不能为null,而是存储的链表中的第一个元素的地址。

以下是循环链表的常用操作：

1. 头节点：循环链表第一个节点之前的节点，通常没有存储数据，主要作用是方便对循环链表的操作。

2. 尾节点：循环链表最后一个节点，其next指针指向头节点。

3. 插入元素：在指定位置插入新元素，需要修改前一个节点的next指针和新节点的next指针。

4. 删除元素：删除指定位置的元素，需要修改前一个节点的next指针。

5. 查找元素：从头节点开始遍历循环链表，直到找到目标元素或遍历完整个链表。

6. 遍历元素：从头节点开始遍历循环链表的所有元素，可以使用while循环或for循环实现。

7. 反转链表：将循环链表中的所有节点反转顺序，需要使用三个指针来实现。

需要注意的是，在进行各种操作时，需要保证循环链表的连续性和有序性，即每个节点的next指针都指向下一个节点，并且最后一个节点的next指针指向头节点。实现细节参见下面的 C#代码：

  /// <summary>
    /// 循环单链表数据结构实现接口具体步骤
    /// </summary>
    /// <typeparam name="T"></typeparam>
     class CLinkedList<T>:ILinarList<T>
    {
        public SNode<T> tail;
        int length;//循环链表长度
 
        public CLinkedList()
        {
            this.tail = null;
        }
 
 
        /// <summary>
        /// 在链表的末尾追加数据元素 data
        /// </summary>
        /// <param name="data">数据元素</param>
        public void InsertNode(T data)
        {
            SNode<T> node = new SNode<T>(data);
            if (IsEmpty())
            {
                tail = node;
                tail.Next = tail;
            }
            else
            {
                T firstData = tail.Data;
                SNode<T> current = tail;
                while (current.Next != null && !current.Next.Data.Equals(firstData))
                {
                    current = current.Next;
                }
                current.Next = new SNode<T>(data);
                current.Next.Next = tail;
             
            }
            length++;
            return;
        }
 
        /// <summary>
        /// 在链表的第i个数据元素的位置前插入一个数据元素data
        /// </summary>
        /// <param name="data"></param>
        /// <param name="i"></param>
        public void InsertNode(T data, int i)
        {
            if (i < 1 || i > (length+1))
            {
                Console.WriteLine("Position is error!");
                return;
            }
            SNode<T> current;
            SNode<T> newNode = new SNode<T>(data);
            if (i == 1)
            {              
                newNode.Next = tail;
                tail = newNode;
                length++;
                current = tail;
                for (int j = 0; j < length; j++)
                {
                    if (j== (length - 1))
                    {
                        current.Next = tail;
                        break;
                    }
                    current = current.Next;
                }
                return;
                
            }
            //两个元素中间插入一个元素
            current = tail;
            SNode<T> previous = null;
            int index = 1;
            while (current != null && index < i)
            {
                previous = current;
                current = current.Next;
                index++;
            }
            if (index == i)
            {
                previous.Next = newNode;
                newNode.Next = current;
                length++;
            }
            return;
        }
 
 
        /// <summary>
        /// 删除链表的第i个数据元素
        /// </summary>
        /// <param name="i"></param>
        public void DeleteNode(int i)
        {
 
            if (IsEmpty() || i < 1)
            {
                Console.WriteLine("Link is empty or Position is error");
            }
            SNode<T> current = tail;
            SNode<T> previus = null;
            if (i == 1)
            {
                tail.Data = current.Next.Data;
                tail.Next = current.Next.Next;
                length--;
                return;
            }
            if (i > length)
            {
                return;
            }
 
            int j = 1;
           
            while (current.Next != null && j < i)
            {
                previus = current;
                current = current.Next;
                j++;
            }
            if (j == i)
            {
                previus.Next = current.Next;
                current = current.Next;
                length--;
                return;
            }
            //第i个节点不存在
            Console.WriteLine("the ith node is not exist!");
        }
 
        /// <summary>
        /// 获取链表的第i个数据元素
        /// </summary>
        /// <param name="i"></param>
        /// <returns></returns>
        public T SearchNode(int i)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is empty");
                return default(T);
            }
            SNode<T> current = tail;
            int j = 1;
            while (current.Next != null && j < i && j<=length)
            {
                current = current.Next;
                j++;
            }
            if (j == i)
            {
                return current.Data;
            }
            //第i个节点不存在
            Console.WriteLine("the ith node is not exist!");
            return default(T);
        }
 
        /// <summary>
        /// 在链表中查找值为data的数据元素
        /// </summary>
        /// <param name="data"></param>
        /// <returns></returns>
        public T SearchNode(T data)
        {
            if (IsEmpty())
            {
                Console.WriteLine("List is empty");
                return default(T);
            }
            SNode<T> current = tail;
            int i = 1;
            bool isFound = false;
            while (current != null && i<=length)
            {
                if (current.Data.ToString().Contains(data.ToString()))
                {
                    isFound = true;
                    break;
                }
                current = current.Next;
                i++;
            }
            if (isFound)
            {
                return current.Data;
            }
            return default(T);
        }
 
        /// <summary>
        /// 获取链表的长度
        /// </summary>
        /// <returns></returns>
        public int GetLength()
        {
            return length;
        }
 
 
        /// <summary>
        /// 清空链表
        /// </summary>
        public void Clear()
        {
            tail = null;
            length = 0;
        }
 
 
 
        public bool IsEmpty()
        {
            return length == 0;
        }
 
        /// <summary>
        /// 该函数将链表头节点反转后，重新作为链表的头节点。算法使用迭代方式实现，遍历链表并改变指针指向
        /// 例如链表头结点start:由原来的
        /// data:a,
        /// next:[
        ///      data:b,
        ///      next:[
        ///           data:c,
        ///           next:[
        ///                data:a,
        ///                next:[
        ///                     data:b,
        ///                     next:...
        ///                     ]
        ///                ]
        ///           ]
        ///      ] 
        ///翻转后的结果为:
        /// data:c,
        /// next:[
        ///      data:b,
        ///      next:[
        ///           data:a,
        ///           next:[
        ///                 data:c,
        ///                 next:[
        ///                       data:b,
        ///                       next:....
        ///                      ]
        ///                ]
        ///          ]
        ///     ] 
        /// </summary>
        // 反转循环链表
        public void ReverseList()
        {
 
            if (length == 1 || this.tail == null)
            {
                return;
            }
            //定义 previous next 两个指针
            SNode<T> previous = null;
            SNode<T> next;
            SNode<T> current = this.tail;
            //循环操作
            while (current != null)
            {
                //定义next为Head后面的数，定义previous为Head前面的数
                next = current.Next;
                current.Next = previous;//这一部分可以理解为previous是Head前面的那个数。
                //然后再把previous和Head都提前一位
                previous = current;
                current = next;
            }
            this.tail = previous.Next;
            //循环结束后，返回新的表头，即原来表头的最后一个数。
            return;
 
        }
    }

总之，循环链表是一种特殊的链表结构，在实际应用中具有广泛的使用。需要注意的是，在进行各种操作时，需要保证循环链表的连续性和有序性，以避免数据不一致等问题的发生。

实现方法和原理:

循环链表是一种特殊的单向或双向链表结构，其最后一个节点的next指针指向第一个节点，形成了一个循环。本人已经在其他文章介绍了单向和双向循环链表的实现方法和原理。

总之，循环链表是一种特殊的链表结构，在实现时需要注意保证链表的连续性和有序性。

应用场景和使用注意事项:

循环链表是一种特殊的链表结构，适用于需要循环访问节点的场景。以下是一些常见的循环链表应用场景：

1. 约瑟夫问题：约瑟夫问题是一个经典的数学问题，可以通过循环链表来实现。具体来说，可以使用循环链表模拟一组人围成一个圆圈，然后依次杀掉每个第M个人，最后剩下的人就是胜利者。

2. 缓存淘汰算法：在缓存淘汰算法中，可以使用循环链表来实现LRU（Least Recently Used）算法。具体来说，可以将缓存中的数据按照访问时间顺序形成一个循环链表，当缓存满时，删除最久未被访问的数据。

3. 跑马灯效果：在图形界面开发中，可以使用循环链表来实现跑马灯效果，即使一段文本以循环滚动的方式展示。

使用循环链表时，需要注意以下几点：

1. 循环链表的操作与普通链表类似，在插入、删除和查找等方面相对容易。但是，需要注意循环链表的连续性和有序性，避免出现死循环或数据不一致等问题。

2. 循环链表的节点需要额外存储一个指针，因此比普通链表占用更多的空间。

3. 在使用双向循环链表时，需要注意头节点和尾节点的处理，避免操作失误导致链表出现断裂。

总之，循环链表是一种特殊的链表结构，适用于需要循环访问节点的场景。在实际应用中，需要根据具体的需求和场景选择合适的数据结构，并注意其特点和使用注意事项。

算法和复杂度分析：

循环链表的一些基本算法包括：

1. 在指定位置插入元素：需要先找到插入位置的前一个节点，然后将新节点的next指针指向插入位置的节点，再将前一个节点的next指针指向新节点。时间复杂度为O(n)。

2. 在指定位置删除元素：需要先找到删除位置的前一个节点，然后将其next指针指向删除位置的下一个节点即可。时间复杂度为O(n)。

3. 查找元素：需要从头节点开始遍历循环链表，直到找到目标元素或者遍历完整个链表为止。时间复杂度为O(n)。

4. 遍历元素：从头节点开始遍历循环链表的所有元素，可以使用while循环或for循环实现。时间复杂度为O(n)。

5. 反转链表：将循环链表中的所有节点反转顺序，需要使用三个指针来实现。时间复杂度为O(n)。

需要注意的是，在循环链表中，插入和删除操作需要额外考虑最后一个节点的next指针和第一个节点的prev指针的修改。同时，由于循环链表的特殊性质，遍历和查找元素时需要判断是否已经满足循环结束条件。

总之，循环链表是一种特殊的链表结构，在实现各种操作时需要注意其连续性和有序性，并针对特殊情况进行相应的处理。在实际应用中，需要根据具体的需求和场景选择合适的算法和数据结构，并进行权衡和折衷。

与其他数据结构的比较：

循环链表是一种特殊的链表结构，与其他数据结构相比具有以下优缺点：

1. 与普通链表相比，循环链表在操作上更灵活，可以实现循环访问和遍历等功能。但是，在插入、删除和查找等操作中，其时间复杂度与普通链表相同。

2. 与数组相比，循环链表可以动态扩容，并且支持高效的插入和删除操作。但是，在随机访问元素时，其时间复杂度较高，不如数组效率高。

3. 与栈和队列相比，循环链表可以存储更多的元素，并支持更灵活的访问方式。但是，在插入和删除元素时，其时间复杂度相对较高，不适合频繁进行这类操作。

4. 与树和图等复杂数据结构相比，循环链表的实现简单，易于理解和维护。但是，在对大量数据进行搜索和遍历时，其时间复杂度较高，不适合用于这类应用场景。

5. 与哈希表相比，循环链表的查找效率较低，同时不支持快速插入和删除操作。但是，其实现简单，无需处理哈希冲突等问题。

总之，循环链表是一种特殊的链表结构，在实际应用中需要根据具体场景和需求进行选择。需要注意的是，不同数据结构之间存在权衡和折衷的问题，在使用时需要综合考虑其优点和缺点，并选择合适的数据结构和算法。

PS：如有错漏之处，敬请指正