Java集合(三) —— LinkedList源码分析

Java集合(一) —— Collection源码分析
Java集合(二) —— ArrayList源码分析
Java集合(三) —— LinkedList源码分析
Java集合(四) —— PriorityQueue源码分析
Java集合(五) —— HashSet源码分析
Java集合(六) —— LinkedHashSet源码分析
Java集合(七) —— TreeSet源码分析
Java集合(八) —— HashMap源码分析
Java集合(九) —— LinkedHashMap源码分析
Java集合(十) —— TreeMap源码分析
因为表述方便问题，有时使用前驱&后继节点，有时使用前驱&后继指针，事实上对象保存的就是对象的地址，也就是指针。

1.LinkedList继承关系

LinkedList.png

2.LinkedList的数据结构

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继承自AbstractSequentialList并实现了List接口，底层是双向链表数据结构；LinkedList同时实现了Deque接口，可用作双向队列。

3.LinkedList性能分析

1.LinkedList是基于链表实现的，不存在容量不足的问题，所以没有扩容方法，也就没有因扩容带来的性能问题。
2.LinkedList查找元素时，根据index的大小需要从开始或从结尾遍历到index位置，其时间复杂度为O(n)。
3.LinkedList新增/删除元素时，不存在数据的移动，只需要修改前驱节点与后继节点的指向，不考虑查找的情况下，其时间复杂度为O(1)。
总结(对比ArrayList)：

  • LinkedList在查找数据时需要遍历链表，性能较差；而新增或删除只需要修改指针的指向，具有较好的性能，所以LinkedList常用于查询较少，新增/删除较多的场景。
  • ArrayList具有较好的查询性能，而新增/删除都可能引起大量元素的移动，性能较差，所以ArrayList适用于查询较多，新增/删除较少的场景。
  • LinkedList需要额外的内存空间保存指针(前向指针(前向节点)/后继指针(后继节点))信息，如果对内存有较高要求，可以考虑其他方案。
  • 尽量不要使用for循环遍历LinkedList，应该使用迭代器，因为LinkedList每访问一个数据都要遍历链表一次(具体看源码分析)。

4.LinkedList源码分析

1.成员变量分析

// 链表的大小
transient int size = 0;
// 第一个节点(头结点)
transient Node<E> first;
// 最后一个节点(尾结点)
transient Node<E> last;

2.构造方法分析

// .. 没啥好说的
public LinkedList() {
}

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

3.核心方法分析

3.1新增元素

1.从链表尾部新增一个节点

public boolean add(E e) {
    linkLast(e);
    return true;
}
/**
 * 从链表尾部添加一个新节点
 */
void linkLast(E e) {
    // 定义一个临时变量保存最后一个节点
    final Node<E> l = last;
    // 创建一个新的节点，l == 上一个节点 ； null == 下一个节点(最后一个节点的下一个节点为null)
    final Node<E> newNode = new Node<>(l, e, null);
    // 将新建的节点置为最后一个节点
    last = newNode;
    if (l == null)
        // 如果 l == null表示之前一个节点都没有，新增节点之后first也指向新节点
        first = newNode;
    else
        // 否则，之前的最后一个节点的后继指针指向新建的节点
        l.next = newNode;
    // 链表大小+1
    size++;
    // 修改次数+1
    modCount++;
}

2.指定位置新增节点

/**
 * 指定位置新增元素
 */
public void add(int index, E element) {
    // 检查是否越界
    checkPositionIndex(index);

    if (index == size)
        // 链表最后新增节点
        linkLast(element);
    else
        // 查找指定下标节点，在指定下标之前新增节点
        linkBefore(element, node(index));
}

/**
 * 查找节点的方法
 * 这是LinkedList一个很重要的方法，LinkedList很多方法都要依赖此方法查找对应的节点
 */
Node<E> node(int index) {
    // 判断index的大小，决定要从头开始遍历链表的一半还是从尾部开始遍历链表的一半
    if (index < (size >> 1)) {
        // 顺序遍历查找第index个节点并返回
        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;
    }
}

/**
 * 指定位置插入新的节点
 */
void linkBefore(E e, Node<E> succ) {
    // succ：指定位置节点
    // pred保存指定位置节点的前向指针
    final Node<E> pred = succ.prev;
    // 创建一个新的节点
    final Node<E> newNode = new Node<>(pred, e, succ);
    // 指定位置的节点的前向指针指向新建的节点
    succ.prev = newNode;
    if (pred == null)
        // 如果pred == null，表示原来链表为空或者刚好从第一个节点插入新的节点(因为第一个节点没有前向节点，pred = null)
        first = newNode;
    else
        // 否则，指定位置节点的前向节点的后继指针指向新建的节点(有些绕口，自己理解吧)
        pred.next = newNode;
    size++; // 链表大小+1
    modCount++; // 修改次数+1
}

3.批量插入数据

public boolean addAll(Collection<? extends E> c) {
    return 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 {
        // 指定位置节点
        succ = node(index);
        // 记录指定位置节点的前向节点
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            // 从头部新增节点
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        // 如果是从尾部新增的节点，就将原先最后一个节点指向新增元素之后的最后一个节点
        last = pred;
    } else {
        // 如果是从其他某个位置新增的节点，就将新增的最后的一个节点的后继指针指向指定位置节点(succ)；指定位置节点的前向指针指向新增的最后一个节点
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

3.2查找元素

1.查找数据

public E get(int index) {
    // 检查是否越界
    checkElementIndex(index);
    // 返回指定节点的元素
    return node(index).item;
}

关于node方法之前已经说过，这里不再重复，但是再说一遍，该方法很重要！！！

3.3修改元素

1.修改元素

public E set(int index, E element) {
    checkElementIndex(index);
    // 查找指定位置的Node节点(又是熟悉的node方法)
    Node<E> x = node(index);
    // 记录节点上的元素
    E oldVal = x.item;
    // 将旧元素指向新元素
    x.item = element;
    // 返回旧元素
    return oldVal;
}

3.4删除元素

1.根据索引删除

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}
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) {
        // prev == null表示删除的x是头结点
        first = next;
    } else {
        // 否则，前驱节点的后继指针指向x的后继节点
        prev.next = next;
        // 将x的前驱节点置为null
        x.prev = null;
    }

    if (next == null) {
        // next == null，说明删除的x的尾结点
        last = prev;
    } else {
        // 否则，后继节点的前驱指针指向x的前驱节点
        next.prev = prev;
        // 将x的后继节点置为null
        x.next = null;
    }
    // 将x节点中的元素item置为null，此时达到删除一个节点的目的
    x.item = null;
    size--;
    modCount++;
    // 返回移除的元素
    return element;
}

2.根据元素删除

public boolean remove(Object o) {
    // 无论o是否为null，最终都是调用unlink(x)方法进行删除
    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;
}

3.批量删除

/**
 * LinkedList并没有该方法，该方法是定义在其父类AbstractCollection上的
 */
public boolean removeAll(Collection<?> c) {
    Objects.requireNonNull(c);
    boolean modified = false;
    // 迭代器
    Iterator<?> it = iterator();
    while (it.hasNext()) {
        // 判断迭代的元素是否包含在容器c中
        if (c.contains(it.next())) {
            // 真正删除元素的方法
            it.remove();
            modified = true;
        }
    }
    return modified;
}

/**
 * AbstractSequentialList复写父类的方法
 */
public Iterator<E> iterator() {
    return listIterator();
}

public ListIterator<E> listIterator() {
    return listIterator(0);
}

/**
 * LinkedList复写父类的方法
 */
public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

private class ListItr implements ListIterator<E> {
    private Node<E> lastReturned;
    private Node<E> next;
    private int nextIndex;
    // ListItr初始化时，将操作计数器modCount赋值给expectedModCount。
    // 之后每次调用remove方法都会校验expectedModCount与modCount是否相等，否则会抛出异常。
    private int expectedModCount = modCount;
    // ...
}

/**
 * 调用next方法，迭代到下一个节点
 */
public E next() {
    checkForComodification();
    if (!hasNext())
        throw new NoSuchElementException();

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

public void remove() {
    checkForComodification();
    if (lastReturned == null)
        throw new IllegalStateException();
    // lastReturned的下一个节点
    Node<E> lastNext = lastReturned.next;
    // 删除lastReturned节点
    unlink(lastReturned);
    if (next == lastReturned)
        next = lastNext;
    else
        nextIndex--;
    lastReturned = null;
    expectedModCount++;
}

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

5.关于LinkedList作为双向队列

前面已经说过LinkedList实现了Deque接口，可以作为双向队列使用
1.从链表头部或尾部新增节点

// 作为双向队列从头部或尾部新增节点
public void addFirst(E e) {
    linkFirst(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的前向指针指向新增的节点
        f.prev = newNode;
    size++;
    modCount++;
}

/**
 * 从尾部新增节点
 */
public void addLast(E e) {
    linkLast(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++;
}

2.从头部或尾部获取元素

// 过于简单不做分析
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

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

3.从头部或尾部删除元素

/**
 * 从头部删除节点
 */
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

private E unlinkFirst(Node<E> f) {
    final E element = f.item;
    // 记录f的下一个节点
    final Node<E> next = f.next;
    // 置为null，表示删除节点
    f.item = null;
    f.next = null; // help GC
    // 使next成为第一个节点
    first = next;
    if (next == null)
        // 删除的是最后一个节点，则last也置为null
        last = null;
    else
        // 否则next节点的前向指针置为null(头结点的前向指针与尾结点的后继指针为null)
        next.prev = null;
    size--;
    modCount++;
    return element;
}

/**
 * 从尾部删除节点
 * 与从头部删除节点的逻辑类似
 */
public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return unlinkLast(l);
}

private E unlinkLast(Node<E> l) {
    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.总结

1.LinkedList是双向链表的数据结构，相比于单链表，在删除一个节点时，不需要像单链表一样一路保存当前节点的前向节点，因为双向链表当前节点本身就已经保存有前向指针，所以删除时双向链表比单向链表效率更高。
2.需要额外的内存空间保存节点信息。
3.对于大数据量来说，相比ArrayList，具有增删快查找慢特性。

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