Java数据结构源码分析-ArrayList

迈不过友情╰ 2022-08-23 01:24 211阅读 0赞

## 1.ArrayList简介 ##

ArrayList是基于数组实现的顺序容器，其具有O(1)速度的访问的特点。其结构比较简单，因为我们快速的看下其中比较重要的几个方法。

//ArrayList在调用构造函数的时候，分配数组的内存
    public ArrayList(int initialCapacity) {
            super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
            this.elementData = new Object[initialCapacity];
        }
    //ArrayList可以存入其他的Collection集合（Set,List）来初始化元素。其copy是浅拷贝，其只是拷贝集合中元素的引用,本质上使用System.arraycopy来进行，其只是copy对象的引用。
    //注意：Set、Map、List的带集合的构造函数都是浅copy
    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);
        }
    //ArrayList在加入对象的时候，通过该方法来确保其有足够的内存来加入该元素。可以看到其是以3*oldCapacity的大小进行扩展
    private void grow(int minCapacity) {
            // overflow-conscious code
            int oldCapacity = elementData.length;
            int newCapacity = oldCapacity + (oldCapacity >> 1);
            if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;
            if (newCapacity - MAX_ARRAY_SIZE > 0)
                newCapacity = hugeCapacity(minCapacity);
            // minCapacity is usually close to size, so this is a win:
            elementData = Arrays.copyOf(elementData, newCapacity);
        }
    //ArrayList提供了在指定位置加入元素的方法。其主要通过向后移动指定位置元素的方式实现
    public void add(int index, E element) {
            rangeCheckForAdd(index);
    
            ensureCapacityInternal(size + 1);  // Increments modCount!!
            System.arraycopy(elementData, index, elementData, index + 1,
                             size - index);
            elementData[index] = element;
            size++;
        }
    //可以发现在ArrayList中频繁的使用System.arraycopy来拷贝数组，在平常有数组copy的场景也可以考虑
    public boolean addAll(Collection<? extends E> c) {
            Object[] a = c.toArray();
            int numNew = a.length;
            ensureCapacityInternal(size + numNew);  // Increments modCount
            System.arraycopy(a, 0, elementData, size, numNew);
            size += numNew;
            return numNew != 0;
        }
    //clone方法也是浅层copy，其主要是在数组层次的内存新建，并不会copy数组中的对象，其copy的是对象的引用
    public Object clone() {
            try {
                @SuppressWarnings("unchecked")
                    ArrayList<E> v = (ArrayList<E>) super.clone();
                v.elementData = Arrays.copyOf(elementData, size);
                v.modCount = 0;
                return v;
            } catch (CloneNotSupportedException e) {
                // this shouldn't happen, since we are Cloneable
                throw new InternalError();
            }
        }
    //该方法说明ArrayList是可以保存null的对象，并且可重复，remove会移除所有的o
    public boolean remove(Object o) {
            if (o == null) {
                for (int index = 0; index < size; index++)
                    if (elementData[index] == null) {
                        fastRemove(index);
                        return true;
                    }
            } else {
                for (int index = 0; index < size; index++)
                    if (o.equals(elementData[index])) {
                        fastRemove(index);
                        return true;
                    }
            }
            return false;
        }
    private void fastRemove(int index) {
            modCount++;
            int numMoved = size - index - 1;
            if (numMoved > 0)
                System.arraycopy(elementData, index+1, elementData, index,
                                 numMoved);
            elementData[--size] = null; // clear to let GC do its work
        }
    //ArrayList的subList是通过共享ArrayList的内存来实现的，具体的方法可以参看下面的内部类SubList
    public List<E> subList(int fromIndex, int toIndex) {
                subListRangeCheck(fromIndex, toIndex, size);
                return new SubList(this, offset, fromIndex, toIndex);
            }

//从ArrayList的SubList可以看出，其并不会分配新的空间，其主要是保存一个ArrayList的位移，对于SubList的操作都会影响ArrayList的结构

private class SubList extends AbstractList<E> implements RandomAccess { 
            private final AbstractList<E> parent;
            private final int parentOffset;
            private final int offset;
            int size;
    
            SubList(AbstractList<E> parent,
                    int offset, int fromIndex, int toIndex) {
                this.parent = parent;
                this.parentOffset = fromIndex;
                this.offset = offset + fromIndex;
                this.size = toIndex - fromIndex;
                this.modCount = ArrayList.this.modCount;
            }
    
            public E set(int index, E e) {
                rangeCheck(index);
                checkForComodification();
                E oldValue = ArrayList.this.elementData(offset + index);
                ArrayList.this.elementData[offset + index] = e;
                return oldValue;
            }
    
            public E get(int index) {
                rangeCheck(index);
                checkForComodification();
                return ArrayList.this.elementData(offset + index);
            }
    
            public int size() {
                checkForComodification();
                return this.size;
            }
    
            public void add(int index, E e) {
                rangeCheckForAdd(index);
                checkForComodification();
                parent.add(parentOffset + index, e);
                this.modCount = parent.modCount;
                this.size++;
            }
    
            public E remove(int index) {
                rangeCheck(index);
                checkForComodification();
                E result = parent.remove(parentOffset + index);
                this.modCount = parent.modCount;
                this.size--;
                return result;
            }
    
            protected void removeRange(int fromIndex, int toIndex) {
                checkForComodification();
                parent.removeRange(parentOffset + fromIndex,
                                   parentOffset + toIndex);
                this.modCount = parent.modCount;
                this.size -= toIndex - fromIndex;
            }
    
            public boolean addAll(Collection<? extends E> c) {
                return addAll(this.size, c);
            }
    
            public boolean addAll(int index, Collection<? extends E> c) {
                rangeCheckForAdd(index);
                int cSize = c.size();
                if (cSize==0)
                    return false;
    
                checkForComodification();
                parent.addAll(parentOffset + index, c);
                this.modCount = parent.modCount;
                this.size += cSize;
                return true;
            }
    
            public Iterator<E> iterator() {
                return listIterator();
            }
    
            public ListIterator<E> listIterator(final int index) {
                checkForComodification();
                rangeCheckForAdd(index);
                final int offset = this.offset;
    
                return new ListIterator<E>() {
                    int cursor = index;
                    int lastRet = -1;
                    int expectedModCount = ArrayList.this.modCount;
    
                    public boolean hasNext() {
                        return cursor != SubList.this.size;
                    }
    
                    @SuppressWarnings("unchecked")
                    public E next() {
                        checkForComodification();
                        int i = cursor;
                        if (i >= SubList.this.size)
                            throw new NoSuchElementException();
                        Object[] elementData = ArrayList.this.elementData;
                        if (offset + i >= elementData.length)
                            throw new ConcurrentModificationException();
                        cursor = i + 1;
                        return (E) elementData[offset + (lastRet = i)];
                    }
    
                    public boolean hasPrevious() {
                        return cursor != 0;
                    }
    
                    @SuppressWarnings("unchecked")
                    public E previous() {
                        checkForComodification();
                        int i = cursor - 1;
                        if (i < 0)
                            throw new NoSuchElementException();
                        Object[] elementData = ArrayList.this.elementData;
                        if (offset + i >= elementData.length)
                            throw new ConcurrentModificationException();
                        cursor = i;
                        return (E) elementData[offset + (lastRet = i)];
                    }
    
                    public int nextIndex() {
                        return cursor;
                    }
    
                    public int previousIndex() {
                        return cursor - 1;
                    }
    
                    public void remove() {
                        if (lastRet < 0)
                            throw new IllegalStateException();
                        checkForComodification();
    
                        try {
                            SubList.this.remove(lastRet);
                            cursor = lastRet;
                            lastRet = -1;
                            expectedModCount = ArrayList.this.modCount;
                        } catch (IndexOutOfBoundsException ex) {
                            throw new ConcurrentModificationException();
                        }
                    }
    
                    public void set(E e) {
                        if (lastRet < 0)
                            throw new IllegalStateException();
                        checkForComodification();
    
                        try {
                            ArrayList.this.set(offset + lastRet, e);
                        } catch (IndexOutOfBoundsException ex) {
                            throw new ConcurrentModificationException();
                        }
                    }
    
                    public void add(E e) {
                        checkForComodification();
    
                        try {
                            int i = cursor;
                            SubList.this.add(i, e);
                            cursor = i + 1;
                            lastRet = -1;
                            expectedModCount = ArrayList.this.modCount;
                        } catch (IndexOutOfBoundsException ex) {
                            throw new ConcurrentModificationException();
                        }
                    }
    
                    final void checkForComodification() {
                        if (expectedModCount != ArrayList.this.modCount)
                            throw new ConcurrentModificationException();
                    }
                };
            }
    
            public List<E> subList(int fromIndex, int toIndex) {
                subListRangeCheck(fromIndex, toIndex, size);
                return new SubList(this, offset, fromIndex, toIndex);
            }
    
            private void rangeCheck(int index) {
                if (index < 0 || index >= this.size)
                    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
            }
    
            private void rangeCheckForAdd(int index) {
                if (index < 0 || index > this.size)
                    throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
            }
    
            private String outOfBoundsMsg(int index) {
                return "Index: "+index+", Size: "+this.size;
            }
    
            private void checkForComodification() {
                if (ArrayList.this.modCount != this.modCount)
                    throw new ConcurrentModificationException();
            }
        }