LinkedList源码解读（最网最详细）

2022-12-30 10:28:11

LinkedList源码解读

LinkedList的继承结构

LinkedList的属性

LinkedList的构造器

LinkedList的核心方法

FailFast机制

LinkedList的继承结构

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

LinkedList的属性

/**
 * LinkedList 双向链表的长度
 */
transient int size = 0;
/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 * 指针，指向双向链表的首结点，初始值为null
 */
transient Node<E> first;
/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 * 指针，指向双向链表的尾结点，初始值为null
 */
transient Node<E> last;
/**
 * 一个私有静态内部类，很重要的数据结构，代表双向链表的一个结点
 */ 
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;
    }
}
/**
 * 记录双向链表添加、删除结点的次数，这个属性继承自直接父类AbstractSequentialList的父类AbstractList，用于在并发环境下，同时读、写双向链表时保护数据安全
 */
protected transient int modCount = 0;

LinkedList的构造器

  • 无参构造器

    public LinkedList() {    //啥也没干
}

  • 有参构造器

    public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

    调用了另一个重载的addAll方法addAll方法

    public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

    重载的addAll方法定义如下，这里只看执行路线

    public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);    // 校验索引位置是否合法，0 合法

    Object[] a = c.toArray();    // 集合转数组
    int numNew = a.length;    // 获取转化后的数组长度，后面要做链表长度的增加
    if (numNew == 0)
        return false;

    Node<E> pred, succ;    // pred:指向待插入结点的前结点；succ:指向待插入结点的后结点
    if (index == size) {    //走这里，在尾部添加，succ为null，pred为last所指向的尾结点
        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);    //组装结点，前指针指向尾结点，后指针为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的核心方法

  1. addFirst (E e)方法

    public void addFirst(E e) {
    linkFirst(e);
}

    调用私有的linkFirst方法，linkFirst (E 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++;
}

    双向链表的头插法。

    这个方法用于在双向链表的首部添加元素，首先定义一个新结点，新结点的前指针指向null，后指针指向原首结点，把新结点作为首结点，然后判断原首结点是否为null，是则说明原链表没有任何结点，并将新结点同时也作为尾结点，否则令原首结点的前指针指向新结点，双向链表的长度加1。

  2. addLast (E e)方法

    public void addLast(E e) {
    linkLast(e);
}

    调用私有的linkLast方法，linkLast (E e)方法定义如下

    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++;
}

    双向链表的尾插法。

    这个方法用于在双向链表的尾部添加一个元素，首先定义一个新结点，新结点的前指针指向原尾结点，后指针指向null，把新结点作为尾结点，然后判断原尾结点是否为null，是则说明原链表没有任何结点，并把新结点同时也作为首结点，否则令原尾结点的后指针指向新结点，双向链表的长度加1。

  3. removeFirst ()方法

    public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

    这个方法用于删除双向链表的首结点。

    先判断首结点是否存在，不存在，则抛出NoSuchElementException异常，否则调用unlinkFirst方法删除首结点。

    unlinkFirst方法定义如下

    private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

    先找到首结点的下一个结点next，让首结点的后指针指向为null，把next结点作为新的首结点，然后判断next结点是否存在，若存在，则取消next结点前指针的指向，原首结点失去应用会被GC回收，若不存在，则说明原链表只有首结点这一个结点，令last指针指向为null，原首结点同时失去first和last的引用，触发GC，被回收。删除成功，双向链表长度减1。

  4. removeLast ()方法

    public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

    这个方法用于删除双向链表的尾结点。

    先判断尾结点是否存在，若不存在，则抛出NoSuchElementException异常，否则，调用unlinkLast方法删除尾结点。

    unlinkLast方法定义如下

    private E unlinkLast(Node<E> l) {
    // assert l == last && l != null;
    final E element = l.item;
    final 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;
}

    先找到原尾结点的上一个结点prev，取消原尾结点的前指针的指向，prev作为新的尾结点，再判断prev是否为null，如果是，说明原链表中只有尾结点这一个结点，令first指针为null，这样原尾结点同时失去first和last的引用，触发GC，被回收；如果不是，取消prev后指针的指向，原尾结点失去引用被GC回收。

  5. getFirst方法

    public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

    这个方法用于获取首结点的值。

    如果首结点不存在，抛出NoSuchElementException异常，否则，返回首结点的值。

  6. getLast方法

    public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

    这个方法用于获取尾结点的值。

    如果尾结点不存在，则抛出NoSuchElementException异常，否则，返回尾结点的值。

  7. add (E e)方法

    调用LinkeLast方法，添加元素到尾部

    public boolean add(E e) {
    linkLast(e);
    return true;
}

  8. remove (Object o)方法

    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;
}

    从头至尾遍历链表，寻找指定的Object对象，如果找不到，返回false，如果找到了，调用unlink函数删除对应结点，然后返回true。

    unlink函数定义如下

    E unlink(Node<E> x) {
    // assert x != null;
    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;
}

    找到要删除结点的前结点和后结点。

    如果前结点不存在，则后结点作为首结点，否则，前结点的后指针指向后结点，要删除的结点的前指针置为null。

    如果后结点不存在，则前结点作为尾结点，否则，后结点的前指针指向前结点，要删除的结点的后指针置为null。

  9. remove ()方法

    public E remove() {
    return removeFirst();
}

    很简单，调用removeFirst方法，删除双向链表的第一个元素。

  10. remove (int index)方法

    public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

    checkElementIndex方法用于校验索引是否合法，定义如下

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

    isElementIndex方法定义如下

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

    索引不合法，则抛出IndexOutOfBoundsException异常，否则，调用unlink方法删除指定的结点，其中又调用了node方法，根据索引获取结点，node方法定义如下

    Node<E> node(int index) {
    // assert isElementIndex(index);

    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;
    }
}

    如果索引偏右，则从后往前找，找到结点后，返回该结点。

    如果索引偏左，则从前往后找，找到结点后，返回该结点。

  11. add (int index, E element)

    public void add(int index, E element) {
    checkPositionIndex(index);

    if (index == size)
        linkLast(element);
    else
        linkBefore(element, node(index));
}

    checkPositionIndex校验下标是否合法，checkPositionIndex方法定义如下

    private void checkPositionIndex(int index) {
    if (!isPositionIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

    如果索引不合法，则抛出IndexOutOfBoundsException异常。

    如果索引为size，则调用linkLast方法，将元素插入到双向链表的尾部。

    否则，调用linkBefore方法，将元素插入到指定位置，linkBefore方法定义如下

    void linkBefore(E e, Node<E> succ) {
    // assert succ != null;
    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++;
}

    该函数找出原索引位置上的结点及其前结点，这两个结点分别为待插入结点的前后结点，然后正确处理各结点前后指针的指向即可。

  12. get (int index)方法

    public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

    很简单，定义如上。

  13. set (int index, E e)

    public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

    很简单，定义如上。

  14. indexOf (Object o)方法

    public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

    很简单，定义如上。

  15. lastIndexOf (Object o)函数

    public int lastIndexOf(Object o) {
    int index = size;
    if (o == null) {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (x.item == null)
                return index;
        }
    } else {
        for (Node<E> x = last; x != null; x = x.prev) {
            index--;
            if (o.equals(x.item))
                return index;
        }
    }
    return -1;
}

    很简单，定义如上。

  16. toArray ()方法

    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;
}

    创建一个大小为size的Object数组，把双向链表的数据依次拷贝到Object数组中，返回Object数组。

  17. clear ()方法

    public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    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++;
}

    把每个结点的后指针、值、前指针都置为null，同时把first和last的指向也置为null，最后把双向链表的长度置为0。

FailFast机制

FailFast机制，即快速失败机制。

通过上面LinkedList的核心方法，我们可以看到，在添加结点、删除结点中，都会对modCount进行自增，modCount表示修改次数。

FailFast机制，就是为了在同时对LinkedList做读、写操作时，保护LinkedList中数据的安全和正确性。

具体实现是这样的，next迭代函数定义如下

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

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

其中，checkForComodification函数定义如下

final void checkForComodification() {
    if (modCount != expectedModCount)
        throw new ConcurrentModificationException();
}

modCount就是当前的修改次数，expectedModCount就是期待的修改次数，如果这两值不一致，就代表在读链表的过程中，同时对链表做了写操作，这是不允许的，这时，会抛出ConcurrentModificationException异常。这个过程可以类比数据库的共享锁。

FailFast机制测试

读线程

package cn.edu.hstc.LinkedList;

import java.util.Iterator;
import java.util.List;

/**
 * ReadObject
 */
public class ReadThread extends Thread {

    private List list;

    public ReadThread(List list) {
        this.list = list;
    }

    @Override
    public void run() {
        while (true){
            for (Iterator iterator = list.iterator(); iterator.hasNext();){
                System.out.println("ReadThread: " + iterator.next());
                try {
                    Thread.sleep(5);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }
    }
}

写线程

package cn.edu.hstc.LinkedList;

import java.util.List;

/**
 * wirteThread
 */
public class WirteThread extends Thread {

    private List list;

    public WirteThread(List list) {
        this.list = list;
    }

    @Override
    public void run() {
        for (int i = 0; i < 100; i++){
            list.add(i);
            try {
                Thread.sleep(5);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

测试类

package cn.edu.hstc.LinkedList;

import cn.edu.hstc.Array.WiretThread;

import java.util.LinkedList;
import java.util.List;

/**
 * test FailFast
 */
public class TestFailFast {

    public static void main(String[] args) {
        List<Object> list = new LinkedList<>();

        new ReadThread(list).start();
        new WiretThread(list).start();
    }
}

测试结果

loop execute : 0
loop execute : 1
loop execute : 2
Exception in thread "Thread-0" java.util.ConcurrentModificationException
	at java.util.LinkedList$ListItr.checkForComodification(LinkedList.java:966)
	at java.util.LinkedList$ListItr.next(LinkedList.java:888)
	at cn.edu.hstc.LinkedList.ReadThread.run(ReadThread.java:21)
loop execute : 3
loop execute : 4
loop execute : 5
loop execute : 6
loop execute : 7
loop execute : 8
loop execute : 9
上一篇：【数据结构】链表篇


下一篇：C# 实现 Leetcode203. 移除链表元素