欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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) {

        }
    }
}