乐趣区

JAVA基础整理四

<img src=”https://i.loli.net/2019/03/27…; alt=”” />

ArrayList 类

通过自定义的 arraylist 类与 jdk 源码里的 ArrayList 的实现的对比学习:

1. 所需的变量:

private Object[] elementData;
private int size;
private static final int DEFAULT_LENGTH=10;

private static final int DEFAULT_CAPACITY = 10;
transient Object[] elementData;
private int size;

(1)默认长度设置成 static final 因为这个是不随具体对象改变的,是属于类的通用不变属性。

(2)为什么要把核心数组定义成 transient 数据类型,大概是因为序列化和反序列化的过程类要自己做,不要用默认的,至于原因深入后再谈。

2. 构造函数

1. 无参构造

public MyList(){

elementData = new Object[DEALULT_LENGTH];

}

public ArrayList() {

this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;

}
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

无参构造可以定义成 static final,没必要每次都 new 一个新的空对象。

2. 传入 length 的构造

public MyList(int length){

elementData = new Object[length];

}

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);
}

}

对 length 进行判断,大于 0 的情况处理一样的,等于 0 的话还是调用了静态的那个空对象,小于 0 抛出非法长度的异常。

3. 增加元素

public void add(E obj){

Object[] newArray;
if(size == elementData.length) {newArray = new Object[elementData.length + (elementData.length >> 1)];
    System.arraycopy(elementData, 0, newArray, 0, elementData.length);
    elementData=newArray;
}
    elementData[size++]=obj;

}

public boolean add(E e) {

ensureCapacityInternal(size + 1);  // Increments modCount!!
elementData[size++] = e;
return true;

}

add 的差别比较大,MyList 的简单逻辑:判断目前存的 size 与 elementData 的长度的大小,如果 size 等于开的长度的话,再存进去会溢出,所以需要数组扩容,扩容的基本步骤:开一个新的数组,长度是原来的 1.5 倍(>>1 就是加上了一半,这样运算快点),将原来数组的东西拷贝到新数组的前面,将新数组指向 elementData 数组,把 obj 存进新数组里。

源码的逻辑多了几层判断,最终的扩容操作逻辑也是大同小异的:

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);

}

4. 删除元素

public void remove(int index){

for(int i=index+1;i<elementData.length;i++){elementData[i-1] = elementData[i];
}
size--;

}

将 index 后的元素前移一位,size–;

public E remove(int index) {

rangeCheck(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;

}

源码里 remove 后返回了删除的值,并且多了一个 rangecheck 的函数进行 index 判断,因为这个功能很多地方都可以用到,相似的。

private void rangeCheck(int index) {

if (index >= size)
    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));

}

移动使用的是 for 循环,源码使用了 copy 方法,做一个时间的测试:

5. 修改元素

public void set(int index,E obj){

elementData[index]=obj;

}

public E set(int index, E element) {

rangeCheck(index);

E oldValue = elementData(index);
elementData[index] = element;
return oldValue;

}

也是多了一个 rangecheck 的判断,然后返回了旧的的 value。

<h4>6. 查找元素 </h4>

public E get(int index){

return (E)elementData[index];

}

public E get(int index) {

rangeCheck(index);
checkForComodification();
return ArrayList.this.elementData(offset + index);

}

差别不大,就是返回 elementdata 的 index 元素。

退出移动版