数组
数组是一种线性表数据结构，通过一组连续的内存空间，来存储一组具有相同类型的数据。
1、线性表：
数据排成线性的结构，只有前后两个方向。数组、链表、队列和栈都是线性表。
2、随机访问：
数组通过计算在连续内存空间中的内存地址，来实现随机访问，时间复杂度为O(1)。
a[i]_address = base_address + i * data_type_size
数组的查找操作，时间复杂度为O(logn)
当 i=0时，表示内存地址的偏移量为 0，即数组的第一个元素 a[0]
3、插入
- 当需要在数组的第 K 个位置插入元素时，数组需要将 K 之后的所有元素都往后挪一位，因此时间复杂度为 O(n)。最好的时间复杂度为 O(1)，当插入数组末尾时发生。
-
如果数组中的数据不需要保持顺序，那么可以将第 K 个位置的元素放到末尾，然后空出位置给新元素，这样的时间复杂度就是 O(1)
4、删除
- 删除第 K 个位置的元素，和插入一样需要搬移元素，因此时间复杂度为 O(n)。最好的时间复杂度为 O(1)
- 可以将多次删除操作合并在一起执行，先标记等空间满了之后再删除，这样可以减少搬移元素的次数
链表
链表分为单链表，双向链表、循环链表、双向循环链表
链表不需要连续的内存空间，他通过指针将一组零散的内存块串联起来使用
1、单链表
插入和删除的时间复杂度为 O（1）
查找的时间复杂度为 O（n）
2、循环链表
循环链表就是首位相连的单向链表，末尾节点的指针指向头结点
3、双向链表
- 双向链表的每个节点不仅有next 指针，还有 prev 指针，所以支持双向遍历，增加了链表的灵活性
1）删除操作
- 删除某个给定值的节点：时间复杂度为 O（n），需要依次遍历
- 删除给定指针指向的节点：删除该节点需要知道其前驱节点，双向链表可以通过 prev 指针获取，时间复杂度为 O（1）
2）插入同理
3）查找操作：对于一个有序链表，可以记录上一次查找的位置 P，然后下次查找不用全部遍历，只需要遍历一半节点就可以
4、用链表实现 LRU （Least Recently Used）缓存淘汰算法
- 通过有序单链表来实现，将最少使用的放在末尾。
- 当有新数据访问时，判断是否已存在，是的话从末尾删除插入到表头
- 否则的话直接插入到表头，若链表已满，则同时删除最末节点