【Java基礎】LinkedList工作原理

LinkedList

以雙向鏈表實現。鏈表無容量限制，但雙向鏈表本身使用了更多空間，每插入一個元素都要構造一個額外的Node對象，也需要額外的鏈表指針操作。按下標訪問元素－get（i）、set（i,e）要悲劇的部分遍歷鏈表將指針移動到位（如果i>數組大小的一半，會從末尾移起）。插入、刪除元素時修改前後節點的指針即可，不再需要復制移動。但還是要部分遍歷鏈表的指針才能移動到下標所指的位置。只有在鏈表兩頭的操作－add（）、addFirst（）、removeLast（）或用iterator（）上的remove（）倒能省掉指針的移動。

// Node為LinkedList的內部類，它定義了存儲的元素，上一個元素，下一個元素，這是典型的雙向鏈表的定義方式。
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;
    }
}

構造方法

LinkedList提供了兩個構造方法：

• LinkedList()：構造一個空的LinkedList

• LinkedList(Collection<? extends E> c)：構造一個包含指定元素的LinkedList

add()

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++; // 容量修改次數分別+1
}

調用add()方法，將元素追加到鏈表末尾。除了add()方法，還提供了其他add方法

• addFirst(E e)：插入新元素到鏈表頭部
• addLast(E e)：插入新元素到鏈表尾部
• addAll(Collection<? extends E> c)：插入新的集合
• addAll(int index, Collection<? extends E> c)：在指定位置插入新的集合

remove()

// 移除鏈表中遇到的第一個指定元素，如果列表中不包含，不做任何操作
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;
}

set()

// 替換指定位置的元素
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

get()

// 返回指定位置的元素
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}