前几天面试时被问到“数组和链表之间的差别”，自己一时紧张，回答的不是很好，于是重新复习了 一下相关的知识点，现在记录下来。

数组和链表之间，一个差别是数组是固定长度的，而链表的长度是不固定的。因此，如果数据长度是 固定的，那么我们可以使用数组来进行存储。如果数据长度不固定，我们则可以使用链表。

两者之间另一个差别是，对数据访问的差别。如下表所示：

查找 插入 删除
数组 O(1) O(n) O(n)
链表 O(n) O(1) O(1)

因为数组是可以用下标访问元素的，所以在知道下标情况下它的查找效率为 O(1)；又因为数组中每个元素相邻 存放的，对于插入和删除操作都需要成片地移动数组中元素，所以这两个操作的时间复杂度为 O(n)。

链表中，每个元素用指针进行连接，存放在内存中不连续的空间中。要查找链表中的一个元素，只能遍历整个 链表，所以链表的查找效率为 O(n)；对于插入和删除操作，链表只需要修改对应位置的指针即可，所以时间 复杂度为 O(1)。

因此，在进行程序设计时，如果需要查找效率高些，而且不经常进行插入和删除操作，那么可以选择数组进行 数据存储。如果需要频繁的进行插入和删除操作，那么可以选择链表进行数据存储。

以上。