11.6 链表
LinkedList<T>是一个双向链表，其元素指向它前面和后面的元素，如图11-3所示。这样一来，通过移动到下一个元素可以正向遍历整个链表，通过移动到前一个元素可以反向遍历整个链表。
图11-3
链表的优点是，如果将元素插入列表的中间位置，使用链表就会非常快。在插入一个元素时，只需要修改上一个元素的Next引用和下一个元素的Previous引用，使它们引用所插入的元素。在List<T>类中，插入一个元素时，需要移动该元素后面的所有元素。
当然，链表也有缺点。链表的元素只能一个接一个地访问，这需要较长的时间来查找位于链表中间或尾部的元素。
链表不能在列表中仅存储元素。存储元素时，链表还必须存储每个元素的下一个元素和上一个元素的信息。这就是LinkedList<T>包含LinkedListNode<T>类型的元素的原因。使用LinkedListNode<T>类，可以获得列表中的下一个元素和上一个元素。LinkedListNode<T>定义了属性List、Next、Previous和Value。List属性返回与节点相关的LinkedList<T>对象，Next和Previous属性用于遍历链表，访问当前节点之后和之前的节点。Value返回与节点相关的元素，其类型是T。
LinkedList<T>类定义的成员可以访问链表中的第一个和最后一个元素(First和Last)、在指定位置插入元素(AddAfter()、AddBefore()、AddFirst()和AddLast()方法)，删除指定位置的元素(Remove()、RemoveFirst()和RemoveLast()方法)、从链表的开头(Find()方法)或结尾(FindLast()方法)开始搜索元素。
示例应用程序使用了一个链表和一个列表。链表包含文档，这与上一个队列例子相同，但文档有一个额外的优先级。在链表中，文档按照优先级来排序。如果多个文档的优先级相同，这些元素就按照文档的插入时间来排序。
图11-4描述了示例应用程序中的集合。LinkedList<Document>是一个包含所有Document对象的链表，该图显示了文档的标题和优先级。标题指出了文档添加到链表中的时间。第一个添加的文档的标题是“One”。第二个添加的文档的标题是“Two”，依此类推。可以看出，文档One和Four有相同的优先级8，因为One在Four之前添加，所以One放在链表的前面。
在链表中添加新文档时，它们应放在优先级相同的最后一个文档后面。集合LinkedList <Document>包含LinkedListNode<Document>类型的元素。LinkedListNode<T>类添加Next和Previous属性，使搜索过程能从一个节点移动到下一个节点上。要引用这类元素，应把List<T>定义为List<LinkedListNode<Document>>。为了快速访问每个优先级的最后一个文档，集合List<LinkedList-Node>应最多包含10个元素，每个元素分别引用每个优先级的最后一个文档。在后面的讨论中，对每个优先级的最后一个文档的引用称为优先级节点。
图11-4
在上面的例子中，Document类扩展为包含优先级。优先级用类的构造函数设置(代码文件LinkedListSample/Document.cs)：
public class Document
{
public string Title { get; private set; }
public string Content { get; private set; }
public byte Priority { get; private set; }
public Document(string title, string content, byte priority)
{
Title = title;
Content = content;
Priority = priority;
}
}
解决方案的核心是PriorityDocumentManager类。这个类很容易使用。在这个类的公共接口中，可以把新的Document元素添加到链表中，可以检索第一个文档，为了便于测试，它还提供了一个方法，在元素链接到链表中时，该方法可以显示集合中的所有元素。
PriorityDocumentManager类包含两个集合。LinkedList<Document>类型的集合包含所有的文档。List<LinkedListNode<Document>>类型的集合包含最多10个元素的引用，它们是添加指定优先级的新文档的入口点。这两个集合变量都用PriorityDocumentManager类的构造函数来初始化。列表集合也用null初始化(代码文件LinkedListSample/PriorityDocumentManager.cs)：
public class PriorityDocumentManager
{
private readonly LinkedList<Document> _documentList;
// priorities 0.9
private readonly List<LinkedListNode<Document>> _priorityNodes;
public PriorityDocumentManager()
{
_documentList = new LinkedList<Document>();
_priorityNodes = new List<LinkedListNode<Document>>(10);
for (int i = 0; i < 10; i++)
{
_priorityNodes.Add(new LinkedListNode<Document>(null));
}
}
在类的公共接口中，有一个AddDocument()方法。AddDocument()方法只调用私有方法AddDocumentToPriorityNode()。把实现代码放在另一个方法中的原因是，AddDocumentToPriorityNode()方法可以递归调用，如后面所示。
public void AddDocument(Document d)
{
if (d == null) throw new ArgumentNullException("d");
AddDocumentToPriorityNode(d, d.Priority);
}
在AddDocumentToPriorityNode()方法的实现代码中，第一个操作是检查优先级是否在允许的优先级范围内。这里允许的范围是0~9。如果传送了错误的值，就会抛出一个ArgumentException类型的异常。
接着检查是否已经有一个优先级节点与所传送的优先级相同。如果在列表集合中没有这样的优先级节点，就递归调用AddDocumentToPriorityNode()方法，递减优先级值，检查是否有低一级的优先级节点。
如果优先级节点的优先级值与所传送的优先级值不同，也没有比该优先级值更低的优先级节点，就可以调用AddLast()方法，将文档安全地添加到链表的末尾。另外，链表节点由负责指定文档优先级的优先级节点引用。
如果存在这样的优先级节点，就可以在链表中找到插入文档的位置。这里必须区分是存在指定优先级值的优先级节点，还是存在以较低的优先级值引用文档的优先级节点。对于第一种情况，可以把新文档插入由优先级节点引用的位置后面。因为优先级节点总是引用指定优先级值的最后一个文档，所以必须设置优先级节点的引用。如果引用文档的优先级节点有较低的优先级值，情况就会比较复杂。这里新文档必须插入优先级值与优先级节点相同的所有文档的前面。为了找到优先级值相同的第一个文档，要通过一个while循环，使用Previous属性遍历所有的链表节点，直到找到一个优先级值不同的链表节点为止。这样，就找到了必须插入文档的位置，并可以设置优先级节点。
private void AddDocumentToPriorityNode(Document doc, int priority)
{
if (priority > 9 || priority < 0)
throw new ArgumentException("Priority must be between 0 and 9");
if (_priorityNodes[priority].Value == null)
{
--priority;
if (priority <= 0)
{
// check for the next lower priority
AddDocumentToPriorityNode(doc, priority);
}
else // now no priority node exists with the same priority or lower
// add the new document to the end
{
_documentList.AddLast(doc);
_priorityNodes[doc.Priority] = _documentList.Last;
}
return;
}
else // a priority node exists
{
LinkedListNode<Document> prioNode = _priorityNodes[priority];
if (priority == doc.Priority)
// priority node with the same priority exists
{
_documentList.AddAfter(prioNode, doc);
// set the priority node to the last document with the same priority
_priorityNodes[doc.Priority] = prioNode.Next;
}
else // only priority node with a lower priority exists
{
// get the first node of the lower priority
LinkedListNode<Document> firstPrioNode = prioNode;
while (firstPrioNode.Previous ! = null &&
firstPrioNode.Previous.Value.Priority == prioNode.Value.Priority)
{
firstPrioNode = prioNode.Previous;
prioNode = firstPrioNode;
}
_documentList.AddBefore(firstPrioNode, doc);
// set the priority node to the new value
_priorityNodes[doc.Priority] = firstPrioNode.Previous;
}
}
}
现在还剩下几个简单的方法没有讨论。DisplayAllNodes()方法只是在一个foreach循环中，把每个文档的优先级和标题显示在控制台上。
GetDocument()方法从链表中返回第一个文档(优先级最高的文档)，并从链表中删除它：
public void DisplayAllNodes()
{
foreach (Document doc in documentList)
{
WriteLine($"priority: {doc.Priority}, title {doc.Title}");
}
}
// returns the document with the highest priority
// (that's first in the linked list)
public Document GetDocument()
{
Document doc = _documentList.First.Value;
_documentList.RemoveFirst();
return doc;
}
在Main()方法中，PriorityDocumentManager类用于说明其功能。在链表中添加8个优先级不同的新文档，再显示整个链表(代码文件LinkedListSample/Program.cs)：
public static void Main()
{
var pdm = new PriorityDocumentManager();
pdm.AddDocument(new Document("one", "Sample", 8));
pdm.AddDocument(new Document("two", "Sample", 3));
pdm.AddDocument(new Document("three", "Sample", 4));
pdm.AddDocument(new Document("four", "Sample", 8));
pdm.AddDocument(new Document("five", "Sample", 1));
pdm.AddDocument(new Document("six", "Sample", 9));
pdm.AddDocument(new Document("seven", "Sample", 1));
pdm.AddDocument(new Document("eight", "Sample", 1));
pdm.DisplayAllNodes();
}
在处理好的结果中，文档先按优先级排序，再按添加文档的时间排序：
priority: 9, title six
priority: 8, title one
priority: 8, title four
priority: 4, title three
priority: 3, title two
priority: 1, title five
priority: 1, title seven
priority: 1, title eight