List ADT有两种流行的实现方式，Java中ArrayList类提供了可增长数组的实现，LinkedList提供了双链表实现。
使用ArrayList的有点在于，对get和set操作花费常数时间。其缺点是新元素的插入和元素的删除付出的代价非常昂贵，除非变动实在末端进行。
为说明增长数组实现的一些思想，本篇文章将编写ArrayList的简单实现。为避免与类库中的ArrayList类相混淆，这里将把实现的类叫做MyArrayList，即MyArrayList是独立的。
MyArrayList的一些细节：
- 维护数组的元素（elementData），数组的容量(elementData.length)，数组当前的存储的元素个数(size)。
- 提供一种机制来动态改变数组的容量。通过建立新的数组，将老数组的元素拷贝到新数组中，然后允许虚拟机回收老数组。
- 提供set和get操作的实现。
- 提供基本操作，例如：size()，isEmpty()，和Clear()。提供remove(...)操作和add(...)操作 。
- MyArrayList实现Iterable接口，并提供了一个实现Iterator接口的实现类MyListIterator，该类实现了hasNext()，next()和remove()操作。最后通过实现的iterator放回一个Iterator实例。
代码####
public class MyArrayList<E> implements Iterable<E> {
private static final int DEFULT_CAPASITY = 10;
private int size; // 维护数组当前元素的个数
private E[] elementData; // 存储当前List的元素
// 构造器
public MyArrayList() {
doClear();
}
// 清空List
public void clear() {
doClear();
}
// 清空List操作，设置size为0，elementData容量为默认值10
private void doClear() {
size = 0;
ensureCapacity(DEFULT_CAPASITY);
}
// 获取size
public int size() {
return size;
}
// 判断是否为空
public boolean isEmpty() {
return size == 0;
}
// 为了避免浪费空间，设置容量为size
public void trimToSize() {
ensureCapacity(size);
}
// 通过索引获取元素
public E get(int index) {
CheckRange(index);
return elementData[index];
}
// 修改某个位子的元素
public E set(int index, E element) {
CheckRange(index);
E old = elementData[index];
elementData[index] = element;
return old;
}
// 保证对List的操作时有足够的空间。比如add操作，如果数组的容量和size相同，则没有位子可以添加元素。
// 传入一个新的容量minCapacity，表示需要的最小容量。
// 如果size>=newCapacity，则说明容量足够，不作处理。
// 如果size<newCapacity，则将elementData扩容至minCapacity。
@SuppressWarnings("unchecked")
public void ensureCapacity(int minCapacity) {
if (size >= minCapacity) {
return;
}
E[] old = elementData; // 将elementData拷贝到old
elementData = (E[]) new Object[minCapacity]; // 把elementData扩容至minCapacity
for (int i = 0; i < size; i++) {
elementData[i] = old[i]; // 还原elementData原来的元素
}
}
// 在List的末尾添加元素，实际调用了add(int index, E element)方法。
public void add(E element) {
add(size, element);
}
// 在某个位子添加元素。
public void add(int index, E element) {
CheckRangeForAdd(index); // 数组越界检查
// 如果数组的容量等于size，即数组被填满，则需要扩容
if (elementData.length == size) {
ensureCapacity(size + 1); // 扩容一个元素的空间
}
for (int i = size; i > index; i--) {
elementData[i] = elementData[i - 1]; // index及其后面的元素后移
}
elementData[index] = element;
size++;
}
// 删除某位子的元素
public void remove(int index) {
CheckRange(index); // 数组越界检查
for (int i = index; i < size - 1; i++) {
elementData[i] = elementData[i + 1]; // 索引大于index的元素迁移
}
size--;
}
// 越界检查，智能访问0~size-1的范围
private void CheckRange(int index) {
if (index < 0 || index >= size) {
throw new IndexOutOfBoundsException();
}
}
// 针对add操作的数组越界检查，因为可以在List末尾添加元素，所以其访问范围为0~size
private void CheckRangeForAdd(int index) {
if (index < 0 || index > size) {
throw new IndexOutOfBoundsException();
}
}
// iterator方法，返回一个MyIterator实例
public Iterator<E> iterator() {
return new MyIterator();
}
// MyArrayList的内部类，实现了Iterator接口，用来实现遍历List的操作
private class MyIterator implements Iterator<E> {
// 遍历数组，默认从0开始
private int currentIndex = 0;
// 如果没有超过size，则说明还有下一元素
public boolean hasNext() {
return currentIndex < size;
}
// 每一次调用都返当前元素，比如第一调用next()返回第一元素，第二次调用则返回第二个元素
public E next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return elementData[currentIndex++];
}
// 删除当前元素。实际上是调用了MyAarrayList的remove方法。
@SuppressWarnings("unused")
public void remove() {
MyArrayList.this.remove(--currentIndex);
}
}
}
测试代码####
public static void main(String[] args) {
MyArrayList<String> myArrayList = new MyArrayList<String>();
Iterator<String> sIterator = myArrayList.iterator();
// 在末尾添加元素
System.out.println("添加元素：b,c,d");
myArrayList.add("b");
myArrayList.add("c");
myArrayList.add("d");
// 遍历数组元素
System.out.print("iterator遍历List:");
while (sIterator.hasNext()) {
System.out.print(sIterator.next());
}
System.out.println();
// size()
System.out.println();
System.out.println("此时List中元素的个数为：" + myArrayList.size());
System.out.println();
// 在指定位置添加元素，并输出结果
System.out.println("在List首部添加元素:a");
myArrayList.add(0, "a");
System.out.print("iterator遍历List:");
sIterator = myArrayList.iterator();
while (sIterator.hasNext()) {
System.out.print(sIterator.next());
}
System.out.println();
// 删除指定位子元素(删除d)
System.out.println();
System.out.println("删除index为3的元素(d)");
myArrayList.remove(3);
System.out.print("iterator遍历List:");
sIterator = myArrayList.iterator();
while (sIterator.hasNext()) {
System.out.print(sIterator.next());
}
System.out.println();
System.out.println();
// set()和get()
System.out.println("修改List的第一个元素为z.");
myArrayList.set(0, "z");
System.out.println("获取第一个元素" + myArrayList.get(0));
System.out.println();
// iterator.remove()
System.out.println("测试iterator的remove方法：遍历List，每次遍历删除当前元素");
Iterator<String> rIterator = myArrayList.iterator();
while (rIterator.hasNext()) {
if (rIterator.next() != null) {
rIterator.remove();
}
}
System.out.println("删除后的List长度为" + myArrayList.size());
}
测试结果####
测试结果
本篇只给出了ArrayList的一些基本操作，如果大家想更深入的了解，可以去查看ArrayList的源码，下面是一篇ArrayList源码分析很好的文章：
http://blog.csdn.net/jzhf2012/article/details/8540410
大家可以思考两个问题：
- 为什么MyArrayList有了remove方法，为什么iterator中还要实现remove方法。
- 为什么MyIterator要作为MyArrayList的内部类，还有其他实现方式吗？
如果有答案，欢迎大家在评论区讨论。
网友评论