我使用了很多列表和数组,但我还没有遇到一个场景,数组列表不能像链表一样容易使用,如果不是更容易的话。我希望有人能给我一些例子,说明什么时候链表明显更好。
当前回答
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
数组列表适用于写一次读多次或追加程序,但不适用于从前面或中间进行添加/删除。
其他回答
Algorithm ArrayList LinkedList
seek front O(1) O(1)
seek back O(1) O(1)
seek to index O(1) O(N)
insert at front O(N) O(1)
insert at back O(1) O(1)
insert after an item O(N) O(1)
数组列表适用于写一次读多次或追加程序,但不适用于从前面或中间进行添加/删除。
嗯,我猜数组列表可以用在以下情况下:
您无法确定将会出现多少个元素 但是您需要通过索引随机访问所有元素
例如,您需要导入并访问联系人列表中的所有元素(您不知道其大小)
我做了一些基准测试,发现list类实际上比LinkedList随机插入更快:
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace ConsoleApplication1
{
class Program
{
static void Main(string[] args)
{
int count = 20000;
Random rand = new Random(12345);
Stopwatch watch = Stopwatch.StartNew();
LinkedList<int> ll = new LinkedList<int>();
ll.AddLast(0);
for (int i = 1; i < count; i++)
{
ll.AddBefore(ll.Find(rand.Next(i)),i);
}
Console.WriteLine("LinkedList/Random Add: {0}ms", watch.ElapsedMilliseconds);
watch = Stopwatch.StartNew();
List<int> list = new List<int>();
list.Add(0);
for (int i = 1; i < count; i++)
{
list.Insert(list.IndexOf(rand.Next(i)), i);
}
Console.WriteLine("List/Random Add: {0}ms", watch.ElapsedMilliseconds);
Console.ReadLine();
}
}
}
链表需要900毫秒,列表类需要100毫秒。
它创建后续整数的列表。每个新的整数被插入到一个已经在列表中的随机数之后。 也许List类使用了比数组更好的东西。
如果您需要在中间插入项,并且不想开始调整数组大小和移动内容,则列表的优势就会显现出来。
你是对的,通常情况下并非如此。我遇到过一些非常具体的案例,但不是很多。
使用链表对数组和多项式操作进行基数排序。