乐趣区

关于程序员:六张图详解LinkedList-源码解析

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 的后置指针指向新节点

如果原尾部节点为空,间接创立一个节点,这个节点是 lastfirst节点。
如果原尾部节点不为空,创立新节点,新节点的前置指向原来的 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指向 prednext 指向succ
  • succpre 指向新节点。
  • 如果 pred 为 null,示意首节点是succ, 将节点赋值给first 节点。
  • 如果 pred 不为 null,prednext指向新节点。

比方一个长度为 5 的链表,在下标为 1 的地位增加数据:

获取数据

获取数据次要有getgetFirstgetLast

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奇妙的判断 indexsize一半长度的关系, 小于就从前往后遍历,大于就从后往前遍历。无需遍历整个链表。
    • 找到节点之后,记录节点的 prev 节点,在 prev 和节点之间创立新的节点。
  • remove(Object o), 遍历找到元素,再调用 unlink 办法。记录元素的前置节点 prev 和后置节点 next, 前置节点next 指向后置节点,后置节点的 next 指向前置节点,删除其它的前置节点和后置节点的指针。
  • remove(int index), 先通过 node 办法找到下标的数据,找到元素之后,再调用 unlink 办法。

本文由 mdnice 多平台公布

退出移动版