算法 - 数组和链表

注：本文仅为笔记。

原文

• 极客时间 - 数据结构与算法之美 - 05 | 数组
• 极客时间 - 数据结构与算法之美 - 06 | 链表（上）
• 极客时间 - 数据结构与算法之美 - 07 | 链表（下）

数组

• 数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。
• 随机访问高效，O(1)，见下面一维数组内存寻址公式。
• 插入和删除低效，O(n)，需要移动后面的元素。
  • 删除优化策略，标记删除，直到无空间可用时再做删除。

一维数组内存寻址公式：

对于二维数组 a[n]
a[i]_addr = base_addr + i * type_size

二维数组内存寻址公式：

对于二维数组 a[m][n]
a[i][j]_addr = base_addr + (i * n + j) * type_size

三维数组内存寻址公式：

对于三维数组 a[m][n][p]
a[i][j][k]_addr = base_addr + (i * n * p + j * p + k) * type_size

关于多维数组在内存中的布局参考这篇文章：Memory Layout of Multi-Dimensional Arrays

链表

• 通过“指针”将一组零散的内存块串联起来使用
• 随机访问低效，需要遍历，O(n)
• 插入和删除高效，O(1)

类型：

• 单链表，每个节点有一个后继指针。
• 循环链表，tail->next指向head的单链表。约瑟夫问题可由这个数据结构解决。
• 双向链表，每个节点除了有一个后继指针，还有一个前驱指针。
• 双向循环链表，略。

用单链表实现LRU

维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。

1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：
   • 如果此时缓存未满，则将此结点直接插入到链表的头部；
   • 如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的的头部；

写好链表代码

• 技巧一：理解指针或引用的含义
• 技巧二：警惕指针丢失和内存泄漏
• 技巧三：利用哨兵简化实现难度。针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。哨兵结点不存储数据的，作为head存在，简化代码复杂度。
• 技巧四：重点留意边界条件处理
  1. 如果链表为空时，代码是否能正常工作？
  2. 如果链表只包含一个结点时，代码是否能正常工作？
  3. 如果链表只包含两个结点时，代码是否能正常工作？
  4. 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
• 技巧五：举例画图，辅助思考
• 技巧六：多写多练，没有捷径
  1. 单链表反转
  2. 链表中环的检测
  3. 两个有序的链表合并
  4. 删除链表倒数第 n 个结点
  5. 求链表的中间结点