Java基础面试题(18)----ArrayList集合源码解析
我们对ArrayList集合的源码进行解析,他是属于线性数据结构中的顺序存储结构,这里我们只是写出了增删改查的方法。
首先我们来看一下ArrayList的数据结构
- 底层实际上是一个数组,在增加元素的时候,对数组进行扩容,添加一个元素,容量增加1。
- 实际线性存储结构中的顺序存储的结构,每个位置的元素都有执行的索引,所以可以实现快速的查找元素。
用简单的图片展示,如下: - 但是当在指定位置添加元素的时候,后面位置的元素统一向后移动,效率较低,这里会调用系统的复制数组的方法,因为无法看到源码,所以内有办法深入研研究,这段代码如下:
- 移除元素的图片展示如下
//复制数组
System.arraycopy(elementData, index+1, elementData, index, numMoved);
那我们简单的看一下ArrayList的内部代码实现
package com.mainshi.mylist;
import java.io.Serializable;
import java.util.AbstractList;
import java.util.Arrays;
import java.util.List;
import java.util.RandomAccess;
public class MyArrayList<E> extends AbstractList implements List,RandomAccess,Cloneable,Serializable{
//首先定义成员变量
//静态常量值,UID
private static final long serialVersionUID = 8683452581122892189L;
//默认容量
private static final int DEFAULT_CAPACITY = 10;
//空的元素数据
private static final Object[] EMPTY_ELEMENTDATA = {};
//
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
//非序列化对象数组
transient Object[] elementData;
//长度
private int size;
//构造方法
public MyArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
public MyArrayList(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);
}
}
@Override//获取数值的方法
public Object get(int index) {
if(index>=size){
throw new IndexOutOfBoundsException();
}
return elementData[index];
}
//获取长度
@Override
public int size() {
return size;
}
//添加的方法
@Override
public boolean add(Object o) {
//扩容的方法
ensureCapacityInternal(size + 1);
//将新的元素赋值给最末尾的长度
elementData[size++]=o;
return true;
}
//扩容的方法
private void ensureCapacityInternal(int minCapacity) {
//三元运算符,如果现在的集合大小不等于默认的长度(构造函数有确认),最小扩容为0,
//如果相等,最小扩容为10
int minExpand=(elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)?0:DEFAULT_CAPACITY;
//输入的长度大于扩容的长度
if (minCapacity>minExpand){
ensureExplicitCapacity(minCapacity);
}
}
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
if (minCapacity-elementData.length>0){
grow(minCapacity);
}
}
//常见一个新的数组,长度比之前的数组加1;
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
//在指定的索引位置添加元素
public void add(int index,Object obj){
//数据合法性检查
rangCheck(index);
//扩容
ensureCapacityInternal(size + 1);
//赋值数组
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
//将元素装到对应位置
elementData[index] = obj;
//集合长度增加
size++;
}
private void rangCheck(int index) {
if (index>size || index<0){
throw new IndexOutOfBoundsException("指定元素的位置"+index+"超出集合的长度");
}
}
//移除指定位置的元素的方法
public E remove(int index){
//合法性检查
rangCheck(index);
//集合长度变化的监控
modCount++;
//提取指定位置的元素
E oldValue = elementData(index);
//指定位置的元素的个数
int numMoved = size - index - 1;
if (numMoved > 0)
//复制数组
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
//让垃圾收集器回收
elementData[--size] = null; // clear to let GC do its work
//将移除的元素返回
return oldValue;
}
//提取元素的方法
E elementData(int index) {
return (E) elementData[index];
}
//移除指定的对象
public boolean remove(Object object){
if (object==null){//如果执行对象为null
for (int index=0;index<size;index++){
if(elementData(index)==null){
fastRemove(index);
return true;
}
}
}else{//如果指定对象部位null
for (int index=0;index<size;index++){
if(elementData(index).equals(object)){
fastRemove(index);
return true;
}
}
}
return false;
}
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index,
numMoved);
elementData[--size] = null; // clear to let GC do its work
}
//修改元素的放法
public Object set(int index,Object object){
//范围检查
rangCheck(index);
//取出旧元素
Object oldValue = elementData(index);
//指定位置放入新的元素
elementData[index]=object;
//返回旧的元素
return oldValue;
}
}