数组

数组是连续的地址空间，2倍2倍地扩容，空间上不够灵活，容易造成空间浪费。但是给定索引查找效率比较高，最大时间复杂度是O(1)。如果不知道索引，则需要在地址空间上顺序查找，最大时间复杂度是O(n)。python中的数组底层是用c可变长数组实现的。插入、删除也是O(n)。

list的增长方式为：0、4、8、16、25、35、46、58、72、88，….

链表

链表在地址空间上可以以不连续，比较灵活，链表每个结点保存了数据和下一个结点的内存地址，能够键数据分散到内存各处，高效地使用内存空间。

  • 读取：O(n)
  • 查找：O(n）
  • 插入：O(n)(不同位置插入效率不一样）
  • 删除：O(n)

补充理解材料

高效地遍历单个列表并删除其中多个元素，是链表的亮点之一。

假设我们正在写一个整理电子邮件地址的应用，它会删掉列表中无效格式的地址。具体算法是，每次读取一个地址，然后用正则表达式（一种用于识别数据格式的特定模式）来校验其有效性。如果发现该地址无效，就将它从列表中移除。不管这个列表是数组还是链表，要检查每个元素的话，都得花N步。

然而，当要删除邮件地址时，它们的效率却不同，下面我们来验证一下。用数组的话，每次删除邮件地址，我们就要另外再花 O(N)步去左移后面的数据，以填补删除所产生的空隙。而且还必须完成这些平移才能执行下一次邮件地址的检查。所以如果存在需要删除的无效地址，那么除了遍历邮件地址的 N步，还得加上 N步乘以无效地址数。假设每10个地址就有1个是无效的。如果列表包含1000个地址，那么无效的就应该会有100个。于是我们的算法就要花1000步来读取，再加上删除所带来的大约100000步的操作（100个无效地址×N）。

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