本文共 5570 字，大约阅读时间需要 18 分钟。

首先ArrayList和LinkedList都是List接口下面的实现类，先简单的介绍一下他们基础的底层实现是怎样的；说一说他们的底层结构；

一：ArrayList

从原码中可以看出，ArrayList的底层的数据结构使用的是数组，再者因为可以使用泛型，所以采用的是Object[]的数组类型。

/**     * The array buffer into which the elements of the ArrayList are stored.     * The capacity of the ArrayList is the length of this array buffer. Any     * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA     * will be expanded to DEFAULT_CAPACITY when the first element is added.     */    transient Object[] elementData; // non-private to simplify nested class access

可能有些小伙伴会说ArrayList的初始容量是10，其实初始容量为10的说法并不准确；现在市面上大多数JDK的版本都是8，在1.6中new ArrayList<>()的操作，初始容量确实是10，而在1.8之后，一个new ArrayList<>()的操作初始容量是为0的；只有在存入数据的时候，容量才会变为10。其实在上面的原码注释中也解释的非常清楚了。所以说，在new ArrayList<>()操作时不指定大小，那么这个ArrayList的容量并不是默认容量。

/**     * Default initial capacity.     */    private static final int DEFAULT_CAPACITY = 10;    /**     * Shared empty array instance used for empty instances.     */    private static final Object[] EMPTY_ELEMENTDATA = {};

对于ArrayList的扩容机制；我们就由add()方法来引出ArrayList的扩容机制

/**     * Appends the specified element to the end of this list.     *     * @param e element to be appended to this list     * @return true (as specified by {@link Collection#add})     */    public boolean add(E e) {        ensureCapacityInternal(size + 1);  // Increments modCount!!        elementData[size++] = e;        return true;    }

这里很明显是用到了一个叫 ensureCapacityInternal(size + 1); 的方法，我们可以点进去看一下；

// 这里这个方法的作用就是根据elementData 对象和minCapacity再次确定minCapacity的大小    private static int calculateCapacity(Object[] elementData, int minCapacity) {        /*这里的判断就是想看看elementData 是否为[]，如果为[]的话，调用add()的方法，那么minCapacity的大小就是1，就会使用到DEFAULT_CAPACITY = 10*/        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {            return Math.max(DEFAULT_CAPACITY, minCapacity);        }        /*如果elementData 不是[]话，就直接返回minCapacity*/        return minCapacity;    }    /*minCapacity的大小必须大于elementData*/        private void ensureCapacityInternal(int minCapacity) {        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));    }    private void ensureExplicitCapacity(int minCapacity) {        modCount++;        // overflow-conscious code        /*这里是判断elementData是否大于minCapacity   大于就不需要扩容*/        if (minCapacity - elementData.length > 0)            /*扩容的主要方法*/            grow(minCapacity);    }

上面所说的还是一个判断点，也显示出了扩容的条件，在扩容当中grow(minCapacity)才是核心的方法；可以深入的看一下；

/**     * Increases the capacity to ensure that it can hold at least the     * number of elements specified by the minimum capacity argument.     *     * @param minCapacity the desired minimum capacity     */    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);    }

elementData 被赋予的是空数组，此时的 newCapacity 为 0，minCapacity 为 10，需要使用 10 来进行扩容；另外一种就是创建 ArrayList 的时候，指定的容量是 1，此时的 newCapacity 虽然是经过 oldCapacity 计算过的，但还是 1，而minCapacity 是 2，就会使用 minCapacity 进行扩容；

二：LinkedList

LinkedList也是单列集合的一种，底层是基于双向链表实现的，支持高效的插入和删除操作，同时也实现了Deque接口，使得LinkedList类也具有队列的特性。

public class LinkedList
   
     extends AbstractSequentialList
    
      implements List
     
      , Deque
      
       , Cloneable, java.io.Serializable
      
     
    
   

LinkedList有个内部类Node类，Node类有三个属性，分别是前驱节点，本节点跟后继节点。

private static class Node
   
     {    E item;    Node
    
      next;    Node
     
       prev;    Node(Node
      
        prev, E element, Node
       
         next) {        this.item = element;        this.next = next;        this.prev = prev;    }}
       
      
     
    
   

每次的插入与删除操作，都是通过移动指针去实现的，所以说相对于ArrayList的增删，效率会更高一点。

还是以新增方法add()作为解说对象来一波解析；原码如下：：

public boolean add(E e) {         linkLast(e);         return true;     }    /**     * Links e as last element.     */    void linkLast(E e) {         // 在这里来说，就是取到最后一个元素        final Node
   
     l = last;        // 创建一个新的节点，保存前驱节点，当前节点，因为后面没有，所以为null        final Node
    
      newNode = new Node<>(l, e, null);        // 然后更新最后一个元素的引用        last = newNode;        // 判断链表的第一个元素是否为null        if (l == null)            // 如果为null，就说明链表为空，创建头节点            first = newNode;        else            // 否则就在下一位创建节点            l.next = newNode;        // 刷新节点数量        size++;        modCount++;    }
    
   

LinkedList相对于ArrayList的查询是较慢的，至于为什么，这里可以简单地说两句；

public E get(int index) {        checkElementIndex(index);        return node(index).item;    }    /**     * Returns the (non-null) Node at the specified element index.     */    Node
   
     node(int index) {        // assert isElementIndex(index);        if (index < (size >> 1)) {            Node
    
      x = first;            for (int i = 0; i < index; i++)                x = x.next;            return x;        } else {            Node
     
       x = last;            for (int i = size - 1; i > index; i--)                x = x.prev;            return x;        }    }
     
    
   

其实这里不难看出使用的二分查找，有兴趣的小伙伴可以自己去了解；使用index离size的距离去判断是从头节点进行迭代还是尾节点进行迭代；node()方法会通过O(n/2)去寻找一个节点，如果大于链表大小的一半，就会从尾节点开始迭代；所以说特别在index距离size的中间值越近，效率是非常低的，LinkedList的查改效率相比于ArrayList是较低的。。

总结：

区别：ArrayList底层基于数组，具有index，相比较于LinkedList，查改快，增删慢；LinkedList底层基于双向链表，查询需要指针进行迭代，相比较于ArrayList，查改慢增删快。

使用场景：ArrayList适用于查改操作；而LinkedList适用于增删的操作。

转载地址：https://blog.csdn.net/weixin_43398098/article/details/118800861 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！