思路：
一 载体
ArrayList是一个集合容器，必然要有一个保存数据的载体。
public class MyArraylist {
private final static int INIT_COUNT = 10;
Object[] arrays;
public MyArraylist() {
this(INIT_COUNT);
}
public MyArraylist(int count) {
arrays = new Object[count];
}
}
二属性
长度
得到集合会初始化一个数组长度，集合的元素个数不能是数组长度。
public class MyArraylist2 {
private int size;
public int size(){
return size;
}
}
三方法
增删改查
增加
按默认索引加入元素，按索引加入元素，加入单个元素，加入批量元素。这里只举按单个加入元素的例子。
首先需要判断索引是否非法
public void checkIndexRange(int index) {
if (index > size) {
throw new IndexOutOfBoundsException("数组越界");
}
}
public void checkIndexRangeForAdd(int index) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("数组越界");
}
}
判断当前数组是否需要扩容。如果索引大于当前数组长度，按当前长度的50%增加。并将当前数组复制到新的数组。
public void checkIndex(int index) {
if (index > arrays.length) {
int oldLength = size;
int newLength = oldLength + (index >> 1);
arrays = Arrays.copyOf(arrays, newLength);
}
}
增加单个元素
public void add(Object obj, int index) {
checkIndexRangeForAdd(index);//判断索引是否非法
checkIndex(size + 1);//判断数组是否需要扩容
System.arraycopy(arrays, index, arrays, index + 1, size - index);
arrays[index] = obj;
size++;
}
public boolean add(Object obj) {
checkIndex(size + 1);//判断数组是否需要扩容
arrays[size++] = obj;
return true;
}
获取元素
public T get(int index) {
checkIndexRangeForAdd(index);
return (T) arrays[index];
}
更新元素
public T set(Object obj, int index) {
checkIndexRange(index);
T t = (T) arrays[index];
arrays[index] = obj;
return t;
}
删除元素
public T remove(int index) {
checkIndexRange(index);
T t = (T) arrays[index];
int moveLength = size - index - 1;
if (moveLength > 0) {
System.arraycopy(arrays, index + 1, arrays, index, moveLength);
}
arrays[--size] = null;
return t;
}
四迭代
使用增强型for循环迭代输出，以及Java 8引进的lambda表达式实现foreach。
首先生成一个迭代器。
private class MyArrayListIterator implements Iterator<T> {
private int count;
public boolean hasNext() {
return count != size;
}
public T next() {
checkModcount();
return (T) arrays[count++];
}
}
然后继承Iterable接口。
public class MyArraylist2<T> implements Iterable<T>{
@Override
public Iterator<T> iterator() {
return new MyArrayListIterator();
}
}
五线程安全问题
ArrayList没有实现线程安全，但是在迭代的时候，不允许修改。
ArrayList使用一个成员变量modCount在迭代开始的时候记录ArrayList正在做修改(增加，修改，删除)的数量，然后在每迭代一行的时候，去比较modCount是否发生变化。如果发生变化，证明此刻有其它的线程或者就是本线程就对它进行修改，然后抛出异常。
定义modcount变量。
private transient int modcount;
在增加，修改，删除的时候，均需将此值加1。
public boolean add(Object obj) {
checkIndex(size + 1);
modcount++;//加1
arrays[size++] = obj;
return true;
}
public void checkIndex(int index) {
if (index > arrays.length) {
modcount++;//加1
int oldLength = size;
int newLength = oldLength + (index >> 1);
arrays = Arrays.copyOf(arrays, newLength);
}
}
public T set(Object obj, int index) {
checkIndexRange(index);
modcount++;//加1
T t = (T) arrays[index];
arrays[index] = obj;
return t;
}
public T remove(int index) {
checkIndexRange(index);
modcount++;//加1
@SuppressWarnings("unchecked")
T t = (T) arrays[index];
int moveLength = size - index - 1;
if (moveLength > 0) {
System.arraycopy(arrays, index + 1, arrays, index, moveLength);
}
arrays[--size] = null;
return t;
}
在迭代的时候，将此值赋给另一个变量exceptCount。然后再每迭代一行的时候，将exceptCount与modcount比较。
private class MyArrayListIterator implements Iterator<T> {
private int exceptCount = modcount;
public void checkModcount() {
if (exceptCount != modcount) {
throw new ConcurrentModificationException();
}
}
}
最后实现的全部代码
package com.skycomm.sdf; import java.util.Arrays;
import java.util.ConcurrentModificationException;
import java.util.Iterator; public class MyArraylist<T> implements Iterable<T> { private final static int INIT_COUNT = 10; private int size = 0; private transient int modcount; Object[] arrays; public MyArraylist() {
this(INIT_COUNT);
} public MyArraylist(int count) {
arrays = new Object[count];
} public void add(Object obj, int index) {
checkIndexRangeForAdd(index);
checkIndex(size + 1);
System.arraycopy(arrays, index, arrays, index + 1, size - index);
arrays[index] = obj;
size++;
} public boolean add(Object obj) {
checkIndex(size + 1);
modcount++;//加1
arrays[size++] = obj;
return true;
} public void checkIndex(int index) {
if (index > arrays.length) {
modcount++;//加1
int oldLength = size;
int newLength = oldLength + (index >> 1);
arrays = Arrays.copyOf(arrays, newLength);
}
} public T get(int index) {
checkIndexRangeForAdd(index);
return (T) arrays[index];
} public T remove(int index) {
checkIndexRange(index);
modcount++;//加1 @SuppressWarnings("unchecked")
T t = (T) arrays[index];
int moveLength = size - index - 1;
if (moveLength > 0) {
System.arraycopy(arrays, index + 1, arrays, index, moveLength);
}
arrays[--size] = null;
return t;
} public T set(Object obj, int index) {
checkIndexRange(index);
modcount++;//加1
T t = (T) arrays[index];
arrays[index] = obj;
return t;
} public void checkIndexRange(int index) {
if (index > size) {
throw new IndexOutOfBoundsException("数组越界");
}
} public void checkIndexRangeForAdd(int index) {
if (index > size || index < 0) {
throw new IndexOutOfBoundsException("数组越界");
}
} public int size() {
return size;
} public boolean isEmpty() {
return size == 0;
} public String toString() {
Iterator<T> it = iterator();
if (!it.hasNext())
return "[]"; StringBuilder sb = new StringBuilder();
sb.append('[');
for (;;) {
T e = it.next();
sb.append(e == this ? "(this Collection)" : e);
if (!it.hasNext())
return sb.append(']').toString();
sb.append(',').append(' ');
}
} public Iterator<T> iterator() {
return new MyArrayListIterator();
} private class MyArrayListIterator implements Iterator<T> { private int count; private int exceptCount = modcount; public boolean hasNext() {
return count != size;
} public T next() {
checkModcount();
return (T) arrays[count++];
} public void checkModcount() {
if (exceptCount != modcount) {
throw new ConcurrentModificationException();
}
} } }