手写ArrayList实现基本功能
2021/7/17 23:06:10
本文主要是介绍手写ArrayList实现基本功能,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
手写ArrayList实现基本功能
文章目录
- 手写ArrayList实现基本功能
- 概述
- 手写内容
- 构造器
- 成员变量和常量
- 添加-add方法
- 扩容-ensureExplicitCapacity(size + 1);
- System.arraycopy
- rangeCheck(int index)
- 删除元素 remove
- get() getsize()
- 完整手写源码
概述
List是一种线性的列表结构,继承自Collection接口,是一种有序集合。
ArrayList是用数组来实现的List
- 随机访问效率高
- 读快写慢 写的过程涉及元素的移动因此写操作的效率比较低。
直接看源码可得
public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
AbstractList:大部分List集合的共同父类,提供了一些基本的方法和封装,以及通用的一些Api
List:列表标准接口,列表是一个有序集合,又被称为序列,该接口对内部的每一个元素的插入位置都有精确控制
RandomAccess:一个标记性质的随机访问接口,没有提供任何方法,如果一个类实现这个接口,表示这个类用索引比迭代器更快
Cloneable:标记可克隆对象 ,没有实现该接口的对象在调用Object.clone()方法时会抛出异常 分为浅拷贝和深拷贝 这里默认都是浅拷贝
java.io.Serializable:序列化标记接口 被此接口标记的类 可以实现Java序列化和反序列化
手写内容
构造器
- 一个默认的构造器 默认创建大小为10的数组
- 一个可以自定义创建的构造函数 但是需要对参数校验 不能为负
/** * 指定数组初始容量 * @param initialCapacity */ public MyArrayList(int initialCapacity){ if(initialCapacity < 0){ throw new IllegalArgumentException("初始容量不能小于0"); } elementData = new Object[initialCapacity]; } /** * 默认初始化容量为10 */ public MyArrayList(){ this(DEFAULT_CAPACITY); }
成员变量和常量
elementData是一个对象数组 用来存储数据的
DEFAULT_CAPACITY则是和ArrayList的默认大小一样为10
size则是实际ArrayList的大小
/** * 定义默认的数组容量 */ private final static int DEFAULT_CAPACITY = 10; /** * 底层采用数组存放数据 */ private Object[] elementData; /** * 实际ArrayList的大小 */ private int size;
添加-add方法
- 添加数据前 需要进行判断 当前的数组容量是否需要扩容 也就是ensureExplicitCapacity方法
public void add(Object object){ //判断实际存放的数据容量是否大于elementData容量 ensureExplicitCapacity(size + 1); elementData[size++] = object; } public void add(int index, Object object){ //判断实际存放的数据容量是否大于elementData容量 ensureExplicitCapacity(size + 1); //数组拷贝 System.arraycopy(elementData, index,elementData, index + 1, size - index); elementData[index] = object; size ++; }
扩容-ensureExplicitCapacity(size + 1);
-
ArrayList的扩容规则是变成原来最大容量的1.5倍+1
-
源码中的扩容采用的是位运算,通过右移运算符>> 事实上就是oldCapacity/2 只不过这样运算更加快
-
为什么需要传入的时候size + 1呢 因为如果传入的第一个大小为1 进行扩容的时候 最终还是为1 这样就会发生异常 因此通过+1可以防止这种情况发生 源码里也正是这样做的
if(newCapacity - minCapacity < 0){ newCapacity = minCapacity; }
是为了保证最小容量要和minCapacity 相同 假使自定义时的容量为1 +1以后变成2 但是经过位运算以后 1 + 1>>1 为1.5还是1 扩容事实上是失败的 出现java.lang.ArrayIndexOutOfBoundsException异常 而加个if判断和赋值 保证一个最小容量 也就是 初始为1 时 1+ 1传入后 minCapacity = 2 此时判断为负 执行newCapacity = minCapacity 这是新数组的长度就为2 就可以正常插入数据
-
copyOf方法
最终还是调用了System.arraycopy 这个方法后面说
/** * 扩容 * @param minCapacity 最小的扩容量 当前的size + 1 */ private void ensureExplicitCapacity(int minCapacity){ if(size == elementData.length){ // int newCapacity = 2 * size; //源码中的扩容 int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //至少保证最小容量和minCapacity相同 if(newCapacity - minCapacity < 0){ newCapacity = minCapacity; } //将老数组的值赋值到新的数组 elementData = Arrays.copyOf(elementData,newCapacity); // Object[] newObjects = new Object[newCapacity]; // for (int i = 0; i < elementData.length; i++) { // newObjects[i] = elementData[i]; // // } // elementData = newObjects; } }
System.arraycopy
System.arraycopy 是Java标准类库提供的static方法,用它复制数组比用for循环快很多。System.arraycopy针对所有类型都做了重载
public static void arraycopy(Object src, int srcPos, Object dest, int destPos, int length) Object src : 原数组 int srcPos : 从元数据的起始位置开始 Object dest : 目标数组 int destPos : 目标数组的开始起始位置 int length : 要copy的数组的长度
rangeCheck(int index)
判断下标是否越界
/** * 判断下标是否越界 * @param index */ private void rangeCheck(int index) { if (index < 0 || index >= this.size) { throw new IndexOutOfBoundsException("下标越界"); } }
删除元素 remove
public Object remove(int index)
-
先判断下标是否越界
-
然后计算需要删除的元素后面的长度numMoved
假设有 1 2 3 4 5 五个数,分别对应下标 0 1 2 3 4 当前的size就为5 需要删除下标为2 的 则说明需要起始移动的为5 -2 -1 也就是说明删除元素后面的长度为2
System.arraycopy上面也介绍了
-
复制结束以后 将最后一位的元素置为null 也就是–size
remove(Object o)
- for循环遍历是否等于当前下标的元素
- 相等就执行remove(index)
- 未找到就返回false
/** * 删除元素 * @param index * @return */ public Object remove(int index){ rangeCheck(index); //使用下标查询值是否存在 Object oldObject = get(index); //计算后面删除元素后面的长度 int numMoved = size - index - 1; //删除原理 arraycopy 往前移动数据 将最后一个置为空 if(numMoved > 0){ System.arraycopy(elementData, index + 1,elementData, index, numMoved); } elementData[--size] = null; return oldObject; } /** * 删除相同元素 取第一个删除 * @param o * @return */ public boolean remove(Object o){ for (int index = 0; index < size; index++) { Object val = elementData[index]; if (val.equals(o)) { remove(index); return true; } } return false; }
get() getsize()
- 判断越界
- 直接返回数组
- 直接返回size大小
/** * 使用下标获取元素 * @param index * @return */ public Object get(int index){ rangeCheck(index); return elementData[index]; } /** * 当前大小 * @return */ public int getSize(){ return size; }
完整手写源码
package com.bluedot; import com.sun.org.apache.bcel.internal.generic.RETURN; import java.util.Arrays; /** * @author Yu W * @version V1.0 * @ClassName * @Description: * @date 2021/7/17 19:50 */ public class MyArrayList { /** * 定义默认的数组容量 */ private final static int DEFAULT_CAPACITY = 10; /** * 底层采用数组存放数据 */ private Object[] elementData; /** * 实际ArrayList的大小 */ private int size; /** * 指定数组初始容量 * @param initialCapacity */ public MyArrayList(int initialCapacity){ if(initialCapacity < 0){ throw new IllegalArgumentException("初始容量不能小于0"); } elementData = new Object[initialCapacity]; } /** * 默认初始化容量为10 */ public MyArrayList(){ this(DEFAULT_CAPACITY); } /** * 1.判断实际存放的数据容量是否大于elementData * 2.直接使用下标进行赋值 * * @param object */ public void add(Object object){ //判断实际存放的数据容量是否大于elementData容量 ensureExplicitCapacity(size + 1); elementData[size++] = object; } /** * * @param index * @param object */ public void add(int index, Object object){ //判断实际存放的数据容量是否大于elementData容量 ensureExplicitCapacity(size + 1); System.arraycopy(elementData, index,elementData, index + 1, size - index); elementData[index] = object; size ++; } /** * 扩容 * @param minCapacity 最小的扩容量 当前的size + 1 */ private void ensureExplicitCapacity(int minCapacity){ if(size == elementData.length){ // int newCapacity = 2 * size; //源码中的扩容 int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); //至少保证最小容量和minCapacity相同 if(newCapacity - minCapacity < 0){ newCapacity = minCapacity; } //将老数组的值赋值到新的数组 elementData = Arrays.copyOf(elementData,newCapacity); // Object[] newObjects = new Object[newCapacity]; // for (int i = 0; i < elementData.length; i++) { // newObjects[i] = elementData[i]; // // } // elementData = newObjects; } } /** * 使用下标获取元素 * @param index * @return */ public Object get(int index){ rangeCheck(index); return elementData[index]; } /** * 判断下标是否越界 * @param index */ private void rangeCheck(int index) { if (index < 0 || index >= this.size) { throw new IndexOutOfBoundsException("下标越界"); } } /** * 当前大小 * @return */ public int getSize(){ return size; } /** * 删除元素 * @param index * @return */ public Object remove(int index){ rangeCheck(index); //使用下标查询值是否存在 Object oldObject = get(index); //计算后面删除元素后面的长度 int numMoved = size - index - 1; //删除原理 arraycopy 往前移动数据 将最后一个置为空 if(numMoved > 0){ System.arraycopy(elementData, index + 1,elementData, index, numMoved); } elementData[--size] = null; return oldObject; } /** * 删除相同元素 取第一个删除 * @param o * @return */ public boolean remove(Object o){ for (int index = 0; index < size; index++) { Object val = elementData[index]; if (val.equals(o)) { remove(index); return true; } } return false; } }
这篇关于手写ArrayList实现基本功能的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南