LinkedList源码分析（基于JDK8）

本文介绍

1、LinkedList相关面试题。
2、LinkedList基本信息。
3、LinkedList属性和方法。
4、LinkedList最佳实践。
5、LinkedList的总结。

相关面试题

ArrayList与LinkedList有哪些区别？
（todo待收集面试题）

概述

LinkedList 是一种变长的集合类。底层数据结构是双向链表，是非连续的内存空间。
LinkedList 允许空值和重复元素，因为add方法不做空值和重复元素校验。
LinkedList 是非线程安全类，并发环境下，多个线程同时操作 LinkedList，会引发不可预知的错误。

LinkedList类关系图

LinkedList 继承AbstractSequentialList，实现了List, Deque, Cloneable, java.io.Serializable接口。
LinkedList 实现List接口，即提供相关的添加、删除、修改、遍历功能。
LinkedList 实现Cloneable接口，即覆盖了函数clone()，能被克隆。
LinkedList 实现Serializable接口，这意味着LinkedList 支持序列化。

下面让我们翻开LinkedList 的源代码，看看一些常用的方法属性，以及一些需要注意的地方。

数据结构

LinkedList最最最核心的就是节点的数据结构。组成链表的节点由 prev：指向上一个节点的引用、next：指向下一个节点的引用、item：存储的元素组成。

// 静态内部类形式的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;
    }
}

下图是由Node节点组成双向链表，LindedList底层的数据存储基本上就是酱紫了。


属性

LinkedList 属性主要有当前链表长度size，first 指向第一个节点 这里我称为首节点，last 指向最后一个节点简称尾节点 。除此之外还有一个经常用到的属性就是从 AbstractList 继承过来的 modCount 属性，代表 LinkedList 集合的修改次数。

transient int size = 0;

/**
 * Pointer to first node.
 * Invariant: (first == null && last == null) ||
 *            (first.prev == null && first.item != null)
 */
transient Node<E> first;

/**
 * Pointer to last node.
 * Invariant: (first == null && last == null) ||
 *            (last.next == null && last.item != null)
 */
transient Node<E> last;

加入first属性和last属性后的双向链表


构造函数

无参构造函数

如果不传入参数，则使用默认无参构建方法创建LinkedList对象，如下：

public LinkedList() {
}

带collection类型的构造函数

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

// 添加 collection 中所有元素
public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}

// 在index位置添加 collection 所有元素
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index); // 范围插入范围，[0 , size]位置为正常

    Object[] a = c.toArray(); // 将集合转成Object数组
    int numNew = a.length;
    if (numNew == 0) // 如果新增元素数量为0，直接返回false
        return false;

    Node<E> pred, succ; // pred与succ是两个临时变量，为将c中的元素构建成Node再将其连接到链表上的临时变量，（具体理解该的方法：先要理解链表是什么,也就是先搞清楚不懂的概念。再Debug进来具体的代码）
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    // 此处for循环主要把a中的元素链接到已有的元素上
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null); // 创建一个新节点，新节点的prev 指向 pred，item 为e，next 为null
        if (pred == null)
            first = newNode; // 设置首节点
        else
            pred.next = newNode;   // pred.next 指向新的节点
        pred = newNode; // pred 指向新的节点
    }

    if (succ == null) {
        last = pred; // 设置尾节点
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew; // 添加元素后数据大小
    modCount++; 
    return true;
}

/**
 * 将集合转成Object数组
 *  1、创建一个size长度的数组 
 *  2、循环将链表节点的元素赋值给新数组中并返回。
 */
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;
}

add方法

add(E e) 方法

添加单个元素方法

public boolean add(E e) {
    linkLast(e); // 在尾部添加元素 
    return true;
}

/**
 * 添加元素到链表最后
 * 1、生成新节点
 * 2、插入到链表尾部
 * 3、更新 last/first 节点。
 */
void linkLast(E e) {
    final Node<E> l = last;
    final Node<E> newNode = new Node<>(l, e, null);  // 创建pre指向l，item赋值为e，next赋值为null
    last = newNode; // 设置last引用
    if (l == null)
        first = newNode; // 空链表情况设置first
    else
        l.next = newNode; // 设置尾节点指向新节点
    size++;
    modCount++;
}

add(int index, E element) 方法

添加元素到指定位置方法

public void add(int index, E element) {
    checkPositionIndex(index); // 检查插入点的范围 [0,size]
    if (index == size)
        linkLast(element); // 添加到链表最后
    else
        linkBefore(element, node(index));
}

/**
 * Returns the (non-null) Node at the specified element index.
 * 返回指定元素索引处的(非空)节点。下标从0开始
 */
Node<E> node(int index) {
    if (index < (size >> 1)) { // index是否小于size的一半，小于则从首节点往后移
        Node<E> x = first;
        for (int i = 0; i < index; i++) // 从首节点开始，循环往后移动，直到 i=index
            x = x.next;
        return x; // 返回下标为index处的节点（下标从0开始）
    } else { // 反之大于从尾节点往前移
        Node<E> x = last;
        for (int i = size - 1; i > index; i--) // 从尾节点开始，循环往前移动，直到 i=index
            x = x.prev; 
        return x;  // 返回下标为index处的节点（下标从0开始）
    }
}

/**
 * 将 e元素连接到 succ节点之前
 */
void linkBefore(E e, Node<E> succ) {
    final Node<E> pred = succ.prev;  // pred指向succ的上一个节点
    final Node<E> newNode = new Node<>(pred, e, succ); // 创建新的节点，新节点的prev指向pred，新节点的item为e，新节点的nextr指向succ.
    succ.prev = newNode; // succ节点的prev指向新节点
    if (pred == null) // 如果pred是null，说明succ.prev是第一个节点，则新的节点设置为首节点
        first = newNode; 
    else  // 修改pred指向的下一个节点为新节点
        pred.next = newNode;
    size++;
    modCount++;
}

get方法

get(int index)

获取指定位置节点元素方法

public E get(int index) {
    checkElementIndex(index); // 检查索引元素范围，[0 , size）位置为正常。注意：不包括size
    return node(index).item; // 返回节点中具体的值
}

/** 检查元素的索引位置 */
private void checkElementIndex(int index) {
    if (!isElementIndex(index))  // 是否是元素的索引，如果不是则抛出异常
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}

/** 是否是元素的索引，[0,size)  包括0不包括size*/
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

getFirst()

获取第一个节点元素方法

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

getLast()

获取最后一个元素方法

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

remove方法

remove(int index)

移除指定位置元素方法

public E remove(int index) {
    checkElementIndex(index);  // 检查元素索引位置，如不是则抛出异常
    return unlink(node(index)); // 找到index位置节点，并移除
}

/** 移除节点 */
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) { // x是否为首节点，如果是则修改首节点指向
        first = next;
    } else { // 不是首节点
        prev.next = next;  // 修改x前一个节点的next指向x后一个节点
        x.prev = null; // 修改x节点的prev指向null
    }

    if (next == null) { // x是否为尾节点，如果是则修改尾节点指向
        last = prev;
    } else { // 不是尾节点
        next.prev = prev; // 修改x后一个节点的prev指向x前一个节点。
        x.next = null; // 修改x节点的next指向null
    }

    x.item = null;
    size--;
    modCount++;
    return element;
}

remove(Object o)

根据对象移除元素方法

public boolean remove(Object o) {
    if (o == null) { // o是否为空，为空。循环遍历链表，找到一个就移除，并返回，假如有两个null只会移除第一个。
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x); 
                return true;
            }
        }
    } else { // 不为空，循环遍历链表，找到一个就移除，并返回，假如有两个o对象只会移除第一个。
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

removeFirst()

移除第一个节点方法

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

/** 将第一个元素移除，将移除元素置空，first指向下一个节点，size减1，修改次数加1，返回旧值 */
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;
}

removeLast()

移除最后一个节点方法

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

/** 将最后一个元素移除，last指向上一个节点，将移除元素置空，size减1，修改次数加1，返回旧值 */
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;
}

set方法

set(int index, E element)

设置指定位置元素方法

public E set(int index, E element) {
    checkElementIndex(index);  // 检查元素索引位置，如不是则抛出异常
    Node<E> x = node(index); // 获取index位置的节点
    E oldVal = x.item; // 保存旧值
    x.item = element; // 设置item为新值
    return oldVal; // 返回旧值
}

clear方法

clear()

清除链表方法

/** 将所有链表元素置空，然后将链表长度修改成0，修改次数加1 */
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; ) { // 从首节点开始，循环遍历链表，将节点只有item、next、prev设置为null
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    first = last = null; // 首尾节点设置为null
    size = 0; // 设置大小为0
    modCount++; 
}

push和pop方法

最后说下两个栈操作的方法，这也是链表的另一种用法，把LinkedList当做栈来使用。push其实就是调用addFirst(e)方法，pop调用的就是removeFirst()方法。

/** 出栈 */
public E pop() {
    return removeFirst();
}

/** 入栈 */
public void push(E e) {
    addFirst(e);
}

总结

LinkedList基于双向链表实现，无容量的限制。
LinkedList下标从0开始，最大下标为size-1。
LinkedList当作栈使用，可以调用push和pop方法。
LinkedList移除对象时，如果有多个相同对象只会移除第一个。
LinkedList根据下标和对象获取元素的值时都会循环遍历链表，时间复杂度为都为O(n)，而ArrayList根据下标获取时直接可取到值，时间复杂度为O(1)，而根据对象查询是需要遍历数据，时间复杂度为O(n)。

最佳实践

1、适合用于增加删除多，查询修改少的业务中，与ArrayList对比刚好互补。但是目前对于这个容器的使用还是极少，以至于找不到一个好点的例子（后续补上）。

引文

面试必备：LinkedList源码解析（JDK8）
https://blog.csdn.net/zxt0601/article/details/77341098
LinkedList源码分析（基于JDK8）
https://blog.csdn.net/fighterandknight/article/details/61476335

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
  • 人面猴
    序言：七十年代末，一起剥皮案震惊了整个滨河市，随后出现的几起案子，更是在滨河造成了极大的恐慌，老刑警刘岩，带你破解...
    沈念sama阅读 220,884评论 6赞 513
  • 死咒
    序言：滨河连续发生了三起死亡事件，死亡现场离奇诡异，居然都是意外死亡，警方通过查阅死者的电脑和手机，发现死者居然都...
    沈念sama阅读 94,212评论 3赞 395
  • 救了他两次的神仙让他今天三更去死
    文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
    开封第一讲书人阅读 167,351评论 0赞 360
  • 道士缉凶录：失踪的卖姜人
    文/不坏的土叔 我叫张陵，是天一观的道长。 经常有香客问我，道长，这世上最难降的妖魔是什么？ 我笑而不...
    开封第一讲书人阅读 59,412评论 1赞 294
  • 港岛之恋（遗憾婚礼）
    正文 为了忘掉前任，我火速办了婚礼，结果婚礼上，老公的妹妹穿的比我还像新娘。我一直安慰自己，他们只是感情好，可当我...
    茶点故事阅读 68,438评论 6赞 397
  • 恶毒庶女顶嫁案：这布局不是一般人想出来的
    文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
    开封第一讲书人阅读 52,127评论 1赞 308
  • 城市分裂传说
    那天，我揣着相机与录音，去河边找鬼。 笑死，一个胖子当着我的面吹牛，可吹牛的内容都是我干的。 我是一名探鬼主播，决...
    沈念sama阅读 40,714评论 3赞 420
  • 双鸳鸯连环套：你想象不到人心有多黑
    文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
    开封第一讲书人阅读 39,636评论 0赞 276
  • 万荣杀人案实录
    序言：老挝万荣一对情侣失踪，失踪者是张志新（化名）和其女友刘颖，没想到半个月后，有当地人在树林里发现了一具尸体，经...
    沈念sama阅读 46,173评论 1赞 319
  • 护林员之死
    正文 独居荒郊野岭守林人离奇死亡，尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 38,264评论 3赞 339
  • 白月光启示录
    正文 我和宋清朗相恋三年，在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 40,402评论 1赞 352
  • 活死人
    序言：一个原本活蹦乱跳的男人离奇死亡，死状恐怖，灵堂内的尸体忽然破棺而出，到底是诈尸还是另有隐情，我是刑警宁泽，带...
    沈念sama阅读 36,073评论 5赞 347
  • 日本核电站爆炸内幕
    正文 年R本政府宣布，位于F岛的核电站，受9级特大地震影响，放射性物质发生泄漏。R本人自食恶果不足惜，却给世界环境...
    茶点故事阅读 41,763评论 3赞 332
  • 男人毒药：我在死后第九天来索命
    文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹，春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 32,253评论 0赞 23
  • 一桩弑父案，背后竟有这般阴谋
    文/苍兰香墨 我抬头看了看天上的太阳。三九已至，却和暖如春，着一层夹袄步出监牢的瞬间，已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 33,382评论 1赞 271
  • 情欲美人皮
    我被黑心中介骗来泰国打工， 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留，地道东北人。 一个月前我还...
    沈念sama阅读 48,749评论 3赞 375
  • 代替公主和亲
    正文 我出身青楼，却偏偏与公主长得像，于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子，可洞房花烛夜当晚...
    茶点故事阅读 45,403评论 2赞 358