1.时间复杂度分析方式

时间复杂度会因为数据输入的不同，得出来的时间复杂度不同，所以我们先介绍一下常见的时间复杂度的方法

最好、最坏时间复杂度都好理解，我们讲一下平均与平摊复杂度

平均复杂度：先要考虑发生的可能性比如：一个数组数据，我要对数组数据进行查找，可能数值中没有或者有（1/2）概率 ，每次遍历一个对应是n复杂度 n/2 复杂度

平摊复杂度：一般可以用来分析，阶段性前他的复杂度是一样的，达到一个阶段性的阀值后就会是一个更高的复杂度，可以使用平摊来分析，在一般算法中复杂度是取最大复杂度，但是平摊是下下取复杂度，取得就是我们阶段之前出现的连续的复杂度。

2.线性数据结构

第一个线性表：顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。

第二个是 连续的内存空间和相同类型的数据 。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。 但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，为了保证连续性，就需要做大量的数据搬移工作。

3.为什么数组下标不从1开始

第一点：从数据结构的角度看，下标是对数据偏移量的体现数据寻址的计算（ a[k]_address = base_address + k * type_size ）k这代表偏移量 ，如果我们使用1位初始下标，寻址的公示变为（ a[k]_address = base_address + （k-1） * type_size ）可以看到多了一个减法，数组作为底层的数据结构，一个减法会对性能有所影响的。

第二点：可能是因为语言发展史影响，C语言是较早语言，它的数组是以下标位0开始，后面较晚的语言后面都是使用0位开始可以受影响了，后面还有一些可以支持负数下标的语言python。

4.链表种类

链表是使一组零散的内存块串联在一起，的一种数据结构，第一个节点被称为首节点，最后一个节点被称为尾结点，每个节点都是通过节点直接的后续指针next进行关联上。尾结点的next结点是null，用来标记是尾结点。

单链表：一条分散的内存组成的一条链表，也是链表中最简单的链表。

循环链表：其实就是一种特殊的单链表，就是尾结点和首结点是相连的链表结构。

双向链表：实际开发中双向链表的使用场景比，单链表场景多，双向链表的上在单链表基础上添加了前结点，把他们前后都关联上，单结点只有后结点，只能知道后面数据，前面数据只能遍历进行获得，而双向链表则天生满足，并且在插入和删除性能都优于单链表，比如删除，我知道需要删除那个结点，我又有前后结点地址我只需要把前后结点地址换一下就可以了。

循环双向链表：其他特性都和双向链表一样的，但是首结点和尾结点都是相互关联起来的。

5.轻松写出链表代码的思考思路

技巧一：理解指针和引用的的含义

?? ?将某个变量赋值给指针，实际上就是将这个变量的地址赋值给指针，或者反过来说，指针中存储了这个变量的内存地址，指向了这个变量，通过指针就能找到这个变量。

技巧二：谨防指针丢失和内存泄漏

?? ?1.记得插入结点时，对结点处理的顺序导致指针丢失 2.记得删除结点时，对内存手动清理（如：Java 则不需要考虑了，有GC回收）

技巧三：利用哨兵简化实现难度

?? ?没有实现哨兵（不带头链），实现需要考虑插入和删除最尾结点要进行特殊处理（没有带头链会对实现的处理差异化）。使用哨兵头结点（带头链），实现不要考虑插入删除不要特殊处理，应为不会影响的带头链（插入和删除结点不需要特殊处理）。

技巧四：重点留意边界条件处理

?? ?一定要在编写的过程中以及编写完成之后，检查边界条件是否考虑全面（全部场景），以及代码在边界条件下是否能正确运行。

技巧五：举例画图，辅助思考

?? ?举例法：是对数据进行带入然后进行验证，类似于程序dobug调试一样。画图法：画出图形方便理解和思考，直观观察数据的变动方便理解。

技巧六：多写多练，没有途径

?? ?多手写代码与思考，多练代码题。