数组，链表

数组：

所有元素都连续的存储于一段内存中，且每个元素占用的内存大小相同。这使得数组具备了通过下标快速访问数据的能力。
但连续存储的缺点也很明显，增加容量，增删元素的成本很高，时间复杂度均为 O(n)。增加数组容量需要先申请一块新的内存，然后复制原有的元素。如果需要的话，可能还要删除原先的内存。删除元素时，需要移动被删除元素之后的所有元素。

  • 优点：可以根据偏移实现快速的随机读写。
  • 缺点：扩容，增删元素极慢。

参考链接