1、数组与链表的区别

数组

• 存储方式

数组由于是紧凑连续存储,可以随机访问，通过索引快速找到对应元素，而且相对节约存储空间。

• 扩容方式

但正因为连续存储，内存空间必须一次性分配够，所以说数组如果要扩容，需要重新分配一块更大的空间，再把数据全部复制过去，时间复杂度O(N)。

• 插入和删除

在数组中间进行插入和删除，每次必须搬移后面的所有数据以保持连续，时间复杂度 O(N)。

链表

• 存储方式

链表存储空间不连续，是根据每个元素存储指向前后元素位置的指针把数据连接起来。这样会消耗相对更多的储存空间，并且无法根据一个索引算出对应元素的地址，不能进行随机访问。

• 扩容方式

链表因为元素不连续，而是靠指针指向下一个元素的位置，所以不存在数组的扩容问题；

• 插入和删除

如果知道某一元素的前驱