六张图详解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 的后置指针指向新节点

如果原尾部节点为空，直接创建一个节点，这个节点是last和first节点。

如果原尾部节点不为空，创建新节点，新节点的前置指向原来的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指向pred，next指向succ。
• succ的pre 指向新节点。
• 如果pred 为null，表示首节点是succ,将节点赋值给first节点。
• 如果pred 不为null，pred的next指向新节点。

比如一个长度为5的链表，在下标为1的位置添加数据：

获取数据

获取数据主要有get、getFirst、getLast。

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巧妙的判断index和size一半长度的关系,小于就从前往后遍历，大于就从后往前遍历。无需遍历整个链表。
  • 找到节点之后，记录节点的prev节点，在prev和节点之间创建新的节点。
• remove(Object o),遍历找到元素，再调用unlink方法。记录元素的前置节点prev和后置节点next,前置节点next指向后置节点，后置节点的next指向前置节点，删除其它的前置节点和后置节点的指针。
• remove（int index）,先通过node方法找到下标的数据，找到元素之后，再调用unlink方法。

如果感觉文章不错的话，点个赞吧！

六张图详解LinkedList 源码解析的更多相关文章

1. SpringBoot之DispatcherServlet详解及源码解析

   在使用SpringBoot之后,我们表面上已经无法直接看到DispatcherServlet的使用了.本篇文章,带大家从最初DispatcherServlet的使用开始到SpringBoot源码中Di ...

2. AFNetworking 3.0 使用详解 和 源码解析实现原理

   AFN原理&& AFN如何使用RunLoop来实现的: 让你介绍一下AFN源码的理解,首先要说说封装里面主要做了那些重要的事情,有那些重要的类(XY题) 一.AFN的实现步骤: NSS ...

3. CharacterEncodingFilter详解及源码解析

   字符编码过滤器  (Spring框架对字符编码的处理) 基于函数回调,对所有请求起作用,只在容器初始化时调用一次,依赖于servlet容器. web.xml配置文件 <filter> &l ...

4. cas客户端流程详解（源码解析）--单点登录

   博主之前一直使用了cas客户端进行用户的单点登录操作,决定进行源码分析来看cas的整个流程,以便以后出现了问题还不知道是什么原因导致的 cas主要的形式就是通过过滤器的形式来实现的,来,贴上示例配置: ...

5. Ros学习——移动机器人Ros导航详解及源码解析

   1 执行过程 1.运行仿真机器人fake_turtlebot.launch:加载机器人模型——启动机器人仿真器——发布机器人状态 2.运行amcl节点fake_amcl.launch:加载地图节点ma ...

6. 基于双向BiLstm神经网络的中文分词详解及源码

   基于双向BiLstm神经网络的中文分词详解及源码 基于双向BiLstm神经网络的中文分词详解及源码 1 标注序列 2 训练网络 3 Viterbi算法求解最优路径 4 keras代码讲解 最后 源代码 ...

7. 详解 QT 源码之 Qt 事件机制原理

   QT 源码之 Qt 事件机制原理是本文要介绍的内容,在用Qt写Gui程序的时候,在main函数里面最后依据都是app.exec();很多书上对这句的解释是,使 Qt 程序进入消息循环.下面我们就到ex ...

8. Android应用AsyncTask处理机制详解及源码分析

   1 背景 Android异步处理机制一直都是Android的一个核心,也是应用工程师面试的一个知识点.前面我们分析了Handler异步机制原理(不了解的可以阅读我的<Android异步消息处理机 ...

9. Java SPI机制实战详解及源码分析

   背景介绍 提起SPI机制,可能很多人不太熟悉,它是由JDK直接提供的,全称为:Service Provider Interface.而在平时的使用过程中也很少遇到,但如果你阅读一些框架的源码时,会发现 ...

10. Spring Boot启动命令参数详解及源码分析

    使用过Spring Boot,我们都知道通过java -jar可以快速启动Spring Boot项目.同时,也可以通过在执行jar -jar时传递参数来进行配置.本文带大家系统的了解一下Spring ...

随机推荐

1. office 2013 产品秘钥

   9RN4T-JPBQV-XQMC9-PM9FP-PGWP9 TKX7J-VDN26-Y2WKQ-7MG8R-X2CC9 N9M8X-QDKGK-W27Q6-2GQYT-TJC9K 4VNXV-F7PB ...

2. C# 线程（六）：定时器

   From : http://kb.cnblogs.com/page/42532/ Timer类:设置一个定时器,定时执行用户指定的函数. 定时器启动后,系统将自动建立一个新的线程,执行用户指定的函数. ...

3. win10 uwp 俄罗斯方块

   俄罗斯方块是一个很经典的游戏,做一个UWP俄罗斯方块没有什么用,我想说的是移植,把经典游戏移植到UWP. 我的所有博客都是抄别人的,这个才是我自己写的.后台很多代码还是抄别人的,我想说的是我们之前有很 ...

4. mybati源码之ReuseExecutor

   /** * @author Clinton Begin */ public class ReuseExecutor extends BaseExecutor { private final Map&l ...

5. SQL中IF和CASE语句

   IF表达式 IF(A,B,C): 如果 A 是TRUE (A <> 0 and A<> NULL),则 IF()的返回值为B; 否则返回值则为 C.IF() 的返回值为数字值或 ...

6. 牛客训练赛25-A-最长区间

   https://www.nowcoder.com/acm/contest/158#question 这题问最长的严格连续递增序列的最长长度是多少? 最开始感觉这道题不可做,因为有1e5个点,还有1e5 ...

7. dir命令详解

   dir命令:DIR [drive:][path][filename] [/A[[:]attributes]] [/B] [/C] [/D] [/L] [/N]  [/O[[:]sortorder]] ...

8. mysql图形化界面MySQL_Workbench

   1,下载最新版本的MySQL Workbench,下载地址: http://www.mysql.com/downloads/workbench/   2,安装Workbench的依赖组件两个 http ...

9. JVM profiler tools

   http://docs.oracle.com/javase/7/docs/technotes/samples/hprof.html https://codeascraft.com/2015/05/12 ...

10. Python之re模块正则表达式

    re模块用于对python的正则表达式的操作 字符: .匹配除换行符以外的任意字符 \w匹配字母或数字或下划线或汉字 \s匹配任意空白符 \b匹配单词的开始或结束 ^匹配字符串的开始 $匹配字符串的结 ...