六张图详解 LinkedList 源码解析

2022-11-02
广东
本文字数：3302 字
阅读完需：约 11 分钟

LinkedList 底层基于链表实现，增删不需要移动数据，所以效率很高。但是查询和修改数据的效率低，不能像数组那样根据下标快速的定位到数据，需要一个一个遍历数据。

基本结构

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 前置指针和next 后置指针。

还有首节点first、尾节点last、长度size:

transient int size = 0;
transient Node<E> first;
transient Node<E> last;

复制代码

添加数据

LinkedList 添加元素有两个方法：add(E e) 和 add(int index,E e)。

add(E e) 是在链表的尾部添加数据
add(int index,E e) 在指定链表位置添加数据

add(E e)

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 自增      size++;    modCount++;}

复制代码

记录原尾部节点 l
创建新的节点，前置指向原尾部节点。
如果 l 为空，更新头部节点
更新尾部节点
如果 l 不为空，l 的后置指针指向新节点

如果原尾部节点为空，直接创建一个节点，这个节点是last和first节点。如果原尾部节点不为空，创建新节点，新节点的前置指向原来的 last，原来的 last 的 next 指向新节点。

add在链尾添加数据，添加前后指针。以及更新为last节点。

add(int index,E e)

这个方法是添加元素到链表的指定位置，链表的下标和数组一样，也是从0开始算起:

先看一下 add(int index, E element) 方法

public void add(int index, E element) {    // 检查下标是否越界    checkPositionIndex(index);    if (index == size)        // 下标等于size，直接添加到链表尾部        linkLast(element);    else        //         linkBefore(element, node(index));}

复制代码

checkPositionIndex 判断下标是否越界，index >= 0 && index <= size index 是否在 0 ~ size 范围之内。

如果index等于 size，和 add(E e) 操作一样，都是添加在链表尾部。如果index小于 size，调用 linkBefore 方法，往链表中间插入节点。首先看 node 方法：

Node<E> node(int index) {    // assert isElementIndex(index);    // size >> 1 表示 size 右移一位，就是 size/2 size的一半    // index 小于 size 的一半，从首节点往后遍历    if (index < (size >> 1)) {        Node<E> x = first;        for (int i = 0; i < index; i++)            x = x.next;        return x;    // index 大于 size 的一半，从最后一个节点往前遍历        } else {        Node<E> x = last;        for (int i = size - 1; i > index; i--)            x = x.prev;        return x;    }}

复制代码

node() 方法就是找到 index 对应的 node 节点。

比如一个长度为5的链表:

node(1) 从 first 节点（第 0 个节点）往后遍历一个，也就是1对应的节点。node(3) 从 last 节点（第 4 个节点）往前遍历一个，也就是3对应的节点。

通过下标找到节点，链表一般是需要遍历一遍，这里最多需要遍历一半的链表，主要是利用了双链表的特性，既可以从前往后遍历，又可以从后往前遍历。

size>>1 表示 size/2,判断 index 是在链表的前半部分还是后半部分，如果在前半部分就从首节点往后遍历，如果在后半部分就从最后一个节点往前遍历，**，这样最多遍历 size 的一半，避免遍历整个链表。**找到 index 下的节点之后，再看 linkedBefore 方法:

void linkBefore(E e, Node<E> succ) {    // assert succ != null;    // 记录前置节点 pred    final Node<E> pred = succ.prev;    // 创建新节点，新节点的pre指向 pred，next指向succ节点    final Node<E> newNode = new Node<>(pred, e, succ);    // succ pre指向新节点    succ.prev = newNode;    // 如果pred为空，表示succ就是首节点，新节点赋为首节点    if (pred == null)        first = newNode;    else    // pred的next 指向新节点        pred.next = newNode;    size++;    modCount++;}

复制代码

记录succ节点的前置节点 pred。
新建节点，pre指向pred，next指向succ。
succ的pre 指向新节点。
如果pred 为 null，表示首节点是succ,将节点赋值给first节点。
如果pred 不为 null，pred的next指向新节点。

比如一个长度为5的链表，在下标为1的位置添加数据：

获取数据

获取数据主要有get、getFirst、getLast。

get 方法主要是通过 node 方法下标的节点，获取节点的 item 数据。

getFirst 方法获取首节点的item。

getLast 方法获取尾节点的item。

删除数据

remove(Object o)

从列表中删除第一个匹配的元素

public boolean remove(Object o) {    // 判断是否为null    if (o == null) {        // 遍历node         for (Node<E> x = first; x != null; x = x.next) {            if (x.item == null) {                unlink(x);                return true;            }        }    } else {        // 遍历node        for (Node<E> x = first; x != null; x = x.next) {            if (o.equals(x.item)) {                unlink(x);                return true;            }        }    }    return false;}

复制代码

删除指定元素，需要判断元素是否为 null。

如果为null，就使用x.item == null语句判断。
如果不为null，就使用o.equals(x.item)语句判断。

然后再调用unlink方法：

E unlink(Node<E> x) {    // assert x != null;    // 记录节点element、next和prev    final E element = x.item;    final Node<E> next = x.next;    final Node<E> prev = x.prev;    // prev为null，next 赋为首节点     if (prev == null) {        first = next;    } else {        // prev的next指向next节点        prev.next = next;        // x节点prev置为null        x.prev = null;    }    // next为null，prev赋为尾节点    if (next == null) {        last = prev;    } else {        // next的prev指向prev        next.prev = prev;        // x节点next置为null        x.next = null;    }    // x.item置为null    x.item = null;    // 长度自减    size--;    modCount++;    return element;}

复制代码

如图，要删除1数据的节点：

remove(int index)

删除指定下标的数据：

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

复制代码

首先通过 node找到对应下标的节点，再调用unlink删除数据即可。

总结

LinkedList 是一个双链表的数据格式，为了支持双链表结构，有头节点，尾节点以及 size 大小。
add(E e) 直接添加在队列尾部，新节点 prev 指向尾节点，尾节点指向新节点。
add(int index,E e)如果添加位置等于链表长度，直接在链表尾节点添加数据。否则在链表中间添加数据。
在链表中间添加数据首先要通过node方法获取数据，node巧妙的判断index和size一半长度的关系,小于就从前往后遍历，大于就从后往前遍历。无需遍历整个链表。
找到节点之后，记录节点的prev节点，在prev和节点之间创建新的节点。
remove(Object o),遍历找到元素，再调用unlink方法。记录元素的前置节点prev和后置节点next,前置节点next指向后置节点，后置节点的 next 指向前置节点，删除其它的前置节点和后置节点的指针。
remove（int index）,先通过node方法找到下标的数据，找到元素之后，再调用unlink方法。

发布于: 刚刚阅读数: 3

Jeremy Lai

关注

还未添加个人签名 2018-02-12 加入

还未添加个人简介

发布

暂无评论

创作场景

六张图详解 LinkedList 源码解析

基本结构

添加数据

add(E e)

add(int index,E e)

获取数据

删除数据

remove(Object o)

remove(int index)

总结

Jeremy Lai

评论