前言叨逼叨(近期计划)
- 技术书籍(已看完):
- 《数据结构与算法分析》
- 《Redis设计与实现》
- 《RocketMQ实战与原理解析》
- 《深入理解Apache Dubbo与实战》
- 《ZooKeeper：分布式过程协同技术详解》
- 先后顺序开写总结。
- 正在进行中
- 极客时间《mysql实战45讲》进度 40%
- 《tcp/ip详解 卷一》 进度 5%
- 《深入理解Kafka：核心设计与实践原理》
- 非技术书籍：
- 《绝非偶然》进度 98%
- 《逆商》进度 20%
- 《增长黑客》
- 《旅行摄影圣经》
- 《社会心理学》
- 《经济学原理》曼昆 10%
时间空间复杂度
这是算法的时空复杂度的表示。不仅仅用于表示时间复杂度，也用于表示空间复杂度。
O后面的括号中有一个函数，指明某个算法的耗时/耗空间与数据增长量之间的关系。其中的n代表输入数据的量。
- 比如时间复杂度为O(n)，就代表数据量增大几倍，耗时也增大几倍。比如常见的遍历算法。
- 再比如时间复杂度O(n^2)，就代表数据量增大n倍时，耗时增大n的平方倍，这是比线性更高的时间复杂度。比如冒泡排序，就是典型的O(n^2)的算法，对n个数排序，需要扫描n×n次。
- 再比如O(logn)，当数据增大n倍时，耗时增大logn倍（这里的log是以2为底的，比如，当数据增大256倍时，耗时只增大8倍，是比线性还要低的时间复杂度）。二分查找就是O(logn)的算法，每找一次排除一半的可能，256个数据中查找只要找8次就可以找到目标。
- O(nlogn)同理，就是n乘以logn，当数据增大256倍时，耗时增大256*8=2048倍。这个复杂度高于线性低于平方。归并排序就是O(nlogn)的时间复杂度。
- O(1)就是最低的时空复杂度了，也就是耗时/耗空间与输入数据大小无关，无论输入数据增大多少倍，耗时/耗空间都不变。 哈希算法就是典型的O(1)时间复杂度，无论数据规模多大，都可以在一次计算后找到目标（不考虑冲突的话）
抽象数据类型
抽象数据类型(abstract data type，ADT)是带有一组操作的一些对象的集合。抽象数据类型是数学的抽象；在 ADT 的定义中没有地方提到关于这组操作是如何实现的任何解释。诸如表、结合、图及与它们各自的操作一起形成的这些对象都可以被看做是抽象数据类型，这就像整数、实数、布尔数都是数据类型一样。
表 ADT
对表的所有操作都可以通过使用数组来实现。虽然数组是由固定容量创建的，但在需要的时候可以用双倍容量创建一个不同的数组。不过，插入和删除的花费却潜藏着昂贵的开销，这要看插入和删除发生在什么地方。最坏的情形下，在位置 0 的插入(即在表的前端插入)首先需要将整个数组后移一个位置以空出空间来，而删除第一个元素则需要将表中的所有元素前移一个位置，因此这两种操作的最坏情况为 O(N)。平均来看，这两种操作都需要移动表的一半元素，因此仍然需要线性时间。另一方面，如果所有的操作都发生在表的高端，那就没有元素需要移动，而添加和删除则只花费O(1)时间。
存在许多情形，在这些情形下的表是通过高端进行插入操作建成的，其后只发生对数组的访问。在这种情况下，数组是表的一种恰当的实现。然而如果发生对表的一些插入和删除操作，特别是对表的前端进行，那么数组就不说一种好的选择。
链表
为了避免插入和删除的线性开销，我们需要保证表可以不连续存储，否则表的每个部分都可能需要整体移动。
链表由一系列节点组成，这些节点不必在内存中相连。每个节点均含有表元素和到包含该元素后继元的节点的链。称为 next 链。最后一个单元的 next 链引用 null。
remove 方法可以通过修改一个 next 引用来实现。下图给出在原表中删除第三个元素的结果。
insert 方法需要使用 new 操作符从系统取得一个新节点，此后执行两次引用的调整。其一般想法在下图中给出，其中的虚线表示原来的 next 引用。
如果知道变动将要发生的地方，那么向链表插入或从链表中删除一项的操作不需要移动很多项，而只涉及常数个节点链的改变。
在表的前端添加或删除第一项的特殊情形此时也属于常数时间操作，当然要假设到链表前端的链是存在的。只要拥有到链表最后节点的链，那么在链表末尾进行添加操作的特殊情形(即让新的项成为最后一项)可以花费常数时间。因此，典型的链表拥有到该表两端的链。删除最后一项比较复杂，因为必须找出指向最后节点的项，把它的 next 链改成 null，然后再更新持有最后节点的链。在经典的链表中，每个节点均存储到其下一节点的链，而拥有指向最后节点的链并不提供最后节点的前驱节点的任何信息。
保留指向最后节点的第 3 个链的想法行不通，因为它在删除操作期间也需要更新。做法是，让每一个节点持有一个指向它在表中的前驱节点的链，如下图，称为双链表。
Iterator、List 接口
java.util 包中Iterator接口中有个 remove 方法，该方法可以删除由 next 最新返回的项，虽然 Collection 接口也包含一个 remove 方法，但是使用Iterator的 remove 可能有更多的有点。
Iterator 的 remove 方法的主要优点在于，Collection 的 remove 方法必须首先找出要被删除的项。如果知道所要删除的项的准确位置，那么删除它的开销很可能要小的多。
List ADT 有两种流行的实现方式。ArrayList 类提供了 list ADT 的一种可增长数组的实现。使用 ArrayList 的优点在于，对 get 和 set 的调用花费常数时间。其缺点是新项的插入和现有项的删除代价昂贵，除非变动是在 ArrayList 的末端进行。
LinkedList 类则提供了 List ADT 的双链表实现。使用LinkedList的优点在于，新项的插入和现有项的删除均开销很小。假设变动项的位置是已知的，这意味着，在表的前端进行添加和删除都是常数时间的操作，由此LinkedList更提供了方法 addFirst 和 removeFirst、addLast 和 removeLast、以及 getFirst 和getLast 等以有效地添加、删除和访问表两端的项。使用LinkedList的缺点是它不容易作索引，因此对 get 的调用是昂贵的，除非调用非常接近表的端点。
LinkedList、ArrayList 末端添加，时间空间复杂度都是 O(N)
LinkedList、ArrayList 前端添加，LinkedList 时间空间复杂度是 O(N)，ArrayList时间空间复杂度是 O(N^2)
