Java中ArrayList和LinkedList區別

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
    
    //默認大小
    private static final int DEFAULT_CAPACITY = 10;
     
    //省略。。。
    
    //動態數組
    transient Object[] elementData; 
    
    //數組大小
    private int size;
    
    //空構造器
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
    
    // 查詢元素
    public E get(int index) {
        // 檢查索引是否在范圍內
        rangeCheck(index);                    
        return elementData(index);
    }
    
    //順序添加元素
    public boolean add(E e) {
        //擴容
        ensureCapacityInternal(size + 1); 
        elementData[size++] = e;
        return true;
    }
    
    //從數組中間添加元素
    public void add(int index, E element) {
        // 檢查索引是否在范圍內
        rangeCheckForAdd(index);
        // 擴容
        ensureCapacityInternal(size + 1); 
        // 復制數組
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);
        // 替換元素
        elementData[index] = element;
        size++;
    }
    
    //是否要擴容
    private void ensureCapacityInternal(int minCapacity) {
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
    
    //確定容量
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
    //計算數組容量
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }
    
    //動態數組擴容放法
    private void grow(int minCapacity) {
        // 
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // 數組復制
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
     //省略。。。
    
  }

//JDK1.8
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{ 
    // 元素數量
    transient int size = 0;
    
    // 鏈表首節點
    transient Node<E> first;
    
    // 鏈表尾節點
    transient Node<E> last;
    
    // 空構造器
    public LinkedList() {
        
    }
    
    // Node內部類
    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;
        }
    }
    
    // 順序添加元素
    public boolean add(E e) {
        linkLast(e);
        return true;
    }
    
    // 指定位置添加元素
    public void add(int index, E element) {
        // 檢查是否越界
        checkPositionIndex(index);    
        // 在鏈表末尾添加，否則在之前插入元素
        if (index == size)            
            linkLast(element);
        else
            linkBefore(element, node(index));
    }
    
    // 添加元素e
    void linkLast(E e) {
        //把鏈表中last元素賦給l ，如果是第一個元素則為null
        final Node<E> l = last;
        //把元素封裝為一個Node對象
        final Node<E> newNode = new Node<>(l, e, null);
        //把鏈表的last元素指向新的元素
        last = newNode;
        //如果添加的是第一個元素
        if (l == null){
            //把鏈表的first元素指向新的元素
            first = newNode;
        }
        //如果添加的不是第一個元素
        else{
            //把l的下一個元素指向新的元素
            l.next = newNode;            
        }
        //集合中元素數量加1
        size++;
        modCount++;
    }
    
    void linkBefore(E e, Node<E> succ) {
        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++;
    }
    
    //獲取元素
    public E get(int index) {
        //檢測元素索引
        checkElementIndex(index);
        return node(index).item;
    }
    
    //返回指定元素索引處的（非空）節點
    Node<E> node(int index) {
        //把鏈表分為兩段，如果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;
        }
    }
    
    //省略。。。
    
}