动态数组的实现-ArrayList

程序员文章站 2022-03-21 17:05:02

...

动态数组的实现-ArrayList

说完了LinkedList,来谈下另外一种常用的数组ArrayList。
动态数组的实现-ArrayList

可以看到他们同时实现了List接口，但是ArrayList和LinkedList的区别是LinkedList利用了双向链表的方法来进行创建，ArrayList利用了动态数组的方法，进行创建，类似于c中的动态数组申请。

从他们的创建方法也可以看出来，当数据较大时候，从中间插入，从头部插入，和在尾部插入的时候，他们的效率差距很大，同时查找也会存在很大的效率差异。

比如ArrayList是利用动态数组的方式，也就意味着如果我们在它头部插入的时候，他会将后面的所有的内容全部后移，而链表会在判断过后判断从头部还是尾部进行遍历，同时插入数据，而且它的链表特性也不会将所有的数据向后移动。当两种数组在查找的时候，链表需要遍历，而数组可以通过数字进行查找，所以如果在数据很大的时候，在选择两种链表的时候，可以进行一番商酌。

构造函数

 public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }


    public ArrayList() {
        super();
        this.elementData = EMPTY_ELEMENTDATA;
    }


    public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

这里可以看到他一共有三个构造函数，当不传入任何参数的时候，他会默认创建一个大小为EMPTY_ELEMENTDATA的数组，我们也可以通过指定大小进行指定大小的传入，当判断好数组大致大小过后，可以进行一个数组大小的生，可以避免后期的频繁的申请空间。
同样他也可以通过一个实现了collection的数组进行初始化。

addAll方法和申请数组大小函数

 public boolean addAll(Collection<? extends E> c) {  
   Object[] a = c.toArray();  
    int numNew = a.length;  
    ensureCapacity(size + numNew);      // Increments modCount  
    System.arraycopy(a, 0, elementData, size, numNew);  
    size += numNew;  
    return numNew != 0;  
 }

public void ensureCapacity(int minCapacity) {  
    modCount++;  
    int oldCapacity = elementData.length;  
    if (minCapacity > oldCapacity) {     //判断是否大于默认申请空间
        Object oldData[] = elementData;    
        int newCapacity = (oldCapacity * 3)/2 + 1;  //增加50%+1
            if (newCapacity < minCapacity)          //如果还是不够，直接让其等于最新的长度
                newCapacity = minCapacity;  
      // minCapacity is usually close to size, so this is a win:  
      elementData = Arrays.copyOf(elementData, newCapacity);       //新的数组
    }  
 }

照例来看一下addAll方法，ensureCapacityInternal判断当前的数字是否大于了申请的长度，如果空间不够了，在申请 1.5倍的空间，如果还是不够，直接让最新的长度等于需要的长度，然后将旧的数组给新的数组。

注意这里有一片代码片。

Object oldData[] = elementData;

可能会问这个有什么作用，前面后面都没有用到它，但是这个在这里面确实也是起着它的作用，Arrays.copyOf将一个旧的数组赋值给新的数组，elementData 指向了一个新的引用，可能会在复制过程中被回收，elementData被回收了怎么办，这个时候创建一个Object oldData[] = elementData; ，将它们指向同一个引用，当数组被复制过后才会被回收，确保数组复制的完整性。

动态数组的实现-ArrayList