C#中LinkedList< T >的快速上手
1. 基础
1.1 介绍
- 命名空间:位于 System.Collections.Generic 命名空间中。
- LinkedList< T> 是 C# 中的一个泛型集合,这个集合实现了一个双向链表;
- 集合的每个元素都是一个链表节点(LinkedListNode< T> 类型);
- 每个 LinkedListNode< T> 对象包含三个关键部分:
- Value:存储实际的数据(泛型类型 T)。
- Next:指向链表中下一个 LinkedListNode< T> 的引用。
- Previous:指向链表中上一个 LinkedListNode< T> 的引用。
LinkedList< T> 提供了在序列中快速添加和删除元素的功能,特别是在表头和表尾。
1.2 常用属性
Count:获取链表中的节点数。
First:获取链表的第一个节点(LinkedListNode< T> 类型)。
Last:获取链表的最后一个节点(LinkedListNode< T> 类型)。
1.3 常用方法
AddAfter(LinkedListNode, T):在指定节点之后添加一个新节点。
AddBefore(LinkedListNode, T):在指定节点之前添加一个新节点。
AddFirst(T):在链表的开头添加一个新节点。
AddLast(T):在链表的末尾添加一个新节点。
Clear():移除链表中的所有节点。
Contains(T):判断链表是否包含特定值。
Remove(T):移除链表中的第一个匹配项。
RemoveFirst():移除链表的第一个节点。
RemoveLast():移除链表的最后一个节点。
2 实例及时间复杂度分析
2.1 实例
LinkedList<string> linkedList = new LinkedList<string>();
// 增加:在链表尾部添加新元素
linkedList.AddLast("Item 1");
linkedList.AddLast("Item 2");
Console.WriteLine($"当前元素个数{
linkedList.Count}");
// 增加:在链表头部添加新元素
linkedList.AddFirst("Item 0");
Console.WriteLine($"当前元素个数{
linkedList.Count}");
// 查找:查找链表中是否存在某个元素
Console.WriteLine("Contains 'Item 1': " + linkedList.Contains("Item 1"));
// 修改:首先找到元素,然后修改其 Value
var node = linkedList.Find("Item 1");
if (node != null)
{
node.Value = "Item 1 Updated";
Console.WriteLine("Updated 'Item 1' to 'Item 1 Updated'");
}
// 删除:移除特定元素
linkedList.Remove("Item 2");
Console.WriteLine("Removed 'Item 2'");
// 删除:移除第一个和最后一个元素
linkedList.RemoveFirst();
linkedList.RemoveLast();
Console.WriteLine("Removed first and last items");
// 遍历链表
Console.WriteLine("Current LinkedList:");
foreach (var item in linkedList)
{
Console.WriteLine(item);
}
2.2 时间复杂度分析
增加元素:
- AddLast 和 AddFirst 方法分别在链表的尾部和头部添加新元素。这些操作的时间复杂度是 O(1),因为它们只涉及到更新几个节点的引用。
查找
- Contains 方法和 Find 方法用于查找元素。这些操作的时间复杂度是 O(n),因为最坏情况下可能需要遍历整个链表。
修改
- 首先使用 Find 方法找到节点(时间复杂度 O(n)),然后更新其 Value 属性。修改节点值的操作是 O(1)。
删除
- Remove 方法根据值移除元素。它首先需要找到元素(时间复杂度 O(n)),然后更新相邻节点的引用来移除它(时间复杂度 O(1))。
- RemoveFirst 和 RemoveLast 分别移除链表的第一个和最后一个元素。这些操作的时间复杂度是 O(1),因为只需要改变几个引用。
3 总结
LinkedList< T> 的许多操作都具有较低的时间复杂度,特别是那些涉及到链表头部和尾部的操作;
然而,查找和删除特定值的操作可能涉及到遍历整个链表,这使得它们的时间复杂度增加到 O(n)。