以武侠形式理解Java LinkedList源码

目录
  • 一、LinkedList 的剖白
  • 二、LinkedList 的内功心法
  • 三、LinkedList 的招式
    • 1)招式一:增
    • 2)招式二:删
    • 3)招式三:改
    • 4)招式四:查
  • 四、LinkedList 的挑战

一、LinkedList 的剖白

大家好,我是 LinkedList,和 ArrayList 是同门师兄弟,但我俩练的内功却完全不同。师兄练的是动态数组,我练的是链表。

问大家一个问题,知道我为什么要练链表这门内功吗?

举个例子来讲吧,假如你们手头要管理一推票据,可能有一张,也可能有一亿张。

该怎么办呢?

申请一个 10G 的大数组等着?那万一票据只有 100 张呢?

申请一个默认大小的数组,随着数据量的增大扩容?要知道扩容是需要重新复制数组的,很耗时间。

关键是,数组还有一个弊端就是,假如现在有 500 万张票据,现在要从中间删除一个票据,就需要把 250 万张票据往前移动一格。

遇到这种情况的时候,我师兄几乎情绪崩溃,难受的要命。师父不忍心看到师兄这样痛苦,于是打我进入师门那一天,就强迫我练链表这门内功,一开始我很不理解,害怕师父偏心,不把师门最厉害的内功教我。

直到有一天,我亲眼目睹师兄差点因为移动数据而走火入魔,我才明白师父的良苦用心。从此以后,我苦练“链表”这门内功,取得了显著的进步,师父和师兄都夸我有天赋。

链表这门内功大致分为三个层次:

  • 第一层叫做“单向链表”,我只有一个后指针,指向下一个数据;
  • 第二层叫做“双向链表”,我有两个指针,后指针指向下一个数据,前指针指向上一个数据。
  • 第三层叫做“二叉树”,把后指针去掉,换成左右指针。

但我现在的功力还达不到第三层,不过师父说我有这个潜力,练成神功是早晚的事。

先赞后看:《Java 程序员进阶之路》专栏在 GitHub 上已经开源了,有 GitHub 账号的小伙伴,来安排一波 star 呀!看能不能冲一波 trending 榜单,求求各位了。

GitHub 地址:https://github.com/itwanger/toBeBetterJavaer

二、LinkedList 的内功心法

好了,经过我这么样的一个剖白后,大家对我应该已经不陌生了。那么接下来,我给大家展示一下我的内功心法。

我的内功心法主要是一个私有的静态内部类,叫 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;
    }
}

它由三部分组成:

  • 节点上的元素
  • 下一个节点
  • 上一个节点

我画幅图给你们展示下吧。

  • 对于第一个节点来说,prev 为 null;
  • 对于最后一个节点来说,next 为 null;
  • 其余的节点呢,prev 指向前一个,next 指向后一个。

我的内功心法就这么简单,其实我早已经牢记在心了。但师父叮嘱我,每天早上醒来的时候,每天晚上睡觉的时候,一定要默默地背诵一遍。虽然我有些厌烦,但我对师父的教诲从来都是言听计从。

三、LinkedList 的招式

和师兄 ArrayList 一样,我的招式也无外乎“增删改查”这 4 种。在此之前,我们都必须得初始化。

LinkedList<String> list = new LinkedList();

师兄在初始化的时候,默认大小为 10,也可以指定大小,依据要存储的元素数量来。我就不需要。

1)招式一:增

可以调用 add 方法添加元素:

list.add("沉默王二");
list.add("沉默王三");
list.add("沉默王四");

add 方法内部其实调用的是 linkLast 方法:

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

linkLast,顾名思义,就是在链表的尾部链接:

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++;
}
  • 添加第一个元素的时候,first 和 last 都为 null。
  • 然后新建一个节点 newNode,它的 prev 和 next 也为 null。
  • 然后把 last 和 first 都赋值为 newNode。

此时还不能称之为链表,因为前后节点都是断裂的。

  • 添加第二个元素的时候,first 和 last 都指向的是第一个节点。
  • 然后新建一个节点 newNode,它的 prev 指向的是第一个节点,next 为 null。
  • 然后把第一个节点的 next 赋值为 newNode。

此时的链表还不完整。

  • 添加第三个元素的时候,first 指向的是第一个节点,last 指向的是最后一个节点。
  • 然后新建一个节点 newNode,它的 prev 指向的是第二个节点,next 为 null。
  • 然后把第二个节点的 next 赋值为 newNode。

此时的链表已经完整了。

我这个增的招式,还可以演化成另外两个:

  • addFirst() 方法将元素添加到第一位;
  • addLast() 方法将元素添加到末尾。

addFirst 内部其实调用的是 linkFirst:

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

linkFirst 负责把新的节点设为 first,并将新的 first 的 next 更新为之前的 first。

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.prev = newNode;
    size++;
    modCount++;
}

addLast 的内核其实和 addFirst 差不多,就交给大家自行理解了。

2)招式二:删

我这个删的招式还挺多的:

  • remove():删除第一个节点
  • remove(int):删除指定位置的节点
  • remove(Object):删除指定元素的节点
  • removeFirst():删除第一个节点
  • removeLast():删除最后一个节点

remove 内部调用的是 removeFirst,所以这两个招式的功效一样。

remove(int) 内部其实调用的是 unlink 方法。

public E remove(int index) {
    checkElementIndex(index);
    return unlink(node(index));
}

unlink 方法其实很好理解,就是更新当前节点的 next 和 prev,然后把当前节点上的元素设为 null。

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 {
        prev.next = next;
        x.prev = null;
    }

    if (next == null) {
        last = prev;
    } else {
        next.prev = prev;
        x.next = null;
    }

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

remove(Object) 内部也调用了 unlink 方法,只不过在此之前要先找到元素所在的节点:

public boolean remove(Object o) {
    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;
}

这内部就分为两种,一种是元素为 null 的时候,必须使用 == 来判断;一种是元素为非 null 的时候,要使用 equals 来判断。equals 是不能用来判 null 的,会抛出 NPE 错误。

removeFirst 内部调用的是 unlinkFirst 方法:

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

unlinkFirst 负责的就是把第一个节点毁尸灭迹,并且捎带把后一个节点的 prev 设为 null。

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

3)招式三:改

可以调用 set() 方法来更新元素:

list.set(0, "沉默王五");

来看一下 set() 方法:

public E set(int index, E element) {
    checkElementIndex(index);
    Node<E> x = node(index);
    E oldVal = x.item;
    x.item = element;
    return oldVal;
}

首先对指定的下标进行检查,看是否越界;然后根据下标查找原有的节点:

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

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

size >> 1:也就是右移一位,相当于除以 2。对于计算机来说,移位比除法运算效率更高,因为数据在计算机内部都是二进制存储的。

换句话说,node 方法会对下标进行一个初步判断,如果靠近前半截,就从下标 0 开始遍历;如果靠近后半截,就从末尾开始遍历。

找到指定下标的节点就简单了,直接把原有节点的元素替换成新的节点就 OK 了,prev 和 next 都不用改动。

4)招式四:查

我这个查的招式可以分为两种:

  • indexOf(Object):查找某个元素所在的位置
  • get(int):查找某个位置上的元素

indexOf 的内部分为两种,一种是元素为 null 的时候,必须使用 == 来判断;一种是元素为非 null 的时候,要使用 equals 来判断。因为 equals 是不能用来判 null 的,会抛出 NPE 错误。

public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

get 方法的内核其实还是 node 方法,这个之前已经说明过了,这里略过。

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}

其实,查这个招式还可以演化为其他的一些,比如说:

  • getFirst() 方法用于获取第一个元素;
  • getLast() 方法用于获取最后一个元素;
  • poll()pollFirst() 方法用于删除并返回第一个元素(两个方法尽管名字不同,但方法体是完全相同的);
  • pollLast() 方法用于删除并返回最后一个元素;
  • peekFirst() 方法用于返回但不删除第一个元素。

四、LinkedList 的挑战

说句实在话,我不是很喜欢和师兄 ArrayList 拿来比较,因为我们各自修炼的内功不同,没有孰高孰低。

虽然师兄经常喊我一声师弟,但我们之间其实挺和谐的。但我知道,在外人眼里,同门师兄弟,总要一较高下的。

比如说,我们俩在增删改查时候的时间复杂度。

也许这就是命运吧,从我进入师门的那天起,这种争论就一直没有停息过。

无论外人怎么看待我们,在我眼里,师兄永远都是一哥,我敬重他,他也愿意保护我。

好了,LinkedList 这篇就到这了。

如果大家有闲情逸致的话,建议手撕一下链表,可以从单向链表开始撕起。

希望大家能点赞下,给我注入一点点更新的动力。我也会不断地提升品质,给大家带来更硬核的技术文章,笔芯~

到此这篇关于以武侠形式理解Java LinkedList源码的文章就介绍到这了,更多相关Java LinkedList内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们!

(0)

相关推荐

  • 看动画学算法之Java实现doublyLinkedList

    简介: 和LinkedList相比,doublyLinkedList中的节点除了next指向下一个节点之外,还有一个prev之前的一个节点.所以被称为doublyLinkedList. doublyLinkedList是一个双向链表,我们可以向前或者向后遍历list. 今天我们来学习一下doublyLinkedList的基本操作和概念. 1.doublyLinkedList的构建 和linkedList一样,doublyLinkedList是由一个一个的节点构成的.而每个节点除了要存储要保存的数

  • java中LinkedList使用迭代器优化移除批量元素原理

    本文主要介绍了java中LinkedList使用迭代器优化移除批量元素原理,分享给大家,具体如下: public interface Iterator<E> { /** *是否还有下一个元素 */ boolean hasNext(); /** *下一个元素 */ E next(); /** * 从集合中删除最后一个返回的元素 */ default void remove() { throw new UnsupportedOperationException("remove"

  • Java集合框架之List ArrayList LinkedList使用详解刨析

    目录 1. List 1.1 List 的常见方法 1.2 代码示例 2. ArrayList 2.1 介绍 2.2 ArrayList 的构造方法 2.3 ArrayList 底层数组的大小 3. LinkedList 3.1 介绍 3.2 LinkedList 的构造方法 4. 练习题 5. 扑克牌小游戏 1. List 1.1 List 的常见方法 方法 描述 boolean add(E e) 尾插 e void add(int index, E element) 将 e 插入到 inde

  • Java基础之容器LinkedList

    一.LinkedList的整体结构 1.1.LinkedList的继承关系 public class LinkedList<E> extends AbstractSequentialList <E> implements List<E>, Deque<E> LinkedList具备AbstractSequentialList的特点:AbstractSequentialList 只支持按次序访问,而不像 AbstractList 那样支持随机访问 Linked

  • java中ArrayList和LinkedList的区别详解

    ArrayList和LinkedList都实现了List接口,有以下的不同点: 1.ArrayList是基于索引的数据接口,它的底层是数组.它可以以O(1)时间复杂度对元素进行随机访问.与此对应,LinkedList是以元素列表的形式存储它的数据,每一个元素都和它的前一个和后一个元素链接在一起,在这种情况下,查找某个元素的时间复杂度是O(n). 2.相对于ArrayList,LinkedList的插入,添加,删除操作速度更快,因为当元素被添加到集合任意位置的时候,不需要像数组那样重新计算大小或者

  • Java实现单链表SingleLinkedList增删改查及反转 逆序等

    节点类 可以根据需要,对节点属性进行修改.注意重写toString()方法,以便后续的输出操作. //节点类 class Node { public int id; public String name; public Node next; public Node(int id, String name) { this.id = id; this.name = name; } @Override public String toString() { return "Node{" + &

  • Java容器源码LinkedList原理解析

    LinkedList简介 LinkedList是一个使用双向链表结构实现的容器,与ArrayList一样,它能动态扩充其长度,LinkedList相较于ArrayList,其任意位置插入速度比ArrayList要快,但是其查询速度要比ArrayList要慢:LinkedList继承自AbstractSequentialList,实现了List.Deque.Cloneable.Serializable接口. LinkedList UML图如下: 和ArrayList一样,LinkedList也不是

  • 以武侠形式理解Java LinkedList源码

    目录 一.LinkedList 的剖白 二.LinkedList 的内功心法 三.LinkedList 的招式 1)招式一:增 2)招式二:删 3)招式三:改 4)招式四:查 四.LinkedList 的挑战 一.LinkedList 的剖白 大家好,我是 LinkedList,和 ArrayList 是同门师兄弟,但我俩练的内功却完全不同.师兄练的是动态数组,我练的是链表. 问大家一个问题,知道我为什么要练链表这门内功吗? 举个例子来讲吧,假如你们手头要管理一推票据,可能有一张,也可能有一亿张

  • java LinkedList源码详解及实例

    一.LinkedList概述: LinkedList与ArrayList一样,是实现了List接口.由于LinkedList是基于链表实现的,所以它执行插入和删除操作时比ArrayList更高效,而随机访问的性能要比ArrayList低. 二.LinkedList的实现: 1.构造方法 //构造一个空的LinkedList public LinkedList() { } //接收一个Collection参数c,默认构造方法构造一个空的链表,并通过addAll将c中的元素全部添加到链表中. pub

  • java  LinkedList源码详解及实例

    一.LinkedList概述: LinkedList与ArrayList一样,是实现了List接口.由于LinkedList是基于链表实现的,所以它执行插入和删除操作时比ArrayList更高效,而随机访问的性能要比ArrayList低. 二.LinkedList的实现: 1.构造方法 //构造一个空的LinkedList public LinkedList() { } //接收一个Collection参数c,默认构造方法构造一个空的链表,并通过addAll将c中的元素全部添加到链表中. pub

  • Java集合系列之LinkedList源码分析

    上篇我们分析了ArrayList的底层实现,知道了ArrayList底层是基于数组实现的,因此具有查找修改快而插入删除慢的特点.本篇介绍的LinkedList是List接口的另一种实现,它的底层是基于双向链表实现的,因此它具有插入删除快而查找修改慢的特点,此外,通过对双向链表的操作还可以实现队列和栈的功能.LinkedList的底层结构如下图所示. F表示头结点引用,L表示尾结点引用,链表的每个结点都有三个元素,分别是前继结点引用(P),结点元素的值(E),后继结点的引用(N).结点由内部类No

  • java TreeMap源码解析详解

    java TreeMap源码解析详解 在介绍TreeMap之前,我们来了解一种数据结构:排序二叉树.相信学过数据结构的同学知道,这种结构的数据存储形式在查找的时候效率非常高. 如图所示,这种数据结构是以二叉树为基础的,所有的左孩子的value值都是小于根结点的value值的,所有右孩子的value值都是大于根结点的.这样做的好处在于:如果需要按照键值查找数据元素,只要比较当前结点的value值即可(小于当前结点value值的,往左走,否则往右走),这种方式,每次可以减少一半的操作,所以效率比较高

  • java集合类源码分析之Set详解

    Set集合与List一样,都是继承自Collection接口,常用的实现类有HashSet和TreeSet.值得注意的是,HashSet是通过HashMap来实现的而TreeSet是通过TreeMap来实现的,所以HashSet和TreeSet都没有自己的数据结构,具体可以归纳如下: •Set集合中的元素不能重复,即元素唯一 •HashSet按元素的哈希值存储,所以是无序的,并且最多允许一个null对象 •TreeSet按元素的大小存储,所以是有序的,并且不允许null对象 •Set集合没有ge

  • Java集合源码全面分析

    Java集合工具包位于Java.util包下,包含了很多常用的数据结构,如数组.链表.栈.队列.集合.哈希表等.学习Java集合框架下大致可以分为如下五个部分:List列表.Set集合.Map映射.迭代器(Iterator.Enumeration).工具类(Arrays.Collections). 从上图中可以看出,集合类主要分为两大类:Collection和Map. Collection是List.Set等集合高度抽象出来的接口,它包含了这些集合的基本操作,它主要又分为两大部分:List和Se

  • Java String源码分析并介绍Sting 为什么不可变

    Java String源码分析 什么是不可变对象? 众所周知, 在Java中, String类是不可变的.那么到底什么是不可变的对象呢? 可以这样认为:如果一个对象,在它创建完成之后,不能再改变它的状态,那么这个对象就是不可变的.不能改变状态的意思是,不能改变对象内的成员变量,包括基本数据类型的值不能改变,引用类型的变量不能指向其他的对象,引用类型指向的对象的状态也不能改变. 区分对象和对象的引用 对于Java初学者, 对于String是不可变对象总是存有疑惑.看下面代码: String s =

  • java String源码和String常量池的全面解析

    1. String 介绍,常用方法源码分析 2. String 常量池分析 常用方法 equals trim replace concat split startsWith 和 endsWith substring toUpperCase() 和 toLowerCase() compareTo String 介绍 String类被final所修饰,也就是说String对象是不可变量,并发程序最喜欢不可变量了.String类实现了Serializable, Comparable, CharSequ

随机推荐