LinkedList源码分析，基于JDK1.8逐行分析

博主关于ArrayList源码分析的文章，传送地址：ArrayList源码分析，基于JDK1.8逐行分析

LinkedList

文章目录

• LinkedList
• • 一、基本介绍
  • 二、源码分析
  • • 1. 主要属性
    • 2. 主要内部类
    • 3. 主要构造方法
    • 4. 添加元素方法
    • 5. 删除元素方法
    • 6. 其余方法
  • 三、方法对比
  • 四、迭代器

一、基本介绍

1. 继承体系

• LinkedList不仅实现了List接口，还实现了Queue和Deque接口，所以它既能作为List使用，也能作为双端队列使用（先进先出），当然也可以作为栈使用（先进后出）
• LinkedList没有实现RandomAccess，所以不支持随机访问，只能遍历节点
  • 访问非队列首尾的元素比较低效

2. 整体架构

LinkedList底层数据结构是一个双向链表，整体结构如下图所示：

上图代表了一个双向链表结构，链表中的每个节点都可以向前或者向后追溯，有几个概念如下：

• 链表的每个节点叫做 Node，Node 有 prev 属性，代表前一个节点，next 属性，代表后一个节点
• first 是双向链表的头节点，它的前一个节点是 null
• last 是双向链表的尾节点，它的后一个节点是 null
• 当链表中没有数据时，first 和 last 是同一个节点，前后指向都是 null
• 因为是个双向链表，只要机器内存足够强大，是没有大小限制的

二、源码分析

1. 主要属性

//元素个数
transient int size = 0;

//链表头节点，可以理解为指向头节点的指针
transient Node<E> first;

//链表尾节点，可以理解为指向尾节点的指针
transient Node<E> last;

//AbstractList类中的属性
//统计修改的次数
protected transient int modCount = 0;

2. 主要内部类

典型的双向链表结构

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

3. 主要构造方法

public LinkedList() {
}

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

两个构造方法也很简单，可以看出是一个*队列

4. 添加元素方法

• 作为一个双端队列，添加元素主要有两种
  • 一种是在队列尾部添加元素
  • 一种是在队列首部添加元素
• 作为一个List，可以支持在链表中间添加元素

故添加方式有三种，如下图所示：

4.1 从尾部添加

add() 方法默认是从尾部添加元素的，调用了 linkLast() 方法，时间复杂度为O(1)

linkLast() 方法源码如下：

// 从尾部开始追加节点
private void linkLast(E e) {
    
    // 把尾节点数据暂存
    final Node<E> l = last;
    
    // 新建节点，初始化入参含义：
    // l是新节点的前一个节点，即当前尾节点的值
    // e表示当前新增节点，当前新增节点后一个节点是null
    final Node<E> newNode = new Node<>(l, e, null);
    
    //新建节点追加到尾部
    last = newNode;
    
    //如果链表为空（l是尾节点，尾节点为空，链表即空），头部和尾部是同一个节点，都是新建的节点
    if (l == null)
        first = newNode;
    
    //如果链表不为空，把前尾节点的下一个节点指向当前尾节点
    else
        l.next = newNode;
    
    //大小和版本更改
    size++;
    modCount++;
}

4.2 从头部添加

addFirst() 方法是从头部添加元素，时间复杂度为O(1)

addFirst() 方法源码如下：

// 从头部追加元素
private void linkFirst(E e) {
    
    // 头节点赋值给临时变量
    final Node<E> f = first;
    
    // 新建节点，前一个节点指向null，e是新建节点值，f是新建节点的下一个节点，即当前头节点的值
    final Node<E> newNode = new Node<>(null, e, f);
    
    // 新建节点成为头节点
    first = newNode;
    
    // 头节点为空，就是链表为空，头尾节点是一个节点
    if (f == null)
        last = newNode;
    
    // 链表不为空，上一个头节点的前一个节点指向当前节点
    else
        f.prev = newNode;
    
    // 大小和版本更改
    size++;
    modCount++;
}

4.3 从链表中间添加

add(int index, E element) 方法在指定index位置添加元素，时间复杂度为O(n)

add(int index, E element) 方法源码如下：

public void add(int index, E element) {
    
    //判断是否越界
    checkPositionIndex(index);

    //如果index是尾节点之后的那个位置，则采用尾插法
    if (index == size)
        linkLast(element);
    
    else
        //要在链表中间添加节点
        //首先调用node方法得到index位置的节点
        //再调用linkBefore方法将element插入到index位置的节点之前
        //在index之前添加节点，那么此节点就成了index位置的节点，原index位置的节点会成为index+1位置的节点 
        linkBefore(element, node(index));
}

node() 方法源码如下：

此方法同时也是节点查询对应的源码

LinkedList 并没有采用从头循环到尾的做法，而是采取了简单二分法，首先看看 index 是在链表的前半部分，还是后半部分；如果是前半部分，就从头开始寻找，反之从尾部开始向前遍历

//得到index位置的节点
Node<E> node(int index) {
    //assert isElementIndex(index);

    //此方法会根据index是在前半段还是后半段决定从前遍历还是从后遍历
    
    //如果index在前半段，则从前开始遍历，减少一半元素的遍历
    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        //index在后半段，从后开始遍历
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

linkBefore() 方法源码如下：

//在节点succ之前添加元素e
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;
    
    //否则修改前置节点的next为新节点
    else
        pred.next = newNode;
    
    //大小和版本更改
    size++;
    modCount++;
}

5. 删除元素方法

• 作为双端队列，删除元素有两种方式

  • 一种是队列首删除元素
  • 一种是队列尾删除元素

• 作为List，支持中间删除元素

故删除方式有三种，如下图所示：

5.1 从尾部删除

removeLast() 方法从尾部删除节点，时间复杂度为O(1)

removeLast() 方法源码如下：

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException(); //如果没有元素抛出异常
    
    //调用unlinkLast方法，参数为尾节点
    return unlinkLast(l);
}

unlinkLast() 方法源码如下：

private E unlinkLast(Node<E> l) {
    
    //参数l是非空的尾节点
    
    // assert l == last && l != null;
    
    //保存尾节点的元素值，需要返回
    final E element = l.item;
    
    //保存尾节点的前置指针
    final Node<E> prev = l.prev;
    
    //将尾节点的前置指针和元素值置为null，方便GC回收
    l.item = null;
    l.prev = null; // help GC
    
    //让前置节点成为新的尾节点
    last = prev;
    
    //如果链表中只有一个节点，且被删除了，则将first、last均置为null
    if (prev == null)
        first = null;
    
    //如果链表不仅仅只有一个节点，将前置节点的next置为空
    else
        prev.next = null;
    
    //大小和版本更改
    size--;
    modCount++;
    
    //返回被删除的节点值
    return element;
}

5.2 从头部删除

remove() 方法从头部删除节点，调用removeFirst() 方法，时间复杂度为O(1)

removeFirst() 方法源码如下：

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException(); //如果没有元素抛出异常
    
    //调用unlinkFirst方法删除头部节点，参数为头节点
    return unlinkFirst(f);
}

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

5.3 从链表中间删除

remove(int index) 方法删除指定位置的节点，时间复杂度为O(n)

remove(int index) 方法源码如下：

public E remove(int index) {
    
    //检查越界
    checkElementIndex(index);
    
    //删除指定index位置的节点
    return unlink(node(index));
}

unlink() 方法源码如下：

//删除x节点
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;

    //如果前置节点为空，说明被删节点是首节点，让first指向x的后置节点
    if (prev == null) {
        first = next;
    } else { //如果被删的不是头节点，修改前置节点的next为x的后置节点
        prev.next = next;
        x.prev = null;
    }

    //如果后置节点为空，说明被删节点是尾节点，让last指向x的前置节点
    if (next == null) {
        last = prev;
    } else { //如果被删的不是尾节点，修改后置节点的prev为x的前置节点
        next.prev = prev;
        x.next = null;
    }

    x.item = null; //帮助GC
    
    size--;
    modCount++;
    return element;
}

6. 其余方法

6.1 弹出元素方法

pollFirst / poll，如果没有元素返回null

public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

pollLast，如果没有元素返回null

public E pollLast() {
    final Node<E> l = last;
    return (l == null) ? null : unlinkLast(l);
}

总结：remove时没有元素则抛出异常，poll时没有元素会返回null

6.2 当作栈来使用

添加 / 删除元素都只操作链表头节点即可

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

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

三、方法对比

LinkedList 实现了 Queue 接口，在新增、删除、查询等方面增加了很多新的方法，这些方法在平时特别容易混淆，在链表为空的情况下，返回值也不太一样，如下述表格所示：

方法含义	返回异常	返回特殊值	底层实现
新增	add(e)	offer(e)	底层实现相同
删除	remove()	poll(e)	链表为空时，remove 会抛出异常，poll 返回 null
查找	element()	peek()	链表为空时，element 会抛出异常，peek 返回 null

• LinkedList 也实现了 Deque 接口，对新增、删除和查找都提供从头开始，还是从尾开始两种方向的方法，比如 remove 方法，Deque 提供了 removeFirst 和 removeLast 两种方向的使用方式，但当链表为空时的表现都和 remove 方法一样，都会抛出异常

四、迭代器

由于 LinkedList 要实现双向的迭代访问，所以使用 Iterator 接口无法满足要求，因为 Iterator 只支持从头到尾的访问

Java 新增了一个迭代接口，叫做：ListIterator，这个接口继承Iterator接口，并提供了向前和向后的迭代方法，如下所示：

迭代顺序	方法
从尾到头迭代方法	hasPrevious、previous、previousIndex
从头到尾迭代方法	hasNext、next、nextIndex

public interface ListIterator<E> extends Iterator<E> {

    boolean hasNext(); //若仍有下一个元素可以迭代，返回true

    E next(); //1.指针下移 2. 返回被跨过的元素

    boolean hasPrevious(); //若仍有上一个元素可以迭代，返回true

    E previous(); //1.指针上移 2. 返回被跨过的元素

    int nextIndex(); //下一个该迭代的元素的索引，索引从0开始，迭代器位于集合的末尾会返回集合长度

    int previousIndex(); //上一个该迭代的元素的索引，返回-1表示迭代器在集合的开始处

    void remove(); //删除next或previous方法跨过的元素
}

4.1 迭代器属性

LinkedList中的ListIterator接口的实现类 ListItr 源码如下：

private class ListItr implements ListIterator<E> {
    
    //执行next()或者previous()方法时被跨过的节点
    private Node<E> lastReturned; 
    
    //下一个节点
    private Node<E> next; 
    
    //下一个节点的位置
    private int nextIndex; 
    
    //expectedModCount：期望版本号
    //modCount：目前LinkedList最新版本号
    private int expectedModCount = modCount;
    …………
}

4.2 迭代器方法演示

List<String> linkedList = new LinkedList<>();

linkedList.add("Amy");
linkedList.add("Bob");
linkedList.add("Carl");

ListIterator<String> stringListIterator = linkedList.listIterator();

System.out.println(stringListIterator.hasNext()); //true
System.out.println(stringListIterator.next()); //Amy
stringListIterator.remove(); //删除了集合的第一个元素
System.out.println(stringListIterator.hasPrevious()); //false

//从前向后遍历集合
while (stringListIterator.hasNext()) {
    System.out.println(stringListIterator.next()); //Bob Carl
}

//从后向前遍历集合
while (stringListIterator.hasPrevious()) {
    System.out.println(stringListIterator.previous()); //Carl Bob
    stringListIterator.remove(); //删除跨过的所有元素
}

System.out.println(linkedList); //[]