C#单链表实现 [英] C# singly linked list implementation
问题描述
当试图了解如何在C#中实现单个列表时，我遇到了以下链接:
While trying to understand how a singly list can be implemented in C#, I came across the link below :
但是，由于我是C#的新手，所以我对上面讨论的初始部分中列出的语法感到困惑.正在声明一个名为Node的类，并且该类中还有另一个声明为"next public Node"的语句.该语句称为构造函数吗?请帮忙.
However, as I am new to C#, I got confused by the syntax that is listed in the initial section of the discussion above. A class named Node is being declared and there is another statement within the class declared as "public Node next". Is this statement called a constructor? Please help.
public class Node {
public Node next;
public Object data;
}
推荐答案
在简单的单链接列表实现中，Node类型包含对列表中下一项的引用，这是其中的next字段您发布的Node类型.此引用用于允许列表的迭代.
In a simple singly-linked list implementation the Node type contains a reference to the next item in the list, which is what the next field in the Node type you posted does. This reference is used to allow iteration of the list.
封闭的LinkedList类(或任何您想调用的类)将包含对列表中第一项的单个Node引用.从第一个节点开始，然后可以通过获取next字段来逐步浏览列表.如果next为null，则您已到达列表的末尾.
The enclosing LinkedList class (or whatever you wish to call it) will contain a single Node reference to the first item in the list. Starting from that first node you can then step through the list by getting the next field. When next is null then you have reached the end of the list.
以下面的代码为例:
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的节点(表示列表的末尾)为止.
The First property simply returns the root node, which is the first node in the list. The Last property starts at the root node and steps through the list until it finds a node whose next property is null, indicating the end of the list.
这使得将项目追加到列表变得很简单:
This makes it simple to append items to the list:
public void Append(object value)
{
Node n = new Node { data = value };
if (root == null)
root = n;
else
Last.next = n;
}
要删除一个节点，您必须在列表中找到该节点之前的节点，然后将next链接从那个节点更新为指向要删除的节点之后的节点:
To delete a node you have to find the node that precedes it in the list, then update the next link from that node to point to the node following the one to be deleted:
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链接.
There are a few other operations you can perform, like inserting values at positions in the list, swapping nodes, etc. Inserting after a node is fast, before is slow since you have to locate the prior node. If you really want fast 'insert-before' you need to use a doubly-linked list where the Node type has both next and previous links.
要在评论中扩展您的问题...
To expand on your question in the comment...
在C#中，所有类型都属于两种基本分类:值类型和引用类型.名称反映了它们在代码块之间传递的方式:值类型按值传递(值复制到新变量)，而引用类型按引用传递(将引用/指针复制到新变量).区别在于，对值类型参数的更改不会影响调用方的值副本，而对引用类型参数的更改将反映在调用方的引用副本中.
In C# there are two basic classifications that all types fall into: value types and reference types. The names reflect the way they are passed between blocks of code: value types are passed by value (value is copied to a new variable), while reference types are passed by reference (a reference/pointer is copied to a new variable). The difference there is that changes to a value type parameter will have no effect on the caller's copy of the value, while changes to a reference type parameter will be reflected in the caller's copy of the reference.
为变量赋值和引用同样如此.在以下情况中，当更改b时，a的值不会更改:
The same is true of assigning values and references to variables. In the following, the value of a is not changed when b is changed:
int a = 0;
int b = a;
b = 1;
那是很直观的.可能会使您失望的是，在C#中，struct也是一种值类型:
That's fairly intuitive. What might trip you up is that in C# a struct is also a value type:
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时，将进行复制.但是，如果我们更改一个类的结构:
The above will give the output a b because when you assigned a to b a copy was made. But if we change the struct for a class:
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是对 same 对象的引用，作为一个变量a引用，所以这里的输出将是b b.这两个变量引用相同的 object .
Because the variable b is a reference to the same object as the one variable a references, the output here will be b b. The two variables reference the same object.
如果您来自C/C ++或其他类似语言，则可以将引用类型变量视为指针.它并不完全相同，C#实际上具有指针(它们从常规托管代码中隐藏了)，但是它足够接近.除非您将其指向该类型的 instance ，否则它无法完全使用.就像C/C ++中的char*并不是特别有用，直到您将其指向某个位置.
If you've come from C/C++ or some other similar language, you can think of reference type variables as being pointers. It's not quite the same, and C# does actually have pointers (they're hidden from normal managed code), but it's close enough. Until you point it to an instance of the type it is not fully usable. Just like a char* in C/C++ isn't particularly useful until you point it somewhere.
Joseph Alhabari(撰写了一篇有关值和引用类型的好文章: C#概念:值与引用类型 .正如他的许多著作一样，值得一读.我也强烈建议您考虑让他的 C#果壳 书籍.
Joseph Alhabari (has written a great article about value and reference types: C# Concepts: Value vs Reference Types. It is well worth a read, as is much of what he writes. I would also highly recommend you consider getting one of his C# Nutshell books.
这篇关于C#单链表实现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
