亲宝软件园·资讯

展开

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

沉默王二 人气:0
想了解以武侠形式理解Java LinkedList源码的相关内容吗,沉默王二在本文为您仔细讲解Java LinkedList的相关知识和一些Code实例,欢迎阅读和指正,我们先划重点:Java,LinkedList,Java,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;
    }
}

它由三部分组成:

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

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

三、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++;
}

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

此时的链表还不完整。

此时的链表已经完整了。

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

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 内部调用的是 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 的内部分为两种,一种是元素为 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;
}

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

四、LinkedList 的挑战

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

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

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

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

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

好了,LinkedList 这篇就到这了。

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

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

加载全部内容

相关教程
猜你喜欢
用户评论