ArrayList与LinkedList的区别？

ゝ一世哀愁。 2022-10-19 05:38 221阅读 0赞

### ArrayList与LinkedList的区别 ###

*  区别
 *  相同点
 *  ArrayList与LinkedList的\`add\`谁更快 ？
 *   *  如果向尾部添加一个元素
     *  如果向中间位置添加元素
 *  java集合框架图
 *   *  ArrayList扩容
     *   *  新增时源代码
         *  扩容源代码

--------------------

# 区别 #

1.  数据结构不同。Array是数组，Linked是链表。
2.  适用场景不同。由于结构不同，Array更适合随机查询，而Linked更适合删除和添加。由于结构不同，导致两者对查询，新增和删除的时间复杂度不同。
3.  由于LinkedList实现了`Deque`接口，因此LinkedList可以作为队列使用。
4.  ArrayList添加元素时需要计算扩容，由于LinkedList是双链表，因此LinkedList是不要扩容的。

# 相同点 #

1.  ArrayList和LinkedList都实现了`List`接口
2.  都可以作为列表使用，只是作为列表时的查询，新增，删除的时间复杂度不同。

# ArrayList与LinkedList的`add`谁更快 ？ #

> 这里没有标准答案 ？

## 如果向尾部添加一个元素 ##

如果ArrayList新增时不需要扩容，理论上不需要再去申请新的内存因此ArrayList更快。

如果ArrayList新增元素时需要进行扩容，则LinkedList更快，ArrayList每次扩容都会扩容当前的1.5倍，代价还是很昂贵的（具体见下方简介）。

## 如果向中间位置添加元素 ##

由于ArrayList需要移动元素，因此LinkedList更快。

--------------------

# java集合框架图 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2NDYyNTY3_size_16_color_FFFFFF_t_70]

## ArrayList扩容 ##

每次向ArrayList添加元素时，都会计算元素的数量是否已经超出数组的容量，如果超出，数组将会进行扩容，以满足添加数据的需求。ArrayList扩容是通过一个公开的方法`ensureCapacity(int minCapacity)`来实现。

> 在实际添加大量元素前，我也可以使用ensureCapacity来手动增加ArrayList实例的容量，以减少递增式再分配的数量。

数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。

**这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张:**

1.  创建ArrayList实例时，就指定其容量，以避免数组扩容的发生。
2.  根据实际需求，通过调用ensureCapacity方法来手动增加ArrayList实例的容量。

### 新增时源代码 ###

public boolean add(E e) { 
            ensureCapacityInternal(size + 1);  // 计算容量
            elementData[size++] = e;
            return true;
        }

### 扩容源代码 ###

//可通过该方法手动扩容
        public void ensureCapacity(int minCapacity) { 
            int minExpand = (elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                // any size if not default element table
                ? 0
                // larger than default for default empty table. It's already
                // supposed to be at default size.
                : DEFAULT_CAPACITY;
    
            if (minCapacity > minExpand) { 
                ensureExplicitCapacity(minCapacity);
            }
        }
    
        private void ensureCapacityInternal(int minCapacity) { 
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
                minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
            }
    
            ensureExplicitCapacity(minCapacity);
        }
    
        private void ensureExplicitCapacity(int minCapacity) { 
            modCount++;
    
            // overflow-conscious code
            if (minCapacity - elementData.length > 0)
                grow(minCapacity);
        }
        private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
    
    	// 最终执行扩容的方法
        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);
        }
    
        private static int hugeCapacity(int minCapacity) { 
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
        }

扩容过程如下图所示 ：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2NDYyNTY3_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2NDYyNTY3_size_16_color_FFFFFF_t_70]: /images/20221005/0449978a30234466979ba113af2cfe70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzI2NDYyNTY3_size_16_color_FFFFFF_t_70 1]: /images/20221005/68a8657b92754711aac5316ecfd74eb7.png