最近看了java.util包下的集合类,学习其中的原理,参照底层方法,自己实现。
定义集合Collection接口:
package com.java.myutil;
public interface Collection {
public void add(Object object);
public int size();
public Iterator iterator();
public Object get(int i);
public void remove(Object object);
}
定义迭代器接口:
package com.java.myutil;
public interface Iterator {
boolean hasNext();
Object Next();
void remove();
}
ArrayList比较简单,底层就是一个数组的结构,实现如下:
ArrayList的实现:
package com.java.myutil;
public class ArrayList implements Collection{
//底层就是一个数组结构
private Object[] dataObjects;
private int size;
private static final int DEFAULT_CAPACITY = 10;
public ArrayList() {
dataObjects=new Object[DEFAULT_CAPACITY];
size=0;
}
//数组中添加数据,如果超出了原始的大小,就扩展数组
public void add(Object object) {
if (size==dataObjects.length) {
ensureCapacity();
}
dataObjects[size]=object;
size++;
}
//删除数组中的原始
public void remove(Object object) {
for (int i = 0; i < size; i++) {
if (object.equals(dataObjects[i])) {
int numMove=size-i-1;
System.arraycopy(dataObjects, i+1, dataObjects, i, numMove);
dataObjects[--size]=null;
}
}
}
//扩展数组大小
private void ensureCapacity() {
Object [] newObjects=new Object[dataObjects.length*2];
System.arraycopy(dataObjects, 0, newObjects, 0, dataObjects.length);
dataObjects=newObjects;
}
public int size() {
return size;
}
public Object get(int i) {
if (i<0 ||i>size-1) {
throw new IndexOutOfBoundsException();
}
return dataObjects[i];
}
/*迭代器的实现*/
private class ArrayListIterator implements Iterator{
private int index=0;
private int lastIndex=-1;//存一下上一次的操作的位置,remove方法需要记录上一次操作的位置
public boolean hasNext() {
return index!=size;
}
public Object Next() {
lastIndex=index;
return dataObjects[index++];
}
public void remove() {
if (lastIndex<0) {
throw new IllegalStateException();
}
//删除元素,就是将要删掉元素的位置的后面的元素向前面移动
int numMoved=size-lastIndex-1;
System.arraycopy(dataObjects, lastIndex+1, dataObjects, lastIndex, numMoved);
dataObjects[--size]=null;
index--;
lastIndex=-1;//lastIndex直接赋值-1,因为remove方法和next方法是相互依赖的,remove之前必须调用next方法
}
}
public Iterator iterator() {
return new ArrayListIterator();
}
public static void main(String[] args) {
ArrayList myaArrayList=new ArrayList();
myaArrayList.add("aaa");
myaArrayList.add("bbb");
myaArrayList.add("ccc");
Iterator it=myaArrayList.iterator();
while (it.hasNext()) {
System.out.println(it.Next());
}
//myaArrayList.remove("bbb");
Iterator it2=myaArrayList.iterator();
while (it2.hasNext()) {
it2.remove();
}
System.out.println(myaArrayList);
}
}