前言
前一篇我们对数据结构有了个整体的概念上的了解，没看过的小伙伴们可以看我的上篇文章：一文十三张图带你彻底了解所有数据结构。那么从今天开始，我们来对每一个数据结构进行一个详细的讲解，并带着大家一起手写代码实现或者通过阅读源码来加强对数据结构的学习。我们从最简单的也是最常用的数组开始。
线性表
在介绍数组之前，我们先了解一下什么是线性表。
线性表是指n个类型相同的数据元素的有限序列。在线性表的定义中我们可以提取出三个关键因素：
- 有限：这个n是指线性表的有限长度，线性表中的每个数据元素都有一个唯一确定的序号，我们通常也叫做下标，比如a[0]在线性表中的序号就是0，a[n]的序号就是n，这儿要注意的是，对于n个数据元素的线性表，第N个数据元素的序号是n-1，因为我们的序号是从0开始的。
- 类型相同：即数据元素的属性相同，可以是数字、字符串，或者结构复杂的数据元素，比如商品、汽车、学生等。数据元素类型相同意味着每个数据元素在内存中存储时都占用相同的内存空间，便于我们的查找定位。
- 序列：表示顺序性，即线性表的相邻元素之间存在着序偶关系。比如a[1]的直接前驱是a[0],a[1]的直接后续是a[2]。一言概之，线性表的的表头没有直接前驱，表尾没有直接后续。除此之外，线性表中的每一个元素都有且仅有一个直接前驱和一个直接后续。
线性表的存储结构分为两种：
- 顺序表：顺序存储结构
- 链表：链式存储结构
数组
数组一种线性表数据结构，用一组连续的内存空间来存储一组相同类型的数据。
从数组的定义中我们也可以提取三个关键因素：
- 线性表：见上面定义
- 连续内存空间：数据元素存储在内存中的连续地址上。
- 类型相同：见线性表的介绍。
数组的特点
在内存中分配连续的空间，不需要存储地址信息，位置就隐含着地址信息。
数组的优点
- 高效的随机访问：数组按照索引查询元素速度快。因为数组的数据元素是通过下标来访问的，可以通过数组的首地址和寻址公式就能快速找到想要访问的结点元素和存储地址。
下面我们通过一张图来看看数组是怎样快速查找到结点的数据元素的。
查找数组元素
在上篇文章中我介绍过数组的寻址公式：
数据元素存储的内存地址=数组的起始地址+每个数据元素的大小下标*
通过寻址公式，我们可以很快的查找数组中每一个结点的存储地址和数据元素，比如上图中arr[3]的内存地址=1000+5*4=1020，（我们存的是int类型，所以元素的大小是4个字节），知道了存储的存地址，也就查到了结点的数据元素68。
数组的缺点
- 删除和插入数据元素效率较低：因为不管是删除还是插入数据都需要大量移动数据元素，所以效率低下。
下面我画图来给大家演示数组中删除和插入数据元素的步骤。
删除元素：
在这里插入图片描述
可以看出，我们删除数组下标为2的数据，但是上图中第二个图并没有真正删掉，因为数组下标为2的位置还占着呢，最多算更新，把38变成null，那怎样才算真正的删除呢？就是把后续的数据都往前移一位，如上图中步骤二黄色箭头所示，最后变成第三章图的结构，数组下标为5的结点内存地址没有存任何数据。
这只是数组长度为6的一个数组，如果数组长度很大呢，每删除一个元素，该元素后的元素都要相应往前移一位，相当于都要修改存储地址，效率自然而然就低下了。
插入元素：
在这里插入图片描述
看上图，如果我们要插入36这个元素，该怎么办呢？我们都知道如果是添加的话自动往数组尾端添加，但是现在是在固定位置插入一个元素，我们只能将要插入元素位置的数据及其后续的所有元素都往后移一位，如上图步骤二中黄色箭头所示，最终结果见步骤三。
注意：元素右移要从最后一个元素右移，否则前面的值会将后面的值覆盖。
同样的道理，如果数组元素很多，每次插入都要移动大量的数据元素位置，效率也自然低下。
上面的插入和删除，你可以想象在火车站排队进站的时候，如果有个人跟你说赶不及了需要在你前面插个队，那你包括你后面的人自然就要往后退一步。同理，你前面有个人因为看到个漂亮小姐姐跑走搭讪了，那你和你后面的人就会自动向前走一步。
接下来我们从源码角度详细的看一下数组的实现方式。
ArrayList源码解析
基本上每个程序员面试的时候都被问过ArrayList底层是通过什么实现的，我想有很多小伙伴都是看面试题回答说通过数组实现，但是我想知道有多少乡亲们是真的去看了ArrayList的源码才这样回答的，如果让你自己去实现一个数组，或者用数组实现一个ArrayList，你会写吗？
没看过没关系，没写过也没关系，今天我带大家一起去读ArrayList的源码，我希望看完本篇文章的乡亲们，以后不但要知其然，还要知其所以然，这也是我写这篇文章的初衷。好了，我们进入正题。
数组有哪些基本操作
说到数组，我们首先能想到常用的几个方法：
- add：增加一个元素（或者是在指定下标处添加一个数据元素）
- get：返回指定索引（下标）位置的元素
- remove：删除元素(或者是删除指定下标处的元素)
- size：数组所有元素的数量
我们知道，数组存储数据需要分配连续的内存空间，所以在定义数组的时候，需要预先指定数组的大小，如果超过数组的大小，则不能再往数组中添加元素。如果非要添加，则需要重新分配一块更大的连续内存空间，将老的数组的元素复制过来，再添加新的元素。
但是，使用ArrayList则可以不用关系底层的扩容逻辑，因为它已经帮我们实现好了，也就是ArrayList会帮我们动态扩容，这也是使用ArrayList最大的优势，ArrayList将很多数组操作的细节封装起来。
下面我们来详细解读ArrayList的源码。
ArrayList的完整结构图
ArrayList的完整结构图
ArrayList定义
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
private static final long serialVersionUID = 8683452581122892189L;
// 默认容量
private static final int DEFAULT_CAPACITY = 10;
// 初始化的一个空数组对象
private static final Object[] EMPTY_ELEMENTDATA = {};
// 同样是一个空数组对象，如果使用默认构造函数创建，则默认对象内容默认是该值，为了与EMPTY_ELEMENTDATA区分开来
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 当前要操作的数据存放的对象
transient Object[] elementData; // non-private to simplify nested class access
// 当前数组的长度
private int size;
// 当前数组允许的最大长度
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
// ....
}
ArrayList构造函数
ArrayList默认有三个构造函数，分别为：
- 无参构造函数
- 指定大小的构造函数
- 带Collection对象的构造函数
我们来看一下源码：
// 指定大小的构造函数，如果为0，使用上面定义的EMPTY_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);
}
}
// 无参构造函数，默认为空，使用上面定义的DEFAULTCAPACITY_EMPTY_ELEMENTDATA
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
// 带Collection对象的构造函数
public ArrayList(Collection<? extends E> c) {
// 将collection对象转换成数组，然后将数组的地址的赋给elementData，浅拷贝
elementData = c.toArray();
if ((size = elementData.length) != 0) {
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
// 深拷贝
elementData = Arrays.copyOf(elementData, size, Object[].class);
} else {
// replace with empty array.
this.elementData = EMPTY_ELEMENTDATA;
}
}
add()方法
ArrayList提供了两个add方法，一个是一个参数，另一个两个参数，看源码注释，我将解释写在注释上。
// 一个参数的代表将新元素加到数组的最后一个位置，如果数组长度大小够的话
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将新数据放到数组最后一个
elementData[size++] = e;
return true;
}
// 两个参数的add方法表示将新元素添加到指定的数组下标位置处。
public void add(int index, E element) {
// 校验要添加的位置下标是否小于0或者大于数组的size，是的话无法添加就抛异常
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
// 将需要插入的位置（index）后面的元素统统往后移动一位。
System.arraycopy(elementData, index, elementData, index + 1, size - index);
// 将新的数据内容存放到数组的指定位置（index）上
elementData[index] = element;
size++;
}
上面两个add方法的代码中都有一句
ensureCapacityInternal(size + 1);
这是什么意思呢？这也是我认为的ArrayList源码中最重要的一段代码，下面我们来详细看一下这句代码里干了哪些事。
// 1、见下方解释
private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
// 2、见下方解释
private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
// 3、见下方解释
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
// 4、见下方解释
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
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);
}
按照顺序对应解释一下上面代码的意思：
- 确保数组已使用长度（size）加1之后足够存储下一个数据。
- 确保添加的元素有地方存储。在使用默认构造函数初始的时候（比如List list = new ArrayList()），这个时候elementData数组其实是空的，当第一次往数组里添加元素时，先判断数组是不是空的，如果是空的，会将当前elementData数组的长度变为10：
- 将修改次数（modCount）自增1，判断是否需要扩充数组长度,判断条件就是用当前所需的数组最小长度与当前数组的长度对比，如果大于0，则需要增长数组长度（比如数组长度10，这时候需要添加第11个元素，11-10>0，则需要扩大数组容量。），也就是动态扩容。
- 动态扩容：如果当前的数组已使用空间（size）加1之后 大于数组长度，则增大数组容量，扩大为原来的1.5倍（oldCapacity + (oldCapacity >> 1)表示右移一位，位运算相当于oldCapacity/2）。
上面就是我个人认为ArrayList操作中最重要的一个特点和优势：动态扩容 。怎么样？小伙伴们现在都明白了吗？如果还不明白，送给你一段代码，打个断点，将源码debug一遍，你就知道我说的意思了。测试代码很简单，如下：
package com.mzc.datastrcuture;
import java.util.ArrayList;
import java.util.List;
public class ArrayListDemo {
public static void main(String[] args) {
List list = new ArrayList();
list.add(1);
list.add(2);
list.add(3);
list.add(4);
list.add(5);
list.add(6);
list.add(7);
list.add(8);
list.add(9);
list.add(10);
list.add(11); // 在这一行打断点，走到add方法里面去，看看发生了什么，是不是如我上面1234的步骤所说。
System.out.println(list.size());
}
}
好了，add方法就讲到这儿了，说完了add方法和动态扩容，ArrayList中的其他方法就都很简单了，只要理解了我上面说的数组操作，基本上看一遍就都能懂了，就不多说了。
总结
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
一、从ArrayList的定义上我们能看出来：
- ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
- ArrayList 实现了RandmoAccess接口，即提供了随机访问功能。
- ArrayList实现了Cloneable接口，即覆盖了函数clone()，能被克隆。
- ArrayList实现java.io.Serializable接口，这意味着ArrayList支持序列化，能通过序列化去传输。
二、方法操作总结：
- ArrayList自己实现了序列化和反序列化的方法，因为它自己实现了writeObject和readObject方法。
private void writeObject(java.io.ObjectOutputStream s)、
private void readObject(java.io.ObjectInputStream s)
- ArrayList基于数组方式实现，无容量的限制（会扩容）。
- 添加元素时可能要扩容（所以最好预判一下），删除元素时不会减少容量（若希望减少容量，trimToSize()），删除元素时，将删除掉的位置元素置为null，下次gc就会回收这些元素所占的内存空间。
- 线程不安全
- add(int index, E element)：添加元素到数组中指定位置的时候，需要将该位置及其后边所有的元素都整块向后复制一位，注意是从最后一位开始向后移动，即先将n-1 移动到n，再将n-2移动到n-1，以此类推到index。
- get(int index)：获取指定位置上的元素时，可以通过索引直接获取（O(1)）。
- remove(Object o)需要遍历数组。
- remove(int index)不需要遍历数组，只需判断index是否符合条件即可，效率比remove(Object o)高。
- contains(E)需要遍历数组。
- 使用iterator遍历可能会引发多线程异常。
三、面试常问总结：
- ArrayList初始化大小是10。
- ArrayList通过grow()方法扩容，每次扩容1.5倍。
- ArrayList读取查找数据效率高，修改删除效率低。
- ArrayList可以存放重复元素，也可以有null值。
- 和Vector不同，ArrayList中的操作不是线程安全的。所以，建议在单线程中才使用ArrayList，而在多线程中可以选择Vector或者CopyOnWriteArrayList。
喜欢本文的同学可以关注我的公众号，码之初。带你解锁更多数据结构和源码解读。
网友评论