深入剖析LinkedList源码

很久前我们已经学习了 ArrayList 和 HashMap 的源码，有兴趣的同学请移步：深入剖析 ArrayList 源码
深入剖析 HashMap 源码
今天我们来谈谈 LinkedList 源码。

简介

LinkedList 是用链表实现的 List，是一个 双向链表。

public class LinkedList<E> extends AbstractSequentialList<E>
      implements List<E>, Deque<E>, Cloneable, java.io.Serializable{// 底层是双向链表
    // 元素数量    
    transient int size = 0;
    // 第一个结点
    transient Node<E> first;
    // 最后一个结点
    transient Node<E> last;
}

我们还看到了 LinkedList 实现了 Deque 接口，因此，我们可以操作 LinkedList 像操作队列和栈一样。

LinkedList 底层维护着一个 Node 组成的链表，在源码中，是如下图的一个静态内部类：

  // 内部类 Node
    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 实现的一些操作链表的辅助函数，看了这几个函数后再去看别的方法会容易很多。

操作链表

插入元素到头部

void linkFirst(E e) {
    final Node<E> f = first;
    final Node<E> newNode = new Node<>(null, e, f);// 设置 newNode 的前结点为 null，后结点为 f
    first = newNode;
    if (f == null)// 首先链接元素，同时把 newNode 设为最后一个结点
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

插入元素到尾部

void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);// 设置 newNode 的前结点为 l，后结点为 null
    last = newNode;// 新结点变成最后一个结点
    // 若 l == null 说明是首次链接元素，将 first 也指向新结点
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;// 修改次数 +1
}

在给定结点前插入元素 e

void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;
    final Node<E> newNode = new Node<>(pred, e, succ);// 设置 newNode 的前结点为 pred，后结点为 succ
    succ.prev = newNode;
    if (pred == null)// 如果 succ 是头结点，将 newNode 设置为头结点
        first = newNode;
    else
        pred.next = newNode;
    size++;
    modCount++;
}

删除链表结点

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;//GC 回收
    }
    // 判断是否是尾结点
    if (next == null) {last = prev;} else {
        next.prev = prev;
        x.next = null;//GC 回收
    }
    x.item = null;//GC 回收
    size--;
    modCount++;
    return element;
}

返回指定位置的结点

Node<E> node(int index) {
    // 根据 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;
    }
}

构造器

public LinkedList() {}
// 构造一个包含指定集合元素的 LinkenList
public LinkedList(Collection<? extends E> c) {this();
    addAll(c);
}

很简单，这里跳过。

add 方法

/*
 * 添加元素到末尾
 */
public boolean add(E e) {linkLast(e);// 插入到链表尾部
    return true;
}

/*
 * 添加元素到指定位置
 */
public void add(int index, E element) {checkPositionIndex(index); // 参数校验 ——> index >= 0 && index <= size
    if (index == size)
        linkLast(element);// 插入到链表尾部
    else
        linkBefore(element, node(index));// 插入到指定结点前面
}

/**
 * 将指定集合中的元素插入到链表中
 * addAll(Collection<? extends E> c)——>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 {// 在 index 位置插入
        succ = node(index);
        pred = succ.prev;
    }
    // 依次从集合中取出元素插入到链表
    for (Object o : a) {E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);// 设置 newNode 的前结点为 pred，后结点为 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;
}
//addFirst、addLast 省略.....

get/set 方法

/*
 * 返回指定位置元素
 */
public E get(int index) {checkElementIndex(index);
    return node(index).item;
}
 /*
  * 设置元素
  */
public E set(int index, E element) {checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

peek/poll 方法

/*
 * 返回头结点值，如果链表为空则返回 null
 */
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

/*
 * 删除头结点并返回头结点值，如果链表为空则返回 null
 */
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

remove 方法

/*
 * 默认删除头结点
 */
public E remove() {return removeFirst();
}

/*
 * 删除指定位置结点
 */
public E remove(int index) {checkElementIndex(index);
    return unlink(node(index));
}

/*
 * 删除指定结点
 */
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;
}

indexOf/lastIndexOf 方法

/*
 * 返回指定对象在链表中的索引（如果没有则返回 -1）* lastIndexOf 同理（其实就是从后向前遍历）*/
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;
}

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

/*
 * 将链表包装成指定类型数组返回
 */
public <T> T[] toArray(T[] a) {if (a.length < size)// 给点的数组长度小于链表长度
        // 创建一个类型与 a 一样，长度为 size 的数组
        a = (T[])java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
        
    int i = 0;
    Object[] result = a;// 定义 result 指向给定数组，修改 result == 修改 a
    // 依次把结点值放入 result 数组
    for (Node<E> x = first; x != null; x = x.next)
        result[i++] = x.item;

    if (a.length > size)
        a[size] = null;

    return a;
}

listIterator 方法

ListIterator 是一个功能更加强大的接口, ListIterator 在 Iterator 基础上提供了 add、set、previous 等对列表的操作。

public ListIterator<E> listIterator(int index) {checkPositionIndex(index);// 参数校验
    return new ListItr(index);
}
ListItr 是一个内部类

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;// 上次越过的结点
    private Node<E> next;// 下次越过的结点
    private int nextIndex;// 下次越过结点的索引
    private int expectedModCount = modCount;// 预期修改次数

    ListItr(int index) {next = (index == size) ? null : node(index);//index 默认为 0
        nextIndex = index;
    }

     /* 判断是否有下一个元素 */
    public boolean hasNext() {return nextIndex < size;}
    
     /* 向后遍历，返回越过的元素 */
    public E next() {checkForComodification();//fail-fast
        if (!hasNext())
            throw new NoSuchElementException();

        lastReturned = next;
        next = next.next;
        nextIndex++;
        return lastReturned.item;
    }
    
     /* 判断是否有上一个元素 */    
    public boolean hasPrevious() {return nextIndex > 0;}
    
     /* 向前遍历，返回越过的元素 */
    public E previous() {checkForComodification();//fail-fast
        if (!hasPrevious())
            throw new NoSuchElementException();

        lastReturned = next = (next == null) ? last : next.prev;// 调用 previous 后 lastReturned = next
        nextIndex--;
        return lastReturned.item;
    }
    
     /* 返回下一个越过的元素索引 */
    public int nextIndex() {return nextIndex;}
    
     /* 返回上一个越过的元素索引 */
    public int previousIndex() {return nextIndex - 1;}
    
     /* 删除元素 */
    public void remove() {checkForComodification();//fail-fast
        if (lastReturned == null)
            throw new IllegalStateException();

        Node<E> lastNext = lastReturned.next;
        unlink(lastReturned);// 从链表中删除 lastReturned，modCount++（该方法会帮你处理结点指针指向）if (next == lastReturned)// 调用 previous 后 next == lastReturned
            next = lastNext;
        else
            nextIndex--;
            
        lastReturned = null;//GC
        expectedModCount++;
    }
    
     /* 设置元素 */
    public void set(E e) {if (lastReturned == null)
            throw new IllegalStateException();
        checkForComodification();//fail-fast
        lastReturned.item = e;
    }
    
     /* 插入元素 */
    public void add(E e) {checkForComodification();//fail-fast
        lastReturned = null;
        if (next == null)
            linkLast(e);
        else
            linkBefore(e, next);
        nextIndex++;
        expectedModCount++;
    }
    
     /* 操作未遍历的元素 */
    public void forEachRemaining(Consumer<? super E> action) {Objects.requireNonNull(action);// 判空
        while (modCount == expectedModCount && nextIndex < size) {action.accept(next.item);
            lastReturned = next;
            next = next.next;
            nextIndex++;
        }
        checkForComodification();}
    
     /*fail-fast*/
    final void checkForComodification() {if (modCount != expectedModCount)
            throw new ConcurrentModificationException();}
}

总结

还有很多关于 LinkedList 的方法这里就不一一列举了，总的来说如果链表学得好的话看懂源码还是没问题的，今天就学到这里，如果错误请多指教。