数据结构基础知识
1.初识集合框架
Java 集合框架 Java Collection Framework ，又被称为容器 container ，是定义在 java.util 包下的一组接口 interfaces和其实现类 classes 。
其主要表现为将多个元素 element 置于一个单元中，用于对这些元素进行快速、便捷的存储 store 、检索 retrieve 、管理 manipulate ，即平时我们俗称的增删查改 CRUD 。
例如，一副扑克牌 ( 一组牌的集合 ) 、一个邮箱 ( 一组邮件的集合 ) 、一个通讯录 ( 一组姓名和电话的映射关系 ) 等等。
数据结构 (Data Structure)是计算机存储、组织数据的方式，指相互之间存在一种或多种特定关系的数据元素的集合。
算法 (Algorithm):就是定义良好的计算过程，他取一个或一组的值为输入，并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤，用来将输入数据转化成输出结果。
容器背后对应的数据结构
该阶段，我们主要学习以下容器，每个容器其实都是对某种特定数据结构的封装，大概了解一下，后序会给大家详细讲解并模拟实现：
1. Collection ： 是一个接口，包含了大部分容器常用的一些方法
2. List ： 是一个接口，规范了 ArrayList 和 LinkedList 中要实现的方法
ArrayList ： 实现了 List 接口，底层为动态类型顺序表
LinkedList ：实现了 List 接口，底层为双向链表
3. Stack ：底层是栈，栈是一种特殊的顺序表
4. Queue ：底层是队列，队列是一种特殊的顺序表
5. Deque ：是一个接口
6. Set ：集合，是一个接口，里面放置的是 K 模型
HashSet ：底层为哈希桶，查询的时间复杂度为 O(1)
TreeSet ：底层为红黑树，查询的时间复杂度为 O(
), 关于 key 有序的
7. Map ：映射，里面存储的是 K-V 模型的键值对
HashMap ：底层为哈希桶，查询时间复杂度为 O(1)
TreeMap ：底层为红黑树，查询的时间复杂度为 O(
) ，关于 key 有序
3.3 相关 java 知识
1. 泛型 Generic
2. 自动装箱 autobox 和自动拆箱 autounbox
3. Object 的 equals 方法
4. Comparable 和 Comparator 接口
2.时间和空间复杂度
算法效率分析分为两种：第一种是时间效率，第二种是空间效率 。 时间效率被称为时间复杂度，而空间效率被称作 空间复杂度 。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间
算法中的基本操作的执行次数，为算法的时间复杂度
大概执行次数，那么这里我们 使用大 O 的渐进表示法。
大 O 符号（ Big O notation ）：是用于描述函数渐进行为的数学符号
1 、用常数 1 取代运行时间中的所有加法常数。
2 、在修改后的运行次数函数中，只保留最高阶项。
3 、如果最高阶项存在且不是 1 ，则去除与这个项目相乘的常数。得到的结果就是大 O 阶。
使用大 O 的渐进表示法以后， Func1 的时间复杂度为：
N = 10 F(N) = 100
N = 100 F(N) = 10000
N = 1000 F(N) = 1000000
通过上面我们会发现大 O 的渐进表示法 去掉了那些对结果影响不大的项 ，简洁明了的表示出了执行次数。
另外有些算法的时间复杂度存在最好、平均和最坏情况：
最坏情况：任意输入规模的最大运行次数 ( 上界 )
平均情况：任意输入规模的期望运行次数
最好情况：任意输入规模的最小运行次数 ( 下界 )
例如：在一个长度为 N 数组中搜索一个数据 x
最好情况： 1 次找到
最坏情况： N 次找到
平均情况： N/2 次找到
在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为 O(N)
空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度
空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似，也使用大O渐进表示法。
3..List的介绍
在集合框架中，List是一个接口，继承自Collection
Collection 也是一个接口 ，该接口中规范了后序容器中常用的一些方法，具体如下所示
Iterable也是一个接口，表示实现该接口的类是可以逐个元素进行遍历的，具体如下：
站在数据结构的角度来看， List 就是一个线性表，即 n 个具有相同类型元素的有限序列，在该序列上可以执行增删 改查以及变量等操作 。
List 中提供了好的方法，具体如下：
注意： List 是个接口，并不能直接用来实例化.
如果要使用,必须去实例化 List 的实现类.在集合框架中, ArrayList 和 LinkedList 都实现了 List 接口