1. 簡(jiǎn)介

LinkedList基于鏈表實(shí)現(xiàn)，非線程安全，其既實(shí)現(xiàn)了List接口又實(shí)現(xiàn)了Deque接口，所以既可以做為列表使用又可以做雙端隊(duì)列使用，隊(duì)頭隊(duì)尾插入刪除時(shí)間復(fù)雜度都為O(1)，查找效率為O(n)。

2. 實(shí)現(xiàn)

結(jié)點(diǎn)類型

private static class Node<E> {
    E item;
    // 下一個(gè)結(jié)點(diǎn)
    Node<E> next;
    // 上一個(gè)結(jié)點(diǎn)
    Node<E> prev;

    Node(Node<E> prev, E element, Node<E> next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

屬性

// 結(jié)點(diǎn)數(shù)量
transient int size = 0;

// 指向鏈表頭結(jié)點(diǎn)
transient Node<E> first;

// 指向鏈表尾結(jié)點(diǎn)
transient Node<E> last;

構(gòu)造函數(shù)

// 構(gòu)造函數(shù)為空
public LinkedList() {
}

獲取索引對(duì)應(yīng)的結(jié)點(diǎn)

用鏈表實(shí)現(xiàn)的List不同于數(shù)組，查找對(duì)應(yīng)索引的結(jié)點(diǎn)不支持隨機(jī)訪問，只能遍歷鏈表找到對(duì)應(yīng)位置的結(jié)點(diǎn)。
因?yàn)槌钟蓄^尾結(jié)點(diǎn)的引用所以可以根據(jù)索引位于List中的位置而搜索對(duì)應(yīng)的部分進(jìn)一步提高搜索效率。

Node<E> node(int index) {
    // assert isElementIndex(index);
    // 如果索引位于List的前半部分則從頭結(jié)點(diǎn)開始搜索
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else { // 否則從尾結(jié)點(diǎn)開始搜索
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

增刪改查方法

// 將新結(jié)點(diǎn)插入到List后面
void linkLast(E e) {
    final Node<E> l = last;
    // 創(chuàng)建新結(jié)點(diǎn)
    final Node<E> newNode = new Node<>(l, e, null);
    // 尾指針指向新結(jié)點(diǎn)
    last = newNode;
    // 如果之前不存在尾結(jié)點(diǎn)則設(shè)置頭指針為新結(jié)點(diǎn)
    if (l == null)
        first = newNode;
    else // 否則將原來的尾結(jié)點(diǎn)指向新結(jié)點(diǎn)
        l.next = newNode;
    size++;
    modCount++;
}

// 調(diào)用linkLast方法將元素e作為新結(jié)點(diǎn)插入List后面
public boolean add(E e) {
    linkLast(e);
    return true;
}

public boolean remove(Object o) {
    // 如果要移除的結(jié)點(diǎn)為空則從頭結(jié)點(diǎn)開始遍歷直到找到值為空的結(jié)點(diǎn)將其鏈接釋放
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else { //否則找到一個(gè)值相等的結(jié)點(diǎn)
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

// 遍歷鏈表把每一個(gè)結(jié)點(diǎn)的屬性都設(shè)置為null
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++;
}

// 獲取指定位置上的值
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

// 找到其對(duì)應(yīng)結(jié)點(diǎn)修改其值并返回舊值
public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

// 將元素作為新結(jié)點(diǎn)插入到指定位置
public void add(int index, E element) {
    // 判斷插入位置是否在有效范圍
    checkPositionIndex(index);
    // 如果插入位置在尾部則調(diào)用linkLast方法插入
    if (index == size)
        linkLast(element);
    else // 找到對(duì)應(yīng)位置上的結(jié)點(diǎn)插入其前面
        linkBefore(element, node(index));
}

public E remove(int index) {
    // 判斷索引位置是否合法
    checkElementIndex(index);
    // 找到指定位置對(duì)應(yīng)的結(jié)點(diǎn)將其釋放其鏈接
    return unlink(node(index));
}

toArray方法

創(chuàng)建一個(gè)數(shù)組，將鏈表所有結(jié)點(diǎn)的值都一一賦值到該數(shù)組上

public Object[] toArray() {
    Object[] result = new Object[size];
    int i = 0;
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;
    return result;
}