基本数据结构

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

线性结构

线性表

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

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

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

跳表

202031284446

查找时,从上层开始查找,找到对应的区间后再到下一层继续查找,类似于二分查找

这种查找数据结构跟红黑树相比:

完美跳表:所用的存储空间和查询过程,应该和二叉树是非常像的,要求每一层都包含下一层一半的节点,且同一层指针跨越的节点数量是一样的,第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2,第 k级索引结点的个数就是 $\frac{n}{2^k}$

但随着元素不断增减,很难维护这样的完美跳表,在插入元素时可以引入随机性:通过随机函数来决定将将结点插入到哪一层索引中,来维护索引和原始链表大小的平衡,避免退化为链表的查找效率

先进后出(LIFO) 结构

使用数组实现

使用链表实现

应用:

队列

先进先出(FIFO)的线性表,只允许在表的一段进行插入,另一端删除

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

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

链表实现