动态数组的创建与维护

说是动态数组，其实就是在满容量时，再创建创建一个一定容量的数组（实例代码中是原数组容量的一倍），并将对数组的引用指向新的数组。

而当数组容量比较小时，则创建一个一定容量的数组（示例代码中是原数组容量的1/4）,并将对数组的引用指向新的数组。

示例代码如下：

import java.util.Iterator;
import java.util.List;

public class FixedCapacityStack<Item> implements Iterable<Item> {
    private Item[] a;
    private int N;

    public FixedCapacityStack(int cap){
        a = (Item[]) new Object[cap];
    }

    public boolean isEmpty(){
        return N==0;
    }

    public int size(){
        return N;
    }

    public void push(Item item){
        if(N== a.length){
            resize(2*a.length);
        }
        a[N++]=item;

    }

    public Item pop(){
        Item item = a[--N];
        a[N]=null;
        if(N>0 && N== a.length/4){
            resize(a.length/2);
        }
        return item;
    }

    private void resize(int max){
        Item[] temp = (Item[]) new Object[max];
        for( int i=0;i< N;i++){
            temp[i]=a[i];
        }
        a=temp;
    }

    @Override
    public Iterator<Item> iterator() {
        return new ReverseArrayIterator();
    }

    private class ReverseArrayIterator implements Iterator<Item>{
        private int i =N;

        @Override
        public boolean hasNext() {
            return i> 0;
        }

        @Override
        public Item next() {
            return a[--i];
        }

        @Override
        public void remove() {

        }
    }


    public static void main(String[] args) {
        FixedCapacityStack<String> a = new FixedCapacityStack<>(100);

        String testStr = "a,34ai,342a,a,4,ba,asi,asdi,45";
        String[] testArray = testStr.split(",");

        for(String temp : testArray){
            a.push(temp);
        }

        for( String result: a){
            System.out.println(result);
        }

    }
}

代码为了方便，所以直接用main函数代替。

Java中常用的List集合对应的实现类，原理大概类似：

以ArraList为例

我们通常使用的他的无参构造器。而这个无参构造器，对应的数组，默认大小为10。如下图所示

而我们调用add方法时，执行逻辑如下

ensureCapacityInternal方法的实现如下：

核心的grow 方法：

即，当ArrayList需要扩容时，将原数组利用Arrays工具类的copyOf方法，复制一份给新的数组，新数组的大小为老数组的长度的1.5倍。具体可以继续看Arrays.copyOf的实现。在这里，不在赘言。