Java源码解析之LinkedList源码剖析(基于JDK1.8)

       学过数据结构的都知道双端队列(链表),没学过的也没有关系,下面我先介绍一下双端队列(链表),为什么要介绍它了,因为LinkedList本质上就是一个双端队列(链表)。

一.  双端队列(链表)的介绍

1.  如下图:双端队列(链表)中单个节点对应的结构

每个节点包含三个部分:

  1. 指向前一个节点的引用

  2. 指向后一个节点的引用

  3. 自身存储的数据元素

引用在C语言中就相当于指针,在Java语言中,习惯用引用来描述地址的指向。

2.  如下图:双端队列的整体结构

二.  LinkedList的介绍(基于JDK1.8)

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

(1)实现了List接口,表明LinkedList是一个有序、可重复元素的集合

(2)实现了Deque,表明LinkedList是一个双端队列(链表)

(3)实现了Cloneable接口,表明LinkedList支持克隆,即可以重写Object.clone方法,否则在重写clone方法时,报CloneNotSupportedException

(4)实现了Serializable接口,可以被序列化与反序列化

三.  基本属性

// 链表的长度transient int size = 0;// 链表的头节点transient Node<E> first;// 链表的尾节点transient Node<E> last;

四.  构造方法(有2个)

(1)无参构造函数

// 无参构造函数public LinkedList() {}

(2)传入一个集合对象

// 传入一个集合,自动初始化一个含有相同长度的,且列表元素相同的LinkedListpublic LinkedList(Collection<? extends E> c) {    this();    addAll(c);}

五.  静态内部类 (重点)

(1)表示双端队列(链表)的一个节点的类

// 此类使用了泛型,传入的类型表示存储元素的类型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;    }}

六.  主要方法解析

(1)linkFirst(E e),将元素插入到头部

图解源码:红色为原始链表部分,蓝色为修改部分,如下所示

(2)linkLast(E e),插入一个元素到尾部

void linkLast(E e) {    // 定义一个节点,指向尾节点,在插入完成之后,f表示倒数第二个节点    final Node<E> l = last;    // 构造一个新节点,用它来表示新尾节点,尾节点的定义就是(下一个节点引用指向null)    // 如下表示(之前last节点,就变成了倒数第二个节点,就是新尾节点的上一个节点引用)    final Node<E> newNode = new Node<>(l, e, null);    // 改变全局尾节点的引用,指向新尾节点    last = newNode;    // f为空,表示插入的元素为第一个,即头节点和首节点为一个,如果插入的不是第一个元素,    // 则需要把之前的last节点的下一个节点引用指向新尾节点    if (l == null)        first = newNode;    else        l.next = newNode;    size++;    modCount++;}

 

图解源码:红色为原始链表部分,蓝色为修改部分,如下所示

(3)linkBefore(E e,Node succ),在指定节点之前插入一个元素

// 在指定节点之前插入一个元素void linkBefore(E e, Node<E> succ) {    // assert succ != null;    // 定义一个指定节点的上一个引用    final Node<E> pred = succ.prev;    // 定义一个新节点,新节点的前引用指向pred,新节点的后引用指向指定节点    final Node<E> newNode = new Node<>(pred, e, succ);    // 指定节点的前节点引用为新节点    succ.prev = newNode;    if (pred == null)        first = newNode;    else        // pred的后节点引用为新节点        pred.next = newNode;    size++;    modCount++;}

图解源码:红色为原始链表部分,蓝色为修改部分,如下所示

(4)unlinkFirst(Node f),移除头节点

// 移除头节点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    // 将全局变量的头节点重新定义为f.next    first = next;    // 如果当前链表只有一个元素,则移除头节点后,头节点和尾节点都为空    if (next == null)        last = null;    else        // 如果当前链表中有多个元素,移除头节点后,第二个节点就为头节点        next.prev = null;    size--;    modCount++;    return element;}

图解源码:红色为原始链表部分,蓝色为修改部分,如下所示

(5)unlinkLast(Node l),移除尾节点

// 移除尾节点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;}

图解源码:红色为原始链表部分,蓝色为修改部分,如下所示

(6)unlink(Node 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;    // 如果前节点为空,则表示移除的是头节点    if (prev == null) {        first = next;    } else {        // 如果移除的是中间的某个节点,则移除节点的后节点为next        prev.next = next;        x.prev = null;    }    // 如果后节点为空,则表示移除的是尾节点    if (next == null) {        last = prev;    } else {        // 如果移除的是中间的某个节点,则移除节点的前节点为prev        next.prev = prev;        x.next = null;    }    x.item = null;    size--;    modCount++;    return element;}

图解源码:红色为原始链表部分,蓝色为修改部分,如下所示

(7)node(int index),根据下标找到对应的节点,重点的重点

// 根据下标找到对应的节点Node<E> node(int index) {    // assert isElementIndex(index);    // size >> 1表示size的一半,就是size/2    if (index < (size >> 1)) {        // 下标小于size的一半,就从0开始遍历到,每遍历一次把节点引用后移一位        Node<E> x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    } else {        // 下标大于或者等于size的一半,就从最后一个开始遍历,每遍历一次把节点引用前移一位        Node<E> x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}

图解源码:红色为原始链表部分,蓝色为修改部分,如下所示

总结:

1). LinkedList的add,remove方法都是基于以上7个方法扩展来的

2). LinkedList本身没有下标的概念,因为从源码上看,每个节点都只包含三个属性(前节点引用,后节点引用,存储元素),但这并不代表它是无序的,因为双向链表的前后引用,导致它成为了一个有序队列。

本文分享自微信公众号 - Java学习进阶手册(javastudyup)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

评论

暂无评论