C# 实现循环链表：节点定义与核心操作代码示例

节点类设计

循环链表的基础单元是节点（Node），它需要存储数据并指向下一个节点。以下是节点类的定义：

public class Node
{
    public object Element;
    public Node Link;

    public Node()
    {
        Element = null;
        Link = null;
    }

    public Node(object theElement)
    {
        Element = theElement;
        Link = null;
    }
}

该类包含两个主要属性：Element 用于存储数据，Link 用于指向链表的下一个节点。提供了无参和有参两种构造函数以方便初始化。

链表管理类与初始化

链表类（LinkedList）负责管理一系列节点。在循环链表中，通常需要一个“头结点”或特殊标记来标识结束位置，从而实现循环效果。

public class LinkedList
{
    protected Node Header;
    private int count;

    public LinkedList()
    {
        count = 0;
        Header = new Node("header"); // 使用特殊字符串作为标记
        Header.Link = Header; // 初始时指向自身，形成空循环
    }

    public bool IsEmpty()
    {
        return (Header.Link == null); // 注意：标准循环链表判断需结合逻辑，此处保留原逻辑供参考
    }

    public void MakeEmpty()
    {
        Header.Link = null;
    }
}

构造函数中将 Header 初始化为一个值为 "header" 的特殊节点，并将其 Link 指向自己，构成一个空的循环结构。count 变量用于记录链表中的元素个数。

核心操作方法

第1步：实现查找功能

为了执行插入或删除操作，首先需要能够定位到特定的节点或它的前驱节点。

private Node FindPrevious(object n)
{
    Node current = Header;
    while (!(current.Link == null) && current.Link.Element != n)
    {
        current = current.Link;
    }
    return current;
}

private Node Find(object item)
{
    Node current = new Node();
    current = Header.Link;
    while (current.Element != item)
    {
        current = current.Link;
    }
    return current;
}

FindPrevious 方法返回指定元素前一个节点的引用，这是删除和插入操作的关键。Find 方法直接返回包含指定元素的节点。

第2步：实现插入操作

在循环链表中插入新节点有两种常见方式：在特定节点后插入或在头部插入。

public void Insert(object newItem, object after)
{
    Node current = new Node();
    Node newNode = new Node(newItem);
    current = Find(after);
    newNode.Link = current.Link;
    current.Link = newNode;
    count++;
}

public void InsertFirst(object n)
{
    Node current = new Node(n);
    current.Link = Header;
    Header.Link = current;
    count++;
}

Insert 方法将新节点插入到名为 after 的节点之后。InsertFirst 将新节点放在头部，并更新头结点的指向。

第3步：实现删除操作

删除节点同样依赖于找到其前驱节点，然后跳过目标节点。

public void Remove(object n)
{
    Node p = FindPrevious(n);
    if (!(p.Link == null))
    {
        p.Link = p.Link.Link;
        count--;
    }
}

该方法找到要删除节点的前一个节点，将其 Link 指向被删除节点的下一个节点，从而实现逻辑上的移除，并递减计数器。

第4步：遍历与输出

由于是循环链表，遍历时需要避免无限循环。可以通过检查是否回到特殊标记节点来终止循环。

public void PrintList()
{
    Node current = new Node();
    current = Header;
    while (current.Link.Element.ToString() != "header")
    {
        Console.WriteLine(current.Link.Element);
        current = current.Link;
    }
}

此方法从头部开始，逐个打印节点元素，直到再次遇到值为 "header" 的节点为止。

第5步：辅助移动与获取

提供按索引移动和获取首个节点的辅助方法，便于更灵活地访问链表。

public Node Move(int n)
{
    Node current = Header.Link;
    Node tmp;
    for (int i = 0; i <= n; i++)
    {
        current = current.Link;
    }
    if (current.Element.ToString() == "header")
    {
        current = current.Link;
    }
    tmp = current;
    return tmp;
}

public Node GetFirst()
{
    return Header;
}

Move 方法允许用户根据偏移量定位节点，并在到达尾部标记时进行修正处理。GetFirst 返回头结点引用。

总结

以上代码展示了 C# 中循环链表的基本构建块。通过组合这些类和操作，可以创建一个功能完整的循环队列或其他依赖循环结构的算法模型。需要注意的是，实际生产环境中可能需要考虑泛型类型、异常处理以及更严谨的空指针检查，上述代码旨在演示核心逻辑结构。