自己动手实现集合框架类(一)之ArrayList

时间:2022-03-26 19:21:18

最近看了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);
}

}