ArrayList简介
ArrayList是一个动态数组，Array的复杂版本，它提供了动态的增加和减少元素，实现了ICollection和IList接口，灵活的设置数组的大小等好处，ArrayList不是线程安全的。
MyArrayList
在实现MyArrayList前先实现MyList，MyAbstractList，他们的关系如下。
MyArrayList--->（继承于）MyAbstractList--->（实现）MyList接口--->（实现）java.lang.Iterable接口
通过编写新的ArrayList来实现java中ArrayList的部分功能
MyList接口定义如下
public interface MyList<E> extends Iterable<E> {
public void add(E e);
public void add(int index, E e);
public void clear();
public boolean contains(E e);
public E get(int index);
public int indexOf(E e);
public boolean isEmpty();
public int lastIndexOf(E e);
public boolean remove(E e);
public E remove(int index);
public E set(int index, E e);
public int size();
}
MyAbstractList类定义如下
public abstract class MyAbstractList<E> implements MyList<E> {
protected int size = 0;
protected MyAbstractList() {
}
protected MyAbstractList(E[] objects) {
for(int i = 0; i < objects.length; i++) {
add(objects[i]);
}
}
@Override
public void add(E e) {
add(size, e);
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public int size() {
return size;
}
@Override
public boolean remove(E e) {
if(indexOf(e) >= 0) {
remove(indexOf(e));
return true;
}else {
return false;
}
}
}
MyArrayList定义如下
import java.util.Iterator;
public class MyArrayList<E> extends MyAbstractList<E> {
public static final int INITIAL_CAPACITY = 16;//初始容量
private E[]data = (E[])(new Object[INITIAL_CAPACITY]);;
public MyArrayList() {
}
public MyArrayList(int length) {
if(length >= 0) {
data = (E[])(new Object[length]);
}
}
public MyArrayList(E[] objects) {
for(int i = 0; i < objects.length; i++) {
add(objects[i]);
}
}
@Override
public void add(int index, E e) {
// TODO Auto-generated method stub
ensureCapacity();
for(int i = size - 1; i >= index; i--) {//将data[index]和后面的元素往后移动一位
data[i + 1] = data[i];
}
data[index] = e;
size++;
}
//判断容量满时，新建一个容量为原来两倍+1的数组
private void ensureCapacity() {
if(size >= data.length) {
E[] newData = (E[])(new Object[size * 2 + 1]);//java源码扩容1.5倍＋1
System.arraycopy(data, 0, newData, 0, size);
data = newData;
}
}
@Override
public void clear() {
// TODO Auto-generated method stub
data = (E[])(new Object[INITIAL_CAPACITY]);
size = 0;
}
@Override
public boolean contains(E e) {
// TODO Auto-generated method stub
for(int i = 0; i < size; i++) {
if(e.equals(data[i])) {
return true;
}
}
return false;
}
@Override
public E get(int index) {
// TODO Auto-generated method stub
checkIndex(index);//判断下标是否合法
return data[index];
}
private void checkIndex(int index) {
if(index < 0 || index >= size) {
throw new IndexOutOfBoundsException("index " + index + " out of bounds");
}
}
@Override
public int indexOf(E e) {
// TODO Auto-generated method stub
for(int i = 0; i < size; i++) {
if(e.equals(data[i])) {
return i;
}
}
return -1;
}
@Override
public int lastIndexOf(E e) {
// TODO Auto-generated method stub
for(int i = size - 1; i >= 0; i--) {
if(e.equals(data[i])) {
return i;
}
}
return -1;
}
@Override
public E remove(int index) {
// TODO Auto-generated method stub
checkIndex(index);//判断下标是否合法
E e = data[index];//获取删除对象的值
for(int i = index; i < size - 1; i++) {//将data[index]后面的元素往前移动一位
data[i] = data[i+1];
}
data[size] = null;//删除最后的元素
size--;
return e;
}
@Override
public E set(int index, E e) {
// TODO Auto-generated method stub
checkIndex(index);//判断下标是否合法
E old = data[index];
data[index] = e;
return old;
}
//重写java.lang.Object.toString方法，打印整个数组
@Override
public String toString() {
StringBuilder result = new StringBuilder("[");
for(int i = 0; i < size; i++) {
result.append(data[i]);
if(i < size - 1) {
result.append(",");
}
}
return result + "]";
}
//新建一个刚好等于size的数组，即将数组容量设为刚好足够存放的大小
public void trimToSize() {
if(size != data.length) {
E[] newData = (E[])(new Object[size]);
System.arraycopy(data, 0, newData, 0, size);
data = newData;
}
}
@Override
public Iterator<E> iterator() {
// TODO Auto-generated method stub
return new ArrayListIterator();
}
private class ArrayListIterator implements Iterator<E> {
private int current = 0;
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return (current < size);
}
@Override
public E next() {
// TODO Auto-generated method stub
return data[current++];
}
}
}
测试代码如下
public class TestMyArrayList {
public static void main(String[] args) {
// TODO Auto-generated method stub
// String[] ss = {"China","America","Germany","Canada","France","Germany"};
MyList<String> list = new MyArrayList<String>();
System.out.println("测试add(E e)方法和add(int index, E e)方法添加数据。");
list.add("America");
list.add(0,"China");
list.add("Canada");
list.add("France");
list.add(2,"Germany");
list.add("Germany");
System.out.println("通过toString()方法打印数组" + list.toString());
System.out.println("通过size()方法获取长度：" + list.size());
System.out.println("测试contains()方法：" + list.contains("France"));
System.out.println("通过get()方法获取指定下标的值：" + list.get(1));
System.out.println("通过indexOf()方法获取指定值的下标：" + list.indexOf("Germany"));
System.out.println("通过lastIndexOf()方法获取最后出现的指定值的下标：" + list.lastIndexOf("Germany"));
System.out.println("通过下标删除指定值：" + list.remove(5));
System.out.println("删除后的数组：" + list.toString());
System.out.println("通过set()方法修改值：" + list.set(2, "Russia"));
System.out.print("通过foreach遍历数组：");
for(String s:list) {
System.out.print(s.toUpperCase() + " ");
}
}
}
测试结果
思考：为什么MyArrayList类中的ensureCapacity()扩容倍数是2 * x + 1而不是2 * x？
因为如果我们创建了一个长度为0的数组，如果扩容倍数是2 * x，那么这个数组就无法扩容了。