从小白的角度学习ArrayList

2018-02-03 10:48:22来源:oschina作者:葩_人点击

分享
从小白的角度学习ArrayList

自我介绍一下~小白一枚(其实就是刚工作206天),从今开始将以java小白的视角和大家一起学习java,与大家一同进步。大神勿喷哈~


ArrayList简单介绍
首先我们来简单认识一下ArrayList,相信大家都知道,ArrayList是一个可存储重复元素、无序的集合;它的底层实现为数组,查询快、增删慢,线程不安全;
ArrayList和数组最大区别是数组的长度是固定的,并且只能存储相同类型的元素,而ArrayList是可动态扩容的,并且能存储不同类型的元素,这里需要注意的是ArrayList只能存储引用数据类型,不能存储基本数据类型~
都说ArrayList查询快、增删慢,那为什么查询快、增删慢呢?因为ArrayList的底层实现是数组,相对于数组而言,你只需要告诉它一个下标就能快速定位到你想要的元素,所以ArrayList查询快;而新增一个元素,假设此时数组中有100个元素,你新增的元素要反正第0个下标的位置,那么久需要将第0个至100个元素依次往后移一个位置;删除则相反,需要将删除的元素后面的元素全部向前依次移一个位置;元素越多,移动的次数也越多,所以说ArrayList的增删慢。

ArrayList简单实现

笔者在闲暇时间自己写了一个MyArrayList,在这里和大家分享一下笔者的思路。


1、既然ArrayList底层是数组结构,那么其内部肯定维护了一个数组,并且还需要一个变量来记录集合中元素的个数。不多说,上代码~


public class MyArrayList {
private Object[] data; //内部维护的数组
private int size; //集合中元素的个数
/**
* 无参数构造器默认给集合10个长度的容量
*/
public MyArrayList() {
data = new Object[10];
}
/**
* 手动设置集合的容量
*/
public MyArrayList(int capacity) {
data = new Object[capacity];
}
}

2、这里需要注意的是,数组的长度不等于集合中的元素!那么基本的结构搭好了,那么我们就来实现add的方法吧。


/**
* 添加一个元素
*/
public boolean add(Object obj) {
/**
* 每次添加元素时都要判断是否需要扩容
* 这里传size + 1 是因为是需要判断添加一个元素以后集合的元素是否超过数组的长度
*/
expansion(size + 1);
/**
* 将元素保存进数组的第size个下标中,并且size加1
* 这里注意是size++而不是++size,如果不理解可以写成:
* data[size] = obj;
* size += 1;
*/
data[size++] = obj;
/**
* ArrayList是可以有重复元素的,所以返回true;
*/
return true;
}
/**
* 添加一个元素至指定下标
*/
public boolean add(Object obj, int index) {
/**
* 首先要判断下标是否越界
*/
rangeCheck(index);
expansion(size + 1);// 判断是否需要扩容
/**
* 这一步是将下标index之后的元素往后移一个位置
* System.arraycopy方法5个参数的意思分别为:
* 源数组、重源数组中的第几个下标开始复制、目标数组、目标数组的第几个下标开始复制,复制元素的个数
* 不理解这个方法的同学可以写成:
* for (int i = size; i >= index; i--) {
data[i + 1] = data [i];
}
*/
System.arraycopy(data, index, data, index + 1, size - index);
/**
* 将obj对象赋值到index下标的位置
*/
data[index] = obj;
/**
* 元素个数加1
*/
size++;
return true;
}
/**
* 检查索引是否越界
*/
private void rangeCheck(int index) {
if (index > size || index < 0) {
throw new RuntimeException("索引越界");
}
}
/**
* 扩容
*/
private void expansion(int capacity) {
/**
* 首先我们判断集合的容量是否大于数组的长度,大于就扩容,不大于什么都不用做
*/
int lenth = data.length;
if (capacity > lenth) {
/**
* 这里我们new出一个新的数组,并且新数组的长度是原数组长度的1.5倍
* lenth >> 1 是将 lenth右移一位,相对于 lenth / 2
*/
Object[] newData = new Object[lenth + (lenth >> 1)];
/**
* 将源数组的元素复制到新数组上
*/
System.arraycopy(data, 0, newData, 0, data.length);
/**
* 将新数组的对象引用地址赋给data
*/
data = newData;
}
}

3、接下来实现我们的remove和size方法吧~


/**
* 返回集合元素个数、直接返回size
*/
public int size() {
return this.size;
}

public Object remove(int index){
/**
* 首先要判断下标是否越界
*/
rangeCheck(index);
/**
* 获取index下标的元素并返回出去
*/
Object obj = data[index];
/**
* 得到index下标后面还有几个元素,如果大于0则将index下标后面的元素往前依次移一个位置
*/
int limit = size - 1 - index;
if(limit > 0){
System.arraycopy(data, index + 1, data, index, limit);
}
/**
* 将第size个元素置空
*/
data[--size] = null;

return obj;
}

4、ArrayList基本的方法就全部实现了,有兴趣的同学可以对比着看一下jdk的源码,它里面考虑的东西更多哦~



第一次写博客,如有不正确的地方请各位大佬指正~小白们一起学习一起进步~


我们的征途岂是星辰大海

微信扫一扫

第七城市微信公众平台