LinkedList源码解读

LinkedList

• 介绍

  LinkedList是基于双向链表实现的；

  随机访问头部与尾部速度快；

  随机中间值速度较慢，因为需要移动指针；

  头部与尾部插入与删除速度快；

  中间插入就略慢一下，因为需要移动指针；

  其实现了Deque接口；可当一个Deque使用

• 重要属性

//List的大小
transient int size = 0;
//头部节点
transient Node<E> first;
//尾部节点
transient Node<E> last;

• 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)
        //如果l是空的，说明add之前无元素，将头部节点指向新节点
        first = newNode;
    else
        //将原尾部节点指向新的节点
        l.next = newNode;
    size++;
    modCount++;
}

尾部添加一个节点步骤：

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

与ArrayList相比，ArrayList可能会触发扩容操作(影响速度)，LinkedList则是直接追加道最后一个节点

• addLast方法

//与add方法逻辑一致
public void addLast(E e) {
    linkLast(e);
}

• addFirst方法

public void addFirst(E e) {
    linkFirst(e);
}
private void linkFirst(E e) {
    //获取头节点
    final Node<E> f = first;
    //创建新节点，使其下一个节点指向头节点
    final Node<E> newNode = new Node<>(null, e, f);
    //更新头节点
    first = newNode;
    if (f == null)
        //将尾部节点指向新节点
        last = newNode;
    else
        //将原头部节点指向新的节点
        f.prev = newNode;
    size++;
    modCount++;
}

头部添加一个节点步骤：

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

与ArrayList相比，ArrayList向头部添加一个元素需要后面元素copy移位，还可能触发扩容；效率上LinkedList指定搞一些

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

public void add(int index, E element) {
    //检查index是否有越界
    checkPositionIndex(index);
    //index与size相等，则是往尾部添加
    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}
//往指定节点succ前插入一节点
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++;
}

指定节点前插入一个新节点步骤：

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

与ArrayList相比，ArrayList需要移位index后元素，LinkedList需要遍历寻找节点

• 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循环往后链就得了；

如果不是的话，先遍历找到index对应的节点，然后再往下链，链完后，与尾部接上即可了；

与ArrayList相比，ArrayList尾部添加的话，copy一次数组；ArrayList中间插入的话需copy两次数组；

• get方法

public E get(int index) {
    //检查index是否有越界
    checkElementIndex(index);
    return node(index).item;
}
//根据index获取节点，通过遍历子节点方式
Node<E> node(int index) {
    //判断如果index小于size的一半，则从头部开始遍历子节点；否则从尾部遍历子节点
    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效率略低，需要遍历子节点查询。

• set方法

//根据index获取子节点，然后替换其值
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效率略低，需要遍历子节点查询。

• 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;
}
//移除一个节点
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;
}

移除一个节点的步骤：

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

与ArrayList相比，ArrayList遍历后得到index，然后移除(需要index后元素移位)，LinkedList遍历得到节点，直接移除。

• remove方法(根据index移除)

//遍历获取节点，然后移除
public E remove(int index) {
    //检查index是否有越界
    checkElementIndex(index);
    return unlink(node(index));
}

与ArrayList相比，ArrayList移除元素后index后元素移位，LinkedList是遍历取得节点直接移除

• 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 差不多，都是遍历置空数据