LinkedList

• 介紹

  LinkedList是基于雙向鏈表實(shí)現(xiàn)的；

  隨機(jī)訪問頭部與尾部速度快；

  隨機(jī)中間值速度較慢，因為需要移動指針；

  頭部與尾部插入與刪除速度快；

  中間插入就略慢一下，因為需要移動指針；

  其實(shí)現(xiàn)了Deque接口；可當(dāng)一個Deque使用

• 重要屬性

//List的大小
transient int size = 0;
//頭部節(jié)點(diǎn)
transient Node<E> first;
//尾部節(jié)點(diǎn)
transient Node<E> last;

• add方法

public boolean add(E e) {
    linkLast(e);
    return true;
}
void linkLast(E e) {
    //獲取尾部節(jié)點(diǎn)
    final Node<E> l = last;
    //創(chuàng)建新節(jié)點(diǎn)，使其上一個節(jié)點(diǎn)指向尾部節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(l, e, null);
    //更新尾部節(jié)點(diǎn)
    last = newNode;
    if (l == null)
        //如果l是空的，說明add之前無元素，將頭部節(jié)點(diǎn)指向新節(jié)點(diǎn)
        first = newNode;
    else
        //將原尾部節(jié)點(diǎn)指向新的節(jié)點(diǎn)
        l.next = newNode;
    size++;
    modCount++;
}

尾部添加一個節(jié)點(diǎn)步驟：

newNode.prev=last => last.next=newNode => last=newNode

與ArrayList相比，ArrayList可能會觸發(fā)擴(kuò)容操作(影響速度)，LinkedList則是直接追加道最后一個節(jié)點(diǎn)

• addLast方法

//與add方法邏輯一致
public void addLast(E e) {
    linkLast(e);
}

• addFirst方法

public void addFirst(E e) {
    linkFirst(e);
}
private void linkFirst(E e) {
    //獲取頭節(jié)點(diǎn)
    final Node<E> f = first;
    //創(chuàng)建新節(jié)點(diǎn)，使其下一個節(jié)點(diǎn)指向頭節(jié)點(diǎn)
    final Node<E> newNode = new Node<>(null, e, f);
    //更新頭節(jié)點(diǎn)
    first = newNode;
    if (f == null)
        //將尾部節(jié)點(diǎn)指向新節(jié)點(diǎn)
        last = newNode;
    else
        //將原頭部節(jié)點(diǎn)指向新的節(jié)點(diǎn)
        f.prev = newNode;
    size++;
    modCount++;
}

頭部添加一個節(jié)點(diǎn)步驟：

newNode.next=first => first.prev=newNode => first=newNode

與ArrayList相比，ArrayList向頭部添加一個元素需要后面元素copy移位，還可能觸發(fā)擴(kuò)容；效率上LinkedList指定搞一些

• add方法(添加到指定位置)

public void add(int index, E element) {
    //檢查index是否有越界
    checkPositionIndex(index);
    //index與size相等，則是往尾部添加
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
//往指定節(jié)點(diǎn)succ前插入一節(jié)點(diǎn)
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++;
}

指定節(jié)點(diǎn)前插入一個新節(jié)點(diǎn)步驟：

newNode.pred=succ.prev => newNode.next=succ => succ.prev.next=newNode

與ArrayList相比，ArrayList需要移位index后元素，LinkedList需要遍歷尋找節(jié)點(diǎn)

• addAll方法

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;
    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new 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;
}

如果是往尾部添加的話，直接for循環(huán)往后鏈就得了；

如果不是的話，先遍歷找到index對應(yīng)的節(jié)點(diǎn)，然后再往下鏈，鏈完后，與尾部接上即可了；

與ArrayList相比，ArrayList尾部添加的話，copy一次數(shù)組；ArrayList中間插入的話需copy兩次數(shù)組；

• get方法

public E get(int index) {
    //檢查index是否有越界
    checkElementIndex(index);
    return node(index).item;
}
//根據(jù)index獲取節(jié)點(diǎn)，通過遍歷子節(jié)點(diǎn)方式
Node<E> node(int index) {
    //判斷如果index小于size的一半，則從頭部開始遍歷子節(jié)點(diǎn)；否則從尾部遍歷子節(jié)點(diǎn)
    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;
    }
}

與ArrayList相比，LinkedList.get效率略低，需要遍歷子節(jié)點(diǎn)查詢。

• set方法

//根據(jù)index獲取子節(jié)點(diǎn)，然后替換其值
public E set(int index, E element) {
    //檢查index是否有越界
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

與ArrayList相比，LinkedList.set效率略低，需要遍歷子節(jié)點(diǎn)查詢。

• remove方法(根據(jù)元素移除)

//遍歷找到節(jié)點(diǎn)，然后移除
public boolean remove(Object o) {
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}
//移除一個節(jié)點(diǎn)
E unlink(Node<E> x) {
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;
    if (prev == null) {
        first = next;
    } else {
        prev.next = next;
        x.prev = null;
    }
    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }
    x.item = null;
    size--;
    modCount++;
    return element;
}

移除一個節(jié)點(diǎn)的步驟：

x.prev.next=x.next => x.next.prev=x.prev => x...=null

與ArrayList相比，ArrayList遍歷后得到index，然后移除(需要index后元素移位)，LinkedList遍歷得到節(jié)點(diǎn)，直接移除。

• remove方法(根據(jù)index移除)

//遍歷獲取節(jié)點(diǎn)，然后移除
public E remove(int index) {
    //檢查index是否有越界
    checkElementIndex(index);
    return unlink(node(index));
}

與ArrayList相比，ArrayList移除元素后index后元素移位，LinkedList是遍歷取得節(jié)點(diǎn)直接移除

• clear方法

public void clear() {
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null;
    size = 0;
    modCount++;
}

與ArrayList.clear 差不多，都是遍歷置空數(shù)據(jù)