C#单链表实现

Question

当我试图理解如何在C#中实现单个列表时，我发现了以下链接：

创建一个非常简单的链表。

然而，由于我是C#的新手，我对上面讨论的第一部分中列出的语法感到困惑。正在声明一个名为Node的类，该类中还有另一条声明为"public Node next"。这个语句被称为构造函数吗？请帮忙。

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

Answer 1

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

封闭的LinkedList类（或您希望调用它的任何类）将包含对列表中第一项的单个Node引用。从第一个节点开始，您可以通过获取next字段来遍历列表。当next为空时，则您已到达列表的末尾。

以这个代码为例：

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;
}

要删除节点，您必须在列表中找到它之前的节点，然后从该节点更新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#中，所有类型都有两个基本分类：值类型和引用类型。名称反映了它们在代码块之间传递的方式：值类型按值传递（值被复制到新变量），而引用类型按引用传递（引用/指针被复制到一个新变量）。不同之处在于，对值类型参数的更改不会对调用方的值副本产生影响，而对引用类型参数的修改将反映在调用方的引用副本中。

对变量赋值和引用也是如此。在下文中，当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 Albahari（写了一篇关于价值和参考类型的伟大文章：C#概念：价值与参考类型。这本书非常值得一读，他写的很多东西也是如此。我还强烈建议你考虑在Nutshell书中获得他的一本C#。

Answer 2

有一种简单的方法可以创建Singly Linked List。让我们试着理解这个概念。若概念清晰，那个么你们就能理解逻辑本身。Singly Linked List有一个包含两个部分的Node。一个有数据值，另一个有下一个节点的引用地址。查看以下代码：

首先，我们需要创建链表节点类

/// <summary>
/// Creating the Real World Entity of Linked List Node
/// </summary>
public class LinkedListNode
{
    public Object Value { get; set; }
    public LinkedListNode Next { get; set; }
}

在这里，类有Value和Holder来保存序列中下一个Node的引用。接下来我们需要创建链表本身

/// <summary>
/// Creating the Linked List Class Itself. It defines the First and Last Nodes of Linked List
/// </summary>
public class LinkedList
{
    public LinkedListNode First { get; set; }
    public LinkedListNode Last { get; set; }
    /// <summary>
    /// Method to Add items into the Linked List
    /// </summary>
    /// <param name="_value"></param>
    public void AddToLinkedList(object _value)
    {
        LinkedListNode node = new LinkedListNode();
        node.Value = _value;
        if (First == null)
        {
            First = node;
            Last = node;
        }
        else
        {
            Last.Next = node;
            Last = node;
        }
    }
    /// <summary>
    /// Method to display all items. We can further implement the IEnumerable interface
    /// to Yield IEnumerator Interface.
    /// </summary>
    public void DisplayAllItems()
    {
        LinkedListNode current = First;
        while (current != null)
        {
            Console.WriteLine(current.Value);
            current = current.Next;
        }
    }
}

在这里，关键是将项目添加到链表中。首先，我们需要检查链接列表是否存在。我们检查链表中的第一个或头节点。如果它是空的，我们将该节点指定为第一个入口点。在这个阶段，最后一个项目是第一个项目本身。

现在这就是我们添加和显示项目的方式

class Program
{
    static void Main(string[] args)
    {
        LinkedList singlyLinkedList = new LinkedList();
        singlyLinkedList.AddToLinkedList(4);
        singlyLinkedList.AddToLinkedList(5);
        singlyLinkedList.AddToLinkedList(7);
        singlyLinkedList.AddToLinkedList(2);
        singlyLinkedList.AddToLinkedList(1);
        singlyLinkedList.AddToLinkedList(10);
        singlyLinkedList.DisplayAllItems();
        Console.ReadLine();
    }
}

让我知道它是否有意义：）

Answer 3

它是类字段。参考：http://msdn.microsoft.com/en-us/library/ms173118.aspx

Answer 4

请记住，链表不仅保存数据，还保存指向列表中下一个节点的引用/指针。由于类在C#中是引用类型，所以您不会看到任何在C或C++中会看到的特殊语法。

struct Node
{
    int Number;
    struct Node* next; /* this points to the next node in the linked list */
};