基本数据结构

数据结构的使用要根据场景及数据量来决定

线性结构

线性表

n个数据元素的有限序列。可以看做数组

• Java的ArrayList
• C++的vector

使用三个变量来描述线性表的使用

扩容的设计：当插入新元素后发现预留容量不够了，就需要申请一块新的内存，并将现有的数据复制过去，每次扩容的大小为原来的2倍是比较合适的

当删除了大量的元素，可以进行缩容，ArrayList并没有实现自动缩容，而是提供了一个trimToSize() 的方法可以让使用者手动缩容，自动很难把控，缩容的时机和容量很难确定，取决于业务

如果在存储空间占比低于一半的时候就缩容，会导致反复插入删除，一种较好的实现是当实际使用量为总容量的1/4时，缩为原来的一半

使用场景：需要经常查询、变更，但是很少插入 / 删除

链表

单向链表

stateDiagram-v2
  direction LR
  a --> b
  b --> c

双向链表，可以双向遍历链表，拥有了在遍历中回退的能力

stateDiagram-v2
  direction LR
  a --> b
  b --> a
  b --> c
  c --> b

循环链表

stateDiagram-v2
  direction LR
  a --> b
  b --> c
  c --> a

哑结点：用于标记这整个循环链表的首尾连接处，既是整个链表的开始，也是整个链表的结尾

链表，相比于数组，有更好的灵活性和更低的插入、删除的复杂度，更加适用于查询索引较少、遍历、插入、删除操作较多的场景

栈

先进后出（LIFO） 结构

应用：

• 函数调用栈
• 表达式求值
• 括号匹配

队列

先进先出（FIFO）的线性表，只允许在表的一段进行插入，另一端删除

循环队列：基于数组或链表实现的队列数据结构，与普通队列不同之处在于，当队列尾部指针（rear）指向数组的最后一个位置时，如果再有元素入队，将循环回到数组的第一个位置

双端队列：两端都支持 FIFO 插入删除操作的队列，工作窃取算法就是当本进程消费的队列数据完成时，从其他工作队列的尾部去窃取数据来进行消费，从尾部取数据可以有效避免竞争

链表实现

树结构

有层次的非线性结构

图结构

哈希结构