LinkedList<T>
- 双向链表。通过移动到下一个元素,可以正向遍历整个链表。通过移动到前一个元素,可以反向遍历整个链表
- 插入元素,效率很高。只需要修改前一个元素的Next和后一个元素的Previous。相比之下,
List<T>
插入元素,需要移动后面所有元素。 - 要访问链表位于中间的元素,效率较低。只能从头或者从尾一个一个找过去。
- 元素为
LinkedListNode<T>
成员 | 说明 |
---|---|
First |
第一个元素 |
Last |
最后一个元素 |
AddAfter() |
指定位置后,插入 |
AddBefore() |
指定位置前,插入 |
AddFirst() |
插入到最前面 |
AddLast() |
插入到最后面 |
Remove() |
指定位置,删除 |
RemoveFirst() |
删除第一个 |
RemoveLast() |
删除最后一个 |
Find() |
从链表头,开始找 |
FindLast() |
从链表尾,开始找 |
LinkedListNode<T>
成员 | 说明 |
---|---|
List |
与此Node,相关的LinkedList<T> 对象 |
Next |
下一个Node |
Previous |
前一个Node |
Value |
此Node中,T类型的值 |
示例
- 动态插入Document的过程中,需要保持一种秩序
- 这种秩序是:
- Priority高的,排在前面
- Priority相同时,先插入的排在前面
class Program
{
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();
}
}
public class Document
{
public Document(string title, string content, byte priority)
{
Title = title;
Content = content;
Priority = priority;
}
public string Title { get; }
public string Content { get; }
public byte Priority { get; }
}
复制代码
输出:
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
复制代码
实现:
List<LinkedListNode<Document>> _priorityNodes
用来存储,在每一个Priority上,已经插入了的,最新的,Document。
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));
}
}
public void AddDocument(Document d)
{
if (d is null) throw new ArgumentNullException(nameof(d));
AddDocumentToPriorityNode(d, d.Priority);
}
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;
}
}
}
public void DisplayAllNodes()
{
foreach (Document doc in _documentList)
{
Console.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;
}
}
复制代码
近期评论