数组
- 概念
数组就是相同数据类型的元素按照一定顺序排列的集合 - 特点
- 查询简单，插入和删除比较复杂。
- 需要占用一块连续的内存空间。
- 优点
随机访问性强，查找速度快，时间复杂度是O(1)。因为数组的内存空间是连续的，想访问哪个元素，直接从数组的首地址向后偏移index个元素长度就可以得到。 - 缺点
- 从头部删除/插入的效率低，时间复杂度是O(n)，因为需要把对应的元素向前/向后搬移
- 空间利用率低，必须要有连续的内存空间。
- 扩容复杂。当数组的长度达到设置的阈值后，要想插入新的元素，必须进行扩容，即将旧数组中的所有元素向新数组中拷贝。
链表
- 概念
链表是一种物理存储单元上非连续、非顺序的数据结构。数据元素的逻辑顺序是通过链表中的指针连接次序实现的。链表由一系列结点构成，结点可以在运行时动态生成，每个结点包括两部分，一部分是存储数据元素的数据域，一部分是存储下一个结点地址的指针域。 - 特点
链表存储区间离散，占用内存比较宽松，故空间复杂度很小，但时间复杂度很大。 - 优点
- 任意位置插入元素和删除元素的速度快，时间复杂度为O(1)
- 内存利用率高，不会浪费内存。
- 链表的空间大小不固定，可以动态扩展。
- 缺点
随机访问效率低，时间复杂度为O(1)
总结
- 想要快速访问数据，不经常插入和删除元素的时候，选择数组
- 对于需要经常插入和删除元素，而对访问元素时的效率没有很高要求的话，选择链表。
扩展
数组的底层是ArrayList，链表的底层是HashMap
