源码级深入理解LinkedList,点开即食

在讲LinkedList之前,建议先对ArrayList有一个较为深入的理解,这样两者对比之下,就能找到更适合生产环境中的容器类型,相信我,看下去一定让看官满意~

可以阅读博主的另一边文章,带你全面了解ArrayList,从扩容机制,常见方法,到fail-fast以及并发情况下的问题都有深入分析:深入理解ArrayList

由ArrayList引发的思考

由于ArrayList底层是由数组存储的,优点很明显:连续存储空间可以由角标在o(1)的时间复杂度内完成

缺点:
1.对于元素的增删操作最差达到o(n)
2.并且存在不断扩容的问题,时间消耗较大
3.并且空间并不是你想用多少就给多少,很大可能会造成空间浪费

那么,有没有一种要多少空间就申请多少空间,并且大大较快增删效率的集合呢?

有,那就是接下来讲到的LinkedList

在讲之前来对比一下ArrayList和LinkedList

1.ArrayList底层是由动态数组作为存储结构,LinkedList由双向链表作为存储结构

2.ArrayList对于get(),set()方法效率较高,因为存储空间连续,由下标就可以找到对应存储空间的元素

3.LinkedList对于remove(),add()方法效率较高,因为链表存储结构,只用改变前后指针指向即可,而数组需要挪动数据

4.ArrayList和LinkedList都是线程不安全的,在本文的最后会介绍原因以及解决方案

首先看看LinkedList的继承实现关系

源码级深入理解LinkedList,点开即食
这里的接口不在一一分析了,在博主的ArrayList系列文章中已经深入讲解这些接口,可以移步:深入理解ArrayList
相比于ArrayList,它额外实现了双端队列接口Deque,这个接口主要是声明了队头,队尾的一系列方法。

类内部的成员变量

//容器元素个数 transient int size = 0; //双向链表的头节点 transient Node<E> first; //双向链表的尾节点 transient Node<E> last;  //内部类,链表的实现机制:Node节点,将存储数组转换为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;         }     } 

transient的作用:简单来理解: Map,Set,List等都是使用transient关键字屏蔽变量,然后自己实现的序列化操作(writeObject(),readObject()方法)。

构造方法

//空参构造器 public LinkedList() { } //传入一个Colleaction集合 public LinkedList(Collection<? extends E> c) {         this();         addAll(c);  } 

我查看了网上的大多数博客都没有解释addAll()操作,这里我带大家深入看看这个addAll()方法的奥妙,其中的判断遍历方法大家在算法或者编写代码中都可以借鉴

最难的addAll()方法

先说结论

1.传入集合的构造方法,底层调用,新建一个链表

2.当你想再index位置插入集合时,主动调用

//addAll()方法不止一次调用 public boolean addAll(Collection<? extends E> c) { 		//当构造方法调用时,这时size为默认值0         return addAll(size, c);     } //这里index为传入的size为0 public boolean addAll(int index, Collection<? extends E> c) { 		//简单的判断索引是否合法         checkPositionIndex(index); 		//转换为数组         Object[] a = c.toArray();         int numNew = a.length;         //如果数组为空,就不用往后操作了,直接返回false         if (numNew == 0)             return false; 		//succ表示当前节点插入的位置 		//pred表示插入位置的前一个位置         Node<E> pred, succ;         //接下来看文章来分析         if (index == size) {             succ = null;             pred = last;         } else {             succ = node(index);             pred = succ.prev;         }          for (Object o : a) {             @SuppressWarnings("unchecked") E e = (E) o;             Node<E> newNode = new Node<>(pred, e, null);             if (pred == null)                 first = newNode;             else                 pred.next = newNode;             pred = newNode;         }          if (succ == null) {             last = pred;         } else {             pred.next = succ;             succ.prev = pred;         }          size += numNew;         modCount++;         return true;     } 

我们来看看方法的具体业务逻辑,首先我们明确一点,succ是索引index处的节点,pred是index前一个节点,结合代码看我分析

1.确定succ和pred的位置,当size==index时,说明我们要插入的位置是在队尾,所以我们将succ设为null,pred设为last堆尾

  • 构造方法中调用,这时size==index为0,还没有节点,last还为null,所以prev和succ都为null

  • 如果是你主动调用,size==index,说明要插入到队尾,所以prev=last,succ=null

2.否则我们插入的不是堆尾,我们调用node()方法,我们稍后讲解这个方法,我们暂时只要知道这个方法返回了对应索引位置上的Node(节点),succ = Node,pred = Node.prev,找到了succ和prev的位置

  • 这里构造方法调用addAll()方法时并不会执行,而是当你想在index位置插入一个集合时调用方法时才会走这里的逻辑

3.接下来就是循环入队了, if (pred == null),说明什么?当前要插入位置的前置节点为null,说明要插入的位置就是头节点,所以令头节点first=newNode,否则:pred.next表示当前要插入的位置,令pred.next=newNode,你可能会有疑惑?为什么不直接把succ = newNode,别急接着看

4.succ == null,插入的是队尾,last = pred;

5.这里就是上面的答案,假如你的index是插入到链表中间(也就是else逻辑),将链表劈成两节,pred记录劈开的左端,succ记录劈开的右端,上个for循环将节点都插入到了pred的后面,现在把pred和succ连接,就练成了一条完整的链表,如果没有succ记录,就找不到链表劈开的又断了

上文遗留node(index)方法

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==size/2,所以判断index是偏向链表的左端还是右端,偏向左端从头遍历,偏向右端从尾遍历,加快了找到index节点的速率,是不是很巧妙

一些辅助的方法(private),无法主动调用

不知道你是否记得开头LinkedList同样实现了Deque接口,LinkedList中大多数通过他们来完成List、Deque中类似的操作。

1.linkFirst(E e)方法

把参数中的元素作为链表的第一个元素。

private void linkFirst(E e) {         final Node<E> f = first;         //prev==null,item==e,next==f         final Node<E> newNode = new Node<>(null, e, f);         //将newNode赋给first作为头节点         first = newNode;         //f为null,说明链表为空,将尾节点也指向newNode         if (f == null)             last = newNode;         //f不为null,将f连接在newNode后         else             f.prev = newNode;         //元素个数+1         size++;         //fast-fail实现机制         modCount++;     } 

在集合的CRUD操作中,modCount变量都会改变,设计到fast-fail机制,本文最后讲到

2.linkLast(E e)

把参数中的元素作为链表的最后一个元素

逻辑几乎同上,不在赘述

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

3.linkBefore(E e, Node succ)

在非空节点succ前插入元素E

由于底层调用,不给程序员机会,所以succ传入的一定不为null

void linkBefore(E e, Node<E> succ) {         // assert succ != null;         //记录当前节点的前置节点         final Node<E> pred = succ.prev;         final Node<E> newNode = new Node<>(pred, e, succ);         //将newNode设置在succ前         succ.prev = newNode;         //pred为空,说明当前节点就是头节点,所以在succ前插入节点,         //然后直接将first指向newNode         if (pred == null)             first = newNode;         else         //否则将newNode插入到succ前             pred.next = newNode;         size++;         modCount++;     } 

4.unlinkFirst(Node f)

删除掉链表中第一个节点

private E unlinkFirst(Node<E> f) { 		//这里注释很明显,传入的f == first,并且不为null         // assert f == first && f != null;         //获取到元素         final E element = f.item;         //拿到下一个节点         final Node<E> next = f.next;         //将传入的first头节点清理掉         f.item = null;         f.next = null; // help GC         //令头节点等于第二个节点,next晋升为头节点         first = next;         //头节点的下一个节点是null,说明只有一个节点,         //删除后first==last==null         if (next == null)             last = null;         else         //新晋的next作为头节点,把前置节点设为null             next.prev = null;         size--;         modCount++;         return element;     } 

unlinkLast(Node l)

删除掉最后一个节点,这里的逻辑和上述方法大致相似,更加简单,自己尝试分析试一下

private E unlinkLast(Node<E> l) {         // assert l == last && l != null;         final E element = l.item;         final Node<E> prev = l.prev;         l.item = null;         l.prev = null; // help GC         last = prev;         if (prev == null)             first = null;         else             prev.next = null;         size--;         modCount++;         return element;     }  

5.unlink(Node x)

删除掉x节点,并返回删除节点的元素

E unlink(Node<E> x) { 		//同理,底层调用不给你传null的机会         // assert x != null;         final E element = x.item;         final Node<E> next = x.next;         final Node<E> prev = x.prev; 		//删除的是头节点,直接令next晋升为头节点         if (prev == null) {             first = next;         }                  else {             prev.next = next;             x.prev = null;         } 		//删除的是尾节点,直接令prev晋升为尾节点         if (next == null) {             last = prev;         } else {             next.prev = prev;             x.next = null;         }          x.item = null;         size--;         modCount++;         return element;     } 

这里我们不考虑删除的是头节点,尾节点的情况,一个图带你快速了解删除的过程
源码级深入理解LinkedList,点开即食
由于prev和next是浅赋值,引用指向的是同一个对象,所以修改了prev和next的指针就相当于修改了上图的node和last的指针,这样就删除了X节点
源码级深入理解LinkedList,点开即食

其他方法

其他方法的逻辑就十分简单了,就是通过调用我们上述的各种方法来实现,方法十分多且简单,在此就不再介绍了

关于clone()实现链表的深拷贝

首先我们看到LinkedList实现了clone()接口,并且重写了clone()方法,所以这里我们对于LinkedList调用clone()方法是实现深复制的过程,即不单单拷贝引用,如果对深拷贝和浅拷贝还有疑问:请戳

 public static void main(String[] args) throws CloneNotSupportedException {          LinkedList<Person> objects = new LinkedList<>();         Person jack = new Person("jack");         objects.add(jack);         objects.add(new Person("rose"));         LinkedList clone = (LinkedList) objects.clone(); 		//这里我们删除克隆链表的元素,看看原来的链表是否会改变         objects.remove(jack);         System.out.println(objects);         System.out.println(clone);         //答案是不会,所以这里的clone()是深拷贝         //[Person{name='jack'}, Person{name='rose'}] 		//[Person{name='rose'}]     } 

关于fast-fail机制和线程不安全

上文留下的modCount这个变量的坑,有什么用呢?和ArrayList几乎一摸一样,这里可以看看博主的另一篇文章,点击开头的目录跳转到指定的位置即可:fast-fail机制和线程不安全

写在最后

博主看过许多网上的博客,发现对于许多操作都模糊不堪,例如插入集合,删除指定位置节点,我试图清晰的讲述给你,如果有疑问或者错误,欢迎留演讨论,如果你觉得不错,点个小小的赞,就是对作者最大的鼓励

作者的java集合专栏打算深入ArrayList,LinkedList,Set,Map等等集合,关注一波,相信不会让你失望哒~
源码级深入理解LinkedList,点开即食

版权声明:玥玥 发表于 2021-04-02 5:39:26。
转载请注明:源码级深入理解LinkedList,点开即食 | 女黑客导航