# 数据结构
# 链表
# 单向链表
单向链表为最基础的链表，主要标志为只能单向向后查找元素，在每一个node中都有之后的元素节点地址，若不存在则意味着是尾节点，所以如果不知道链表中的节点地址不论是插入、删除、更新还是查找的时间复杂度在均摊之后都是O(n)，因为都需先找到相对应的元素才可进行相对应的操作；若知道链表中的节点地址，则增删改的时间复杂度为O(1)。
练习：实现链表的增删改查操作（传入节点，和传入元素值两种做法）。
# 双向链表
双向链表即是在单向链表的基础上在每个节点中加上一个指向前一个节点的元素，这样即可完成双向链表的操作。若prev指针为空，则意味着已经到达头节点。双向链表在不知道节点地址时的增删改查操作的复杂度也是O(n)；在知道节点地址时的增删改的时间复杂度为O(1)。双向链表的意义在于可以快速删除某一个节点的前驱节点或快速添加一个节点在当前节点之前，方便做一些特定操作，比如在当前节点的前面加入一个值，完成一个排序操作。
练习：实现双向链表的增删改查操作（传入节点，和传入元素值两种做法）
# 循环链表
循环链表分为单向循环和双向循环链表，和普通的单双向链表的区别在于，他们的尾节点的后驱节点为头节点，而头节点的前驱节点为尾节点。循环链表的经典运用是约瑟夫环、魔术师发牌和拉丁方阵问题 (opens new window)。利用循环链表即可快速解决上述问题。
练习：实现循环链表，并利用循环链表解决这三个问题。
# 带环链表
在链表中可能会存在一部分位置有环，那么通过快慢指针的方式让快指针每次向前两步，慢指针每次向前一步，若两个指针能够相遇，则说明该链表存在环。当他们相遇时，将一个指针重新从链表开始和另一个指针一起每次向后移动一步，若他们再次相遇，该相遇地点则为环的入口点。因为当第一次相遇时，设链表长度为n，慢指针在相遇时步数为x+y，则快指针走了n+y步，因为快指针走过的长度为慢指针的两倍，所以n+y=2(x+y)，所以链表长度n=x+y+x，所以将其中一个指针拉回链表开头，重新向后走，再次相遇时，就是环的入口点。
练习：实现查找带环链表的环的入口点和环的大小。
# 跳表
跳表顾名思义，是可以在链表中跳着查询的数据结构，它便是在单向链表的基础上，增加了有序的条件，这使得二分查找成为了可能。快速查询是通过维护一个多层次的链表，且每一层链表中的元素是前一层链表元素的子集。跳表的建立，也就是在原先链表上做一个索引层，利用该索引层可以去查找对应节点的位置，如果一个链表有 n 个结点，如果每两个结点抽取出一个结点建立索引的话，那么第一级索引的结点数大约就是$\frac{n}{2}$，第二级索引的结点数大约为 $\frac{n}{4}$，以此类推第 m 级索引的节点数大约为 $\frac{n}{2^m}$。
假如一共有 m 级索引，第 m 级的结点数为两个，通过上边我们找到的规律，那么得出$\frac{n}{2^m}=2$ n，从而求得 m=log(n)-1。如果加上原始链表，那么整个跳表的高度就是 log(n)。我们在查询跳表的时候，如果每一层都需要遍历 k 个结点，那么最终的时间复杂度就为 O(k*log(n))。这个k值按照我们每两个结点提取一个基点建立索引的情况，我们每一级最多需要遍历两个个结点，所以 k=2。
练习：实现跳表
# 综合练习
实现一个链表基类，并从基类派生出各类链表，在单向链表基础上派生出双向链表
# 栈
# 基础
栈是一个后进先出的数据结构，最后进的元素是最先被出栈的
一个长度为n的数组，出栈顺序的种数是卡特兰数。
# 单调栈
单调栈顾名思义是栈中存放的数据是单调的，如果当前进栈的元素不能维持栈的单调性，则需要让栈中现有的部分元素出栈，直到将该元素入栈后能保持单调性。
单调栈可以解决以下一类问题：
有N头牛从左到右排成一排，每头牛有一个高度$h_i$，设左数第i头牛与「它右边第一头高度$\geq h_i$」的牛之间有$c_i$头牛，试求$\sum_{i=1}^N c_i$
该题作为练习题。
# 队列
# 单向队列
队列特点为先进先出，最先进的元素是最先出队的。
通常用一个数组模拟一个队列，用两个变量标记队列的首尾。
练习：实现队列的相关操作（插入，删除，访问队首队尾，清空队列）
# 双端队列
双端队列是指一个可以在队首/队尾插入或删除元素的队列。相当于是栈与队列功能的结合。具体地，双端队列支持的操作有 4 个：
- 在队首插入一个元素
- 在队尾插入一个元素
- 在队首删除一个元素
- 在队尾删除一个元素
# 循环队列
使用数组模拟队列会导致一个问题：随着时间的推移，整个队列会向数组的尾部移动，一旦到达数组的最末端，即使数组的前端还有空闲位置，再进行入队操作也会导致溢出（这种数组里实际有空闲位置而发生了上溢的现象被称为“假溢出”）。
解决假溢出的办法是采用循环的方式来组织存放队列元素的数组，即将数组下标为 0 的位置看做是最后一个位置的后继。（数组下标为 x 的元素，它的后继为 (x + 1) % SIZE）。这样就形成了循环队列。
# 单调队列
顾名思义，单调队列的重点分为 "单调" 和 "队列"
"单调" 指的是元素的的 "规律"——递增（或递减）
"队列" 指的是元素只能从队头和队尾进行操作
例题：给出一个长度为n的数组，编程输出每k个连续的数中的最大值和最小值
# 堆
# 大（小）根堆
从二叉堆的结构说起，它是一棵二叉树，并且是完全二叉树，每个结点中存有一个元素（或者说，有个权值）。
堆性质：父亲的权值不小于儿子的权值（大根堆）。同样的，我们可以定义小根堆。本文以大根堆为例。
由堆性质，树根存的是最大值
插入操作是指向二叉堆中插入一个元素，要保证插入后也是一棵完全二叉树。
最简单的方法就是，最下一层最右边的叶子之后插入。
如果最下一层已满，就新增一层。
插入之后可能会不满足堆性质？
向上调整：如果这个结点的权值大于它父亲的权值，就交换，重复此过程直到不满足或者到根。
可以证明，插入之后向上调整后，没有其他结点会不满足堆性质。
向上调整的时间复杂度是O(logn)的。
删除操作
删除操作指删除堆中最大的元素，即删除根结点。
但是如果直接删除，则变成了两个堆，难以处理。
所以不妨考虑插入操作的逆过程，设法将根结点移到最后一个结点，然后直接删掉。
然而实际上不好做，我们通常采用的方法是，把根结点和最后一个结点直接交换。
于是直接删掉（在最后一个结点处的）根结点，但是新的根结点可能不满足堆性质……
向下调整：在该结点的儿子中，找一个最大的，与该结点交换，重复此过程直到底层。
可以证明，删除并向下调整后，没有其他结点不满足堆性质。
时间复杂度O(logn)。
减小某个点的权值
很显然，直接修改后，向上调整一次即可，时间复杂度为O(logn)。
# 对顶堆
一个大根堆和一个小根堆则可以构造出一个对顶堆，对顶堆的含义便是，有一个中间元素，该元素是两个堆的公共元素，若两个堆的元素不等，则需要将该元素push进数目较少的堆中，保持两个堆中的元素实时相同。该数据结构能够很方便的求出动态变化的数组中的中位数。
练习：完成对顶堆的编写
# 树
# 二叉树
二叉树是n个有限元素的集合，该集合或者为空、或者由一个称为根（root）的元素及两个不相交的、被分别称为左子树和右子树的二叉树组成，是有序树。当集合为空时，称该二叉树为空二叉树。在二叉树中，一个元素也称作一个结点。
二叉树是递归定义的，其结点有左右子树之分，逻辑上二叉树有如下几种形态：
- 空二叉树
- 只有一个根节点的二叉树
- 只有左子树
- 只有右子树
- 完全二叉树
满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树，完全二叉树的结点可以不用被填满，只需叶子结点在最底下的两层即可。
# 二叉搜索树
具体可以查看二叉搜索树简介 (opens new window)
# 多叉树
- b树
- 关键字集合分布在整颗树上
- 每一个关键字有且只出现一次
- 所有关键字按照从小到大的顺序进行排列
- 每个节点除了存储关键字，还存储数据
- 若经常访问的元素离根节点较近，则访问更加迅速
- 叶子节点存储在同一层
- 相当于二分查找，可以在非叶节点结束
- b+树
- 有n棵子树的非叶节点有n个关键字，关键字会存储重复。
- 非叶节点只保存关键字，仅包含子树的最大或者最小的关键字，只用来索引，关键字从小到大排列
- 根节点的最大元素就是树的最大元素
- 所有叶子节点包含全部的关键字信息，以及指向关键字记录的指针，
- 叶子节点构成链表
- 有两个指针，一个指向根节点，一个指向关键字最小的叶子节点
# 线段树
线段树可以在O(logn)的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
线段树维护的信息，需要满足可加性，即能以可以接受的速度合并信息和修改信息，包括在使用懒惰标记时，标记也要满足可加性（例如取模就不满足可加性，对4取模然后对3取模，两个操作就不能合并在一起做）。
具体可查看线段树 - OI Wiki (opens new window)
# 树的直径
树的直径可以先随机选择一个节点然后通过bfs找到最远节点，再根据这个最远的节点找到离他最远的点，这样就能找到树的直径了。