单向循环链表及C#的实现

循环链表

循环链表是指链表的尾节点的Next指针域指向头节点。
循环链表判空条件，头节点的后继指向自己。

代码实现

下面的实现中，增加了头节点（头节点进代表链表地址，不含有值，第一个含有值的节点是首节点）。

Node类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    public class Node<T>
    {
        private T data; //数据域
        private Node<T> next; //引用域

        //数据域属性
        public T Data { get => data; set => data = value; }
        //引用域属性
        internal Node<T> Next { get => next; set => next = value; }

        //构造器
        public Node(T val, Node<T> p) {
            Data = val;
            Next = p;
        }

        //构造器
        public Node(Node<T> p) {
            Next = p;
        }

        //构造器
        public Node(T val) {
            Data = val;
        }

        //构造器
        public Node() {
            Data = default(T);
            Next = null;
        }
    }
}

SingleCycle接口

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    interface SingleCycleDs<T>
    {
        int GetLength();    //求长度
        void Clear();   //清空操作
        bool IsEmpty(); //判断线性表是否为空
        void Append(T item);    //附加操作
        void Insert(T item, int i); //插入
        void Delete(int i);    //删除操作
        T GetElem(int i);   //取表元
        int Locate(T value);    //按值查找
        void Reverse(); //逆置
    }
}

SingleCycle类

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    class SingleCycle<T> : SingleCycleDs<T>
    {
        Node<T> head;   //头节点

        //头节点属性
        public Node<T> Head { get => head; set => head = value; }

        //构造器
        public SingleCycle() {
            head = new Node<T>();
            head.Next = head;
        }

        /// <summary>
        /// 附加元素到尾部
        /// </summary>
        /// <param name="item">元素</param>
        public void Append(T item)
        {
            Node<T> p = new Node<T>(item);
            Node<T> c = head;

            //头节点为空时，直接修改头节点和新增节点的引用
            if (IsEmpty()) {
                head.Next = p;
                p.Next = head;
                return;
            }

            //遍历至最后一个节点
            while (c.Next != head) {
                c = c.Next;
            }

            //将新增元素挂载到末尾
            c.Next = p;
            p.Next = head;
        }

        /// <summary>
        /// 清空链表
        /// </summary>
        public void Clear()
        {
            head.Next = head;
        }

        /// <summary>
        /// 删除节点
        /// </summary>
        /// <param name="i">删除节点的位置</param>
        public void Delete(int i)
        {
            //链表为空
            if (IsEmpty() || i < 1)
            {
                Console.WriteLine("链表为空或位置错误");
                return;
            }

            //删除头节点
            if (i == 1)
            {
                head.Next = head.Next.Next;
                return;
            }

            //遍历位置删除节点
            Node<T> c = head.Next;  //目标节点
            Node<T> p = new Node<T>(); //目标节点的前驱节点
            int j = 1;
            while (c.Next != head && j < i)
            {
                /* 记录当前节点，
                 * 因为当前节点为下一次遍历的前驱节点，
                 * 当遍历到目标节点时，可以直接用其前驱节点操作。
                 */
                p = c;

                c = c.Next;
                ++j;
            }
            //遍历到位置
            if (j == i)
            {
                Console.WriteLine(j);
                Console.WriteLine(p.Next.Data);
                //用前驱节点来跳过目标节点，直接挂载目标节点的后继节点到其前驱节点上
                p.Next = p.Next.Next;
                Console.WriteLine("删除成功");
            }
            //未找到位置
            else {
                Console.WriteLine("位置不正确");
            }
        }

        /// <summary>
        /// 根据位置获取元素值
        /// </summary>
        /// <param name="i">元素位置</param>
        /// <returns>元素数据域值</returns>
        public T GetElem(int i)
        {
            //链表为空时返回默认值。
            if (IsEmpty()) {
                Console.WriteLine();
                return default(T);
            }

            //返回第一个元素的值
            if (i == 1) {
                return head.Next.Data;
            }

            //遍历查找并返回
            Node<T> c = head.Next;
            int j = 1;
            while (c.Next != head && j < i) {
                c = c.Next;
                ++j;
            }
            //遍历找到
            if (j == i)
            {
                return c.Data;
            }
            else {
                Console.WriteLine("位置不正确");
            }
            return default(T);
        }

        /// <summary>
        /// 获取列表长度
        /// </summary>
        /// <returns></returns>
        public int GetLength()
        {
            if (IsEmpty()) {
                return 0;
            }

            Node<T> c = head.Next;
            int i = 1;
            while (c.Next != head) {
                c = c.Next;
                ++i;
            }
            return i;

        }

        /// <summary>
        /// 插入节点
        /// </summary>
        /// <param name="item">插入的元素值</param>
        /// <param name="i">插入位置</param>
        public void Insert(T item, int i)
        {
            if (IsEmpty() || i < 1)
            {
                Console.WriteLine("链表为空或位置错误");
            }

            //插入到首节点位置
            if (i == 1) {
                Node<T> c = head.Next; //保存首节点
                head.Next = new Node<T>(item); //将新节点插入到头节点后
                head.Next.Next = c; //将首节点设为新节点的后继
                return;
            }

            //遍历位置插入
            Node<T> c1 = head.Next;
            Node<T> p = new Node<T>();
            int j = 1;
            while (c1.Next != head && j < i)
            {
                p = c1;
                c1 = c1.Next;
                ++j;
            }
            //遍历找到
            if (j == i)
            {
                p.Next = new Node<T>(item);
                p.Next.Next = c1;
            }
            else
            {
                Console.WriteLine("位置不正确");
            }
        }

        //判断链表是否为空
        public bool IsEmpty()
        {
            return head.Next == head;
        }

        /// <summary>
        /// 根据节点值查找位置
        /// </summary>
        /// <param name="value">节点值</param>
        /// <returns>节点位置</returns>
        public int Locate(T value)
        {
            int i = 1;
            Node<T> c = head.Next;


            /* 这里的判断条件要不能写c.Next，
             * 因为当目标值为最后一个节点的值时，c.Next==head会成立
             * 所以要让循环多遍历一次，
             * 当c时头节点时说明列表已遍历完毕，这时如果还未找到，说明不存在。
             * 注意：要将比较语句写在逻辑判断后面，
             * 因为head=null，当c=head时，比较语句会抛异常。
             * 所以要先比较c==head来中断后面的语句。
            */

            while (c != head && !c.Data.Equals(value))
            {
                c = c.Next;
                ++i;
            }

            if (c == head)
            {
                Console.WriteLine("不存在这样的节点");
                return -1;
            }
            else {
                return i;
            }
        }

        public void Reverse()
        {
            throw new NotImplementedException();
        }
    }
}

Program类

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;
using System.Net;
using System.Text;
using System.Threading.Tasks;

namespace test
{
    class Program
    {
        static void Main(string[] args)
        {
            SingleCycle<string> link = new SingleCycle<string>();
            //添加元素
            link.Append("123");
            link.Append("567");
            link.Append("jqk");
            link.Append("qwe");

            //link.Clear();
            //link.Delete(5);
            //Console.WriteLine(link.GetElem(4));
            //Console.WriteLine(link.GetLength());
            //link.Insert("asd", 4);
            Console.WriteLine(link.Locate("1231"));
            
            //输出
            Node<string> c = link.Head.Next;
            while (c != link.Head)
            {
                Console.WriteLine(c.Data);
                c = c.Next;
            }

            Console.Read();
        }
    }
}