雙向鏈表實現(xiàn)的list

transient int size = 0;

    /**
     * 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;

看字段就知道他大概怎么玩的了

總結

• 首尾增加元素開銷固定，O(1)
• 不支持隨機訪問，查詢復雜度O（n）
• 空間占比大，每一個節(jié)點都需要創(chuàng)建一個Node對象
• ArrayList想要在指定位置插入或刪除元素時，主要耗時的是System.arraycopy動作，會移動index后面所有的元素；LinkedList主耗時的是要先通過for循環(huán)找到index，然后直接插入或刪除。這就導致了兩者并非一定誰快誰慢