快捷搜索:

LinkedList 和 List 在三种简单算法中效率比较

.Net 框架供给了两种List类型,一种是基于链表的LinkedList, 一种是基于数组的List。那么在实际利用中到底采纳哪种List,若何取舍呢?本文对两种类型在行列步队,客栈和简单插入三种简单算法中的效率进行了一个对照。

起起首让我们来看一下List的初始容量Capacity对List的机能是否有影响。

测试措施:分手设置初始容量为0,64,255,1024. List插入的最大年夜长度为1000,轮回1000次,获得如下结果,单位为ms,下同。

算法/初始容量

0

64

255

1024

行列步队

35837

35753

37171

35711

客栈

302

279

298

289

简单插入

100

105

100

100

从上面数据中我们可以看出List的初始容量对效率没有显着影响。

行列步队算法对照

测试措施:对LinkedList和List采纳先辈先出的行列步队算法,分手设置行列步队最大年夜长度为10,30,50,100,1000,10000,并轮回1000次,获得如下结果。

List类型/行列步队最大年夜长度

10

30

50

100

1000

10000

LinkedList

0.7659

0.8768

1.1041

2.0401

61

691

List

0.3326

1.1677

1.9985

12

443

37516

从测试结果中我们可以看出LinkedList 跟着最大年夜行列步队长度的增添,所用光阴基础成线性增长。而List则成指数增长。我阐发主要缘故原由应该是每次删除List的数组头时,List都要做一次全部数数组的拷贝,而链表类型则不存在这个问题。有趣的是当行列步队长度小于30时,List的效率要比LinkedList要高,这主如果由于链表在增删元素时必要额外创建链表指针,而数组不必要这个操作。在行列步队长度较小时,这种开销就会显得很显着。

客栈算法对照

测试措施:对LinkedList和List采纳先辈后出的客栈算法,分手设置行列步队最大年夜长度为10,30,50,100,1000,10000,并轮回1000次,获得如下结果。

List类型/客栈最大年夜长度

10

30

50

100

1000

10000

LinkedList

0.8515

0.9295

1.1123

2.1874

58

714

List

0.1109

0.3104

0.5118

1.2256

29

284

从测试结果看两种类型都是线性增长,但List的机能更高一些。我阐发这主如果由于List类型在增长到最大年夜值后在从尾部删除元素,其并不从新分配内存,除非你强行让它压缩。以是List从尾部删除只是将Count改变了一下,是以效率很高。而链表类型的效率和行列步队要领基真相当,这也是在预感之中的,其效率比List低的缘故原由主要照样在增删时创建和删除节点的额外开销。

简单插入算法对照

测试措施:对LinkedList和List采纳向后追加多少元素的算法,分手设置插入最大年夜长度为10,30,50,100,1000,10000,并轮回1000次,获得如下结果。

List类型/插入最大年夜长度

10

30

50

100

1000

10000

LinkedList

0.6778

0.765

0.938

1.7783

40

535

List

0.0864

0.1661

0.2509

0.4312

10

109

其测试结果和客栈算法基础类似,且List的效率更高,这里不再重复叙述。

总结

假如采纳行列步队算法建议采纳LinkedList类型,除非行列步队长度小于30.

假如采纳客栈或简单插入算法,建议采纳List类型。但有一点必要阐明,假如利用对内存占用有限定,建议采纳LinkedList类型。

测试代码

class Program

{

const int TEST_TIMES = 1000;

static private void TestQueue(int count)

{

TestQueue(count, 0);

}

static private void TestQueue(int count, int capacity)

{

Console.WriteLine("Count:" + count.ToString());

LinkedList linkList = new LinkedList();

List list = new List(capacity);

Stopwatch watch = new Stopwatch();

watch.Start();

for (int i = 0; ilinkList = new LinkedList();

List list = new List(capacity);

Stopwatch watch = new Stopwatch();

watch.Start();

for (int i = 0; ilinkList = new LinkedList();

List list = new List(capacity);

Stopwatch watch = new Stopwatch();

watch.Start();

for (int i = 0; i

您可能还会对下面的文章感兴趣: