前言
学习数据结构与算法能够让你了解该用什么数据结构储存数据，这涉及到编程中关键的性能和效率问题。
数据结构
数据结构是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
数据结构的基本功能，可归纳为增删改查及遍历。
数据结构可分为逻辑结构和物理结构：
逻辑结构
数据对象中数据元素的关系
- 集合结构：数据元素同属于一个集合，没有其他关系。
- 线性结构：数据元素之间事一对一的关系。
- 树状结构：数据元素之间是一对多关系。
- 图形结构：数据元素之间是多对多关系。
物理结构
数据的逻辑结构在计算机中的储存方式。
顺序结构：数据元素存放在地址连续的储存单元里，其数据间的逻辑关系和物理关系。
链式储存结构：数据元素存放在任意的储存单元里，同是需要指针储存下一个元素的地址。
算法
算法简单来说就是解决问题的步骤。
五要素
- 有穷性。
- 确定性。
- 可行性。
- 有输入。
- 有输出。
设计原则
- 正确性。
- 可读性。
- 健壮性。
- 高效率与低存储量需求。
复杂度
一般只关注时间复杂度。
注：当然，空间复杂度本身也有其存在的意义，尤其是在对空间效率非常在乎的应用场合，或者是当问题的输入规模极为庞大时。
时间复杂度
表示算法复杂度的度量记号大 O 级别，常见的时间复杂度:
- 常数阶O(1)
- 线性阶O(n)
- 平方阶O(n²)
- 对数阶O(log n)
- 线性对数阶O(n log n)
时间复杂度分析方法：
- 只关注循环执行次数最多的一段代码。
- 总复杂度等于量级最大的那段代码的复杂度。
- 嵌套代码的复杂度等于嵌套你内外代码复杂的的乘积。
空间复杂度分析
表示算法的储存空间与数据规模之间的增长关系。
int[] a = new int[n]
这段代码的空间复杂的就是O(n)。
数组
线性、顺序结构，储存同一种数据类型（Object数组除外）。
随机访问
因为是连续的内存空间，很容易根据下标定位到内存地址。
低效的插入和删除
插入和删除数组末尾，时间复杂度为O(1),其他位置插入元素设计到元素的位置的移动，平均复杂度为O(n),效率低下。
链表
线性、链式结构
链表类型
单链表
链表有一个头指针指向链表的第一个节点，最后一个节点指向空。
循环链表
循环链表的尾结点指针是指向链表的头结点。
双向链表
双向链表需要额外的两个空间来存储后继结点和前驱结点的地址。所以，如果存储同样多的数据，双向链表要比单链表占用更多的内存空间。虽然两个指针比较浪费存储空间，但可以支持双向遍历。
查找慢、插入删除很快
一般我们都使用双向链表，因为它能够很快定位到前驱和后继节点。
因为链表是链式储存结构，定位元素只能通过遍历，复杂度为O(n);
针对链表的插入和删除操作，我们只需要考虑相邻结点的指针改变，所以对应的时间复杂度是 O(1)。
栈
只涉及在一端插入和删除数据，并且满足后进先出、先进后出的特性
栈的应用
- 符号匹配
- 中缀表达式转换为后缀表达式
- 计算后缀表达式
- 实现函数的嵌套调用
- HTML 和 XML 文件中的标签匹配
- 网浏览器中已访问页面的历史记录
队列
队列是一种线性表，它支持 先进先出（FIFO）
尾部添加、头部删除，跟我们生活中的排队类似
队列类型
单队列
单队列就是常见的队列, 每次添加元素时，都是添加到队尾：
单队列会出现“假溢出”现象，每次从队首删除元素，元素都要上前移动一个位置，能放的空位就相对减少了。
循环队列
我们可以将队列看成一个首位相连的环。当一个元素从队列删除后，新空余出来的空间可以作为队列的尾部。
队列应用
消息队列中间件
树
树状结构，像是一个倒挂的树。
基本术语
节点：根节点、叶节点、叶子节点、父节点、子节点、兄弟节点。
高度：