I'll try anything once

人生苦短,何妨一试

LinkedList源码解读

概述

LinkedList底层数据结构是链表,是实现了List接口和Deque接口的双端链表,其能够高效的实现插入删除操作, 而且也拥有了队列所拥有的特性。和ArrayList相比,因为其没有实现RandomAccess,是以下标进行访问元素, 所以对于元素访问不及ArrayList,随机访问元素慢。同时需要注意的是, LinkedList不是线程安全的,需要使用的别的方式实现线程安全。

依赖

《LinkedList源码解读》

阅读套路

按照正常的逻辑, 首先了解其构造方法, 之后了解常用的API(CRUD)操作即可。

  • addAll();
  • add();
  • remove();
  • get();

从节点数据结构开始

《LinkedList源码解读》

其实一个很明显的双向链表的数据结构。

构造函数

  1. 空的构造方法

  2. 含有参数的构造方法(用已有的集合创建链表)

    将已有的linkedlist添加到一个新的linkedlist中(尾插法,下文有提及)。其类似于copy()

可以看到, 初始化之后,使用无参的构造方法,返回的为一个空的链表,若是为含有参数的构造方法,会调用addAll()方法将一个链表的所有元素都拷贝到一个新的元素。

这个部分涉及了大量的双向链表的插入删除,可先理解了双向链表的操作(3、 4步骤的操作顺序在于采用的是哪个节点作为基础节点:也就是选择待插入位置的节点还是该节点的前驱节点,或者是两个都使用,若是两个都是用则3、 4无顺序先后)。

《LinkedList源码解读》

addAll()

addAll()主要为就是依次的遍历已有集合的所有元素,然后依次进行插入(尾插法,保证插入的顺序不会和最后的顺序不变)

判断越界方法

直接在if后跑出异常,可直接跑出异常信息,并且可以根据自己定义信息跑出异常。

add(E e)

add(int index, E element)

小结

  • 链表批量增加,是靠for循环遍历原数组,依次执行插入节点操作。对比ArrayList是通过System.arraycopy完成批量增加的
  • 通过下标获取某个node 的时候,(add select),会根据index处于前半段还是后半段 进行一个折半,以提升查询效率

删: remove相关的方法

remove()

remove(int index)

下图为双向链表的删除操作,仅做参考,具体的写法依据个人采用基础节点。

《LinkedList源码解读》

判断越界方法

其实是和增里面的判断是一样的

remove(Object o)

小结

删也一定会修改modCount。 按下标删,也是先根据index找到Node,然后去链表上unlink掉这个Node。 按元素删,会先去遍历链表寻找是否有该Node,考虑到允许null值,所以会遍历两遍,然后再去unlink它。

改:set()相关的方法

set(int index, E element)

小结

set()也是根据索引去寻找对应Node(),之后替换,但是不会修改modCount

查: get相关方法

get(int index)

判断越界方法

其实是和增里面的判断是一样的

小结

按照索引查找对应的节点,之前的增、删、改都用到了

总结

LinkedList是双向链表

  • 链表的批量添加(addAll())是转化为数组之后使用for-each进行添加,默认在链表尾部添加, 会修改modCount
  • 根据index获取节点时,会根据index处于后半段还是前半段进行查找,提升查找速率
  • 所有的CRUD中都有涉及根据index去寻找节点

LinkedList中还有很多的API没有写,只是简单的写了基础的CRUD

reference

点赞

发表评论

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

15 − 5 =