数组和链表

假设我们要制作一个管理待办事项的应用，需要在计算机的内存中存储一系列的待办事项。这时候，该应用数组还是链表呢？

数组

鉴于数组比较容易理解，我们先将待办事项存储于数组中。使用数组就意味着所有的待办事项在内存中的存储都是紧密相连的。

假设我们要存储 4 个待办事项。在存储完前三个事项后，紧密相连的内存没有了（被其他事物占用），此时就无法存储第四个待办事项。在这种情况下，需要请求计算器重新分配一块可以容纳 4 个待办事项的内存，再将所有待办事项都移到那里。就像和朋友一起出去吃饭，找到地方坐下后，又来了一位朋友，但原来的地方没有空余的位置，只得继续再找一个能容下当前人数的地方。

但是如果又来了一位朋友呢？就得继续转移到足够容纳人数的地方。这样随之带来的成本就是添加新元素的速度会很慢。这就是数组的弊端。

链表

可以用链表来解决以上数组的弊端。链表中的任何元素可以存储在计算机内存中的任何地方。然后链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串联了起来。在链表中添加元素很方便：只需要将其放入内存，并将其地址存储到前一个元素中既可。

链表的优势体现在添加新元素方面，我们看看其他方面数组和链表会有怎样的优势与劣势。

读取

如果要读取链表的最后一个元素的话，不能直接访问最后一个元素，因为并不知道它的地址，而是要从第一个元素开始，按顺序访问下去，直到访问到最后一个元素。这种随机的跳跃式的访问，对链表来说，是低效的。但是要访问所有元素的话，链表的效率很高：读取第一个元素，然后根据其中的地址读取第二个元素，以此类推。

而数组则简单多了，因为它各个元素彼此间的地址是相连的，知道其中某一地址，很快就能猜出其他元素的地址。比如一个数组中有 5 个元素，起始的地址是 00 ，那么很容易知道第五个元素的地址为 04。

删除

如果要删除元素的话，这时候选择谁会更好？答案是链表，因为只需要修改前一个元素指向的地址即可。而使用数组的话，删除一个元素后，后面的元素都必须往前移。

总结

用大 O 表示法来总结一下数组和链表各种情况的运行时间：

O(1) : 常量时间 ， O(n) ：线性时间

数组和链表相比，数组用的比较多，因为很多情况需要支持随机访问，而链表仅支持顺序访问。