C#单向链表实现

Question

在尝试了解如何在 C# 中实现单个列表时，我看到了以下链接:

Creating a very simple linked list .

但是，由于我是 C# 的新手，我对上面讨论的初始部分中列出的语法感到困惑。正在声明一个名为 Node 的类，该类中还有另一个语句声明为“public Node next”。这个语句叫做构造函数吗？请帮忙。

public class Node {
    public Node next;
    public Object data;
 }

Answer 1

在一个简单的单链表实现中，Node 类型包含对列表中下一项的引用，这就是 中的 next 字段您发布的节点 类型确实如此。此引用用于允许迭代列表。

封闭的 LinkedList 类(或任何你想给它起的名字)将包含对列表中第一项的单个 Node 引用。从第一个节点开始，您可以通过获取 next 字段逐步浏览列表。当 next 为 null 时，您已到达列表的末尾。

以这段代码为例:

public class LinkedList
{
    public class Node
    {
        // link to next Node in list
        public Node next = null;
        // value of this Node
        public object data;
    }

    private Node root = null;

    public Node First { get { return root; } }

    public Node Last 
    {
        get
        {
            Node curr = root;
            if (curr == null)
                return null;
            while (curr.next != null)
                curr = curr.next;
            return curr;
        }
    }
}

First 属性只返回根节点，即列表中的第一个节点。 Last 属性从根节点开始，遍历列表，直到找到 next 属性为 null 的节点，表示列表结束。

这使得将项目附加到列表变得简单:

public void Append(object value)
{
    Node n = new Node { data = value };
    if (root == null)
        root = n;
    else
        Last.next = n;
}

要删除一个节点，您必须在列表中找到它之前的节点，然后更新 that 节点的 next 链接以指向该节点之后的节点待删除:

public void Delete(Node n)
{
    if (root == node) 
    {
        root = n.next;
        n.next = null;
    }
    else
    {
        Node curr = root;
        while (curr.next != null)
        {
            if (curr.next == n)
            {
                curr.next = n.next;
                n.next = null;
                break;
            }
            curr = curr.next;
        }
    }
}

您还可以执行一些其他操作，例如在列表中的位置插入值、交换节点等。在节点之后插入速度很快，在节点之前插入速度很慢，因为您必须找到前一个节点。如果您真的想要快速“插入之前”，则需要使用双向链表，其中 Node 类型同时具有 next 和 previous 链接.

---

在评论中扩展您的问题...

在 C# 中，所有类型都属于两个基本分类:值类型和引用类型。名称反射(reflect)了它们在代码块之间传递的方式:值类型按值传递(值被复制到新变量)，而引用类型按引用传递(引用/指针被复制到新变量)。不同之处在于，对值类型参数的更改不会影响调用者的值副本，而对引用类型参数的更改将反射(reflect)在调用者的引用副本中。

对变量赋值和引用也是如此。下面，当b改变时，a的值不变:

int a = 0;
int b = a;
b = 1;

这是相当直观的。可能会让您感到困惑的是，在 C# 中，struct 也是一种值类型:

public struct test
{
    public string value;
}

static void Main()
{
    test a;
    a.value = "a";
    test b = a;
    b.value = "b";

    Console.WriteLine("{0} {1}", a.value, b.value);
}

上面将给出输出 a b 因为当你将 a 分配给 b 时，一个副本就被创建了。但是如果我们改变一个类的结构:

public class test
{
    public string value;
}

static void Main()
{
    test a = new test(); // Note the 'new' keyword to create a reference type instance
    a.value = "a";
    test b = a;
    b.value = "b";
    Console.WriteLine("{0} {1}", a.value, b.value);
}

因为变量 b 是对 相同 对象的引用，作为一个变量 a 引用，这里的输出将是 b b。这两个变量引用相同的对象。

如果您使用过 C/C++ 或其他类似语言，您可以将引用类型变量视为指针。它并不完全相同，C# 实际上有指针(它们对普通托管代码是隐藏的)，但它已经足够接近了。在您将它指向该类型的一个实例 之前，它是不能完全使用的。就像 C/C++ 中的 char* 在您将它指向某个地方之前并不是特别有用。

Joseph Alhabari(写了一篇关于值和引用类型的好文章:C# Concepts: Value vs Reference Types。非常值得一读，他写的很多东西也是如此。我也强烈建议您考虑获得他的一篇文章 C# Nutshell书。