图片来自网络
想要重写ArrayList，我认为要先弄清楚ArrayList源码的实现原理和JDKapi的文档解释。
一、JDKapi详解如下：
1、ArrayList的类分层结构如下：
- java.lang.Object
- java.util.AbstractCollection<E>
- java.util.AbstractList<E>
- java.util.ArrayList<E>
- java.util.AbstractList<E>
- java.util.AbstractCollection<E>
2、所有已实现的接口：
Serializable, Cloneable, Iterable<E>, Collection<E>, List<E>,RandomAccess
3、直接已知子类：
AttributeList, RoleList, RoleUnresolvedList
4、构造方法摘要：
**- ArrayList() **
构造一个初始容量为 10 的空列表。
ArrayList
public ArrayList(int initialCapacity)构造一个具有指定初始容量的空列表。
参数： initialCapacity - 列表的初始容量
抛出： IllegalArgumentException - 如果指定的初始容
**- ArrayList(Collection<? extends E> c) **
构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
ArrayList
public ArrayList()构造一个初始容量为 10 的空列表。
**- ArrayList(int initialCapacity) **
构造一个具有指定初始容量的空列表。
ArrayList
public ArrayList(Collection<? extends E> c)构造一个包含指定 collection 的元素的列表，这些元素是按照该 collection 的迭代器返回它们的顺序排列的。
参数： c - 其元素将放置在此列表中的 collection
抛出： NullPointerException - 如果指定的 collection 为 null量为负
二、重写ArrayList
1、定义ArrayList接口，封装重写的抽象方法，原则上是面向接口编程
代码如下：
public interface MyList<E> {
/**
* 向容器中添加一个元素
* @param element
*/
public void add(E element);
/**
* 向容器中添加一组元素
* @param arrayOfElements 元素的数组
*/
public void add(E[] arrayOfElements);
/**
* 删除指定的元素（首次出现的位置）
* @param e 待删除的元素
* @return 如果元素存在返回true否则返回false
*/
public boolean remove(E e);
/**
* 删除指定的元素
* @param e 元素
* @param allOccurence 如果为true则删除所有位置上的该元素否则只删除首次出现的位置
* @return 如果元素存在返回true否则返回false
*/
public boolean remove(E e, boolean allOccurence);
/**
* 删除指定位置的元素
* @param index 元素的位置（索引）
* @return 被删除的元素
*/
public E removeAtIndex(int index);
// public E[] removeOfRange(int start, int end);
/**
* 修改指定位置的元素
* @param index 元素的位置（索引）
* @param element 新元素
* @return 被修改的旧元素
*/
public E set(int index, E element);
// public boolean contains(E element);
/**
* 查找元素在容器中首次出现的位置
* @param element 元素
* @return 找到了返回元素首次出现的位置（索引）否则返回-1
*/
public int indexOf(E element);
/**
* 获取指定位置的元素
* @param index 元素的位置（索引）
* @return 元素
*/
public E get(int index);
/**
* 用指定的位置获取当前容器的子容器
* @param fromIndex 起始位置（包含）
* @param toIndex 终止位置（不包含）
* @return 子容器
*/
public MyList<E> subList(int fromIndex, int toIndex);
/**
* 是不是空容器
* @return 容器没有元素返回true否则返回false
*/
public boolean isEmpty();
/**
* 清空容器
*/
public void clear();
/**
* 容器的大小
* @return 容器中元素的个数
*/
public int size();
}
2、定义ArrayList实现类，继承ArrayList接口中的抽象方法
代码如下：
import java.util.Arrays;
public class MyArrayList<E> implements MyList<E> {
private static final int DEFAULT_INIT_SIZE = 1 << 4;
private static final Object[] DEFAULT_EMPTY_ARRAY = {};
private E[] elements = null;
private int size = 0;
public MyArrayList() {
this(DEFAULT_INIT_SIZE);
}
public MyArrayList(int capacity) {
if (capacity > 0) {
elements = (E[]) new Object[capacity];
}
else if (capacity == 0) {
elements = (E[]) DEFAULT_EMPTY_ARRAY;
}
else {
throw new IllegalArgumentException("列表容器的容量不能负数");
}
}
public MyArrayList(E[] array) {
assert array != null;
elements = (E[]) new Object[array.length];
for (int i = 0; i < array.length; ++i) {
if (array[i] != null) {
elements[size++] = array[i];
}
}
}
@Override
public void add(E e) {
if (e != null) {
ensureCapacity(size + 1);
elements[size++] = e;
}
}
@Override
public void add(E[] arrayOfElements) {
assert arrayOfElements != null;
ensureCapacity(size + arrayOfElements.length);
for (int i = 0; i < arrayOfElements.length; ++i) {
if (arrayOfElements[i] != null) {
elements[size++] = arrayOfElements[i];
}
}
}
@Override
public boolean remove(E e) {
assert e != null;
int index = indexOf(e);
if (index != -1) {
removeAtIndex(index);
return true;
}
return false;
}
@Override
public boolean remove(E e, boolean allOccurence) {
int counter = 0;
int index;
while ((index = indexOf(e)) != -1) {
removeAtIndex(index);
counter += 1;
}
return counter > 0;
}
// 1 3 4 5 null
@Override
public E removeAtIndex(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("访问元素索引越界: " + index);
}
E e = elements[index];
for (int i = index + 1; i < size; ++i) {
elements[i - 1] = elements[i];
}
elements[--size] = null;
return e;
}
@Override
public E set(int index, E e) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("");
}
E old = elements[index];
elements[index] = e;
return old;
}
@Override
public int indexOf(E e) {
assert e != null;
for (int i = 0; i < size; ++i) {
if (e.equals(elements[i])) {
return i;
}
}
return -1;
}
@Override
public E get(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException("");
}
return elements[index];
}
@Override
public MyList<E> subList(int fromIndex, int toIndex) {
assert toIndex > fromIndex;
if (fromIndex < 0 || toIndex > size) {
throw new IndexOutOfBoundsException("");
}
E[] newArray = Arrays.copyOfRange(elements, fromIndex, toIndex);
return new MyArrayList<E>(newArray);
}
@Override
public boolean isEmpty() {
return size == 0;
}
@Override
public void clear() {
for (int i = 0; i < size; ++i) {
elements[i] = null;
}
size = 0;
}
@Override
public int size() {
return size;
}
private void ensureCapacity(int minCapactiy) {
if (elements.length < minCapactiy) {
int oldCapacity = elements.length;
int newCapacity = oldCapacity + oldCapacity >> 1;
newCapacity = newCapacity < minCapactiy ? minCapactiy : newCapacity;
elements = Arrays.copyOf(elements, newCapacity);
// E[] newArray = (E[]) new Object[newCapacity];
// System.arraycopy(elements, 0, newArray, 0, size);
// elements = newArray;
}
}
}
注：此方法仅代表个人见解，如有错误请指正！到此ArrayList重写完毕，其中大部分方法可以直接使用，但是有些方法不是很严谨，比如其中大部分方法都使用了assert断言，但是在实际上线作用时最好换成用条件语句直接进行判断。
3、进行常规测试
代码如下：
class Test01 {
public static void main(String[] args) {
String[] strs = { "mango", "watermelon", "blueberry" };
MyList<String> myList = new MyArrayList<>(strs);
myList.add("apple");
myList.add("pitaya");
System.out.println(myList.size());
myList.add("mango");
myList.add("orange");
myList.add("mango");
myList.remove("apple");
myList.remove("mango", true);
System.out.println(myList.size());
myList.removeAtIndex(myList.size() - 1);
myList.add(new String[] { "grape", "durian" });
myList = myList.subList(1, 3);
System.out.println(myList.isEmpty());
for (int i = 0; i < myList.size(); ++i) {
System.out.println(myList.get(i));
}
myList.clear();
System.out.println(myList.size());
}
}
4、单元测试
代码如下：
import static org.junit.Assert.*;
import org.junit.After;
import org.junit.AfterClass;
import org.junit.Before;
import org.junit.BeforeClass;
import org.junit.Test;
public class MyArrayListTest {
private MyList<String> myList1 = null;
private MyList<String> myList2 = null;
private MyList<String> myList3 = null;
@BeforeClass
public static void setUpBeforeClass() throws Exception {
}
@AfterClass
public static void tearDownAfterClass() throws Exception {
}
@Before
public void setUp() throws Exception {
myList1 = new MyArrayList<>();
myList2 = new MyArrayList<>(32);
myList3 = new MyArrayList<>(new String[]{
"apple","orange","apple","grape"
});
}
@After
public void tearDown() throws Exception {
}
@Test
public void testAddE() {
myList3.add("watermelon");
assertEquals(5, myList3.size());
assertEquals("watermelon", myList3.get(4));
assertEquals("grape", myList3.get(3));
}
@Test
public void testAddEArray() {
myList3.add(new String[]{
"a","b","c","d"
});
assertEquals(8, myList3.size());
assertEquals("a", myList3.get(4));
assertEquals("b", myList3.get(5));
assertEquals("c", myList3.get(6));
assertEquals("d", myList3.get(7));
}
@Test
public void testRemoveE() {
myList3.remove("apple");
assertEquals(3, myList3.size());
assertEquals("orange", myList3.get(0));
assertEquals("apple", myList3.get(1));
assertEquals("grape", myList3.get(2));
}
@Test
public void testRemoveEBoolean() {
myList3.remove("apple",true);
assertEquals(2, myList3.size());
assertEquals("orange", myList3.get(0));
assertEquals("grape", myList3.get(1));
}
@Test
public void testRemoveAtIndex() {
myList3.removeAtIndex(1);
assertEquals(3, myList3.size());
assertEquals("apple", myList3.get(1));
assertEquals("grape", myList3.get(2));
}
@Test
public void testSet() {
myList3.set(3, "banana");
assertEquals("banana", myList3.get(3));
}
@Test
public void testIndexOf() {
assertEquals(0, myList3.indexOf("apple"));
assertEquals(3, myList3.indexOf("grape"));
assertEquals(-1, myList3.indexOf("watermelon"));
}
@Test(expected = java.lang.IndexOutOfBoundsException.class)
public void testGet() {
//myList3.get(myList3.size());
myList1.get(0);
}
@Test
public void testSubList() {
MyList<String> newList = myList3.subList(1, 3);
assertNotNull(newList);
assertEquals(2, newList.size());
assertEquals("orange", newList.get(0));
assertEquals("apple", newList.get(1));
}
@Test
public void testIsEmpty() {
assertTrue(myList1.isEmpty());
assertTrue(myList2.isEmpty());
assertFalse(myList3.isEmpty());
}
@Test
public void testClear() {
myList3.clear();
assertTrue(myList3.isEmpty());
assertEquals(0, myList3.size());
}
@Test
public void testSize() {
assertEquals(0, myList1.size());
assertEquals(0, myList2.size());
assertEquals(4, myList3.size());
}
}
