Java源码分析 – LinkedList

Java源码分析 – LinkedList

什么是LinkedList

和ArrayList不同,LinkedList是基于链表实现的线性数据结构。节点之间访问不是通过下标进行,而是通过指针。同时,LinkedList实现了List接口和Deque接口。在Deque接口中提供了许多有用的方法,我们下面会选一些详细说。

这是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;
        }
    }
  • item: 数据
  • next: 下一个节点
  • prev: 上一个节点

可以看到,LinkedList是双向链表,因为每个节点都有指向前驱后继节点的指针。

他的数据结构类似这样:

| prev | node1 | next | -> | prev | node2 | next | -> | prev | node3 | next | -> | prev | node4 | next |

LinkedList是基于链表实现的,因此我们的重点就是掌握节点之间是如何添加/删除的。掌握了节点是如何修改指针之后,无论是需要第一个元素,还是最后一个元素,还是要获取其中任意一个元素,我们都能够自己实现了。

LinkedList的add()

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

    void linkLast(E e) {
        final Node<E> l = last;  // 1
        final Node<E> newNode = new Node<>(l, e, null);  // 2
        last = newNode;  // 3
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }
  • add() 方法调用 linkLast() 方法
  • linkLast()方法分以下几步
    • 让一个l 节点指向 last
    • 创建一个新的节点newNode,并且把前驱结点设置为 last
    • last 指向新创建的节点newNode
    • 设置 l.next 为新创建的节点

这就实现了把一个新的节点插入到链表末尾的功能。我们可以画图来表示:

  • | last.prev | last | null | - 这是last节点的数据结构
  • | null | data | null | - 这是新节点的数据结构
  • | last.prev| last | null | -> | last | data | null | - 把 e 的前驱节点设置为 last
  • | last.prev| last | data | -> | last | data | null | - 把 l 的后继节点设置为 newNode

通过这4步,就成功的把两个节点连接在一起了,而且新创建的节点在last节点之后,成为新的尾节点

用文字来总结就是:

  • 持有一个对last节点的引用
  • 创建新的节点
  • 新节点的前驱设置为last
  • last节点的后继设置为新节点

注意:注释3这一步,last = newNode,其实在后面做也可以,只要保证last指向的是最后一个元素地址就可以了。

说完了添加操作,我们再来看看链表的移除。

LinkedList的remove()

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

    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() 方法比add() 要复杂,实际上也确实是的。

想象一下,一条队伍里相邻的两个人互相手牵手,如果要在队尾加上一个人,那么只是最后一个人和新来的人牵手就可以了。

但是如果是中间某个人要离开队伍了,那么和他相邻的两个人(前驱后继)都会受到影响。在链表里面也是一样的,如果我们要进行中间元素的删除操作,那么需要修改的节点是3个。当然插入中间元素也是一样的意思。

下面进入源码分析阶段:

  • remove(): 遍历找到要删除的元素
  • 如果是null,那么找data == null的节点 (null 不能用equals())
  • 如果不为null,那么就找 data.equals(x.item) 的节点,反正是找到第一个值相等的元素

找到之后就进入unlink() 方法:

  • 首先持有x节点的前驱后继节点的指针
  • 判断是不是头节点(没有prev),是的话直接让 first 指向 x.next 就可以了
  • 不是头节点的话,让前驱节点的后继节点设为x的后继节点,也就是把x从前驱节点中去掉了
  • 再把x的前驱节点设为null,也就是松开自己和前面一个人的手(去掉自己的前驱节点)
  • 同样的方法处理后继节点

如果通过画图来展示的话就是:

第一种情况:头节点

| null | x | x.next | -> | x | a | a.next |

直接让first = x.next,也就是让 first 指向 a,完成 x 的删除操作

第二种情况:中间节点

| x | first | first.next | -> | first | x | x.next | -> | x | b | b.next |

首先让 first.next -> b ( x.next ),此时变成了

| x | first | b | -> | first | x | x.next | -> | x | b | b.next |

然后修改x的前驱为null,此时变成了

| x | first | b | -> | null | x | x.next | -> | x | b | b.next |

这就解除了和前驱结点之间的联系,然后相同的思路处理后继节点即可。

第三种情况:尾节点

| x.prev | x | null |

这种情况我们让last指向x.prev就可以了,尾节点就从x变成了它的前一个节点

LinkedList的一些细节

通过我们上面总结的添加和移除元素的思路,再配合Deque接口里面的许多方法,可以实现很多有意思的操作。

有意思的查找Node算法

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

虽然链表一般情况下来说通过下标来查找,时间复杂度为O(n),但是LinkedList里面还是用了点小技巧进行优化,通过类似二分法的思想,把整个链表平分为两部分,判断传入的下标是在前半部分还是后半部分,如果是前半部分,那么从头开始找。如果是后半部分,那么就从尾开始找。这样做的好处是:

  • 把O(n) 的时间复杂度缩短为O(n/2)
  • 利用了双向链表的优势,可以从前往后,也可以从后往前
  • 同样用了位运算来判断index的位置,优化计算效率

LinkedList如何通过下标插入?

LinkedList相比ArrayList的一个优势就是插入删除更加高效,因为只要修改相邻节点就可以了,但是ArrayList需要进行数组的复制移动。需要的内存和时间都更多。

而LinkedList不仅实现了在头/尾插入删除元素,还能指定下标进行添加/删除操作。具体是怎么做到的呢?

    public void add(int index, E element) {
        checkPositionIndex(index);

        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

核心方法其实就是上面说的node ,传入index然后返回找到的node,然后再通过我们在上面说的,修改前驱后继节点来实现插入操作。

Deque的peekFrist() 和 getFirst()有什么区别?

Deque里面这两个实现方法:

    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

    public E element() {
        return getFirst();
    }

    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
  • peek(): 返回 null 或者 元素数据
  • element(): 抛出NoSuchElementException() 或者 元素数据

也就是说,如果我们可以接受null的话,可以使用peekFirst(),类似的方法还有peekLast() 和 getLast()。

LinkedList的clear()

clear():

    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; ) {
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }

为了能够让JVM进行GC,把所有的对象设置为null,包括first & last。

总结

LinkedList的操作都围绕着如果管理相邻节点的前驱后继指针。只要把这个弄清楚,那么无论是添加还是删除都是比较容易写出来的。如果大家觉得不好理解,可以在纸上把数据结构画出来,在每一步操作之后修改对应的节点指针,会好理解一点。

LinkedList实现的Deque接口,提供了许多有用的方法,如果我们需要进行频繁插入删除操作的话,可以优先考虑LinkedList而不是ArrayList,并且看看里面有没有我们需要的实现~

在这里也推荐一些链表相关的算法题,可以通过做题的方式检验一下自己是不是真的掌握了:

  • LeetCode.19 删除链表倒数第N位节点
  • LeetCode.21 合并两个有序链表
  • LeetCode.206 反转链表
  • LeetCode.237 删除链表中的节点

 
 
 

本文以创作共用版权协议发布,转载本文要求遵循“署名-非商业性使用-相同方式共享3.0”的创作共用协议,并以链接形式指明本文地址。

本文链接地址:https://www.bluelzy.top/java-foundation-linkedlist/

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注