C#集合之链表的用法
作者:Ruby_Lu 时间:2022-02-07 13:38:34
LinkedList<T>是一个双向链表,其元素会指向它前面和后面的元素。这样,通过移动到下一个元素可以正向遍历链表,通过移动到前一个元素可以反向遍历链表。
链表在存储元素时,不仅要存储元素的值,还必须存储每个元素的下一个元素和上一个元素的信息。这就是LinkedList<T>包含LinkedListNode<T>类型的元素的原因。使用LinkedListNode<T>,可以获得列表中的下一个和上一个元素。LinkedListNode<T>定义了属性List,Next,Previous和Value。List属性返回与节点相关的LinkedList<T>对象。Next和Previous属性用于遍历链表,访问当前节点之后和之前的节点。Value属性返回与节点相关的元素,其类型是T。
链表的优点是,如果将元素插入到列表的中间位置,使用链表就会很快。在插入一个元素时,秩序啊哟修改上一个元素的Next引用和下一个元素的Previous引用,使它们引用所插入的元素。在List<T>(https://www.jb51.net/article/244084.htm)中,插入一个元素,需要移动该元素后面的所以元素。
链表的缺点是,链表元素只能一个接一个的访问,这需要较长时间来查找位于链表中间或尾部的元素。
LinkedList<T>类定义的成员可以访问链表中的第一个和最后一个元素(First和Last);
在指定位置插入元素:AddAfter(),AddFirst()和AddLast();
删除指定位置的元素:Remove(),RemoveFirst(),RemoveLast();
搜索:Find(),FindLast()。
下面用一个例子演示链表。在链表中,文档按照优先级来排序。如果多个文档的优先级相同,这些元素就按照文档的插入时间来排序:
PriorityDocumentManager类使用一个链表LinkedList<Document> documentList和一个列表List<LinkedListNode<Document>> priorityNodes,链表包含Document对象,Document对象包含文档的标题和优先级。列表List<LinkedListNode<Document>> priorityNodes应最多包含10个元素,每个元素分别是引用每个优先级的最后一个文档对象。
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)
{
//Contract.Requires<ArgumentNullException>(d != null, "argument d must not be null");
if (d == null) throw new ArgumentNullException("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");
//检查优先级列表priorityNodes中是否有priority这个优先级
if (priorityNodes[priority].Value == null)
{
//如果没有,递减优先级值,递归AddDocumentToPriorityNode方法,检查是否有低一级的优先级
--priority;
if (priority >= 0)
{
AddDocumentToPriorityNode(doc, priority);
}
else //如果已经没有更低的优先级时,就直接在链表中添加该节点,并将这个节点添加到优先级列表
{
documentList.AddLast(doc);
priorityNodes[doc.Priority] = documentList.Last;
}
return;
}
else //优先级列表priorityNodes中有priority这个优先级
{
LinkedListNode<Document> prioNode = priorityNodes[priority];
//区分优先级列表priorityNodes存在这个指定的优先级值的节点,还是存在较低的优先级值的节点
if (priority == doc.Priority)
// 如果存在这个指定的优先级值的节点
{
//将这个节点添加到链表
documentList.AddAfter(prioNode, doc);
// 将这个节点赋予优先级列表中的这个优先级值的节点,因为优先级节点总是引用指定优先级节点的最后一个文档
priorityNodes[doc.Priority] = prioNode.Next;
}
else //如果存在较低的优先级值的节点
{
//在链表中找到这个较低优先级的第一个节点,把要添加的节点放到它前面
LinkedListNode<Document> firstPrioNode = prioNode;
//通过循环,使用Previous找到这个优先级的第一个节点
while (firstPrioNode.Previous != null &&
firstPrioNode.Previous.Value.Priority == prioNode.Value.Priority)
{
firstPrioNode = prioNode.Previous;
prioNode = firstPrioNode;
}
documentList.AddBefore(firstPrioNode, doc);
// 设置一个新的优先级节点
priorityNodes[doc.Priority] = firstPrioNode.Previous;
}
}
}
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;
}
}
//存储在链表中的元素是Document类型
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)
{
this.Title = title;
this.Content = content;
this.Priority = priority;
}
}
客户端代码:
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();
Console.ReadKey();
}
来源:https://www.cnblogs.com/afei-24/p/6830160.html
![](/images/zang.png)
![](/images/jiucuo.png)
猜你喜欢
spring boot actuator监控超详细教程
![](https://img.aspxhome.com/file/2023/3/94293_0s.png)
Java基于socket实现的客户端和服务端通信功能完整实例
![](https://img.aspxhome.com/file/2023/0/85440_0s.png)
springboot项目main函数启动的操作
![](https://img.aspxhome.com/file/2023/2/92702_0s.jpg)
C#针对xml基本操作及保存配置文件应用实例
Java的MD5工具类和客户端测试类
不使用Math.random方法生成随机数(随机数生成器)
Unity3d实现无限循环滚动背景
SpringMvc返回modelandview返回的页面无法跳转问题及解决
![](https://img.aspxhome.com/file/2023/8/72358_0s.jpg)
c# WinForm制作图片编辑工具(图像拖动、缩放、旋转、抠图)
![](https://img.aspxhome.com/file/2023/7/104287_0s.png)
java寻找迷宫路径的简单实现示例
C#实现文件上传下载Excel文档示例代码
![](https://img.aspxhome.com/file/2023/1/81051_0s.jpg)
Android树形控件绘制方法
![](https://img.aspxhome.com/file/2023/3/89543_0s.jpg)
浅谈java封装
java实现在线预览--poi实现word、excel、ppt转html的方法
SpringBoot接入支付宝支付的方法步骤
![](https://img.aspxhome.com/file/2023/9/100049_0s.png)
深入讲解SPI 在 Spring 中的应用
![](https://img.aspxhome.com/file/2023/9/105909_0s.png)
IntelliJ IDEA中查看文件内所有已声明的方法(类似eclipse的outline)
![](https://img.aspxhome.com/file/2023/7/62147_0s.png)
使用纯Java实现一个WebSSH项目的示例代码
![](https://img.aspxhome.com/file/2023/8/64148_0s.png)