WEB开发技术知识库

10.5 链表

LinkedList集合类没有非泛型集合的类似版本。LinkedList是一个双向链表，其元素指向它前面和后面的元素，如图10-3所示。

图 10-3

链表的优点是，如果将元素插入列表的中间位置，使用链表会非常快。在插入一个元素时，只需修改上一个元素的Next引用和下一个元素的Previous引用，使它们引用所插入的元素。在List和ArrayList类中，插入一个元素，需要移动该元素后面的所有元素。

当然，链表也有缺点。链表的元素只能一个接一个地访问，这需要较长的时间来查找位于链表中间或尾部的元素。

链表不仅能在列表中存储元素，还可以给每个元素存储下一个元素和上一个元素的信息。这就是LinkedList包含LinkedListNode类型的元素的原因。使用LinkedListNode 类，可以获得列表中的下一个元素和上一个元素。表10-5描述了LinkedListNode的属性。

表 10-5

类LinkedList执行了IEnumerable、ICollection、ICollection、IEnumerable、ISerializable和IDeserializationCallback接口。这个类的成员如表10-6所示。

表 10-6

(续表)

示例应用程序使用了一个链表LinkedList和一个列表List。链表包含文档，这与上一个例子相同，但文档有一个额外的优先级。在链表中，文档按照优先级来排序。如果多个文档的优先级相同，则这些元素就按照文档的插入时间来排序。

图10-4描述了示例应用程序中的集合。LinkedList是一个包含所有Document对象的链表，该图显示了文档的标题和优先级。标题指出了文档添加到链表中的时间。第一个添加的文档的标题是One。第二个添加的文档的标题是Two，依此类推。可以看出，文档One和Four有相同的优先级8，因为One在Four之前添加，所以One放在链表的前面。

图 10-4

在链表中添加新文档时，它们应放在优先级相同的最后一个文档后面。集合LinkedList 包含LinkedListNode类型的元素。类LinkedListNode添加Next和Previous属性，使搜索过程能从一个节点移动到下一个节点上。要引用这类元素，应把List定义为List>。为了快速访问每个优先级的最后一个文档，集合List 应最多包含10个元素，每个元素都引用不同优先级的最后一个文档。在后面的讨论中，对不同优先级的最后一个文档的引用称为优先级节点。

在上面的例子中，Document类扩展为包含优先级。优先级用类的构造函数设置：

public class Document

{

private string title;

public string Title

{

get

{

return title;

}

}

private string content;

public string Content

{

get

{

return content;

}

}

private byte priority;

public byte Priority

{

get

{

return priority;

}

}

public Document(string title, string content, byte priority)

{

this.title = title;

this.content = content;

this.priority = priority;

}

}

解决方案的核心是PriorityDocumentManager类。这个类很容易使用。在这个类的公共接口中，可以把新的Document元素添加到链表中，检索第一个文档，为了便于测试，它还提供了一个方法，在元素链接到链表中时，该方法可以显示集合中的所有元素。

PriorityDocumentManager类包含两个集合。LinkedList类型的集合包含所有的文档。List>类型的集合包含最多10个元素的引用，它们是添加指定优先级的新文档的入口点。这两个集合变量都用PriorityDocumentManager类的构造函数来初始化。列表集合也用null初始化：

public class PriorityDocumentManager

{

private readonly LinkedList documentList;

// priorities 0..9

private readonly List> priorityNodes;

public PriorityDocumentManager()

{

documentList = new LinkedList();

priorityNodes = new List>(10);

for (int i = 0; i < 10; i++)

{

priorityNodes.Add(new LinkedListNode(null));

}

}

在类的公共接口中，有一个方法AddDocument()。它只是调用私有方法AddDocumentTo- PriorityNode()。把实现代码放在另一个方法中的原因是，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 priorityNode = priorityNodes[priority];

if (priority == doc.Priority) // priority node with the same

// priority exists

{

documentList.AddAfter(priorityNode, doc);

// set the priority node to the last document with the same priority

priorityNodes[doc.Priority] = priorityNode.Next;

}

else // only priority node with a lower priority exists

{

// get the first node of the lower priority

LinkedListNode firstPriorityNode = priorityNode;

while (firstPriorityNode.Previous != null &&

firstPriorityNode.Previous.Value.Priority ==

priorityNode.Value.Priority)

{

firstPriorityNode = priorityNode.Previous;

}

documentList.AddBefore(firstPriorityNode, doc);

// set the priority node to the new value

priorityNodes[doc.Priority] = firstPriorityNode.Previous;

}

}

}

现在还剩下一个简单的方法没有讨论。DisplayAllNodes()只是在一个foreach循环中，把每个文档的优先级和标题显示在控制台上。

GetDocument方法从链表中返回第一个文档(优先级最高的文档)，并从链表中删除它：

public void DisplayAllNodes()

{

foreach (Document doc in documentList)

{

Console.WriteLine("priority: {0}, title {1}", doc.Priority, 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个优先级不同的新文档，再显示整个链表：

static void Main()

{

PriorityDocumentManager 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