注：本文仅为笔记。原文极客时间 - 数据结构与算法之美 - 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维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。如果此数据没有在缓存链表中，又可以分为两种情况：如果此时缓存未满，则将此结点直接插入到链表的头部；如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的的头部；写好链表代码技巧一：理解指针或引用的含义技巧二：警惕指针丢失和内存泄漏技巧三：利用哨兵简化实现难度。针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理。哨兵结点不存储数据的，作为head存在，简化代码复杂度。技巧四：重点留意边界条件处理如果链表为空时，代码是否能正常工作？如果链表只包含一个结点时，代码是否能正常工作？如果链表只包含两个结点时，代码是否能正常工作？代码逻辑在处理头结点和尾结点的时候，是否能正常工作？技巧五：举例画图，辅助思考技巧六：多写多练，没有捷径单链表反转链表中环的检测两个有序的链表合并删除链表倒数第 n 个结点求链表的中间结点