数据结构

参考链接：https://zhuanlan.zhihu.com/p/164868036

1. 数组

数组是最常用的数据结构，数组占用一段连续的内存空间，且存储相同的数据类型。开辟空间时知道数组的起始地址，根据数据类型占用的空间大小，可以计算出某个数组下标的具体位置。所以通过数组下标可快速访问获取数据，查询数据的时间复杂度为O(1)。

2. 链表

链表可以通过零散的内存空间来存储数据。链表中的数据在内存中不连续，所以链表中数据元素都必须存储下一个元素的内存地址指针。链表的元素包含两部分内容，一部分是数据，一部分是下一个元素的地址指针。最后一个元素指向null，表示链表到此结束。所以在查询数据时，只能遍历链表，时间复杂度为O(N)。
数组和链表是线性表，每个数据元素只能有一个前驱元素，一个后继元素。可以随机访问，可以在中间添加元素/删除元素。

3. Hash表

Hash表中数据以Key、Value的方式存储。

• 数组（余数法）：计算Key的hashcode（int值），对数组长度进行取模运算，得到的余数为数组下标。

• 链表（拉链法）：当不同Key的hashcode相同，或者不同的hashcode对数组长度取模运算，得到的数组下标相同，这就产生了hash冲突。所以数组中存储了链表，将产生hash冲突的两个键值存储在链表中。

4. 栈

对数据访问增加操作限制，产生了栈和队列。
先进后出。
使用栈来管理每个方法的工作区，不管方法怎么嵌套调用，栈顶元素始终是当前正在执行方法的工作区。

5. 队列

队列也是一种操作受限的线性表，先进先出。
在软件运行期，可采用队列处理资源不足的问题，如：提交任务请求线程池执行，此时线程已经用完了，任务需要存放到队列中，先进先出排队执行。在核心线程数量最大时，新进的任务存放在阻塞队列中，等待线程领取执行任务。

6. 树