线性表

• 每个线性表上的数据最多只有前和后两个方向，如 数组、链表、队列、栈 等
• 非线性表，数据之间不是简单的前后关系，如 二叉树、堆、图 等

数组 Array

• 线性表数据结构
• 连续的内存空间和相同类型的数据
  • 利：“随机访问” 的前提条件
  • 弊：删除、插入操作变得低效，为保证连续性，需要做大量的数据搬移工作
  • 寻址公式：a[i]_address = base_address + i * data_type_size（为什么数组下标以 0 开始，下标意味着“偏移（offset）”）

改进数组的插入、删除操作

1. 改进插入操作，插入第 k 个位置的元素
   • 普通：k～n 的元素顺序后移一位
   • 改进：插入第 k 个位置，并直接将第 k 位的数据搬移到数组元素的最后
2. 改进删除操作，删除第 k 个位置的元素
   • 普通：k～n 的元素顺序前移一位
   • 改进：
     • 将多次删除操作集中在一起执行，减少删除操作导致的数据搬移。每次的删除操作并不是真正地删除并搬移数据，而是记录数据已经被删除，当数组没有更多空间存储数据时，触发一次真正的删除操作。（JVM 标记清除垃圾回收算法）
     • 将最后一位的数据搬移至 k

数组的访问越界问题

1. 访问数组的本质是访问一段连续内存，只要数组通过偏移计算得到的内存地址是可用的，程序就可能不会报任何的错误
2. 数组的访问越界问题，和编译器分配内存和字节对齐有关

容器和数组的选择

1. 容器可以将很多数组操作的细节封装起来，支持动态扩容
2. Java ArrayList，在创建的时候事先指定数据大小
3. Java ArrayList 无法存储基本类型，若特别关注性能或只使用基本类型，可以选用数组
4. 表示多维数组时，使用数组更加直观

链表 Linked List

常见的链表结构

单链表

1. 每个结点都有存储数据和记录下一个结点的地址（后继指针 next）
2. 第一个结点，称作头结点，最后一个结点，称作尾结点，尾结点的 next 指向一个空地址 NULL

   

循环链表

1. 循环链表是一种特殊的单链表，尾结点指针只想链表的头结点
2. 要处理的数据具有环形结构特点，如 约瑟夫问题

双向链表

1. 每个结点有一个后继指针 next 指向后面的结点，有一个前驱指针 prev 指向前面的结点，头结点的 prev、尾结点的 next 指向 NULL
2. 比单链表占用更多的内存空间

双向循环链表

1. 双向链表 + 循环链表
2. 每个结点有一个后继指针 next 指向后面的结点，有一个前驱指针 prev 指向前面的结点，头结点的 prev 指向 尾结点，尾结点的 next 指向 头结点

链表的删除操作

• 删除结点中“值等于某个给定值”的结点，时间复杂度：O（n）
  1. 从头结点开始，依次遍历对比，直到找到值等于给定值的结点
  2. 删除结点操作
• 删除给定指针指向的结点
  1. 单链表，时间复杂度：O（n）
     • 获取要删除结点的前驱结点，从头结点开始依次遍历
     • 删除结点操作
  2. 双向链表，时间复杂度：O（1）
     • 直接获取前驱结点
     • 删除结点操作

有序链表

对于一个有序链表，双向链表的按值查询，可以通过记录上次查找的位置 p，每次查询时，根据要查找的值与 p 的大小关系，决定往前还是往后查找，平均只需要查找一半的数据

数组 VS 链表

1. 数组的储存空间是连续的，可以借助 CPU 的缓存机制，预读数组中的数据，链表则不行
2. 数组的大小是固定的，可能会出现“内存不足”、“重新申请并拷贝操作”（费时），链表没有限制，天然地支持动态扩容
3. 链表需要储存指针，使用的内存比数组多
4. 对链表进行频繁的插入、删除操作，会导致频繁的内存申请和释放，容易造成内存碎片（Java 可能会导致频繁 GC）

链表的应用场景

• LRU 缓存淘汰算法（Least Recently Used 最近最少使用）
  1. 有序单链表，越靠近尾部的结点是越早之前访问的
  2. 有新数据被访问时，从头结点依次遍历
  3. 如果数据已经被缓存在链表中了，找到原本此结点的位置，删除，插入到链表的头部
  4. 如果数据未被缓存，并且缓存未满，则直接插入到链表的头部
  5. 如果数据未被缓存，并且缓存已满，则删除链表的尾结点，并将数据插入到链表的头部
• 判断一个字符串是否是回文字符串
  • 快慢指针法

链表代码实现的技巧

1. 理解指针或引用的含义
   • 指针：将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量
2. 警惕指针丢失和内存泄漏
   • 插入结点时，注意操作顺序
   • 删除结点时，注意内存泄漏问题（手动释放内存空间）
3. 利用哨兵简化难度
   • 针对链表的插入、删除操作，需要对插入第一个结点和删除最后一个结点的情况进行特殊处理
   • 有哨兵结点的链表叫 带头链表，没有哨兵结点的链表叫作 不带头链表

     

4. 留意边界条件处理
   • 链表为空
   • 链表只包含一个结点
   • 链表只包含两个结点
   • 代码逻辑处理头结点和尾结点
5. 举例画图，辅助思考
6. 多写多练！！！

链表代码练习

1. 单链表反转
2. 链表中环的检测
   • 使用快慢指针，时间复杂度O(n)，空间复杂度O(1)。快指针步长两步，慢指针步长一步，若会相遇，则为有环，若快指针遍历完链表，则为无环
   • 使用集合，时间复杂度O(n)，空间复杂度O(n)。依次遍历链表，若存在相同结点，则为有环，若遍历完链表，则为无环
3. 两个有序的链表合并
   • 新增头结点，依次比较两个链表的结点，顺序在头结点后连接
4. 删除链表倒数第 n 个结点
   • 先使用快慢指针找到倒数第 n 个结点
   • 若无第 n 个结点，则删除第一个结点或不执行删除操作
   • 删除第 n 个结点
5. 求链表的中间结点
   • 使用快慢指针，当快指针指向尾结点时，慢指针指向中间结点