一、简介
在项目中，相信大家都已经用过集合List,它提供了一系列的API，方便我们使用。今天有空去看了下ArrayList的源码，本章将会模仿源码实现一个简单的ArrayList,只是帮助理解ArrayList底层是怎么实现的，并没有必要去自定义ArrayList。
二、实现原理
ArrayList底层是通过数组实现的，所有对数据的操作其实底层都是对Object[]数组的操作, 具体的增删查改等功能都是依据这个数组进行数组相关的操作，如复制数组、数组扩容、删除数组中某个元素等。
特点：
* 1. ArrayList查询快(索引),新增、修改、删除慢(需要修改下标)
* 2. ArrayList默认创建大小为10的对象数组，如果超过十个元素会进行扩容。三、自定义ArrayList
package com.wsh.arraylist;
/**
* 自定义一个简单的ArrayList,帮助理解ArrayList底层原理
*
* @author weishihuai
* @date 2018/9/25
* <p>
* 说明:
* 1. ArrayList底层实现是数组,所有对数据的操作其实底层都是对Object[]数组的操作。
* 2. ArrayList查询快(索引),新增、修改、删除慢(需要修改下标)
* 3. ArrayList默认创建大小为10的对象数组，如果超过十个元素会进行扩容。
* 4. 本类只实现了部分常见的方法，帮助自己理解而已。
*/
public class CustomArrayList {
/**
* 数组初始化大小(默认为10)
*/
private static final int DEFAULT_INIT_NUM = 10;
/**
* 数组的大小
*/
private int size;
/**
* 存放数据的对象数组
*/
private Object[] data;
/**
* 无参构造方法
*/
public CustomArrayList() {
this(DEFAULT_INIT_NUM);
}
/**
* 有参构造方法
*
* @param initNum 指定大小
*/
public CustomArrayList(int initNum) {
//如果初始化大小小于0
if (initNum < 0) {
throw new IllegalArgumentException("数组初始化大小不能小于0");
}
//创建指定大小的对象数组
data = new Object[initNum];
}
/**
* 新增元素
*
* @param object 对象
*/
public void add(Object object) {
//数组扩容处理
//创建新数组，复制原数组到新数组，返回新的数组
if (size == data.length) {
Object[] newData = new Object[size * 2 + 1];
// for(int i = 0 ; i < data.length ; i++) {
// newData[i] = data[i];
// }
//拷贝数组
System.arraycopy(data, 0, newData, 0, data.length);
//替换原数组
data = newData;
}
data[size] = object;
//每次新增完元素大小需要加1
size++;
}
/**
* 获取List的大小
*
* @return List的大小
*/
public int size() {
return size;
}
/**
* List是否为空
*
* @return
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 根据下标获取对应的值
*
* @param index 下标索引
* @return
*/
public Object get(int index) {
//判断索引是否合法
if (index < 0 || index >= size) {
throw new IllegalArgumentException("数组下标索引非法，下标越界");
}
return data[index];
}
/**
* 根据索引删除指定位置的对象
* 原理: 被删除下标以后的元素依次往前移
*
* @param index 下标索引
* @return 被删除的旧数据
*/
public Object remove(int index) {
Object old = data[index];
//判断索引是否合法
if (index < 0 || index >= size) {
throw new IllegalArgumentException("数组下标索引非法，下标越界");
}
//原理：数组copy
int num = size - index - 1;
if (num > 0) {
System.arraycopy(data, index + 1, data, index, num);
}
data[--size] = null;
// data[size - 1] = null;
// size--;
//返回被删除的旧数据
return old;
}
/**
* 删除指定值的元素
* 原理: 循环遍历数组，使用equals比较值是否相等，找到第一个匹配的数组元素的下标，根据该下标进行删除
*
* @param object 指定值
* @return
*/
public boolean remove(Object object) {
for (int i = 0; i < size; i++) {
if (get(i).equals(object)) {
remove(i);
return true;
}
}
return false;
}
/**
* 给指定索引下标赋值
* 原理：替换原数组下标的值
* 下标索引
*
* @param index
* @param object 对象
*/
public Object set(int index, Object object) {
//判断索引是否合法
if (index < 0 || index >= size) {
throw new IllegalArgumentException("数组下标索引非法，下标越界");
}
Object oldValue = data[index];
data[index] = object;
return oldValue;
}
/**
* 指定位置添加值
* 原理: 数组copy,依次往后移，空出当前index位置存放object对象
*
* @param index 下标索引
* @param object 对象
*/
public void add(int index, Object object) {
//判断索引是否合法
if (index < 0 || index >= size) {
throw new IllegalArgumentException("数组下标索引非法，下标越界");
}
//数组的扩容
if (size == data.length) {
Object[] newData = new Object[size * 2 + 1];
//拷贝数组
System.arraycopy(data, 0, newData, 0, data.length);
//替换原数组
data = newData;
}
System.arraycopy(data, index, data, index + 1, size - index);
data[index] = object;
size++;
}
/**
* 根据指定值查找下标，未找到返回-1
* 原理: 循环遍历数组，使用equals方法判断值是否相等，返回第一个匹配的下标索引，未找到返回-1
*
* @param object 对象
* @return 下标索引
*/
public int indexOf(Object object) {
if (null == object) {
for (int i = 0; i < size; i++) {
if (null == data[i]) {
return i;
}
}
} else {
for (int i = 0; i < size; i++) {
if (object.equals(data[i])) {
return i;
}
}
}
return -1;
}
/**
* 从后往前找指定值对应的下标索引
* 原理: 倒序循环遍历数组，使用equals方法判断是否相等，找到返回对应的下标索引，未找到返回-1
*
* @param object 指定值
* @return 下标索引
*/
public int lastIndexOf(Object object) {
if (null == object) {
for (int i = size - 1; i >= 0; i--) {
if (data[i] == null) {
return i;
}
}
} else {
for (int i = size - 1; i >= 0; i--) {
if (object.equals(data[i])) {
return i;
}
}
}
return -1;
}
}
以上就是一个简单的ArrayList，提供了简单的增删查改功能，可能会有一些问题，不过帮助理解底层实现已经够了。
四、方法详解
【a】构造方法:
1. 无参构造方法： 默认创建长度为10的Object[]数组。
2. 有参构造方法：创建指定大小的Object[]数组。
【b】public void add(Object object) {} 新增元素
1. 新增元素之前需要判断当前Object[]数组的长度是否等于size,如果相等了说明数组需要扩容了，简单理解就是数组里面不能存放这么多元素了，需要扩大数组的长度，一般是2n+1。
2. 新增实现原理: 实际上是创建一个新的数组，然后将原来Object[]数组中的元素拷贝到新数组中，然后把新数组赋值给存放数据的数组。
3. 每新增一个元素，size需要加1
【c】size(){} 返回list的大小
1. size
【d】isEmpty() {} 判断list是否为空，
1. 即size == 0
【e】get(int index){} 根据索引取出对应list中的元素
1. 需要判断索引是否越界以及是否合法
2. 实现原理: 根据索引，这个索引对应数组的下标，即直接返回data[index]数组下标对应的值
【f】remove(int index) {} 移出list中对应索引的元素
1. 判断索引index参数是否合法
2.实现原理: 数组拷贝，即将对应index索引的元素后面的元素都前移一位，然后把index索引的元素置空，利于垃圾回收器进行无用对象回收。
【g】remove(Object object){} 移出list中指定对象的元素
1. 实现原理: 循环遍历数组，使用equals比较值是否相等，找到第一个匹配的数组元素的下标，根据该下标进行删除。
【h】set(int index, Object object) {} 给list中对应索引的元素赋新值
1. 实现原理: 通过data[index]找到对应索引的元素，直接将原对象的值赋新值
2. 判断索引是否合法
【i】add(int index, Object object) {} list中指定位置新增元素
1. 实现原理: 数组copy,依次往后移，空出当前index位置存放object对象
2. 数组扩容问题
3. 判断索引是否合法
【j】indexOf(Object object){} 判断list中是否含有某个元素
1. 实现元素: 循环遍历数组，使用equals方法判断值是否相等，返回第一个匹配的下标索引，未找到返回-1
2. 注意object为空的情况
【k】lastIndexOf(Object object) {} 从list后面开始查找是否包含某个元素。
1. 实现原理： 倒序循环遍历数组，使用equals方法判断是否相等，找到返回对应的下标索引，未找到返回-1
2. 注意object为空的情况
五、测试
package com.wsh.arraylist;
/**
* 测试自定义ArrayList
*
* @author weishihuai
* @date 2018/9/25
*/
public class TestCustomArrayList {
public static void main(String[] args) {
CustomArrayList customArrayList = new CustomArrayList();
/***********************************add(object)***************************************/
customArrayList.add("aaa");
customArrayList.add("bbb");
customArrayList.add("ccc");
customArrayList.add("ddd");
/***********************************size()********************************************/
//4
System.out.println(customArrayList.size());
/***********************************isEmpty()*****************************************/
//false
System.out.println(customArrayList.isEmpty());
/***********************************get(index)****************************************/
//Exception in thread "main" java.lang.IllegalArgumentException: 数组下标索引非法，下标越界
//System.out.println(customArrayList.get(10));
//ccc
System.out.println(customArrayList.get(2));
/***********************************remove(index)*************************************/
//ccc
System.out.println(customArrayList.remove(2));
//3
System.out.println(customArrayList.size());
//true
System.out.println(customArrayList.remove("bbb"));
//2
System.out.println(customArrayList.size());
/***********************************set(index,object)*********************************/
//ddd
System.out.println(customArrayList.get(1));
//ddd
System.out.println(customArrayList.set(1, "1111"));
//1111
System.out.println(customArrayList.get(1));
/***********************************add(index,object)*********************************/
customArrayList.add(1, "2222");
//2222
System.out.println(customArrayList.get(1));
for (int i = 0; i < customArrayList.size(); i++) {
//aaa=====2222=====1111=====
System.out.print(customArrayList.get(i) + "=====");
System.out.println();
}
/***********************************indexOf(object)************************************/
//1
System.out.println(customArrayList.indexOf("2222"));
//-1
System.out.println(customArrayList.indexOf("abcdef"));
/***********************************lastIndexOf(object)********************************/
//0
System.out.println(customArrayList.lastIndexOf("aaa"));
}
}
至此，我们已经通过模拟ArrayList源码自定义了一个简单的List,虽然只实现了一部分方法，但对于我们理解ArrayList底层是怎么实现的应该会有一定的帮助。
六、总结
ArrayList集合类底层是通过数组实现的，具体的操作都是围绕数组展开，涉及数组拷贝、数组新增、数组删除元素等。本文是作者在看源码之后仿照源码实现的一个ArrayList,不能保证没有问题，只是帮助理解实现原理而已。仅供大家学习参考，一起学习一起进步。