自定义MyArrayList

PS：如果觉得文章有什么地方写错了，哪里写得不好，或者有什么建议，欢迎指点。

ArrayList 类提供了 List ADT 的可增长数组的实现。

一、自定义实现的 ArrayList 类 MyArrayList

源码链接：戳此进GitHub查看

MyArrayList 泛型类实现了 Iterable 接口从而可以拥有增强 for 循环（for each 循环）。

public class MyArrayList<AnyType> implements Iterable<AnyType> {
@Override
public Iterator<AnyType> iterator() {
return new ArrayListIterator();
}
}
复制代码

1. 类属性

MyArrayList 是基于数组实现的，其属性有：

private static final int DEFAULT_CAPACITY = 10;
private int theSize;
private AnyType[] theArrays;
复制代码

其中常量 DEFAULT_CAPACITY 表示数组的基础容量。theSize 表示数组表当前长度（数组元素个数），作索引时，A[theSize - 1] 表示数组的最后一个元素，而 A[theSize] 表示新添加的项可以被放置的位置。泛型数组 theArrays 为 MyArrayList 类的数组实现，即对 MyArrayList 对象的操作实际为对数组 theArrays 的操作。

2. 构造方法

当实例化 MyArrayList 对象时，调用构造方法：

public MyArrayList(){
theArrays = (AnyType[])new Object[DEFAULT_CAPACITY];
doClear();
}
复制代码

在构造方法中先实例化泛型数组 theArrays。由于泛型数组的创建是非法的，所以我们需要创建一个泛型类型限界的数组；即创建一个 Object[] 类型的数组，然后向泛型类型数组 AnyType[] 强制转型。

然后调用 doClear() 方法对数组表进行清空、初始化的操作，此方法仅类内部可调用：

private void doClear(){
theSize = 0;
expandCapacity(DEFAULT_CAPACITY);
}
复制代码

此处先设置 theSize = 0，然后调用 expandCapacity() 方法改变数组容量为基础容量。（在 expandCapacity() 方法的实现中，若扩充的容量（参数）小于 theSize 时表示非法的操作。）

3. 成员方法

数组扩容方法 expandCapacity() ：

public void expandCapacity(int newCapacity){
if (newCapacity < theSize){
return;
}
// 数组容量的扩充:
AnyType[] newArrays = (AnyType[])new Object[newCapacity];
// 利用 System.arraycopy() 方法拷贝数组
System.arraycopy(theArrays,0,newArrays,0,theSize);
theArrays = newArrays;
}
复制代码

System.arraycopy() 方法: public static native void arraycopy(Object src, int srcPos, Object dest, int destPos, int length);

get 方法的实现

/**
* 根据下标得到数组元素的值
*/
public AnyType get(int idx){
if (idx <0 || idx >= theSize){
throw new ArrayIndexOutOfBoundsException();
}
return theArrays[idx];
}
复制代码

set 方法的实现

/**
* 根据下标设置数组元素的值
* 返回该下标元素的原值
*/
public AnyType set(int idx,AnyType newVal){
if (idx <0 || idx >= theSize){
throw new ArrayIndexOutOfBoundsException();
}
AnyType oldVal = theArrays[idx];
theArrays[idx] = newVal;
return oldVal;
}
复制代码

add 方法的实现

 /**
* 根据下标向数组插入新元素
*/
public boolean add(int idx,AnyType newVal){
// 当 idx=theSize 时，在 A[theSize] 位置处插入元素
if (idx < 0 || idx > theSize){
throw new ArrayIndexOutOfBoundsException();
}
// 数组满时扩充容量
if (theArrays.length == theSize){
expandCapacity(theSize*2 + 1);
}
// 数组元素后移
for (int i=theSize;i>idx;i--){
theArrays[i] = theArrays[i-1];
}
theArrays[idx] = newVal;
theSize++;
return true;
}
/**
* 在数组末尾插入新元素
*/
public boolean add(AnyType newVal){
add(theSize,newVal);
return true;
}
复制代码

remove 方法的实现

/**
* 根据下标删除元素
* 返回被删除的元素
*/
public AnyType remove(int idx){
if (idx < 0 || idx >= theSize){
throw new ArrayIndexOutOfBoundsException();
}
// 数组元素前移
AnyType removedElem = theArrays[idx];
for (int i = idx; i < theSize-1; i++) {
theArrays[i] = theArrays[i+1];
}
theSize--;
return removedElem;
}
复制代码

4. Iterator 迭代器

关于 Iterator 接口

实现 Iterable 接口的集合必须提供 iterator 方法，该方法返回一个 Iterator （java.util.Iterator）类型的对象:

public interface Iterator<AnyType> {
boolean hasNext();
AnyType next();
void remove();
}
复制代码

即每个集合均可通过 iterator 方法创建并返回给客户一个实现 Iterator 接口的对象，并把 当前位置 的概念在对象内部存储下来。根据当前位置项每次调用 hasNext() 来判断是否存在下一项，调用 next() 来给出下一项，而 remove() 方法则删除由 next() 方法最新返回的项（即当调用一次 remove() 后，直到对 next() 再调用一次后才能调用 remove() 方法）。例：

public static <AnyType> void print(Collection<AnyType> coll){
Iterator<AnyType> itr = coll.iterator();
while(itr.hasNext()){
AnyType item = itr.next();
System.out.println(item);
// itr.remove();
}
}
复制代码

Java 中的增强 for 循环（for each）底层即是通过这种迭代器模式来实现的，当使用增强 for 循环时也就是间接的使用 Iterator。

MyArrayList 中 Iterator 的实现

import java.util.Iterator;
import java.util.NoSuchElementException;
public class MyArrayList<AnyType> implements Iterable<AnyType> {
......
@Override
public Iterator<AnyType> iterator() {
return new ArrayListIterator();
}
private class ArrayListIterator implements Iterator<AnyType>{
// 初始时当前位置为 0
private int current = 0;
@Override
public boolean hasNext() {
return current < theSize;
}
@Override
public AnyType next() {
if (!hasNext()){
throw new NoSuchElementException();
}
return theArrays[current++];
}
@Override
public void remove() {
/* 因为 remove() 方法有相同的，MyArrayList.this 表示外部类当前对象的一个引用 */
MyArrayList.this.remove(--current);
}
}
}
复制代码

iterator() 方法直接返回 ArrayListIterator 类的一个实例，该类是一个实现 Iterator 接口的类。ArrayListIterator 存储当前位置的概念，并提供 hasNext()、next()、remove() 的实现。当前位置 表示要被查看的下一元素（的数组下标），因此初始化当前位置为 0。

其中，泛型类 ArrayListIterator 是一个 内部类，使用内部类的目的及优点：

1. next() 方法中使用当前位置作为下标访问数组元素然后将当前位置向后推进，而迭代器中是没有数组的，使用内部类可以访问外部类的域 theArrays；
2. theArrays 是 MyArrayList 的私有域，使用内部类访问可以很好的满足面向对象编程的基本原则，即让数据尽可能地隐藏；
3. 满足迭代器 Iterator 的特性，即当集合（外部类）不存在的时候，迭代器（内部类）也是不存在的。

二、MyArrayList 类各方法的算法分析

因为 ArrayList 是基于数组实现的，所以和数组相似：ArrayList 的 get() 和 set() 方法花费常数时间 O(1)；而使用 add() 和 remove() 方法时为了保持内存数据的连续性，需要做大量的数据搬移工作，其花费的时间代价为 O(n)。