基本数据结构

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

线性结构

线性表

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

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

202277152020

扩容的设计:当插入新元素后发现预留容量不够了,就需要申请一块新的内存,并将现有的数据复制过去,每次扩容的大小为原来的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 插入删除操作的队列,工作窃取算法就是当本进程消费的队列数据完成时,从其他工作队列的尾部去窃取数据来进行消费,从尾部取数据可以有效避免竞争

链表实现

树结构

有层次的非线性结构

图结构

哈希结构