基本数据结构
数据结构的使用要根据场景及数据量来决定
线性结构
线性表
n个数据元素的有限序列。可以看做数组
- Java的ArrayList
- C++的vector
使用三个变量来描述线性表的使用
扩容的设计：当插入新元素后发现预留容量不够了，就需要申请一块新的内存，并将现有的数据复制过去，每次扩容的大小为原来的2倍是比较合适的
当删除了大量的元素，可以进行缩容，ArrayList并没有实现自动缩容，而是提供了一个trimToSize() 的方法可以让使用者手动缩容，自动很难把控，缩容的时机和容量很难确定，取决于业务
如果在存储空间占比低于一半的时候就缩容，会导致反复插入删除，一种较好的实现是当实际使用量为总容量的1/4时，缩为原来的一半
使用场景：需要经常查询、变更，但是很少插入 / 删除
链表
哑结点：用于标记这整个循环链表的首尾连接处，既是整个链表的开始，也是整个链表的结尾
链表，相比于数组，有更好的灵活性和更低的插入、删除的复杂度，更加适用于查询索引较少、遍历、插入、删除操作较多的场景
栈
先进后出（LIFO） 结构
应用：
- 函数调用栈
队列
先进先出（FIFO）的线性表，只允许在表的一段进行插入，另一端删除
循环队列
双端队列：两端都支持 FIFO 插入删除操作的队列，工作窃取算法就是当本进程消费的队列数据完成时，从其他工作队列的尾部去窃取数据来进行消费，从尾部取数据可以有效避免竞争
链表实现
树结构
有层次的非线性结构