六张图详解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方法。

如果感觉文章不错的话,点个赞吧!

商匡云商
Logo
注册新帐户
对比商品
  • 合计 (0)
对比
0
购物车