ArrayList与LinkedList区别

向右看齐 2023-02-27 12:19 15阅读 0赞

### 文章目录 ###

*   *  ArrayList与LinkedList区别
     *   *  ArrayList
         *   *  get方法
             *  add方法
         *  LinkedList
         *   *  get方法
             *  add方法
         *  总结

## ArrayList与LinkedList区别 ##

### ArrayList ###

从构造函数中，可以看出，ArrayList底层结构是一个**对象数组**

public ArrayList(int initialCapacity) { 
        if (initialCapacity > 0) { 
            //对象数组
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) { 
            this.elementData = EMPTY_ELEMENTDATA;
        } else { 
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

#### get方法 ####

public E get(int index) { 
        rangeCheck(index);
    	//直接通过索引访问数组
        return elementData(index);
    }

#### add方法 ####

add有两种实现: `add(E e)`，直接数组尾部插入即可, `add(int index, E element)`，需要调整数组后，进行插入，直接介绍第二种方法，可以明显得发现`ArrayList`与`LinkedList`的区别

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++;
    }

`ensureCapacityInternal`方法，首先调用`calculateCapacity`方法，计算所需的数组容量，之后调用`ensureExplicitCapacity`,如果容量不够，则调用`grow`方法，进行扩容操作，每次扩容大小，为原来数组大小一半

private void ensureCapacityInternal(int minCapacity) { 
    	ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    private static int calculateCapacity(Object[] elementData, int minCapacity) { 
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { 
        	return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    private void ensureExplicitCapacity(int minCapacity) { 
        modCount++;
    
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
        grow(minCapacity);
    }
    //扩容操作
    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 ###

从源码中，可以直观看出，LinkedList底层是双向链表结构

/** * Pointer to first node. * Invariant: (first == null && last == null) || * (first.prev == null && first.item != null) */
    transient Node<E> first;
    
    /** * Pointer to last node. * Invariant: (first == null && last == null) || * (last.next == null && last.item != null) */
    transient Node<E> last;
    
    private static class Node<E> { 
        E item;
        Node<E> next;
        Node<E> prev;
    
        Node(Node<E> prev, E element, Node<E> next) { 
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

#### get方法 ####

需要遍历链表，里面有个小技巧，如果index < size/2从头开始遍历，否则从链表尾部进行遍历

public E get(int index) { 
        checkElementIndex(index);
        return node(index).item;
    }
    
    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;
        }
    }

#### add方法 ####

跟ArrayList一样提供两种add形式

`add(E, e)`,直接在链表尾部直接插入。

public boolean add(E e) { 
        linkLast(e);
        return true;
    }
    
    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)`,插入链表指定位置， 也是一个`O(1)`的操作

public void add(int index, E element) { 
        checkPositionIndex(index);
        if (index == size)  linkLast(element);
        else linkBefore(element, node(index));
    }
    
    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++;
    }

### 总结 ###

ArrayList和LinkedList的区别有以下几点：

*  ArrayList是实现了基于动态数组的数据结构，而LinkedList是基于双向链表的数据结构；
 *  对于随机访 问get和set，ArrayList要优于LinkedList，因为LinkedList要移动指针；
 *  对于添加和删除操作add和remove，一般大家都会说LinkedList要比ArrayList快，因为ArrayList要移动数据，但是实际情况可能会有差异。
 *  综上所述，在需要频繁读取集合中的元素时，使用ArrayList效率较高，而在插入和删除操作较多时，使用LinkedList效率较高。