一、数组（Array）

        数组是计算机科学中最基本的数据结构之一。使用数组意味着所有元素在内存中都是相连的（紧靠在一起的）。

array = ["aaa", "bbb", "ccc", "ddd", "eee"]

        这就是一个数组，它刚好包含5个字符串。

二、链表（Linked List）

        像数组一样，链表也用来表示一系列的元素。事实上，能用数组来做的事情，一般也可以用链表来做。然而，链表的实现跟数组是不一样的，在不同场景它们会有不同的性能表现。

        链表中的元素可存储在内存的任何地方。链表的每个元素都存储了下一个元素的地址，从而使一系列随机的内存地址串在一起。

三、对比

1、读取

        需要随机地读取元素时，数组的效率很高，因为可迅速找到数组的任何元素。

        从数组中读取一个值时，其效率为O(1)。

        由于大O记法默认采用最坏情况，所以说读取链表的时间复杂度为O(N)。

2、查找

        链表的查找效率跟数组一样。均为O(N)。

3、插入

        在某些情况下，链表的插入跟数组相比，有着明显的优势。回想插入数组的最坏情况：当插入位置为索引0时，因为需要先将插入位置右侧的数据都右移一格，所以会导致 O(N)的时间复杂度。然而，若是往链表的表头进行插入，则只需一步，即O(1)。

        链表的最坏情况和最好情况与数组刚好相反。在链表开头插入很方便，在数组开头插入却很麻烦；在数组的末尾插入是最好情况，在链表的末尾插入却是最坏情况。

4、删除

        从效率上来看，删除跟插入是相似的。

5、总结

         尽管两者的查找、插入、删除的效率看起来差不多，但在读取方面，数组比链表要快得多。既然如此，那为什么还要用链表呢？

        因为高效地遍历单个列表并删除其中多个元素，是链表的最重要的特点。

        假设我们正在写一个整理客户邮寄地址的应用，它会删掉列表中无效格式的地址。具体算法是，每次读取一个地址，然后用正则表达式（一种用于识别数据格式的特定模式）来校验其有效性。如果发现该地址无效，就将它从列表中移除。

        不管这个列表是数组还是链表，要检查每个元素的话，都得花N步。然而，当要删除邮寄地址时，它们的效率却不同，下面我们来验证一下。用数组的话，每次删除邮件地址，我们就要另外再花 O(N)步去左移后面的数据，以填补删除所产生的空隙。而且还必须完成这些平移才能执行下一次邮寄地址的检查。

        所以如果存在需要删除的无效地址，那么除了遍历邮寄地址的 N步，还得加上 N步乘以无效地址数。假设每10个地址就有1个是无效的。如果列表包含1000个地址，那么无效的就应该会有100个。于是我们的算法就要花1000步来读取，再加上删除所带来的大约100000步的操作（100个无效地址×N）。

        但要是链表的话，每次删除只需1步就好，因为只需改动结点中链的指向，然后就可以继续检查下一邮寄地址了。按这种算法去处理1000个邮寄地址，只需要1100步（1000步读取和100步删除）。