基于 JDK8

一、介绍

LinkedList.java Doc 部分描述如下
image.png
主要几点：

  • LinkedList 是一个双线链表（Doubly-linked List）
  • LinkedList 允许插入任何值，包括 null
  • LinkedList 是非线程安全的

    二、链表数据结构

LinkedList 采用双线链表实现，链表逻辑图如下
LinkedList 关于链表节点结构定义如下
image.png

三、LinkedList 代码简单剖析

3.1、链表属性信息

  • 【头节点引用】transient Node first
  • 【尾节点引用】transient Node last

  • 【链表节点数】transient int size = 0

    3.2、插入元素

    image.png

    3.2.1、尾节点插入

    image.png
    相关代码如下 （linkLast(E)）
    image.png
    如上述代码所示，进行头尾指向的设置

    3.2.2、头节点插入

    image.png
    相关代码如下（ linkFirst(E) )
    image.png
    如上述代码所示，进行头尾指向的设置

    3.2.3、中间节点插入

    image.png
    相关代码如下
    image.png
    插入步骤：

  • 1、找到索引所在位置节点实例

  • 2、重新拼接指针指向

    3.3、查询

    image.png

    3.3.1、获取头节点/尾节点

    头尾节点的获取直接从属性中获取
    image.png

    3.3.2、获取中间节点

    image.png
    一次二分，然后循环遍历

    3.4、移除

    image.png
    除了头尾移除外，其他的移除都需要循环遍历，匹配之后然后移除
    image.png