一、数组
数组支持随机访问，根据下标随机访问的时间复杂度为 O(1)。且数组内存空间连续。
数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效
1. 问题：大多数编程语言，数组下标为什么从 0 开始？
从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：a[k]_address = base_address + k * type_size
但是，如果数组从 1 开始计数，那我们计算数组元素 a[k]的内存地址就会变为：a[k]_address = base_address + (k-1)*type_size
对比两个公式，我们不难发现，从 1 开始编号，每次随机访问数组元素都多了一次减法运算，对于 CPU 来说，就是多了一次减法指令。数组作为非常基础的数据结构，通过下标随机访问数组元素又是其非常基础的编程操作，效率的优化就要尽可能做到极致。所以为了减少一次减法操作，数组选择了从 0 开始编号，而不是从 1 开始。
还有一点是历史原因，C 语言从 0 开始，其他语言效仿 C 语言
二、链表
数组是一块连续的内存空间，比如我申请 100M 内存，如果操作系统没有这么多连续空间，就申请失败。但是如果链表的话，可以使用到零散的内存块。
对链表进行频繁的插入、删除操作，会导致内存的频繁的申请和释放，产生大量的内存碎片
1. 问题：如何基于链表实现LRU缓存淘汰算法
使用一个单链表，越靠近链表结尾的节点是越不常访问的节点，当访问一个节点时。遍历这个链表，如果这个节点找到了，那删除找到的这个节点，把新节点插入到链表头。如果这个节点没有找到，链表缓存满了，则删除链表尾节点，将新节点插入链表头，链表缓存没有满，则直接将新节点插入链表头。
2. 问题：如何基于数组实现LRU缓存淘汰算法
// TODO
3. 技巧
使用带头链表简化难度
检查链表代码是否正确？
- 如果链表为空时，代码是否能正常工作？
- 如果链表只包含一个结点时，代码是否能正常工作？
- 如果链表只包含两个结点时，代码是否能正常工作？
- 代码逻辑在处理头结点和尾结点的时候，是否能正常工作？
链表的代码一定要注意使用哨兵节点、析构掉申请的节点
leetcode 上关于链表的题目：206，141，21，19，876
三、栈
使用数组实现的栈称为顺序栈，使用链表实现的栈称为链式栈。
题目：表达式求值、括号匹配
leetcode上关于栈的题目：20,155,232,844,224,682,496.
- leetcode 224 实现一个简单计算器还没有做
四、递归
递归需要满足的三个条件
- 一个问题的解可以分解为几个子问题的解
- 这个问题与分解之后的子问题，除了数据规模不同，求解思路完全一样
- 存在递归终止条件
写递归代码最关键的是写出递推公式，找到终止条件
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码。
递归的问题：
- 重复计算，相同的逻辑计算多次
- 容易堆栈溢出
- 在时间效率上，递归代码里多了很多函数调用，当这些函数调用的数量较大时，就会积聚成一个可观的时间成本
- 在空间复杂度上，因为递归调用一次就会在内存栈中保存一次现场数据，所以在分析递归代码空间复杂度时，需要额外考虑这部分的开销