《数据结构》的魅力：关于Array和List的使用
写这个是因为如鹏网的学员求助，事情是这样的，他去负责公司的一个培训模块，在培训模
块中，有一个功能是自动成卷。然后，我们会很容易地想到洗牌算法。于是我给他大概解释
了洗牌算法的过程和步骤，然后他给出了这样的代码，还很骄傲地告诉我，他使用了泛型……
杨中科老师点评：这个知识点是很多企业面试、笔试的时候会问的问题，需要格外注意，无
论是C#、Java、C++还是其他语言都会有同样的问题，因为“数据结构不分语言”。
1.Listlist=newList();
2.for(inti=0;i<10;i++)
3.{
4.list.Add(i);
5.}
6.Randomr=newRandom();
7.for(intj=0;j<100;j++)
8.{
9.inttemp;
10.intx1=r.Next(10);
11.intx2=r.Next(10);
12.temp=list[x1];
13.list[x1]=list[x2];
14.list[x2]=temp;
15.}
16.
复制代码
我委婉地告诉他，他这个方法不好，然后写下了下面的代码：
1.int[]array=newint[10];
2.for(inti=0;i<10;i++)
3.{
4.array[i]=i;
5.}
6.Randomr=newRandom();
7.for(intj=0;j<100;j++)
8.{
9.inttemp;
10.intx1=r.Next(10);
11.intx2=r.Next(10);
12.temp=array[x1];
13.array[x1]=array[x2];
14.array[x2]=temp;
15.}
16.
复制代码
他很不屑地对我说，不是都一样么！而且还在以使用了泛型为豪！我无语……
我仅仅把List(链表)换成了Array(数组)，有人会说，这样的关系大么？
让我们先来简单地回顾一下基础知识。
Array和List都属于顺序表。
Array是一段连续的存储结构，如int[]i=newint[3]，i其实记录的是数组的首地址，而i[1]
其实相当于在i的地址的基础上加上1个整数的地址偏移，然后再取这块地址中的值。也就
是相当于(&i[0]+4);
而List则是不连续的存储结构，List的每个节点都有着一个Next属性，这个属性则记录着
他的下一个节点的地址。也就是说当我们想找第100个节点的时候，他还是需要从第一个
节点，然后做99次Next操作，才能找到list[99]节点。这是个蛮痛苦的过程。
很多人会说，那无论是List还是Array，不都是一个索引么！让我们来请出IL:
先来看Array查找某个元素的IL:
IL_0020:ldloc.0
IL_0021:ldc.i4.3
IL_0022:ldelem.i4
IL_0023:stloc.2
然后让我们来看下List查找某个元素的IL:
IL_0022:ldloc.0
IL_0023:ldc.i4.3
IL_0024:callvirtinstance!0class
[mscorlib]System.Collections.Generic.List`1::get_Item(int32)
IL_0029:stloc.2
我们可以发现，虽然他们的写法是一样的，但是在IL中却有着很大的差别。
通过这两段IL，我只是希望证明List和Array对索引元素的方式是不同的。当然，我们无从
知道Microsoft对List方法get_Item的实现。但是我们不难想象：
因为List是一个链表，所以我需要从第一个元素开始逐个Next到所需索引的元素。这是一
个耗时的过程。
因此，在使用洗牌算法时，使用List是个很差劲的做法。再进一步说，当我们需要大量的索
引步骤时，使用List是个很差劲的做法。
那List和Array各自应该用在什么情况下呢？我来做个简单的总结：
1.从空间扩展角度上来说：
数组必须要在初始化时分配固定的大小，比如说int[]a=newint[3];如果我们仅仅写int[]
a=newint[];编译器就会无情地给我们报错。但是List由于空间不必连续，所以无须指定初
始大小。
总结1：当不确定大小时，最好使用List代替Array。
2.从操作角度上来看：
关于索引这个就不赘述了。
总结2：当需要大量的查找操作时，最好使用Array。
对于插入（删除）操作，很多人是从插入（删除）的时间上分析，说List优于Array，我觉
得是不合理的。
更合理的解释应该是从两个角度分析（以插入为例）：
<1>指定位置插入指定元素：
对于Array讲，有两套解决方案：
A.使用一个新数组，N+1个元素重新赋值的过程。一个for循环，时间复杂度O(n)。
B.在原数组上操作，那么首先需要为该数组预留空间，这是个很难办的事情。而且其后续
元素的移动耗费时间复杂度仍未O(n)。
对于List来讲，很多人说复杂度就是O(1)。这其实是不合理的，因为List插入元素固然容
易，但是在指定位置的插入，需要一个时间复杂度为O(n)的查找过程。
但是只考虑时间复杂度是不够的，我们要考虑总体的情况。如果使用新数组，不仅浪费了新
的空间，而且需要反复的赋值过程，是N+1次。如果不使用新数组，预留空间实在太麻烦，
因此综上所述，还是List好。
（补充下：很多同事和朋友都问我，说为什么要学那么多的排序和搜索算法，排序学个快速
排序，搜索学个二分搜索，这样就够了呗！但是我想说的是，所说的最快，不过是他们的平
均（或最坏）情况下的时间复杂度，并不能代表通用的情况，我们在实际工作中，还是要根
据实际情况去选择最适用的算法，这就是我们学习很多算法的目的）
<2>给出前一个节点，然后在后面插入元素。这个我的意思就是不仅仅给出了
PreviousNode的Value，还给出了他的Next。这个情况我就不废话了，List的优势太大了。
可是在实际情况中，这种情况的可能性几乎为零。
因此，总结3：当需要进行频繁的插入，删除操作时，最好使用List代替Array。
另外，给出个不太重要的补充，由于List需要存储他下一个节点的地址，所以List比Array
相对起来浪费了更多的空间。
这次关于List和Array的用法区别就先写到这。希望大家有什么不同意见的多多指教！
|
|
