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 的类，并且在声明为public Node next"的类中还有另一条语句.这个语句叫做构造函数吗?请帮忙.
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 类型包含对列表中下一项的引用，这就是您发布的 Node 类型中的 next 字段确实如此.此引用用于允许迭代列表.
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 为空时，您已到达列表的末尾.
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 属性为空的节点，表示列表的结尾.
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 引用，这里的输出将是 bb.这两个变量引用同一个对象.
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# 实际上确实有指针(它们对普通托管代码是隐藏的)，但已经足够接近了.除非您将它指向一个实例，否则它不能完全可用.就像 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# Nutshell 书籍.
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屋！
