从源码上分析 LinkedList(附图)

前言

上一篇我们介绍了 ArrayList,这次,我们再看看一下它的兄弟:LinkedList

LinkedList 同样也实现了 List 接口,底层原理是双向链表,那么它又是如何实现的呢?继续来看吧。

源码分析

成员变量

LinkedList 只有三个成员变量:

transientint size = 0;

transient Node<E> first;

transient Node<E> last;

size 属性不用说,肯定是表示链表的逻辑长度,first 应该是链表的第一个元素,last 表示最后一个元素。

构造方法

先来看无参构造:

public LinkedList() {
}

无参构造没有任何逻辑,那么再来看看其他的构造方法:

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

这里牵扯到要给 addAll 方法,一会在常用方法里我们会讲到,这里先放一放。

这次我们带上内存图来分析,会更直观一些,首先用无参构造来创建一个对象:

1

List<Student> list = new LinkedList<>();

注:为了节省篇幅,本图省略了一些细节上东西,如常量池,方法区等内容。

常用方法

add

首先是 add 方法:

public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node<E> l = last;  // last 节点表示添加前最后一个节点
    final Node<E> newNode = new Node<>(l, e, null);  // 要添加的节点的上一个节点应该是 last 节点。
    last = newNode;          // 添加了节点后,添加的新节点应该为 last 节点。
    if (l == null)           // 如果当前元素没有上一个元素,则表示为第一次添加,
        first = newNode;     // 那么当前节点应该也算是 first 节点。
    else
        l.next = newNode;
    size++;                  // 逻辑长度 + 1
    modCount++;              // 修改次数 + 1
}

这里提到了 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 类是 LinkedList 的静态内部类,表示链表的一个节点。

那么当我们执行这段代码后,会发送什么呢?

1

list.add(new Student("张三", 20));

那我们再添加一个元素呢?

1

list.add(new Student("李四", 21));

可能看起来有写复杂,其实也不难理解,耐下心对照源码好好看一下,应该就能理解这张图的意思了。

我们再添加两个元素看看效果。

list.add(new Student("王五", 22));
list.add(new Student("赵六", 23));

remove

添加了这么多,我们删除一个试试,先来看看源码:

// 根据索引删除
public E remove(int index) {
    checkElementIndex(index);   // 检查要删除的元素索引是否有效,即 0 <= index < size
    return unlink(node(index)); // node(index) 方法找到第 index 个元素
}

private void checkElementIndex(int index) {
    if (!isElementIndex(index))
        throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isElementIndex(int index) {
    return index >= 0 && index < size;
}

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;             // 删除头节点后,更换 first 指向
    } else {                      // 如果不是头节点
        prev.next = next;         // 将前驱节点的 next 指向要删除节点的后继节点
        x.prev = null;            // 将要删除的节点不再指向任何节点
    }

    if (next == null) {           // 如果当前节点为最后一个节点
        last = prev;              // 将 last 指向倒数第二个
    } else {                      // 如果不是最后一个节点
        next.prev = prev;         // 将后继节点的 prev 指向要删除元素的前驱节点
        x.next = null;            // 将要删除的节点不再指向任何节点
    }

    x.item = null;                // 将要删除的元素的数据清空
    size--;                       // 逻辑长度 - 1
    modCount++;                   // 修改次数 + 1
    return element;               
}

可能这里的这 10 和 17 行不太容易理解:

prev.next = next; // 将前驱节点的 next 指向要删除节点的后继节点

next.prev = prev; // 将后继节点的 prev 指向要删除元素的前驱节点

举个简单的例子: 张三 <==> 李四 <==> 王五

那么要删除李四的话,应该要将张三的 “下一个” 指向王五吧,也就是 prev.next = next;。同样,应为是双向链表,所以也应该让王五的 “上一个” 指向张三,即 next.prev = prev;

这里讲解的是根据索引删除,还有根据元素删除,其实原理是一样的,主要是 unlink 这个方法,先根据传入的参数,找到要删除的元素,然后进行 unlink 方法的逻辑即可,这里就不再展开,如果你看懂了根据索引删除,相信你也能理解根据元素删除。

但是需要注意的是:如果删除的是引用数据类型的话,需要重写 equals 方法,不然可能会无法进行删除操作哦。

其实仔细想想也能理解,既然需要 找到要删除的元素,那么如何判断传入的参数和要删除的是同一个呢?只有 equals 方法了,而默认从 Object 继承的 equals 方法可不一定能满足我们的需求,因为它只比较地址值,所以我们需要重写 equals 方法。

get

 public E get(int index) {
    checkElementIndex(index);    // 检查要获取的元素索引是否有效,即 0 <= index < size
    return node(index).item;     // 根据索引来找到这个元素,返回它的 item 值
}

Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {   // 如果要删除的元素在前半段, 则从 first 开始查找
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {                     // 如果要删除的元素在后半段, 则从 last 开始查找
        Node<E> x = last;  
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

这里用了一个很巧妙的小算法,既然我们知道链表的长度,那么当要删除的元素 索引 < 长度 / 2,就从第一个开始找,反之从最后一个开始找,长度 / 2 可以改写为位运算即:size >> 1,效率更高一些。

先讲这么多,如果你看懂了这些,相信 LinkedList 的其他方法,你也能够轻松的理解。

总结

根据上方的源码分析,我们可以总结出 LinkedList 的一些特性:

  • LinkedList 底层数据结构是双向链表。
  • 不能对元素进行随机访问,虽然提供了 get 方法,但这个方法是通过遍历来实现的。
  • 删除、添加元素的效率很高,但查找元素的的效率较差。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏互扯程序

Java常用集合源码级深度解析

Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组、链表、栈、队列、集合、哈希表等。学习Java集合框架下大致可以分为如下五个部分:...

4946
来自专栏个人分享

LinkedHashMap的实现原理(复习)

   LinkedHashMap是Map接口的哈希表和链接列表实现,具有可预知的迭代顺序。此实现提供所有可选的映射操作,并允许使用null值和null键。此类不...

1034
来自专栏Java技术栈

Java码农必须掌握的循环删除List元素的正确方法!

首先看下下面的各种删除list元素的例子 public static void main(String[] args) { List<Stri...

35710
来自专栏皮皮之路

【JDK1.8】JDK1.8集合源码阅读——LinkedList

31712
来自专栏Bingo的深度学习杂货店

Q67 Add Binary

Given two binary strings, return their sum (also a binary string). For example, ...

2778
来自专栏Java技术

初探Java源码之LinkedList

上篇文章我们分析了常见的ArrayList源码,它的内部是由一个数组来实现的。那么今天,我们来分析另一个常见的类LinkedList。本文分析都来自Java8。...

1192
来自专栏恰同学骚年

剑指Offer面试题:12.在O(1)时间删除链表结点

  在单向链表中删除一个结点,最常规的做法无疑是从链表的头结点开始,顺序遍历查找要删除的结点,并在链表中删除该结点。这种思路由于需要顺序查找,时间复杂度自然就是...

691
来自专栏java一日一条

集合类操作优化经验总结

在实际的项目开发中会有很多的对象,如何高效、方便地管理对象,成为影响程序性能与可维护性的重要环节。Java 提供了集合框架来解决此类问题,线性表、链表、哈希表等...

812
来自专栏好好学java的技术栈

自己动手写一个单链表

单向链表(单链表)是链表的一种,其特点是链表的链接方向是单向的,对链表的访问要通过顺序读取从头部开始。

2176
来自专栏Java帮帮-微信公众号-技术文章全总结

Java集合详解【面试+工作】

在说集合前我们不得不说一下数组 数组的作用: 存放一组相同的数据类型(基本或对象)的数据,从而实现对数据的管理 优势:可以快速的通过下标对数组元素进行访问,效率...

4356

扫码关注云+社区