ArrayList和LinkedList区别

Dear 丶 2023-10-02 13:38 10阅读 0赞

### 1 : 处理机制 ###

ArrayList是动态数组，是有序的，但并不是线程安全的。  
其初始容量为10（DEFAULT\_CAPACITY参数），当超过容量时，会自动扩容（grow（int minCapacity）方法）为原容量的1.5倍。  
当删除其中元素时，后续元素会前移。  
由于会动态扩容，会存在大量的数组拷贝操作，如能预见数组大小的情况，最好赋予ArrayList初始值以减少数组的拷贝操作（grow（int minCapacity）方法）。

部分源码如下：

/**
     * Default initial capacity.
     */
    private static final int DEFAULT_CAPACITY = 10;
    
    /**
     * Shared empty array instance used for empty instances.
     */
    private static final Object[] EMPTY_ELEMENTDATA = {
        };
    
    /**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     */
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {
        };
    
    /**
     * Constructs an empty list with an initial capacity of ten.
     */
    public ArrayList() {
        
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    /**
     * 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);
    }

LinkedList类是List实现类，通过链表来实现。  
类似于火车，一节一节的车厢相当于数据，而前后的链接相当于指针。  
add(E e)不指定放置的位置，默认在最后拼接。

/**
     * Appends the specified element to the end of this list.
     *
     * <p>This method is equivalent to {@link #addLast}.
     *
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        
        linkLast(e);
        return true;
    }
    
    /**
     * Links e as last element.
     */
    void linkLast(E e) {
        
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

add(int index, E element)指定放置的位置，做链表拼接。

/**
     * Inserts the specified element at the specified position in this list.
     * Shifts the element currently at that position (if any) and any
     * subsequent elements to the right (adds one to their indices).
     *
     * @param index index at which the specified element is to be inserted
     * @param element element to be inserted
     * @throws IndexOutOfBoundsException {@inheritDoc}
     */
    public void add(int index, E element) {
        
        checkPositionIndex(index);
    
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {
        
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

checkPositionIndex 做大小比较，判断是否在最后拼接。  
linkLast 在上面已经体现。  
linkBefore 在某个接点后面插入拼接。

### 2 : 查询效率 ###

ArrayList是有序的数组，它的优点是按下标查询元素，故其查询效率比较高。  
LinkedList也可以按下标查询元素，但是LinkedList需要对底层链表进行遍历，才能找到指定下标的元素。  
特殊元素：第一个元素，或最后一个元素，ArrayList和LinkedList在性能上是没有区别的，LinkedList中有两个属性分别记录了链表中的头尾结点，并不需要遍历链表。

### 3 : 插入效率 ###

ArrayList可以插入到指定下标位置，或者数组末尾，这种插入普通情况下是很快的，但是如果某次插入操作触发了1.5倍扩容，那么本次插入就增加了额外的扩容成本。  
LinkedList，如果是插在链表的头部或者是尾部都是很快的，因为LinkedList中有两个属性分别记录了链表中的头尾结点。如果是插在指定下标位置，那么就需要遍历链表找到指定位置，从而降低了效率。  
也就是说需要通过node(int index)方法遍历，找到下标位置的前后指针。  
add方法中，如果是头尾，则调用linkLast，是比较快的。中间插入时，调用linkBefore，其参数中的node方法则是为了找到指针，参考源码如下：

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

### 4 : 内存空间 ###

ArrayList是动态扩容，必定会消耗大量的内存空间，复制后，原数据空间会等待垃圾回收。  
ArrayList的最大容量： 0x7fffffff - 8

/**
     * The maximum size of array to allocate.
     * Some VMs reserve some header words in an array.
     * Attempts to allocate larger arrays may result in
     * OutOfMemoryError: Requested array size exceeds VM limit
     */
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

LinkedList是链表结构，所以不用担心扩容问题的，因为链表是不需要扩容的。  
其最大容量，也并不存在限制。

***总结***  
还是得用大量的数据来比较效率，自己测测，才能认识的更加清晰。

写到这也就差不多了，感兴趣的可以看一下源码。这种设计思路挺有趣的。  
有什么不对的还望指正，书写不易，觉得有帮助就点个赞吧！