在 C# 中，List
1. 基本概念
- List
- 基于动态数组实现。
- 元素在内存中是连续存储的。
- 支持通过索引快速访问元素。
- LinkedList
- 基于双向链表实现。
- 每个元素（节点）存储数据和指向前后节点的引用。
- 不支持通过索引访问元素。
2. 操作性能比较
操作 | List | LinkedList |
随机访问 | O(1): 通过索引快速访问。 | O(n): 需从头遍历到指定位置。 |
插入（中间/开头） | O(n): 需要移动元素。 | O(1): 更新指针即可。 |
插入（末尾） | O(1)（若容量足够）。 | O(1): 直接添加新节点。 |
删除（中间/开头） | O(n): 需要移动元素。 | O(1): 更新指针即可。 |
删除（末尾） | O(1): 若不需缩容。 | O(1): 更新指针即可。 |
遍历 | O(n): 顺序访问。 | O(n): 顺序访问。 |
3. 内存使用
- List
- 内存分配是连续的，适合存储大小固定的对象。
- 如果需要扩容，会分配新的更大数组，并复制原有数据。
- LinkedList
- 每个节点都有额外的内存开销（存储前后节点的引用）。
- 不需要连续内存，但由于节点间的指针，内存使用效率低于 List
。
4. 适用场景
场景 | 选择 |
频繁的随机访问 | List：索引访问性能极高，适合数组替代方案。 |
数据量动态变化且插入/删除频繁 | LinkedList：插入、删除性能优于 List |
内存占用敏感的应用 | List：连续内存使用较少额外开销。 |
需要双向遍历或特殊节点操作 | LinkedList：提供对前后节点的直接引用。 |
固定大小的集合，操作较少 | List：简单高效。 |
5. 示例代码
List 示例
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
List list = new List { 1, 2, 3, 4, 5 };
// 索引访问
Console.WriteLine(list[2]); // 输出: 3
// 插入和删除
list.Insert(2, 10);
list.RemoveAt(3);
// 遍历
foreach (var item in list)
{
Console.WriteLine(item);
}
}
}
LinkedList 示例
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
LinkedList linkedList = new LinkedList();
// 添加元素
linkedList.AddLast(1);
linkedList.AddLast(2);
linkedList.AddFirst(0);
// 插入元素
var node = linkedList.Find(1);
linkedList.AddAfter(node, 5);
// 遍历
foreach (var item in linkedList)
{
Console.WriteLine(item);
}
}
}
6. 总结
- 选择 List
： - 数据量较大但修改较少。
- 需要频繁通过索引访问元素。
- 内存紧张或对额外开销敏感。
- 选择 LinkedList
： - 数据量不大但修改频繁。
- 不确定元素的插入或删除位置。
- 需要灵活地在任意位置操作节点。
