数组和链表的特性以及优缺点

数组：连续存储空间，便于随机访问，通过索引可以快速找到对应元素，而且相对可以节约存储空间，但是正是因为连续存储，所以内存必须一次性分配够，所以如果数组想要扩容，就必须重新申请一块新的内存空间，然后将现有的数据全部复制过去，时间复杂度为 O(n) ；而且如果你想在中间插入或者删除元素的话，每一次都需要搬动后面的元素，所以时间复杂度都为 O(n)。

链表：元素不连续，通过指针访问下一个元素，所以不存在数组的扩容问题，如果知道某一元素的前驱和后继指针，操作指针就可以删除当前元素，时间复杂度 O(1) 。但是因为存储空间不连续，无法根据索引计算出元素的地址，导致无法随机访问某一元素。而且因为需要储存节点的前驱和后继指针，会消耗更多的储存空间。