CPU L1缓存读写速度高出内存100倍左右, 缓存在加载地址的时候，基于Locality of reference也会加载相邻的地址内容。(如果一个地址被访问，那么它相邻的地址也极有可能之后被访问)
数组
-----------------
| 1 | 2 | 3 | 4 |
-----------------
数组使用连续的内存来存储同类型的数据, 需要指定大小, 由于数组内各个元素类型一致, 很容易计算每个元素的偏移量。
数组的一个最大特点是支持随机访问/下标访问, 缓存友好型数据结构, 访问速度很快。
动态数组
-----------------
| 1 | 2 | 3 | 4 | 添加5
-----------------
| | | | |
v v v v v
---------------------------------
| 1 | 2 | 3 | 4 | 5 | | | | 开辟新空间
---------------------------------
为了克服数组的固定大小的缺点，好多语言提供动态数组，可以根据指定或实际情况动态扩容。例如C++中的vector, Java中的ArrayList
扩容的时候需要开辟新的空间，然后把旧的数组拷贝到新的数组中。扩容可以采用倍增的策略。
扩容比较耗费资源，计算机采用均摊复杂度(Amortized Analysis)来衡量其时间复杂度, 记作O*(N)
二维数组
A = [
[11, 12, 13, 14],
[21, 22, 23, 24],
[31, 32, 33, 34],
[41, 42, 43, 44],
]
第N行第M列 = A[N-1][M-1]
子数组的和
# 前0个数的和
PrefixSum[0] = 0
# 前i个数的和
PrefixSum[i] = A[0] + A[1] + ... A[i - 1]
# 则有
Sum(i~j) = PrefixSum[j + 1] - PrefixSum[i]
规避数组缺点
数组最大的缺点是保持连续空间，删除或者插入比较靠前的位置，那么后边的都要做相应的移动。
- 合并两个排序数组，比如[3, 4]合并到[1, 2, 5, null, null]。 可以从大到小合并, 避免数组移动
- 删除某个值，可以将目标位置和结尾对调，在进行删除
恢复旋转排序数组
[10 11 12 13 14 15 16 17 18 19 20 1 2 3 4 5 6 7 8 9]
|---------------左边-------------||-------右边------｜
- 先翻转左边
- 再翻转右边
- 最后翻转全部
字符串
--------------------------
|'H'|'E'|'L'|'L'|'O'|'\0'|
--------------------------
字符串可以看成特殊的unicode字符数组, 以特殊字符’\0’结尾。
可变性
Java中的String是Immutable的, 拼接两个字符串实际先分配足够的空间，然后依次拷贝。如果有大量字符拼接可以使用StringBuilder。
如果使String可修改，可以使用toCharArray方法
String s = "Hello World";
char[] str = s.toCharArray();
链表
p1 p2 栈空间
| |
v v
-------------------------------------
node1 -> node2 堆空间
-------------------------------------
链表也是线性数据结构(也可以看作特殊的树/图)。链表是离散型数据结构，以节点为单位，分散在内存的不同位置。
链表的优点是不需要连续空间，缺点便是无法随机访问/下标访问, 只能顺序查找。
所以, 同样是线性结构, 链表要慢许多, 首先访问链表无法有效命中CPU缓存, 其次node->next需要有寻址操作
单链表
-------- -------- -------- ---------
| 1 | x--->| 2 | x--->| 3 | x--->| 4 | x--> None
-------- -------- -------- ---------
链表一般考察的是编程的基本功，没有什么相应的算法，只是把操作用代码来实现
双向链表
---------- ---------- ---------- ----------
| | x------> | | x------> | | x------> | | x------> None
None <------p | 1 | <------p | 2 | <------p | 3 | <------p | 4 |
---------- ---------- ---------- ----------
双端队列(Deque)算是阉割版本的双向链表，只能从两头添加删除
经典缓存LRU使用的便是双链表+哈希，如果有新访问的便将数据节点放在链表头部
哨兵头节点
对于链表来说，头节点最特殊，没有前继节点。通常需要特殊处理。
如果给链表头加一个新头节点，那么就消除了特殊Case的情况，生活变得简单不少。
1 -> 2 -> 3 -> 4 -> None
^
head
new_head -> 1 -> 2 -> 3 -> 4 -> None
head = new_head.next
哨兵尾节点
同理，对于双链表来讲，再加一个尾节点，会减少空的判断
class CacheNode:
def __init__(self, key, val):
self.key = key
self.val = val
self.pre = None
self.next = None
class DoubleLinkedList:
def __init__(self):
self.head = CacheNode(key=None, val=None)
self.tail = CacheNode(key=None, val=None)
self.head.next = self.tail
self.tail.pre = self.head
双指针
双指针是线性数据结构经常使用的编程技巧, 比如反转链表
同向双指针
- 按条件左右分割(左边奇数右边偶数，左边小于k右边大于k, 左边满足条件右边不满足等)
- 寻找两条链表相交的节点(到达末尾，换另一条链)
- O(1)空间拷贝链表
相向双指针
- 判断数组回文串
- 反转数组
快慢双指针
- 比如链表是否有环，如果快指针追赶上慢指针，便是有环
- 移除链表倒数第K个节点
- 获取链表的中间节点，判断链表是否回文串
Linked-list劈成两半，记得将中间节点node->next = null
–End–