关于数组
有限个相同类型的变量所组成的有序集合
数组在内存中顺序存储
读取元素：给出数组下标，就可以读取到对应的数组元素，时间复杂度O(1)
更新元素：利用数组下标，直接将新值赋给该元素，时间复杂度O(1)
插入元素：尾部插入，中间插入(需要找到位置后将数据后移)，超范围插入(数据超出时需要进行扩容)，时间复杂度O(n)
删除元素： 找到需要删除的位置，将后面的数据前移，时间复杂度O(n)
数组适合随机访问，读取与更新方便，写入有删除复杂，适合读多写少的场景
关于链表
内存中随机存储
查询元素：逐个搜索后读取，时间复杂度O(n)
插入元素： 头部插入、尾部插入、中间插入
删除元素：头部删除、尾部删除、中间删除
栈
时间复杂度O(1)
逻辑结构上，线性结构有：顺序表、栈、队列，非线性结构有：树、图 物理结构上，顺序存储有：数组，链式存储有：链表
队列
用数组实现的队列可采用循环队列的方式来保持队列的容量 队尾的指针指向队首，元素放入队首 直到（队尾下标+1）%数组长度 = 队头下标 时，代表此队列真的已经满了 队列的容量=实际-1，有一个需要存放指针
循环队列不但充分利用了数组的空间，还避免了数组元素整体移动的麻烦，时间复杂度O(1)
栈与队列的使用场景
栈的输入与输出相反，可用于实现递归，面包屑导航
队列：公平锁竞争的线程等待队列，抓包的URL的跳转
其他队列
双端队列：综合的栈和队列的优点，头尾都可以先入先出
优先队列：基于优先级入与出，基于二叉堆实现
散列
key-value，根据key找value的时间复杂度O(1)
散列本质上是一个数组
散列表可以使数组与链表的结合
哈希函数：通过某种方式，把Key和数组下标进行转换。这个中转站就叫作哈希函数
hashMap通过key的hash值取模运算，即可得出数组的index值，实现了从key -> 数组下标 -> value的过程
解决哈希冲突的方法有：开放寻址法、链表法 ThreadLocal所使用的就是开放寻址法 链表法Java的集合类HashMap
扩容 新建一个数组，长度是原来的2倍，将原数组的内容重新挨个insert到新数组（新数组的hash值变化了）
什么是数组 数组是由有限个相同类型的变量所组成的有序集合，它的物理存储方式 是顺序存储，访问方式是随机访问。利用下标查找数组元素的时间复杂 度是O(1)，中间插入、删除数组元素的时间复杂度是O(n)。
什么是链表 链表是一种链式数据结构，由若干节点组成，每个节点包含指向下一节 点的指针。链表的物理存储方式是随机存储，访问方式是顺序访问。查 找链表节点的时间复杂度是O(n)，中间插入、删除节点的时间复杂度是 O(1)。
什么是栈 栈是一种线性逻辑结构，可以用数组实现，也可以用链表实现。栈包含 入栈和出栈操作，遵循先入后出的原则（FILO）。
什么是队列 队列也是一种线性逻辑结构，可以用数组实现，也可以用链表实现。队 列包含入队和出队操作，遵循先入先出的原则（FIFO）。
什么是散列表 散列表也叫哈希表，是存储Key-Value映射的集合。对于某一个Key，散 列表可以在接近O(1)的时间内进行读写操作。散列表通过哈希函数实现 Key和数组下标的转换，通过开放寻址法和链表法来解决哈希冲突。
树
二叉树
根节点、叶子节点、父节点、子节点 左孩子、右孩子 满二叉树、完全二叉树（最后一个节点之前的都是满的即可）
树属于逻辑结构，所以在物理实现上，可以使用数组，可以使用链表
