动态数组的创建与维护

小鱼儿 2022-04-16 05:41 194阅读 0赞

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

而当数组容量比较小时，则创建一个一定容量的数组（示例代码中是原数组容量的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为例

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E4MEM1MQ_size_16_color_FFFFFF_t_70][]

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

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E4MEM1MQ_size_16_color_FFFFFF_t_70 1][]

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

![20181117214909126.png][]

ensureCapacityInternal方法的实现如下：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E4MEM1MQ_size_16_color_FFFFFF_t_70 2][]

核心的grow 方法：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E4MEM1MQ_size_16_color_FFFFFF_t_70 3][]

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

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E4MEM1MQ_size_16_color_FFFFFF_t_70]: /images/20220416/7f939683211f49ef81a037c8d87de486.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E4MEM1MQ_size_16_color_FFFFFF_t_70 1]: /images/20220416/62e1e355ddcd4e51814e0f9ffefc9a45.png
[20181117214909126.png]: /images/20220416/3f34a1df50c24518b2a37620baaeec0b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E4MEM1MQ_size_16_color_FFFFFF_t_70 2]: /images/20220416/9b17996ba6f2493591464a6cd6ed8224.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2E4MEM1MQ_size_16_color_FFFFFF_t_70 3]: /images/20220416/299646bca67547baa006e353948d0242.png