啃透JDK源码-LinkedList

举报
JavaEdge 发表于 2021/06/03 23:49:51 2021/06/03
【摘要】 0 前言 与 ArrayList 一样实现了 List 接口，只是 LinkedList 底层结构为链表.在插入和删除时更优于 ArrayList，而随机访问则比 ArrayList 稍逊. 其允许元素包括 null.除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将...

0 前言

与 ArrayList 一样实现了 List 接口，只是 LinkedList 底层结构为链表.在插入和删除时更优于 ArrayList，而随机访问则比 ArrayList 稍逊.

其允许元素包括 null.除了实现 List 接口外，LinkedList 类还为在列表的开头及结尾 get、remove 和 insert 元素提供了统一的命名方法。这些操作允许将链接列表用作堆栈、队列或双端队列。

该类还实现了 Deque 接口，为 add、poll 提供先进先出队列操作，以及其他堆栈和双端队列操作。
所有操作都是按照双重链接列表的需要执行的。在列表中编索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）.

1 继承体系


LinkedList 继承自 AbstractSequentialList，又实现了 List、Deque、Cloneable、Serializable等接口.
AbstractSequentialList相较于AbstractList(ArrayList的父类),只支持次序访问，而不支持随机访问，因为它的get(int index) ,set(int index, E element), add(int index, E element), remove(int index) 都是基于迭代器实现的。

Deque - 线性 collection，支持在两端插入和移除元素，定义了双端队列的操作.

2 属性

双向链表定义方式.

  • 头节点的指针.不变性约束条件：(first == null && last == null) || (first.prev == null && first.item != null)

  • 尾节点的指针.不变性约束条件:(first == null && last == null) || (last.next == null && last.item != null)

  • 表示 LinkedList 的大小

  • 节点Node

可以看出，这是一个典型的双向链表的结构

3 构造方法

3.1 无参

  • 构造一个空list

3.2 有参

  • 构造一个包含指定 collection 中的元素的list，这些元素按其 collection 的迭代器返回的顺序排列。

    下面开始看各大核心 API 细节.

4 add

4.1 末尾添加

add(E e)

  • 将指定元素添加到此 list 的末尾

    linkLast(E e)


    add(E e)等价于addLast(E e),因为 LinkedList 实现了 Deque 接口.

addLast(E e)


核心都是linkLast方法.

  • 图解末尾添加

4.2 首位添加

addFirst(E e)

linkFirst(E e)

  • 图解首位添加

主要流程：

  • 将原 first 节点保存到 f
  • 将插入元素封装成 newNode，并且该新节点的next指向原来的头节点，即f
  • 若原来的头节点 f 为null，那么新插入头节点也是 last 尾节点，否则设置 f 的前置节点为NewNode，即 NewNode 现在是first 头节点.
  • size加一，修改计数器加一

4.3 指定位置插入

add(int index, E element)

首先调用checkPositionIndex检查index值是否在范围内

checkPositionIndex

isPositionIndex

  • 判断参数是否为迭代器或者添加操作的有效位置的索引.

如果index在最后的话，就调用在尾部插入的函数，否则调用LinkBefore

LinkBefore

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

void linkBefore(E e, Node<E> succ) {  //在succ节点前插入newNode

        // assert succ != null;

        // 将 succ 的前驱结点记为 pred

        final Node<E> pred = succ.prev;  

        // 以 pred 为前驱结点，以 succ 为后继节点新建 newNode

        final Node<E> newNode = new Node<>(pred, e, succ); 

        // 将 newNode 设为 succ 的前驱节点

        succ.prev = newNode;  

        if (pred == null)

            // 若原 succ 的前驱节点为null，则新插入的就是 first 头节点

            first = newNode;  

        else

            // 否则，要把newNode设为原来pred节点的后继节点

            pred.next = newNode; 

        size++;

        modCount++;

}
  • 图解指定位置插入元素

5 remove

  • 因为 Deque 接口，所以本类也实现了如下方法支持双端操作:

5.1 removeFirst()

unlinkFirst(Node f)

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

private E unlinkFirst(Node<E> f) {

        // assert f == first && f != null;

        // 将 f.item 暂存 element

        final E element = f.item;  

        final Node<E> next = f.next;

        f.item = null;   

        f.next = null; // 辅助 GC

        // next成为实际的first节点

        first = next;   

        if (next == null)  // next为空的话，因为next是第一个节点，所以链表都是空的，last也为空

            last = null;

        else

            next.prev = null;  // next不为空，也要将它的前驱节点记为null，因为next是第一个节点

        size--;  // 节点数减一

        modCount++;  // 修改计数器加1

        return element;

    }

5.2 removeLast

unlinkLast

删除非空的尾节点

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

private E unlinkLast(Node<E> l) {

        // assert l == last && l != null;

        final E element = l.item;

        // 将尾节点的前驱节点记为 prev，它将成为last节点

        final Node<E> prev = l.prev;

        l.item = null;

        l.prev = null; // 辅助 GC

        // 设置刚才记录的前驱节点为last

        last = prev;   

        if (prev == null)

            // prev 为 null，说明要删除的l前面原来没前驱节点，那么删了l，整个链表为空

            first = null;

        else

            // prev成为最后一个节点，没有后继节点

            prev.next = null;  

        size--;

        modCount++;

        return element;

    }

remove(int index)

在指定index删除

检验index是否合法.如果删除成功，返回删除的节点。 具体实现在unlink

unlink

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

E unlink(Node<E> x) {

        // assert x != null;

        final E element = x.item;

        final Node<E> next = x.next;

        final Node<E> prev = x.prev;

 

        if (prev == null) {

            first = next;

        } else {

            prev.next = next;

            x.prev = null;

        }

 

        if (next == null) {

            last = prev;

        } else {

            next.prev = prev;

            x.next = null;

        }

 

        x.item = null;

        size--;

        modCount++;

        return element;

    }
  • 图解 unlink 过程
  • 流程如下:
    • 将删除的节点保存在element，同时把要删除节点的前驱节点标记为prev,后继节点标记为next
    • 若prev为null，则 next 节点直接为 first 节点，反之把prev的next指向next节点，如图上面弯曲的红色箭头
    • 若 next 为空，那么prev节点直接为last节点，反之把next的prev指向prev节点，如图下面弯曲的蓝色箭头
    • 把要删除的节点置空，返回第一步保存的element

remove(Object o)

删除首次出现的指定元素（如果存在）
5088755_1583825929230_4EF4CF7A71C30E1ED4A87BD21E9C0BA0uploading.4e448015.gif转存失败重新上传取消

  • o 为 null，遍历链表，找到第一个为 null 的节点删除
  • o 非 null，遍历链表，找到第一个值相等的节点,调用unlink(x)删除

6 get

迭代，比对，然后返回值而已.

get(int index)

  • 返回此列表中指定位置处的元素。

    node(int index)

getFirst()

返回此列表的第一个元素

getLast()

返回此列表的最后一个元素。

indexOf(Object o)

返回此列表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。

lastIndexOf(Object o)

返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1

 

https://stackoverflow.com/questions/23539087/consistency-check-for-a-linked-list

 

文章来源: javaedge.blog.csdn.net，作者：JavaEdge.，版权归原作者所有，如需转载，请联系作者。

原文链接：javaedge.blog.csdn.net/article/details/105315623

【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱： cloudbbs@huaweicloud.com
JDK 数据结构
  • 点赞
  • 收藏
  • 关注作者

评论（0）

0/1000
抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认 取消

加入云驻计划，成为创作者

  • 华为云周边好礼
  • 免费体验产品
  • 特殊身份标识
  • 线下官方门票
  • 内部专家零距离
  • 与10000+优质创作者共同成长
立即加入