本质 : 对数据的查找、 插入和删除
目的:
建立时间复杂度、空间复杂度意识，写出高质量的代码，能够设计基础架构，提升编程技能，训练逻辑思维，积攒人生经验.
以此获得工作回报，实现你的价值，完善你的人生。
效果:
1. 我们学任何知识都是为了“用”的，是为了解决实际工作"快.省"效率和资源寻求最优解的问题.
2. 高手之间的竞争其实就在细节。这些细节包括：算法是不是够优化，数据存取的效率是不是够高，内存是不是够节省.
数据结构就是指一组数据的存储结构。DS=(D,R)
算法就是操作数据的一组方法。
数据结构是为算法服务的，算法要作用在特定的数据结构之上。
数据结构是静态的，它只是组织数据的一种方式。如果不在它的基础上操作、构建算法，孤立存在的数据结构就是没用的。
数据结构和算法解决的是如何更省、更快地存储和处理数据的问题
千万不要被动地记忆，要多辩证地思考，多问为什么。
对于每个概念和实现过程，从实际场景出发，理解“是什么”，“为什么”，并且遇到同类型问题应该“怎么做”。
如何让代码运行得更快，如何让代码更省存储空间
步骤:
1. 时(间)空(间)复杂度分析: 衡量是优化的前提
事后统计法: 1. 测试结果非常依赖测试环境 2. 测试结果受数据规模的影响很大. (开发后-测试阶段)
大 O 复杂度表示法 考量效率和资源消耗的方法 (开发前-分析阶段)
1.1 大 O 时间复杂度表示法:
所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。
T(n) = O(f(n))
T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和。
大 O 时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势，所 以，也叫作渐进时间复杂度（asymptotic time complexity），简称时间复杂度。
当 n 很大时，你可以把它想象成 10000、100000。而公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略。我们只需要记录一个最大量级就可以了，如果用大 O 表示法表示刚讲的那两段代码的时间复杂度，就可以记为：T(n) = O(n)； T(n) = O(n2)。
1. 只关注循环执行次数最多的一段代码
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度
3. 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
从低阶到高阶有：O(1)、O(logn)、O(n)、O(nlogn)、O(n2 )。
非多项式量级:O(2^n) 和 O(n!)。
我们把时间复杂度为非多项式量级的算法问题叫作 NP（Non-Deterministic Polynomial，非确定多项式）问题。
当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。
多项式时间复杂度:
时间复杂度全称是渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。
1.2 大 O 空间复杂度表示法
渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据规模之间的增长关系。
复杂度也叫渐进复杂度，包括时间复杂度和空间复杂度，用来分析算法执行效率与数据规模之间的增长关系.
可以粗略地表示，越高阶复杂度的算法，执行效率越低。
最好情况时间复杂度（best case time complexity）
最坏情况时间复杂度（worst case time complexity）
平均情况时间复杂度（average case time complexity):加权平均时间复杂度或者期望时间复杂度。
均摊时间复杂度（amortized time complexity）
只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种复杂度表示法来区分。
2. 数据结构:
10个数据结构 : 数组、链表、栈、队列、散列表、二叉树、堆、跳表、图、Trie 树；
缓存是一种提高数据读取性能的技术，在硬件设计、软件开发中都有着非广泛的应用.
比如常见的CPU缓存、数据库缓存、浏览器缓存等等。
缓存的大小有限，当缓存被用满时，哪些数据应该被清理出去，哪些数据应该被保留？这就需要缓存淘汰策略来决定.
缓存淘汰策略指的是当缓存被用满时清理数据的优先顺序。
先进先出策略 FIFO（First In，First Out）、
最少使用策略 LFU（Least Frequently Used）、
最近最少使用策略 LRU（Least Recently Used）。
数组实现:
方式一：首位置保存最新访问数据，末尾位置优先清理.
当访问的数据未存在于缓存的数组中时，直接将数据插入数组第一个元素位置，此时数组所有元素需要向后移动1个位置，时间复杂度为O(n)；
当访问的数据存在于缓存的数组中时，查找到数据并将其插入数组的第一个位置，此时亦需移动数组元素，时间复杂度为O(n)。
缓存用满时，则清理掉末尾的数据，时间复杂度为O(1)。
方式二：首位置优先清理，末尾位置保存最新访问数据.
当访问的数据未存在于缓存的数组中时，直接将数据添加进数组作为当前最后一个元素时间复杂度为O(1)；
当访问的数据存在于缓存的数组中时，查找到数据并将其插入当前数组最后一个元素的位置，此时亦需移动数组元素，时间复杂度为O(n)。
缓存用满时，则清理掉数组首位置的元素，且剩余数组元素需整体前移一位，时间复杂度为O(n)。
（优化：清理的时候可以考虑一次性清理一定数量，从而降低清理次数，提高性能。）
单链表实现:
维护一个有序单链表，越靠近链表尾部的结点是越早之前访问的。
当有一个新的数据被访问时，我们从链表头开始顺序遍历链表。
1. 如果此数据之前已经被缓存在链表中了，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部。
2. 如果此数据没有在缓存链表中，又可以分为两种情况：
如果此时缓存未满，则将此结点直接插入到链表的头部；
如果此时缓存已满，则链表尾结点删除，将新的数据结点插入链表的头部。
当访问的数据没有存储在缓存的链表中时，直接将数据插入链表表头，时间复杂度为O(1)；当访问的数据存在于存储的链表中时，将该数据对应的节点，插入到链表表头,时间复杂度为O(n)。如果缓存被占满，则从链表尾部的数据开始清理，时间复杂度为O(1)。
散列表（Hash table）+ 双向链表实现:
散列表加双向链表来实现LRU缓存淘汰算法。
添加时：我们首先根据key在散列表中找到要删除的节点，时间复杂度O(1)。找到后将这个数据移动到链表头部。找不到则添加到链表头部，如果链表满的话还要删除链表的尾结点。
删除时：我们在时间复杂度O(1)内找到这个数据然后执行删除。
查找时：直接根据key在时间复杂度为O(1)内就可以找到了。
如果你的代码对内存的使用非常苛刻，那数组就更适合你。链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是 Java 语言，就有可能会导致频繁的 GC（Garbage Collection，垃圾回收）。
单向链表只有一个方向，结点只有一个后继指针 next 指向后面的结点。
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。
双向链表可以支持 O(1) 时间复杂度的情况下找到前驱结点，正是这样的特点，也使双向链表在某些情况下的插入、删除等操作都要比单链表简单、高效。
对于执行较慢的程序，可以通过消耗更多的内存（空间换时间）来进行优化；而消耗过多内存的程序，可以通过消耗更多的时间（时间换空间）来降低内存的消耗。
线性表（Linear List）。线性表就是数据排成像一条线一样的结构。
每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。
非线性表:
数据之间并不是简单的前后关系。比如二叉树、堆、图等。
3.算法
10个算法: 递归、排序、二分查找、搜索、哈希算法、贪心算法、分治算法、回溯算法、动态规划、字符串匹配算法。
1. 边学边练，适度刷题
2. 多问、多思考、多互动
3. 打怪升级: 打怪升级学习法 4. 练习沉淀: 知识需要沉淀，不要想试图一下子掌握所有
1. 为什么很多编程语言中数组都从0开始编号？
从数组存储的内存模型上来看，“下标”最确切的定义应该是“偏移（offset）”。前面也讲到，如果用 a 来表示数组的首地址，a[0]就是偏移为 0 的位置，也就是首地址，a[k]就表示偏移 k 个 type_size 的位置，所以计算 a[k]的内存地址只需要用这个公式：a[k]_address = base_address + k * type_size
2. 链表练习
技巧一：理解指针或引用的含义
技巧二：警惕指针丢失和内存泄漏
插入结点时，一定要注意操作的顺序，要先将结点 x 的 next 指针指向结点 b，再把结点 a 的 next 指针指向结点 x，这样才不会丢失指针，导致内存泄漏。
删除链表结点时，也一定要记得手动释放内存空间，否则，也会出现内存泄漏的问题。当然，对于像 Java 这种虚拟机自动管理内存的编程语言来说，就不需要考虑这么多了。
技巧三：利用哨兵简化实现难度
插入排序、归并排序、动态规划
技巧四：重点留意边界条件处理
技巧五：举例画图，辅助思考
单链表反转
链表中环的检测
两个有序的链表合并
删除链表倒数第 n 个结点
求链表的中间结点
