源碼

上一篇，我們介紹ArrayList和LinkedList的內(nèi)容仇让，對于這兩個類的源碼只列舉其中的一部分典奉，本篇就來完整的闡述下Ｌ煞！秋柄！

希望能讓你對這兩個類获枝，有一個更完整的理解！

ArrayList

完整源碼：

public class ArrayList<E> extends AbstractList<E>
        implements List<E>, RandomAccess, Cloneable, java.io.Serializable {

    //實(shí)現(xiàn)Serializable接口骇笔，生成的序列版本號：
    private static final long serialVersionUID = 8683452581122892189L;

    //ArrayList初始容量大惺〉辍：在無參構(gòu)造中不使用了
    private static final int DEFAULT_CAPACITY = 10;

    //空數(shù)組對象：初始化中默認(rèn)賦值給elementData
    private static final Object[] EMPTY_ELEMENTDATA = {};

    //ArrayList中實(shí)際存儲元素的數(shù)組：
    private transient Object[] elementData;

    //集合實(shí)際存儲元素長度：
    private int size;

    //ArrayList有參構(gòu)造：容量大小
    public ArrayList(int initialCapacity) {
        //即父類構(gòu)造：protected AbstractList() {}空方法
        super();
        //如果傳遞的初始容量小于0 ，拋出異常
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
        //初始化數(shù)據(jù)：創(chuàng)建Object數(shù)組
        this.elementData = new Object[initialCapacity];
    }

    //ArrayList無參構(gòu)造：
    public ArrayList() {
        //即父類構(gòu)造：protected AbstractList() {}空方法
        super();
        //初始化數(shù)組：空數(shù)組笨触，容量為0
        this.elementData = EMPTY_ELEMENTDATA;
    }

    //ArrayList有參構(gòu)造：Java集合
    public ArrayList(Collection<? extends E> c) {
        //將集合轉(zhuǎn)換為數(shù)組：
        elementData = c.toArray();
        //設(shè)置數(shù)組的長度：
        size = elementData.length;
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

    //將ArrayList的數(shù)組大小懦傍，變更為實(shí)際元素大小：
    public void trimToSize() {
        //操作數(shù)+1
        modCount++;
        //如果集合內(nèi)元素的個數(shù)芦劣，小于數(shù)組的長度粗俱，那么將數(shù)組中空余元素刪除
        if (size < elementData.length) {
            elementData = Arrays.copyOf(elementData, size);
        }
    }

    public void ensureCapacity(int minCapacity) {
        int minExpand = (elementData != EMPTY_ELEMENTDATA) ? 0 : DEFAULT_CAPACITY;
        if (minCapacity > minExpand) {
            ensureExplicitCapacity(minCapacity);
        }
    }

    //ArrayList集合內(nèi)元素的個數(shù)：
    public int size() {
        return size;
    }

    //判斷ArrayList集合元素是否為空：
    public boolean isEmpty() {
        return size == 0;
    }

    //判斷ArrayList集合包含某個元素：
    public boolean contains(Object o) {
        //判斷對象o在ArrayList中存在的角標(biāo)位置
        return indexOf(o) >= 0;
    }

    //判斷對象o在ArrayList中存在的角標(biāo)位置：
    public int indexOf(Object o) {
        //如果o==null：
        if (o == null) {
            //遍歷集合，判斷哪個元素等于null虚吟，則返回對應(yīng)角標(biāo)
            for (int i = 0; i < size; i++)
                if (elementData[i]==null)
                    return i;
        } else {
            //同理：
            for (int i = 0; i < size; i++)
                if (o.equals(elementData[i]))
                    return i;
        }
        //如果不存在寸认，則返回-1
        return -1;
    }

    //判斷對象o在ArrayList中出現(xiàn)的最后一個位置：
    public int lastIndexOf(Object o) {
        //如果o==null：
        if (o == null) {
            //從集合最后一個元素開始遍歷：
            for (int i = size-1; i >= 0; i--)
                if (elementData[i]==null)
                    return i;
        } else {
            //同理：
            for (int i = size-1; i >= 0; i--)
                if (o.equals(elementData[i]))
                    return i;
        }
        //如果不存在，則返回-1
        return -1;
    }

    //返回此ArrayList實(shí)例的 克隆對象：
    public Object clone() {
        try {
            java.util.ArrayList<E> v = (java.util.ArrayList<E>) super.clone();
            v.elementData = Arrays.copyOf(elementData, size);
            v.modCount = 0;
            return v;
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

    //將ArrayList里面的元素賦值到一個數(shù)組中去 生成Object數(shù)組：
    public Object[] toArray() {
        return Arrays.copyOf(elementData, size);
    }

    //將ArrayList里面的元素賦值到一個數(shù)組中去串慰，專成對應(yīng)類型的數(shù)組：
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            return (T[]) Arrays.copyOf(elementData, size, a.getClass());
        System.arraycopy(elementData, 0, a, 0, size);
        if (a.length > size)
            a[size] = null;
        return a;
    }

    //獲取數(shù)組index位置的元素：
    E elementData(int index) {
        return (E) elementData[index];
    }

    //獲取index位置的元素
    public E get(int index) {
        //檢查index是否合法：
        rangeCheck(index);
        //獲取元素：
        return elementData(index);
    }

    //設(shè)置index位置的元素值了element偏塞，返回該位置的之前的值
    public E set(int index, E element) {
        //檢查index是否合法：
        rangeCheck(index);
        //獲取該index原來的元素：
        E oldValue = elementData(index);
        //替換成新的元素：
        elementData[index] = element;
        //返回舊的元素：
        return oldValue;
    }

    //添加元素e
    public boolean add(E e) {
        ensureCapacityInternal(size + 1);
        elementData[size++] = e;
        return true;
    }

    //在ArrayList的index位置，添加元素element
    public void add(int index, E element) {
        //判斷index角標(biāo)的合法性：
        rangeCheckForAdd(index);
        //判斷是否需要擴(kuò)容：傳入當(dāng)前元素大小+1
        ensureCapacityInternal(size + 1);
        System.arraycopy(elementData, index, elementData, index + 1, size - index);
        elementData[index] = element;
        size++;
    }

    //得到最小擴(kuò)容量
    private void ensureCapacityInternal(int minCapacity) {
        //如果此時ArrayList是空數(shù)組,則將最小擴(kuò)容大小設(shè)置為10：
        if (elementData == EMPTY_ELEMENTDATA) {
            minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //判斷是否需要擴(kuò)容：
        ensureExplicitCapacity(minCapacity);
    }

    //判斷是否需要擴(kuò)容
    private void ensureExplicitCapacity(int minCapacity) {
        //操作數(shù)+1
        modCount++;
        //判斷最小擴(kuò)容容量-數(shù)組大小是否大于0：
        if (minCapacity - elementData.length > 0)
            //擴(kuò)容：
            grow(minCapacity);
    }

    //ArrayList最大容量：
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //幫助ArrayList動態(tài)擴(kuò)容的核心方法:
    private void grow(int minCapacity) {
        //獲取現(xiàn)有數(shù)組大邪铞辍：
        int oldCapacity = elementData.length;
        //位運(yùn)算灸叼，得帶新的數(shù)組容量大小，為原有的1.5倍：
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新擴(kuò)容的大小依舊小于傳入的容量值庆捺，那么將傳入的值設(shè)為新容器大泄沤瘛：
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;

        //如果新容器大小，大于ArrayList最大長度：
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            //計算出最大容量值：
            newCapacity = hugeCapacity(minCapacity);
        //數(shù)組復(fù)制：
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    //計算ArrayList最大容量：
    private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0)
            throw new OutOfMemoryError();
        //如果新的容量大于MAX_ARRAY_SIZE滔以。將會調(diào)用hugeCapacity將int的最大值賦給newCapacity:
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

    //在ArrayList的移除index位置的元素
    public E remove(int index) {
        //檢查角標(biāo)是否合法：不合法拋異常
        rangeCheck(index);
        //操作數(shù)+1：
        modCount++;
        //獲取當(dāng)前角標(biāo)的value:
        E oldValue = elementData(index);
        //獲取需要刪除元素 到最后一個元素的長度捉腥，也就是刪除元素后，后續(xù)元素移動的個數(shù)你画；
        int numMoved = size - index - 1;
        //如果移動元素個數(shù)大于0 抵碟，也就是說刪除的不是最后一個元素：
        if (numMoved > 0)
            // 將elementData數(shù)組index+1位置開始拷貝到elementData從index開始的空間
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        //size減1，并將最后一個元素置為null
        elementData[--size] = null;
        //返回被刪除的元素：
        return oldValue;
    }

    //在ArrayList的移除對象為O的元素撬即，不返回被刪除的元素：
    public boolean remove(Object o) {
        //如果o==null立磁，則遍歷集合呈队，判斷哪個元素為null：
        if (o == null) {
            for (int index = 0; index < size; index++)
                if (elementData[index] == null) {
                    //快速刪除剥槐，和前面的remove（index）一樣的邏輯
                    fastRemove(index);
                    return true;
                }
        } else {
            //同理：
            for (int index = 0; index < size; index++)
                if (o.equals(elementData[index])) {
                    fastRemove(index);
                    return true;
                }
        }
        return false;
    }

    //快速刪除：
    private void fastRemove(int index) {
        //操作數(shù)+1
        modCount++;
        //獲取需要刪除元素 到最后一個元素的長度，也就是刪除元素后宪摧，后續(xù)元素移動的個數(shù)粒竖；
        int numMoved = size - index - 1;
        //如果移動元素個數(shù)大于0 颅崩，也就是說刪除的不是最后一個元素：
        if (numMoved > 0)
            // 將elementData數(shù)組index+1位置開始拷貝到elementData從index開始的空間
            System.arraycopy(elementData, index+1, elementData, index, numMoved);
        //size減1，并將最后一個元素置為null
        elementData[--size] = null;
    }

    //設(shè)置全部元素為null值蕊苗，并設(shè)置size為0沿后。
    public void clear() {
        modCount++;
        for (int i = 0; i < size; i++)
            elementData[i] = null;
        size = 0;
    }

    //序列化寫入：
    private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException{
        int expectedModCount = modCount;
        s.defaultWriteObject();
        s.writeInt(size);
        for (int i=0; i<size; i++) {
            s.writeObject(elementData[i]);
        }
        if (modCount != expectedModCount) {
            throw new ConcurrentModificationException();
        }
    }

    // 序列化讀取：
    private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException {
        elementData = EMPTY_ELEMENTDATA;
        s.defaultReadObject();
        s.readInt();
        if (size > 0) {
            ensureCapacityInternal(size);
            Object[] a = elementData;
            for (int i=0; i<size; i++) {
                a[i] = s.readObject();
            }
        }
    }

    //檢查角標(biāo)是否合法：不合法拋異常
    private void rangeCheck(int index) {
        if (index >= size)
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    //返回一個Iterator對象朽砰，Itr為ArrayList的一個內(nèi)部類尖滚，其實(shí)現(xiàn)了Iterator<E>接口
    public Iterator<E> iterator() {
        return new java.util.ArrayList.Itr();
    }

    //其中的Itr是實(shí)現(xiàn)了Iterator接口，同時重寫了里面的hasNext()瞧柔，next()漆弄，remove()等方法；
    private class Itr implements Iterator<E> {
        int cursor; //類似游標(biāo)造锅，指向迭代器下一個值的位置
        int lastRet = -1; //迭代器最后一次取出的元素的位置撼唾。
        int expectedModCount = modCount;//Itr初始化時候ArrayList的modCount的值。
        //modCount用于記錄ArrayList內(nèi)發(fā)生結(jié)構(gòu)性改變的次數(shù)哥蔚，
        // 而Itr每次進(jìn)行next或remove的時候都會去檢查expectedModCount值是否還和現(xiàn)在的modCount值倒谷，
        // 從而保證了迭代器和ArrayList內(nèi)數(shù)據(jù)的一致性。

        //利用游標(biāo)糙箍，與size之前的比較渤愁，判斷迭代器是否還有下一個元素
        public boolean hasNext() {
            return cursor != size;
        }

        //迭代器獲取下一個元素：
        public E next() {
            //檢查modCount是否改變：
            checkForComodification();

            int i = cursor;

            //游標(biāo)不會大于等于集合的長度：
            if (i >= size)
                throw new NoSuchElementException();

            Object[] elementData = java.util.ArrayList.this.elementData;
            //游標(biāo)不會大于集合中數(shù)組的長度：
            if (i >= elementData.length)
                throw new ConcurrentModificationException();
            //游標(biāo)+1
            cursor = i + 1;
            //取出元素：
            return (E) elementData[lastRet = i];
        }

        public void remove() {
            if (lastRet < 0)
                throw new IllegalStateException();
            //檢查modCount是否改變：防止并發(fā)操作集合
            checkForComodification();
            try {
                //刪除這個元素：
                java.util.ArrayList.this.remove(lastRet);
                //刪除后，重置游標(biāo)倍靡，和當(dāng)前指向元素的角標(biāo) lastRet
                cursor = lastRet;
                lastRet = -1;
                //重置expectedModCount：
                expectedModCount = modCount;
            } catch (IndexOutOfBoundsException ex) {
                throw new ConcurrentModificationException();
            }
        }

        //并發(fā)檢查：在Itr初始化時猴伶，將modCount賦值給了expectedModCount
        //如果后續(xù)modCount還有變化，則拋出異常塌西，所以在迭代器迭代過程中他挎，不能調(diào)List增刪操作；
        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
}

LinkedList

完整源碼：

public class LinkedList<E> extends AbstractSequentialList<E>
        implements List<E>, Deque<E>, Cloneable, java.io.Serializable {

    //LinkedList的元素個數(shù)：
    transient int size = 0;

    //LinkedList的頭結(jié)點(diǎn)：Node內(nèi)部類
    transient java.util.LinkedList.Node<E> first;

    //LinkedList尾結(jié)點(diǎn)：Node內(nèi)部類
    transient java.util.LinkedList.Node<E> last;

    //空實(shí)現(xiàn)：
    public LinkedList() {
    }

    //調(diào)用添加方法：
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    //LinkedList添加首結(jié)點(diǎn) first：
    public void addFirst(E e) {
        linkFirst(e);
    }
    //first節(jié)點(diǎn)插入新元素：addFirst()調(diào)用
    private void linkFirst(E e) {
        //頭結(jié)點(diǎn)：
        final java.util.LinkedList.Node<E> f = first;
        //創(chuàng)建一個新節(jié)點(diǎn)捡需，并指向頭結(jié)點(diǎn)f：
        final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(null, e, f);
        //將新節(jié)點(diǎn)賦值給頭幾點(diǎn)：
        first = newNode;
        //如果頭節(jié)點(diǎn)為null办桨，則是第一個元素插入，將新節(jié)點(diǎn)也設(shè)置為尾結(jié)點(diǎn)站辉；
        if (f == null)
            last = newNode;
        else
            //將之前的頭結(jié)點(diǎn)的前指針指向新的結(jié)點(diǎn)：
            f.prev = newNode;
        //長度+1
        size++;
        //操作數(shù)+1
        modCount++;
    }

    //添加元素：添加到最后一個結(jié)點(diǎn)呢撞；
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    //添加最后一個結(jié)點(diǎn) last：
    public void addLast(E e) {
        linkLast(e);
    }

    //last節(jié)點(diǎn)插入新元素：addLast()調(diào)用
    void linkLast(E e) {
        //將尾結(jié)點(diǎn)賦值個體L:
        final java.util.LinkedList.Node<E> l = last;
        //創(chuàng)建新的結(jié)點(diǎn)，將新節(jié)點(diǎn)的前指針指向l:
        final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(l, e, null);
        //新節(jié)點(diǎn)置為尾結(jié)點(diǎn)：
        last = newNode;
        //如果尾結(jié)點(diǎn)l為null：則是空集合新插入
        if (l == null)
            //頭結(jié)點(diǎn)也置為 新節(jié)點(diǎn)：
            first = newNode;
        else
            //l節(jié)點(diǎn)的后指針指向新節(jié)點(diǎn)：
            l.next = newNode;
        //長度+1
        size++;
        //操作數(shù)+1
        modCount++;
    }

    //向?qū)?yīng)角標(biāo)添加元素：
    public void add(int index, E element) {
        //檢查傳入的角標(biāo) 是否正確：
        checkPositionIndex(index);
        //如果插入角標(biāo)==集合長度饰剥，則插入到集合的最后面：
        if (index == size)
            linkLast(element);
        else
            //插入到對應(yīng)角標(biāo)的位置：獲取此角標(biāo)下的元素先
            linkBefore(element, node(index));
    }
    //在succ前插入 新元素e：
    void linkBefore(E e, java.util.LinkedList.Node<E> succ) {
        //獲取被插入元素succ的前指針元素：
        final java.util.LinkedList.Node<E> pred = succ.prev;
        //創(chuàng)建新增元素節(jié)點(diǎn)殊霞，前指針 和 后指針分別指向?qū)?yīng)元素：
        final java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(pred, e, succ);
        succ.prev = newNode;
        //succ的前指針元素可能為null，為null的話說明succ是頭結(jié)點(diǎn)汰蓉，則把新建立的結(jié)點(diǎn)置為頭結(jié)點(diǎn)：
        if (pred == null)
            first = newNode;
        else
            //succ前指針不為null绷蹲，則將前指針的結(jié)點(diǎn)的后指針指向新節(jié)點(diǎn)：
            pred.next = newNode;
        //長度+1
        size++;
        //操作數(shù)+1
        modCount++;
    }
    //移除首個結(jié)點(diǎn)：如果集合還沒有元素則報錯
    public E removeFirst() {
        final java.util.LinkedList.Node<E> f = first;
        //首節(jié)點(diǎn)為null，則拋出異常；
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    //刪除LinkedList的頭結(jié)點(diǎn)：removeFirst()方法調(diào)用
    private E unlinkFirst(java.util.LinkedList.Node<E> f) {
        //f為頭結(jié)點(diǎn)：獲取頭結(jié)點(diǎn)元素E
        final E element = f.item;
        //獲取頭結(jié)點(diǎn)的尾指針結(jié)點(diǎn)：
        final java.util.LinkedList.Node<E> next = f.next;
        //將頭結(jié)點(diǎn)元素置為null：
        f.item = null;
        //頭結(jié)點(diǎn)尾指針置為null：
        f.next = null;
        //將頭結(jié)點(diǎn)的尾指針指向的結(jié)點(diǎn)next置為first
        first = next;
        //尾指針指向結(jié)點(diǎn)next為null的話祝钢，就將尾結(jié)點(diǎn)也置為null（LinkedList中只有一個元素時出現(xiàn)）
        if (next == null)
            last = null;
        else
            //將尾指針指向結(jié)點(diǎn)next的 前指針置為null比规；
            next.prev = null;
        // 長度減1
        size--;
        //操作數(shù)+1
        modCount++;
        //返回被刪除的元素：
        return element;
    }

    //移除最后一個結(jié)點(diǎn)：如果集合還沒有元素則報錯
    public E removeLast() {
        //獲取最后一個結(jié)點(diǎn)：
        final java.util.LinkedList.Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        //刪除尾結(jié)點(diǎn)：
        return unlinkLast(l);
    }
    //刪除LinkedList的尾結(jié)點(diǎn)：removeLast()方法調(diào)用
    private E unlinkLast(java.util.LinkedList.Node<E> l) {
        final E element = l.item;
        final java.util.LinkedList.Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        last = prev;
        if (prev == null)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

    //刪除LinkedList中的元素，可以刪除為null的元素拦英，逐個遍歷LinkedList的元素蜒什；
    //重復(fù)元素只刪除第一個：
    public boolean remove(Object o) {
        //如果刪除元素為null：
        if (o == null) {
            for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            //如果刪除元素不為null：
            for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }
    //移除LinkedList結(jié)點(diǎn)：remove()方法中調(diào)用
    E unlink(java.util.LinkedList.Node<E> x) {
        //獲取被刪除結(jié)點(diǎn)的元素E：
        final E element = x.item;
        //獲取被刪除元素的后指針結(jié)點(diǎn)：
        final java.util.LinkedList.Node<E> next = x.next;
        //獲取被刪除元素的前指針結(jié)點(diǎn)：
        final java.util.LinkedList.Node<E> prev = x.prev;

        //被刪除結(jié)點(diǎn)的 前結(jié)點(diǎn)為null的話：
        if (prev == null) {
            //將后指針指向的結(jié)點(diǎn)置為頭結(jié)點(diǎn)
            first = next;
        } else {
            //前置結(jié)點(diǎn)的  尾結(jié)點(diǎn)指向被刪除的next結(jié)點(diǎn)；
            prev.next = next;
            //被刪除結(jié)點(diǎn)前指針置為null:
            x.prev = null;
        }
        //對尾結(jié)點(diǎn)同樣處理：
        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }

        x.item = null;
        size--;
        modCount++;
        return element;
    }

    //得到首個結(jié)點(diǎn)：集合沒有元素報錯
    public E getFirst() {
        //獲取first結(jié)點(diǎn)：
        final java.util.LinkedList.Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    //得到最后一個結(jié)點(diǎn)：集合沒有元素報錯
    public E getLast() {
        //獲取last結(jié)點(diǎn)：
        final java.util.LinkedList.Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

    //判斷obj 是否存在：
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }
    //LinkedList長度：
    public int size() {
        return size;
    }

    //添加集合：從最后size所在的index開始：
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }
    //LinkedList添加集合：
    public boolean addAll(int index, Collection<? extends E> c) {
        //檢查角標(biāo)是否正確：
        checkPositionIndex(index);
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;
        java.util.LinkedList.Node<E> pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }
        for (Object o : a) {
            E e = (E) o;
            java.util.LinkedList.Node<E> newNode = new java.util.LinkedList.Node<>(pred, e, null);
            if (pred == null)
                first = newNode;
            else
                pred.next = newNode;
            pred = newNode;
        }
        if (succ == null) {
            last = pred;
        } else {
            pred.next = succ;
            succ.prev = pred;
        }
        size += numNew;
        modCount++;
        return true;
    }

    //清空LinkedList：
    public void clear() {
        //遍歷LinedList集合：
        for (java.util.LinkedList.Node<E> x = first; x != null; ) {
            //將每個結(jié)點(diǎn)的前指針 尾指針  元素都置為null：
            java.util.LinkedList.Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        //頭尾結(jié)點(diǎn) 都置為null：
        first = last = null;
        //長度置為0
        size = 0;
        //操作數(shù)+1：
        modCount++;
    }

    //獲取相應(yīng)角標(biāo)的元素：
    public E get(int index) {
        //檢查角標(biāo)是否正確：
        checkElementIndex(index);
        //獲取角標(biāo)所屬結(jié)點(diǎn)的 元素值：
        return node(index).item;
    }

    //設(shè)置對應(yīng)角標(biāo)的元素：
    public E set(int index, E element) {
        checkElementIndex(index);
        java.util.LinkedList.Node<E> x = node(index);
        E oldVal = x.item;
        x.item = element;
        return oldVal;
    }

    //刪除對應(yīng)角標(biāo)的元素：
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));
    }

    //獲取對應(yīng)角標(biāo)所屬于的結(jié)點(diǎn)：
    java.util.LinkedList.Node<E> node(int index) {
        //位運(yùn)算：如果位置索引小于列表長度的一半疤估，從前面開始遍歷灾常；否則，從后面開始遍歷铃拇；
        if (index < (size >> 1)) {
            java.util.LinkedList.Node<E> x = first;
            //從頭結(jié)點(diǎn)開始遍歷：遍歷的長度就是index的長度岗憋，獲取對應(yīng)的index的元素
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            //從集合尾結(jié)點(diǎn)遍歷：
            java.util.LinkedList.Node<E> x = last;
            //同樣道理：
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }
    // 左移相當(dāng)于*2，只是要注意邊界問題锚贱。如char a = 65仔戈； a<<1 按照*2來算為130;
    // 但有符號char的取值范圍-128~127拧廊，已經(jīng)越界，多超出了3個數(shù)值吧碾，
    // 所以從-128算起的第三個數(shù)值-126才是a<<1的正確結(jié)果。
    //而右移相當(dāng)于除以2倦春，只是要注意移位比較多的時候結(jié)果會趨近去一個非常小的數(shù)，如上面結(jié)果中的-1尿庐，0。

    private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

    //判斷傳入的index是否正確：
    private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

    private String outOfBoundsMsg(int index) {
        return "Index: "+index+", Size: "+size;
    }

    private void checkElementIndex(int index) {
        if (!isElementIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }

    //檢查傳入的角標(biāo) 是否正確：
    private void checkPositionIndex(int index) {
        //必須大于0 抄瑟，并且不能大于當(dāng)前size：
        if (!isPositionIndex(index))
            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
    }
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {
            for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
            for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (java.util.LinkedList.Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (java.util.LinkedList.Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

    //獲取第一個元素，不存在則拋異常
    public E element() {
        return getFirst();
    }

    //出隊(duì)枉疼，獲取第一個元素皮假，不出隊(duì)列，只是獲取
    // 隊(duì)列先進(jìn)先出骂维；不存在不拋異常惹资，返回null
    public E peek() {
        //獲取頭結(jié)點(diǎn)：
        final java.util.LinkedList.Node<E> f = first;
        //存在獲取頭結(jié)點(diǎn)元素，不存在返回null
        return (f == null) ? null : f.item;
    }

    //出隊(duì)航闺，并移除第一個元素褪测；不存在不拋異常。
    public E poll() {
        final java.util.LinkedList.Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    //出隊(duì)（刪除第一個結(jié)點(diǎn)），如果不存在會拋出異常而不是返回null汰扭，存在的話會返回值并移除這個元素（節(jié)點(diǎn)）
    public E remove() {
        return removeFirst();
    }

    //入隊(duì)(插入最后一個結(jié)點(diǎn))從最后一個元素
    public boolean offer(E e) {
        return add(e);
    }

    //入隊(duì)（插入頭結(jié)點(diǎn)），始終返回true
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

    //入隊(duì)（插入尾結(jié)點(diǎn)）福铅，始終返回true
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

    //出隊(duì)（從前端）萝毛，獲得第一個元素，不存在會返回null滑黔，不會刪除元素（節(jié)點(diǎn)）
    public E peekFirst() {
        final java.util.LinkedList.Node<E> f = first;
        return (f == null) ? null : f.item;
    }

    //出隊(duì)（從后端）笆包，獲得最后一個元素，不存在會返回null略荡，不會刪除元素（節(jié)點(diǎn)）
    public E peekLast() {
        final java.util.LinkedList.Node<E> l = last;
        return (l == null) ? null : l.item;
    }

    //出隊(duì)（從前端）庵佣，獲得第一個元素，不存在會返回null汛兜，會刪除元素（節(jié)點(diǎn)）
    public E pollFirst() {
        final java.util.LinkedList.Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    //出隊(duì)（從后端）巴粪，獲得最后一個元素，不存在會返回null粥谬，會刪除元素（節(jié)點(diǎn)）
    public E pollLast() {
        final java.util.LinkedList.Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

    //入棧肛根，從前面添加  棧 后進(jìn)先出
    public void push(E e) {
        addFirst(e);
    }

    //出棧，返回棧頂元素漏策，從前面移除（會刪除）
    public E pop() {
        return removeFirst();
    }

    //節(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)派哲，包含前后節(jié)點(diǎn)的引用和當(dāng)前節(jié)點(diǎn)
    private static class Node<E> {
        //結(jié)點(diǎn)元素：
        E item;
        //結(jié)點(diǎn)后指針
        java.util.LinkedList.Node<E> next;
        //結(jié)點(diǎn)前指針
        java.util.LinkedList.Node<E> prev;

        Node(java.util.LinkedList.Node<E> prev, E element, java.util.LinkedList.Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
        
    //迭代器：
    public ListIterator<E> listIterator(int index) {
        checkPositionIndex(index);
        return new java.util.LinkedList.ListItr(index);
    }
    private class ListItr implements ListIterator<E> {
        private java.util.LinkedList.Node<E> lastReturned = null;
        private java.util.LinkedList.Node<E> next;
        private int nextIndex;
        private int expectedModCount = modCount;

        ListItr(int index) {
            next = (index == size) ? null : node(index);
            nextIndex = index;
        }

        public boolean hasNext() {
            return nextIndex < size;
        }

        public E next() {
            checkForComodification();
            if (!hasNext())
                throw new NoSuchElementException();

            lastReturned = next;
            next = next.next;
            nextIndex++;
            return lastReturned.item;
        }

        public boolean hasPrevious() {
            return nextIndex > 0;
        }

        public E previous() {
            checkForComodification();
            if (!hasPrevious())
                throw new NoSuchElementException();

            lastReturned = next = (next == null) ? last : next.prev;
            nextIndex--;
            return lastReturned.item;
        }

        public int nextIndex() {
            return nextIndex;
        }

        public int previousIndex() {
            return nextIndex - 1;
        }

        public void remove() {
            checkForComodification();
            if (lastReturned == null)
                throw new IllegalStateException();

            java.util.LinkedList.Node<E> lastNext = lastReturned.next;
            unlink(lastReturned);
            if (next == lastReturned)
                next = lastNext;
            else
                nextIndex--;
            lastReturned = null;
            expectedModCount++;
        }

        public void set(E e) {
            if (lastReturned == null)
                throw new IllegalStateException();
            checkForComodification();
            lastReturned.item = e;
        }

        public void add(E e) {
            checkForComodification();
            lastReturned = null;
            if (next == null)
                linkLast(e);
            else
                linkBefore(e, next);
            nextIndex++;
            expectedModCount++;
        }

        final void checkForComodification() {
            if (modCount != expectedModCount)
                throw new ConcurrentModificationException();
        }
    }
   
    private java.util.LinkedList<E> superClone() {
        try {
            return (java.util.LinkedList<E>) super.clone();
        } catch (CloneNotSupportedException e) {
            throw new InternalError();
        }
    }

    public Object clone() {
        java.util.LinkedList<E> clone = superClone();
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;
        for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);
        return clone;
    }

    public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
        for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }
    @SuppressWarnings("unchecked")
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                    a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;

        if (a.length > size)
            a[size] = null;

        return a;
    }

    private static final long serialVersionUID = 876323262645176354L;

    private void writeObject(java.io.ObjectOutputStream s)
            throws java.io.IOException {
        s.defaultWriteObject();

        s.writeInt(size);

        for (java.util.LinkedList.Node<E> x = first; x != null; x = x.next)
            s.writeObject(x.item);
    }
    @SuppressWarnings("unchecked")
    private void readObject(java.io.ObjectInputStream s)
            throws java.io.IOException, ClassNotFoundException {
        s.defaultReadObject();

        int size = s.readInt();

        for (int i = 0; i < size; i++)
            linkLast((E)s.readObject());
    }
}