ArrayList和LinkedList的区别、扩容机制以及底层实现

缺乏、安全感 2022-04-22 10:50 202阅读 0赞

*  **ArrayList**  
    ArrayList的底层实现为数组存储在内存中，线程不同步。可通过数组下标的形式进行查找，所以在查询方面的效率较为出色，常用在查询较多的情景下。
 *  **LinkedList**  
    LinkedList的底层实现为链表形式，也为线程不同步。而链表的底层也决定了它在查询方面不如数组底层的ArrayList而在指定位置插入等修改操作下，性能优于ArrayList。
 *  **Vestor**  
    另外还有Vestor，Vestor也是和ArrayList、LinkedList一样实现了java.util.List接口。最大的区别在于Vestor是线程同步的，所以在效率方面不如另外两者，适用于多线程项目中。
 *  **ArrayList的扩容机制**

/**
         * Constructs an empty list with the specified initial capacity.
         */
        public ArrayList(int initialCapacity) {
        super();
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal Capacity: "+
                                                   initialCapacity);
        this.elementData = new Object[initialCapacity];
        }
    
        /**
         * Constructs an empty list with an initial capacity of ten.
         */
        public ArrayList() {
        this(10);
        }

翻阅源码会发现ArrayList初始化如果不指定大小的时候 初始大小为10。

public void ensureCapacity(int minCapacity) {
        modCount++;
        int oldCapacity = elementData.length;
        if (minCapacity > oldCapacity) {
            Object oldData[] = elementData;
            int newCapacity = (oldCapacity * 3)/2 + 1;
                if (newCapacity < minCapacity)
            newCapacity = minCapacity;
                // minCapacity is usually close to size, so this is a win:
                elementData = Arrays.copyOf(elementData, newCapacity);
        }
        }

扩容的规则也在源码中有体现，扩容后的大小= 原始大小+原始大小/2 + 1。在进行插入等操作的时候，如果判断出大小不够，会依据此方法进行扩容。(以上是JDK1.6版本的源码，在JDK1.7中扩容规则进行了修改，改为了扩容后的大小= 原始大小+原始大小/2)

*  **LinkedList的扩容机制**

由于它的底层是用双向链表实现的，没有初始化大小，也没有扩容的机制。