ArrayList类的实现
程序员文章站
2022-04-18 18:37:45
...
导言
动手实现一个ArrayList。为避免冲突我们称它为MyArrayList。该例子不提供MyCollection和MyList接口。
先概括主要细节:
1. MyArrayList将保持基础数组,数组的容量。以及存储在MyArrayList中的当前项数。
2. MyArrayList将提供一种机制以改变基础数组的容量。通过或者一个新数组,将老数组拷贝到新数组中改变数组的容量,允许虚拟机回收老数组。
3. MyArrayList将提供get和set的实现。
4. MyArrayList将提供基本的例程(Routine,系统对外提供的功能接口的集合),如size,isEmpty和clear,他们是典型的单行程序;还提供remove,以及两种不同版本的add。如果数组的大小和容量相同,那么这两个add例程将增加容量
5. MyArrayList将提供一个实现Iterator接口的类。这个类将存储迭代序列中的下一项的下标,并提供next,hasNext和和remove等方法的实现。MyArrayList的迭代器方法直接返回实现Iterator接口的该类的新构造的实例。
import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Spliterator;
import java.util.function.Consumer;
/**
* @author hasherc
* @ 17-7-20
*/
public class MyArrayList<E> implements Iterable<E>{
public static final int DEFAULT_CAPACITY = 10;//默认容量
private int theSize; //当前大小
private E[] theItems; //存储数组对象
public MyArrayList(){
clear();
}
/**
* 清空,初始化
*/
private void clear() {
theSize = 0;
ensureCapaccity(DEFAULT_CAPACITY);
}
/**
* 返回当前数组大小
* @return
*/
public int size(){ return theSize;}
/**
* 判断数组是否空
* @return
*/
public boolean isEmpty(){ return size() == 0;}
/**
* 使ArrayList最大容量与当前大小一致
*/
public void trimToSize(){
ensureCapaccity(size());
}
/**
* 获取指定位置元素
* @param index
* @return
*/
public E get(int index){
if(index < 0 || index >=size())
throw new ArrayIndexOutOfBoundsException();
return theItems[index];
}
/**
* 修改指定位置元素,并返回修改前的值
* @param index
* @param element
* @return
*/
public E set(int index, E element){
if(index < 0 || index >= size())
throw new ArrayIndexOutOfBoundsException();
E old = theItems[index];
theItems[index] = element;
return old;
}
/**
* 重现创建数组,扩容。
* @param newCapacity
*/
private void ensureCapaccity(int newCapacity) {
if(newCapacity < theSize)
return;
E[] old = theItems;
theItems = (E[]) new Object[newCapacity];
for(int i = 0; i < size(); i++){
theItems[i] = old[i];
}
}
/**
* 添加元素
* @param element
* @return
*/
public boolean add(E element){
add(size(),element);
return true;
}
/**
* 向指定位置添加元素
*/
private void add(int index, E element) {
if(theItems.length == size())
ensureCapaccity(size() * 2 +1);
for (int i = theSize; i > index; i--)
theItems[i] = theItems[i - 1];
theItems[index] = element;
theSize++;
}
/**
* 移除指定位置元素
* @param index
* @return
*/
public E remove(int index){
E removedItem = theItems[index];
for (int i = index; i < size(); i--)
theItems[i] = theItems[i-1];
theSize--;
return removedItem;
}
@Override
public Iterator iterator() {
return new ArrayListIterator();
}
@Override
public void forEach(Consumer action) {
}
@Override
public Spliterator spliterator() {
return null;
}
/**
* 迭代器内部类,使用next之后current指向下一个元素 current最大为size,此时hasNext返回false
*/
private class ArrayListIterator implements Iterator<E> {
private int current = 0;
@Override
public boolean hasNext() {
return current < size();
}
@Override
public E next() {
if(!hasNext())
throw new NoSuchElementException();
return theItems[current++];
}
@Override
public void remove() {
MyArrayList.this.remove(--current);
}
@Override
public void forEachRemaining(Consumer<? super E> action) {
}
}
}