1.引子
1.1.为什么要学习数据结构与算法？
有人说，数据结构与算法，计算机网络，与操作系统都一样，脱离日常开发，除了面试这辈子可能都用不到呀！
有人说，我是做业务开发的，只要熟练API，熟练框架，熟练各种中间件，写的代码不也能“飞”起来吗？
于是问题来了：为什么还要学习数据结构与算法呢？
#理由一：
面试的时候，千万不要被数据结构与算法拖了后腿
#理由二：
你真的愿意做一辈子CRUD Boy吗
#理由三：
不想写出开源框架，中间件的工程师，不是好厨子
1.2.如何系统化学习数据结构与算法？
我想好了，还是需要学习数据结构与算法。但是我有两个困惑：
1.如何着手学习呢？
2.有哪些内容要学习呢？
学习方法推荐：
#学习方法 1.从基础开始，系统化学习 2.多动手，每一种数据结构与算法，都自己用代码实现出来 3.思路更重要：理解实现思想，不要背代码 4.与日常开发结合，对应应用场景
学习内容推荐：
数据结构与算法内容比较多，我们本着实用原则，学习经典的、常用的数据结构、与常用算法
#学习内容：
1.数据结构的定义
2.算法的定义
3.复杂度分析
4.常用数据结构
数组、链表、栈、队列
散列表、二叉树、堆
跳表、图
5.常用算法
递归、排序、二分查找
搜索、哈希、贪心、分治
动态规划、字符串匹配
2.考考你
在上一篇【数据结构与算法二（复杂度分析）】中，我们学会了时间复杂度分析，与空间复杂度分析。很简单，有没有？那么这一篇，我们来看最基础的一个数据结构：数组。它也是其它数据结构，比如顺序队列、顺序栈的实现基础。
#考考你： 1.你知道线性表吗？ 2.你能用自己的话给数组下定义吗？ 3.你知道数组的特点吗？ 4.你知道java中的ArrayList吗？ 5.你知道ArrayList的最佳实践吗？
3.数组特点
3.1.线性表
数组的第一个特点：是基于线性表的数据结构。
线性表（Linear List），就是把数据组织成一条线一样，每个线性表上的数据，只有向前和向后两个方向。基于线性表的数据结构有：数组、链表、栈、队列。
图一（数组与链表）：
图二（栈与队列）：
3.2.连续内存空间
数组的第二个特点：内存空间连续。
#内存空间连续 1.假如有一个数组，占用空间10M 2.那么在内存中需要10M的内存空间来存储 3.如果内存中，有一块大于等于10M的空间，则存储数组成功 4.如果内存中，有两块内存： 4.1.内存块memory_1等于 6M 4.2.内存块memory_2等于 5M 4.3.总内存memory_1 + memory_2 = 11M 4.4.虽然总内存：11M > 10M，结果还是不能存储数组 4.5.原因：内存块memory_1、memory_2不是连续的内存空间
3.3.操作：查找
数组的第三个特点：根据下标索引查找效率高，时间复杂度是O(1)
3.4.操作：插入
数组的第四个特点：插入操作，为了保持内存空间连续，需要向后移动数据。效率低，时间复杂度是O(n)
3.5.操作：删除
数组的第五个特点：删除操作，为了保持内存空间连续，需要向前移动数据。效率低，时间复杂度是O(n)
3.6.应用案例：ArrayList
在java开发中的ArrayList，我们是年年见、月月见、天天见有没有？那么：
#关于ArrayList（答案见讨论分享） 1.你知道它的底层其实就是数组吗？ 2.你知道它存在的理由吗？ 3.你知道它的推荐用法吗？
核心源码一：
1.ArrayList底层是基于数组实现
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable{
/*
* Default initial capacity.（初始容量）
*/
private static final int DEFAULT_CAPACITY = 10;
/**
*默认空数组
*/
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
*底层数组
*/
transient Object[] elementData;
/**
*构造方法，指定初始容量
*/
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
/**
* 构造方法，默认空数组
*/
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
......
}
核心源码二：
1.添加元素add操作，首先检查是否需要扩容
2.ArrayList每次扩容后，新空间是原空间的1.5倍
3.结论：ArrayList存在的理由，支持动态扩容
/**
*添加元素
*/
public boolean add(E e) {
// 确认空间，是否需要扩容
ensureCapacityInternal(size + 1);
elementData[size++] = e;
return true;
}
/**
*扩容空间
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
// 新空间 = 原空间（oldCapacity） + 扩容空间（(oldCapacity >> 1)）
// 扩容空间 = (oldCapacity >> 1)，右移1位，即除以2
// 结论：ArrayList每次扩容后，新空间是原空间的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
4.讨论分享
#考考你答案：
1.你知道线性表吗？
1.1.线性表（Linear List），就是把数据组织成一条线一样
1.2.每个线性表上的数据，只有向前和向后两个方向
1.3.基于线性表的数据结构：数组、链表、栈、队列
2.你能用自己的话给数组下定义吗？
2.1.数组是基于线性表的数据结构
2.2.它是以一组连续的内存空间
2.3.用于存储相同数据类型的数据
3.你知道数组的特点吗？
3.1.基于线性表
3.2.内存空间连续
3.3.存储相同数据类型数据
3.4.根据下标索引查找效率高，时间复杂度O(1)
3.5.插入、删除操作效率低，时间复杂度O(n)
4.你知道java中的ArrayList吗？
4.1.ArrayList底层是基于数组实现
4.2.它存在的理由是功能更加丰富，支持动态扩容
4.3.每次扩容后，新的存储空间，是原空间的1.5倍
5.你知道ArrayList的最佳实践吗？
5.1.由于ArrayList底层是数组，为了保持内存空间连续
5.2.每次扩容后，都需要进行数据，从原数组，向新数组的拷贝
5.3.需要额外的临时存储空间，拷贝数据效率低
5.4.在实际开发中，如果预先可以预估存储元素的范围，比如90...100
5.5.那么在创建ArrayList对象的时候，可以指定初始容量100，即：
ArrayList list = new ArrayList(100);
5.6.这样执行效率最优
