ArrayList实现可变数组的原理：
当元素超出数组内容，会产生一个新数组，将原来数组的数据复制到新数组中，再将新的元素添加到新数组中。
ArrayList:是按照原数组的50%来延长，构造一个初始容量为10的空列表
用ArrayList模拟数组：
package iterater.patten.design; //探索ArrayList实现的可变数组的原理，用ArrayList实现一个容器存储对象
public class ArrayList {
Object[] objects = new Object[10];
// 定义计数器，用于计算数组中的元素个数
int index = 0; public void add(Object o) {
// 当数组满时，则创建一个新的数组，将原数组中的元素复制进新数组中，再将新的元素加入到数组中
if (index == objects.length) {
// 按原数组的2倍长度创建新数组，其实这样不太合理
Object[] newObjects = new Object[objects.length * 2];
// 将原数组中的元素复制进新数组中，再将新的元素加入到数组中
System.arraycopy(objects, 0, newObjects, 0, objects.length);
// 数组引用指向新的数组
objects = newObjects;
} // 将新增元素放到数组中
objects[index] = o;
index++;
} // 定义size函数获取元素个数
public int size() {
return index;
}
}
用LinkedList模拟数组
package iterater.patten.design; //探索LinkedList实现的可变数组的原理，用LinkedList实现一个容器存储对象
public class LinkedList { //定义链表的头指针head以及尾指针tail
Node head = null;
Node tail = null;
int size = 0; //添加元素
public void add(Object o) {
//一个新的结点
Node n = new Node(o, null);
//当链表为空时，head指向新添加的结点，tail也指向该结点
if (head == null) {
head = n;
tail = n;
}
//链表不为空时，tail包含的下一个结点的引用指向这个新加入的结点 tail.setNext(n);
tail = n;
size++;
} public int size() {
return size;
}
}
Node结点的类定义
package iterater.patten.design; //定义一个类来存储链表中的结点
public class Node { private Object data;
private Node next;
public Object getData() {
return data;
}
public void setData(Object data) {
this.data = data;
}
public Node getNext() {
return next;
}
public void setNext(Node next) {
this.next = next;
}
public Node(Object data, Node next) {
super();
this.data = data;
this.next = next;
} }
添加的元素对象所属的类的类定义
package iterater.patten.design;
public class Cat {
private int id;
public int getId() {
return id;
}
public void setId(int id) {
this.id = id;
}
public Cat(int id) {
super();
this.id = id;
}
}
测试类
package iterater.patten.design;
import iterater.patten.design.*;
public class IteratorTest {
/**
* @param args
*/
public static void main(String[] args) {
// ArrayList al=new ArrayList();
LinkedList al = new LinkedList();
for (int j = 0; j < 15; j++) {
al.add(new Cat(j));
}
System.out.println(al.size());
}
}
输出结果：15
【温情提示】：我们在测试类中为了提高容器的可替换性，可以定义一个接口Collection,定义add、size方法，只要保证容器类实现该接口，当用户使用add添加元素或者使用size获取元素个数的时候就可以更加方便(因为如果ArrayList中的添加元素方法叫add，而LinkedList中添加元素的方法叫addall,用户在使用的时候就会造成困扰，使用定义接口的方式，我们只对接口进行编程使用，不用去关心具体的实现内容。
代码实现：
public interface Collection {
public Object add(Object o);
public int size();
}
ArrayList和LinkedList实现该接口，并覆盖抽象方法即可，测试类中可以这样使用两个方法：
Collection c=new ArrayList();
c.add(object)、c.size();
父接口引用指向子类对象，并调用子类中覆盖的方法
但是此时又出现了一个新的问题，当我们想要对数组中的元素进行遍历时，因为不同的集合有不同的遍历方法，用ArrayList模拟的数组可以通过数组的下标索引进行遍历，但是LinkedList使用的却是另外一种方法。
针对这样的问题，解决的方法就是定义Iterator接口，里面封装了遍历数组元素的统一方式，话不多说，代码来验证。
定义两个接口Collection和Iterator
public interface Collection {
Iterator iterator();
}
迭代器：
public interface Iterator {
public boolean hasNext();
public Object next();
}
不同的容器实现Iterator接口，获取具体的迭代器对象(即该容器类型的对象)
//具体的实现类，不同的容器，拥有不同的迭代元素的方法
private class ArrayListIterator implements Iterator{
private int currentIndex=0;
@Override
public boolean hasNext() {
if(currentIndex>=index){ return false;
}
else {
return true;
}
} @Override
public Object next() {
Object object=objects[currentIndex];
currentIndex++;
return object;
}
}
只要ArrayList实现我前面自定义的Collection接口，覆盖iterator方法，就可以获取一个具体的实现类的对象
public class ArrayList implements Collection
public Iterator iterator() {
return new ArrayListIterator();
}
此时测试类可以这样写：
package iterater.patten.design;
import iterater.patten.design.*;
public class IteratorTest {
/**
* @param args
*/
public static void main(String[] args) {
ArrayList al = new ArrayList();
for (int j = 0; j < 15; j++) {
al.add(new Cat(j));
}
Iterator it = al.iterator();
while (it.hasNext()) {
Object object = it.next();
System.out.print(object + " ");
}
System.out.println();
}
}
迭代器Iterator的实现原理大致就是这样，尽管不同的集合内部的数据结构不同，统一了遍历集合的方式。
最后附上ArrayList的类的代码：
package iterater.patten.design; //探索ArrayList实现的可变数组的原理，用ArrayList实现一个容器存储对象
public class ArrayList implements Collection{
Object[] objects = new Object[10];
// 定义计数器，用于计算数组中的元素个数
int index = 0; public void add(Object o) {
// 当数组满时，则创建一个新的数组，将原数组中的元素复制进新数组中，再将新的元素加入到数组中
if (index == objects.length) {
// 按原数组的2倍长度创建新数组，其实这样不太合理
Object[] newObjects = new Object[objects.length * 2];
// 将原数组中的元素复制进新数组中，再将新的元素加入到数组中
System.arraycopy(objects, 0, newObjects, 0, objects.length);
// 数组引用指向新的数组
objects = newObjects;
} // 将新增元素放到数组中
objects[index] = o;
index++;
} // 定义size函数获取元素个数
public int size() {
return index;
}
//不同的容器，拥有不同的迭代元素的方法
private class ArrayListIterator implements Iterator{
private int currentIndex=0;
@Override
public boolean hasNext() {
if(currentIndex>=index){ return false;
}
else {
return true;
}
} @Override
public Object next() {
Object object=objects[currentIndex];
currentIndex++;
return object;
}
} @Override
public Iterator iterator() { return new ArrayListIterator();
} }