一、顺序表
1、属于线性表。
2、顺序表插入删除需要移动元素。
3、动态顺序表中，插入需要检查是否需要扩容
4、数据在内存中是连续的，可以支持随机访问
1、顺序表插入删除：
a、顺序表插入元素，需要移动元素，这里需要把[i, n - 1]区间的元素全部向后移动一次，故移动的次数为n - 1 - i + 1
b、顺序表删除元素，需要移动元素，这里需要把[i + 1, n - 1]区间的元素全部向前移动一次，故移动的次数为 n - i - 1
二、链表
1、属于线性表。
2、链表插入删除元素只需要修改指针指向，不需要移动元素。
3、每次插入元素，都是先出开一个节点的空间，不需要事先估计存储空间。
4、链表是用指针链接前后节点，数据在内存中不一定连续，链表没有索引，不能随机访问。
5、链表是由节点构成，自然链表长度越大空间开销越大。 因此会为节点间的逻辑关系而增加额外的存储开销
1、单链表
1.1、插入
链表插入：
a、空链表插入时， 首指针需要改变。
b、非空链表插入时，尾指针需要改变。
//在单链表指针为p的结点之后插入指针为s的结点
s->next=p->next;
p->next=s;具体操作
1.2、删除
//在一个单链表中，q 的前一个节点为 p，删除 q 所指向节点时
p->next=q->next; //链接起来
delete q;注意：
在长度为n(n>1)的单链表上，设有头和尾两个指针，执行.（删除单链表中的最后一个元素操作）与链表的长度有关。
因为其需要遍历单链表，找到尾节点的前一个节点。所以与长度有关。
其他的头删、头插、尾插都不需要遍历链表
2、循环链表
循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的 指针 域指向 头结点 ，整个链表形成一个环。
（1）单循环链表——在单链表中，将终端结点的指针域NULL改为指向表头结点或开始结点即可。
（2）多重链的循环链表——将表中结点链在多个环上。
指针 ，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向 循环链表 。
2.1、双向循环链表判空
//双向带头循环链表中，head不是存放有效数据的节点，如果只有一个head节点，说明链表为空。
head->next==head;2.2、双向循环插入
//在一个循环双向链表中，要在p所指的节点之前插入s所指节点
s->next=p;
s->prev=p->prev;
p->prev->next=s;
p->prev=s;// 最后对p的前继节点做出修改
链表和顺序表的区别：
1、链表和顺序表都属于线性表。
a、顺序存储结构---顺序表
b、链式存储结构---链表
2、链表不能随机访问其中的某个元素，顺序表可以
3、链表能做的事，顺序表都可以完成，只是操作方法不同，效率不同
4、链表插入和删除元素因为不需要移动节点，所以相比较于数组而言，链表的时间复杂度为O(1)，数组的时间复杂度O(n)。
注意：链表的插入和删除不是所有情况下都比顺序表快，比如尾插尾删，顺序表的时间复杂度为O（1），并且如果是单链表，如果要在中间某个节点的前面插入/删除一个节点，则需要遍历。所以时间的快慢要分情况看待。
5、链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
6、顺序表物理相邻逻辑相邻，链表逻辑相邻物理不一定相邻
三、栈
1、栈是一种后进先出的数据结构
2、顺序表和链表都可以用来实现栈，不过一般都使用顺序表，因为栈想当于是阉割版的顺序表，只用到了顺序表的尾插和尾删操作，顺序表的尾插和尾删不需要搬移元素效率非常高，故一般都是使用顺序表实现。
3、栈只能在栈顶进行输入的插入和删除操作。
4、队列只能从队头删除元素。
5、栈是有入栈和出栈操作，出栈就是从栈中删除一个元素。
3.1、链栈与顺序栈区别
1、如果是链栈，一般需要进行头插或者头删操作，而顺序栈一般进行尾插和尾删操作，链表的操作比顺序表复杂，因此使用顺序结构实现栈更简单。
2、链式结构实现栈时，每次入栈相当于链表中头插一个节点，没有扩容一说。
3.2、用栈模拟队列 注意事项：
1、用栈模拟实现队列可以使用两个栈，一个栈模拟入队列，一个栈模拟出队列。
2、出队列时直接弹出模拟出队列栈的栈顶元素，当该栈为空时，将模拟入队列栈中所有元素导入即可，不是每次都需要导入元素。
3、一个栈模拟入队列，一个栈模拟出队列，入队列时，将元素直接往模拟入队列的栈中存放
4、入队列操作时间复杂度为O(1)
四、队列
1、队列是先进先出的
2、顺序表和链表都可以用来实现队列。
3、出队操作，一定会影响头指针，如果出队之后，队列为空，会影响尾指针。
4、数据入队列时一定从尾部插入、
5、队列只能从队头删除元素。
1、出队列注意事项：
用无头单链表存储队列，其头指针指向队头结点，尾指针指向队尾结点，则在进行出队操作时。
一定会修改头指针，如果出队之后，队列为空，需要修改尾指针。
2、顺序结构实现循环队列：
为什么用循环队列：
队列适合使用链表实现，使用顺序结构(即固定的连续空间)实现时会出现假溢出的问题，因此大佬们设计出了循环队列，循环队列就是为了解决顺序结构实现队列假溢出问题的。
1、循环队列的长度都是固定的
2、队头和队尾在同一个位置时 队列可能是空的，也可能是满的，因此无法判断。
3、设置计数即添加一个字段来记录队列中有效元素的个数，如果队列中有效元素个数等于空间总大小时队列满，如果队列中有效元素个数为0时队列空。
4、循环队列也是队列的一种，是一种特殊的线性数据结构
循环队列判空：
(rear - front) % (N + 1)
解释：有效长度一般是rear-front, 但是循环队列中rear有可能小于front，减完之后可能是负数，所以需要+N，此时结果刚好是队列中有效元素个数，但如果rear大于front，减完之后就是有效元素个数了，再加N后有效长度会超过N，故需要%N。
五、堆
1、堆的性质
1、堆是在完全二叉树的基础上进行了条件的限制，即：每个节点都比其孩子节点大，则为大堆；每个节点都比其孩子节点小则为小堆。
2、大根堆：根结点 > 子结点，总是最大的，并且在堆的每一个局部都是如此。例如{3,1,2}可以看作为大根堆，而{3,2,1}亦可以看作为大根堆。大根堆的根结点在整个堆中是最大的元素
3、小根堆：小根堆的性质与大根堆类似。
4、删除操作需要执行向下调整算法
5、插入操作需要执行向上调整算法
向下调整的基本操作：
1、建堆时，从每一个非叶子节点开始，倒着一直到根节点，都要执行一次向下调整算法。
2、删除元素时，首先交换堆顶元素与堆中最后一个元素，对中有效元素个数减1，即删除了堆中最后一个元素，最后将堆顶元素向下调整。
时间复杂度：O(n)
堆的常用场景
1、堆排序。
2、建立优先级队列，若利用堆来建立优先级队列，可以快速的获取到队列中优先级最高/低的任务。
3、n个元素中排列出前k大的元素问题，对于此类问题，可以建立一个小根堆，依次读入n个元素并调整，并在堆的规模达到k+1时，剔除掉第1个元素，剩下k个较大元素，保持堆的规模不超过k，一直循环即可得到最终的结果。
六、二叉树
1、二叉树的基本性质
1、高度h = log(n)向上取整 注意：底数是2。 即log (n) + 1。
2、完全二叉树中如果一个节点没有左孩子，则一定没有右孩子，必定为一个叶子节点，最后一层一定为叶子节点，但是倒数第二层也可能存在叶子节点。
3、在任意二叉树中，度为0的节点都比度为2的节点多1个。
4、在完全二叉树中，如果节点总个数为奇数，则没有度为1的节点，如果节点总个数为偶数，只有一个度为1的节点。
5、对于任意的树都满足：边的条数比节点个数少1，因为每个节点都有双亲，但是根节点没有
6、一颗深度为 h 的满二叉树拥有 2^h-1 个结点（根结点深度为1）
7、一棵非空的二叉树的先序遍历序列与后序遍历序列正好相反，则该二叉树一定满足只有一个叶子结点。
8、一棵具有N个结点的二叉树采用二叉链表进行存储,其中空指针域有 （n + 1）。
n个节点，n-1个非空。
2、哈夫曼树的基本性质
哈夫曼树(Huffman)树又称最优二叉树。它是n个带权叶子结点构成的二叉树中，带权路径长度WPL最小的二叉树。因为构造这种树的算法是最早由哈夫曼于1952年提出的，所以被称之为哈夫曼树。
1、路径
树中从“一个结点”到“另一个结点”之间的分支。
2、路径长度
一个路径上的分支数量。
3、树的路径长度
从树的根节点到每个节点的路径长度之和。
4、节点的带权路径路径长度
其实也就是该节点到根结点的路径长度乘以该节点的权。
5、树的带权路径长度
树中各个叶节点的路径长度*该叶节点的权的和，常用WPL(Weight Path Length)表示。6、哈夫曼树的总结点数是2n-1（n是叶子节点数），并且非叶子节点数目总是比叶子节点数目小1。哈夫曼树没有度为1的节点
3、搜索树
1、线索二叉树中某节点P有左孩子的条件是 （p ->LTag == 0）
2、X是二叉树中序线索树中一个有左孩子的节点，且X不为根，则X的前驱为X的左子树的最右节点
2、引入二叉线索树的目的是( 加快查找结点的前驱和后继速度 )。
比如： 以数据集{4,5,6,7,10,12,18}为叶结点权值所构造的哈夫曼树,其带权路径长度为（）？
七、图
邻接矩阵：
1、用邻接矩阵存储图，用一个矩阵存储顶点信息和顶点间关系的信息。
2、用邻接矩阵存储图，占用的存储空间只与图中顶点数有关，而与边数无关
3、适用于稠密图
邻接表：
1、用邻接表存储图，图中每一个订点对应一个单链表，链表中的一个节点包含了与该节点邻接的另一个顶点构成的一条边信息。
2、用邻接表存储图，占用的存储空间与图中顶点数和边数都有关。
3、适用于稀疏图。
