数组和链表的比较

数组

• 概念
  数组就是相同数据类型的元素按照一定顺序排列的集合
• 特点

1. 查询简单，插入和删除比较复杂。
2. 需要占用一块连续的内存空间。

• 优点
  随机访问性强，查找速度快，时间复杂度是O(1)。因为数组的内存空间是连续的，想访问哪个元素，直接从数组的首地址向后偏移index个元素长度就可以得到。
• 缺点

1. 从头部删除/插入的效率低，时间复杂度是O(n)，因为需要把对应的元素向前/向后搬移
2. 空间利用率低，必须要有连续的内存空间。
3. 扩容复杂。当数组的长度达到设置的阈值后，要想插入新的元素，必须进行扩容，即将旧数组中的所有元素向新数组中拷贝。

链表

• 概念
  链表是一种物理存储单元上非连续、非顺序的数据结构。数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表由一系列结点构成，结点可以在运行时动态生成，每个结点包括两部分，一部分是存储数据元素的数据域，一部分是存储下一个结点地址的指针域。
• 特点
  链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大。
• 优点

1. 任意位置插入元素和删除元素的速度快，时间复杂度为O(1)
2. 内存利用率高，不会浪费内存。
3. 链表的空间大小不固定，可以动态扩展。

• 缺点
  随机访问效率低，时间复杂度为O(1)

总结

1. 想要快速访问数据，不经常插入和删除元素的时候，选择数组
2. 对于需要经常插入和删除元素，而对访问元素时的效率没有很高要求的话，选择链表。

扩展

数组的底层是ArrayList，链表的底层是HashMap