使用 C# 中的链表
3.32/5 (21投票s)
本文旨在鼓励在 C# 中使用链表。
引言
许多程序需要某种形式的动态内存管理。当需要创建其大小在程序构建时无法静态确定的数据结构时，就会出现这种需求。搜索树、符号表和链表是动态数据结构的示例。链表是由称为节点的自引用类对象组成的线性集合（即序列），通过引用链接连接。程序通过对链表中第一个节点的引用来访问链表。每个后续节点都通过前一个节点中存储的链接引用号来访问。数据以动态方式存储在链表中——也就是说，每个节点都在需要时创建。因此，一个节点可以包含任何类型的数据，包括对其他类的其他对象的引用。与数组相比，使用链表的优点在于，数组可以声明包含比预期项目数更多的元素，可能浪费内存。链表提供更好的内存利用率，因为它们可以在执行时增长和收缩，从而节省内存。数组的元素在内存中连续存储，以便于直接访问任何数组元素。也就是说，数组中任何元素的地址都可以直接从其索引计算得出。链表无法快速访问其元素：您必须从头开始遍历链表。我写这篇文章是为了举例说明一个可以被测试程序（一个非常基础的程序）使用的链表库。该程序由四个类组成。我们将构建它，然后将其安装到我们的全局程序集缓存中。
using System;
namespace LinkedListLibrary
{
class ListNode
{
public object Data { get; private set; }
public ListNode Next { get; set; }
public ListNode(object dataValue )
: this (dataValue, null)
{
}
public ListNode(object dataValue, ListNode nextNode )
{
Data = dataValue;
Next = nextNode;
}
}
public class List
{
private ListNode firstNode;
private ListNode lastNode;
private string name;
public List( string listName)
{
name = listName;
firstNode = lastNode = null;
}
public List()
: this("list")
{
}
public void InsertAtFront(object insertItem)
{
if ( IsEmpty() )
firstNode = lastNode = new ListNode(insertItem);
else
lastNode = lastNode.Next = new ListNode(insertItem);
}
public void InsertAtBack(object insertItem)
{
if (IsEmpty())
firstNode = lastNode = new ListNode(insertItem);
else
firstNode = new ListNode( insertItem, firstNode);
}
public object RemoveFromFront()
{
if (IsEmpty())
throw new EmptyListException( name );
object removeItem = firstNode.Data;
if (firstNode == lastNode)
firstNode = lastNode = null;
else
firstNode = firstNode.Next;
return removeItem;
}
public object RemoveFromBack()
{
if (IsEmpty() )
throw new EmptyListException( name );
object removeItem = lastNode.Data;
if (firstNode == lastNode)
firstNode = lastNode = null;
else
{
ListNode current = firstNode;
while (current.Next != lastNode)
current = current.Next;
lastNode = current;
current.Next = null;
}
return removeItem;
}
public bool IsEmpty()
{
return firstNode == null;
}
public void Display()
{
if ( IsEmpty() )
{
Console.WriteLine( "Empty " + name);
}
else
{
Console.Write("The " + name + " is: ");
ListNode current = firstNode;
while ( current != null )
{
Console.Write(current.Data + " " );
current = current.Next;
}
Console.WriteLine("\n");
}
}
}
public class EmptyListException : Exception
{
public EmptyListException()
: base("The list is empty")
{
}
public EmptyListException(string name)
: base("the " + name + " is empty")
{
}
public EmptyListException(string exception, Exception inner)
: base( exception, inner)
{
}
}
}
请注意，在四个类中定义的方法涉及在链表的开头或末尾进行插入或删除。这意味着这种数据结构需要某种形式的动态内存管理；即使它是序列，它也不会像数组那样在内存中存储。节点在逻辑上是连续的，并形成一个图。这种增长和收缩节省了内存。所以如果我们编译它
csc.exe /target:library /out: LinkedListLibrary.dll LinkedListLibrary.cs
现在让我们给它一个键
sn –k LinkedLibrary.key
sn -p LinkedList.key LinkedList.PublicKey
Public key written to LinkedList.PublicKey
sn –tp LinkedList.PublicKey
Public key is
00240000048000009400000006020000002400005253413100040000010001001140e2bd73e36c
ab97d26e829e0c6effdf19cf4bb207d8390ffaff1d6ed27589cf051c73af89f3f2835ec22af689
1014297135206738f65188ab6c344b7e8bf0ff0cacc23835f7e9c36edea4965326c67d91e2dcce
e69aa334c9f4f7973f0fb5ec87b41f75a8f093ce9f538498ea75c070f049c05a43a328f58fb977
0d1bd6ec
Public key token is d45a48ae6bd81f08
csc /keyfile:LinkedList.key /target:library LinkedListLibrary.cs
gacutil -i LinkedListLibrary.dll
Assembly successfully added to the cache
类List 包含private 实例变量firstNode （对 List 中第一个ListNode 的引用）和lastNode （对List中最后一个ListNode 的引用）。方法IsEmpty()是一个谓词方法，用于确定列表是否为空（即，对列表第一个节点的引用为null）。如果列表为空，IsEmpty()返回true。Display()方法显示列表的内容。下一个程序将引用该库，并在所有原始数据类型上使用这些函数。
using System;
using LinkedListLibrary;
class ListTest
{
public static void Main(string[] args)
{
List list = new List();
bool aBoolean = true;
char aCharacter = '$';
int anInteger = 34567;
string aString = "hello";
list.InsertAtFront(aBoolean);
list.Display();
list.InsertAtFront(aCharacter);
list.Display();
list.InsertAtBack(anInteger);
list.Display();
list.InsertAtBack(aString);
list.Display();
object removedObject;
try
{
removedObject = list.RemoveFromFront();
Console.WriteLine( removedObject + " removed");
list.Display();
removedObject = list.RemoveFromFront();
Console.WriteLine( removedObject + " removed");
list.Display();
removedObject = list.RemoveFromBack();
Console.WriteLine( removedObject + " removed");
list.Display();
removedObject = list.RemoveFromBack();
Console.WriteLine( removedObject + " removed");
list.Display();
}
catch (EmptyListException emptyListException)
{
Console.Error.WriteLine( "\n" + emptyListException);
}
}
}
现在是输出
The list is: True
The list is: True $
The list is: 34567 True $
The list is: hello 34567 True $
hello removed
The list is: 34567 True $
34567 removed
The list is: True $
$ removed
The list is: True
True removed
Empty list
典型的外部引用编译
csc.exe /r:LinkedListLibrary.dll ListTest.cs
这四个类构建了LinkedListLibrary ，也可用于其他线性数据结构，如栈和队列。而树则是一种非线性、二维数据结构，具有特殊的属性。但从初学者的角度来看，该可重用组件仅用于演示链表的基本原理。无法避免 BCL 链表类定义。
.NET 2.0 引入了泛型。泛型在原则上类似于模板和 ISO C++ 中的 STD。假设您有一个对象集合，所有对象都是支票的数值金额。它们构成一个明细列表。数据类型显然是 decimal 类型。但是，如果其中一个或多个类型不同（例如，string、Int32、char 等），那么算法或处理过程中使用的函数将无法处理不同数据类型的对象。例如，在处理string类型时会出现编译器错误。最简单的说，泛型涉及参数化类型，以便将数据类型传递给类（就像将参数传递给函数一样）。.NET Framework 提供了一个双向链表类。LinkedList<t>类——位于System.dll程序集中——存储LinkedListNode<t>类型的节点集合，每个节点负责维护指向列表中下一个元素的指针。也就是说，链表本身只维护指向首尾元素的指针（即头部和尾部）——在链表类型上表示为 Front 和 Back 属性。每个节点都有指向列表中相邻节点的 Next 和 Previous 指针。
LinkedListNode<t>实例化通常有三个属性：Next、Previous和Value
列表末尾的 Next 将为null，类似于文件末尾。考虑这段代码
using System;
using System.Collections.Generic;
public sealed class Program
{
public static void Main()
{
LinkedList<int> list = new LinkedList<int>();
list.AddFirst(10); // Contents: ->10
list.AddLast(15); // Contents: ->10->15
list.AddLast(3); // Contents: ->10->15->3
list.AddLast(99); // Contents: ->10->15->3->99
list.AddBefore(list.Last, 25); // Contents: ->10->15->3->25->99
LinkedListNode<int> node = list.First;
while (node != null)
{
Console.WriteLine(node.Value);
node = node.Next;
}
}
}
输出将如预期
10
15
3
25
99
请注意，我们通过链接列表节点进行迭代，直到节点值为null才进行分支。然后，在建立链表元素和对其执行的操作之前，显示初始构造函数的执行结果。但之前我提到了内存资源。在 .NET 中，链表不像数组那样为其元素分配顺序存储或连续存储。这就是集合开始的原因，因为数组存在局限性。相反，链表使用指针将各个元素链接在一起。因此，链表在插入和删除元素方面更快，但在遍历方面更慢——遍历集合内容更慢。访问每个元素都需要额外的指针解引用。因此，链表元素指向内存的其他区域，因为存在这种间接寻址：它们可以指向远离源点的内存区域。这可能会导致垃圾回收开销以及对元素的任何随机访问。文件 I/O 对于顺序访问和随机访问数据也是如此。访问列表中的任意节点需要您从头部或尾部开始。也许动态结构带来的成本应该与遍历列表的开销进行权衡。