资讯专栏INFORMATION COLUMN

LinkedList源码分析:JDK源码分析系列

blair / 3070人阅读

摘要:介绍是线程不安全的,允许元素为的双向链表。构造方法共有两个构造方法,一个是创建一个空的构造函数,一个是将已有的添加到中。是将元素插入到的头部。下一篇文章继续分析上次分析了的结构和添加方法这次开始分析下面的。注意源码版本为直接进入正题。

如果本文中有不正确的地方请指出
由于没有留言可以在公众号添加我的好友共同讨论。

1.介绍

LinkedList 是线程不安全的,允许元素为null的双向链表。

2.继承结构

我们来看一下LinkedList的继承结构图:

代码实现:

public class LinkedList
    extends AbstractSequentialList
    implements List, Deque, Cloneable, java.io.Serializable

Cloneable实现克隆

Serializable序列化

List 定义了一些集合类的方法

Deque双向队列接口(就是两端都可以进行增加删除操作)

注意一点LinkedList并没有实现RandomAccess所以随机访问是非常慢的。

3.属性

元素个数

transient int size = 0;

指向第一个节点的指针(注释直接就写着)

  /**
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node first;

指向最后一个节点的指针

    /**
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node last;

transient关键字的作用是保持变量不被序列化具体的百度。


不过我们注意到LinkedList是有Node类,这里的Node是一个内部类:

item存储的元素

next指向后置节点

prev指向前置节点

内部类同时包含了一个构造函数

其实LinkedList 集合就是由许多个 Node 对象y一个连着一个组成手构成,可以看下方的图

可以看上面的四个元素,分别就是四个Node对象,可以看到node1所指向的prev上一个节点是空也就是没有上节点,node4所指向的next节点为空也就是没有下一个节点。

4.构造方法


LinkedList共有两个构造方法,一个是创建一个空的构造函数,一个是将已有的Collection添加到LinkedList中。

因为LinkedList不同于ArrayList所以初始化不需要指定大小取分配内存空间。

5.添加元素

LinkedList有几种添加方法我们先从add()开始。

5.1 add方法

checkPositionIndex(index);

可以看到在调用Add方法首先校验一下索引是否合法,如果不合法就会抛出异常。

if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));

然后如果索引值等于size的值则直接调用linkLast插入到尾部节点。

否则就linkBefore方法。
linkLast方法:

void linkLast(E e) {
        //将l设为尾节点
        final Node l = last;
        //构造一个新节点,节点上一个节点引用指向尾节点l
        final Node newNode = new Node<>(l, e, null);
        //将尾节点设为创建的新节点
        last = newNode;
        //如果尾节点为空,表示原先链表为空
        if (l == null)
        //将头节点设为新创建的节点(尾节点也是新创建的节点)
            first = newNode;
        else
        //将原来尾节点下一个节点的引用指向新节点
            l.next = newNode;
        size++;//节点数加1
        modCount++;
    }

注意一下这里出现了modCount方法,和ArrayList中一样,iterator和listIterator方法返回的迭代器和列表迭代器实现使用。
linkBefore:

void linkBefore(E e, Node succ) {
        //将pred设为插入节点的上一个节点
        final Node pred = succ.prev;
        //将新节点的上引用设为pred,下引用设为succ
        final Node newNode = new Node<>(pred, e, succ);
        //succ的上一个节点的引用设为新节点
        succ.prev = newNode;
        //如果插入节点的上一个节点引用为空
        if (pred == null)
        //新节点就是头节点
            first = newNode;
        else
        //插入节点的下一个节点引用设为新节点
            pred.next = newNode;
        size++;
        //同上
        modCount++;
    }
5.2 addAll()

在LinkedList中有两个addAll方法一个是 addAll(Collection c)一个是addAll(int index, Collection c),其实

addAll(Collection c)=addAll(int index, Collection c)

可以看下面的截图:

源码如下:


现在开始分析源码:
首先我们可以看到先调用了checkPositionIndex(index);方法来检查索引是否合法。
然后将传进来的Collection转成Object数组

 Object[] a = c.toArray();

如果集合为空就直接返回false

if (numNew == 0)
            return false;

如果插入的位置等于链表的长度就把新增加的元素放在尾部。

Node pred, succ;
        if (index == size) {
            succ = null;
            pred = last;
        } else {
            succ = node(index);
            pred = succ.prev;
        }

最后在循环要插入的元素。这里我们可以看到上面也有modCount。

5.3 addFirst()

addFirst是将元素插入到LinkedList的头部。
如果现在的机构是下图的:

addFirst执行的操作就是:

红色是使用addFirst插入后的位置。一下是源码


调用了linkFirst方法。

上面的操作时:

首先执行final Node f = first;将头节点赋值给 f

final Node newNode = new Node<>(null, e, f);将指定元素构造成一个新节点,此节点的指向下一个节点的引用为头节点

        //将新节点设为头节点,那么原先的头节点 f 变为第二个节点
        first = newNode;
        //如果第二个节点为空,也就是原先链表是空
         if (f == null)
         //将这个新节点也设为尾节点(前面已经设为头节点了)
          last = newNode;
       else
            f.prev = newNode;//将原先的头节点的上一个节点指向新节点
       size++;//节点数加1
       modCount++;//和ArrayList中一样记录修改次数
5.4 addLast方法

addLast是将元素插入到尾部如图(黄色元素):


黄色node是新增加。注意add也是把元素添加到尾部。我们来看一下源码:


这里看到addLast和add是调用的同一方法,这里就不在讲解。可以看上方的代码。

由于文章比较长分为两次更新。下一篇文章继续分析


上次分析了LinkedList的结构和添加方法这次开始分析下面的。

注意源码版本为JDK1.8

直接进入正题。

1.删除 1.2remove()

在LinkedList中remove()和removeFirst()是相同的

在LinkedList中的删除其实就是通过修改上一个节点和指向下一个节点的引用完成的,可以看下面的图片:

我们可以看到把node6的prev指向清空然后把node3的next设置成空就完成了删除的操作。
看一下JDK的源码实现:


调用removeFirst,在调用removeFirst中先获取头部节点,如果头节点为空就抛异常。

调用unlinkFirst

private E unlinkFirst(Node f) {
         final E element = f.item;
         //next 为头结点的下一个节点
         final Node next = f.next;
         f.item = null;
         // 将节点的元素以及引用都设为 null,便于垃圾回收
         f.next = null; 
         //修改头结点为第二个节点
         first = next; 
         //如果第二个节点为空(当前链表只存在第一个元素)
         if (next == null)
            //那么尾节点也置为 null
             last = null;
         else
         //如果第二个节点不为空,那么将第二个节点的上一个引用置为 null
             next.prev = null;
         size--;
         modCount++;
         return element;
     } 
1.3 removeLast()

我们看一下removeLast,从列表中删除最后一个元素

首先看到先获取了last最后一个元素,如果为空然后就抛异常
然后调用了unlinkLast


看到unlinkLast方法中有一个 help gc ,它的主要作用就是帮助GC来做垃圾回收。

private E unlinkLast(Node l) {
       // assert l == last && l != null;
         final E element = l.item;
         final Node prev = l.prev;
         l.item = null;
          //帮助GC垃圾回收
         l.prev = null;
         //尾节点为倒数第二个节点
         last = prev;
         //如果倒数第二个节点为null
         if (prev == null)
            //那么将节点也置为 null
             first = null;
         else
             prev.next = null;
        //如果倒数第二个节点不为空,那么将倒数第二个节点的下一个引用置为 null
         size--;
         modCount++;
         return element;
     }

同样执行了modCount++

1.3 remove(int index)

根据索引来删除元素

  //删除此列表中指定位置的元素
      public E remove(int index) {
          //判断索引 index >= 0 && index <= size中时抛出IndexOutOfBoundsException异常
          checkElementIndex(index);
          return unlink(node(index));
      }
      E unlink(Node x) {
          // assert x != null;
          final E element = x.item;
         final Node next = x.next;
         final Node prev = x.prev;
 
         if (prev == null) {//如果删除节点位置的上一个节点引用为null(表示删除第一个元素)
             first = next;//将头结点置为第一个元素的下一个节点
         } else {//如果删除节点位置的上一个节点引用不为null
             prev.next = next;//将删除节点的上一个节点的下一个节点引用指向删除节点的下一个节点(去掉删除节点)
             x.prev = null;//删除节点的上一个节点引用置为null
         }
 
         if (next == null) {//如果删除节点的下一个节点引用为null(表示删除最后一个节点)
             last = prev;//将尾节点置为删除节点的上一个节点
         } else {//不是删除尾节点
             next.prev = prev;//将删除节点的下一个节点的上一个节点的引用指向删除节点的上一个节点
             x.next = null;//将删除节点的下一个节点引用置为null
         }
        //删除节点内容置为null,便于垃圾回收
         x.item = null;
         size--;
         modCount++;
         return element;
     }
3.set(int index, E element)

简单粗暴直接贴代码

public E set(int index, E element) {
        //检查索引是否合法否则IndexOutOfBoundsException异常
        checkElementIndex(index);
        //获取指定索引的元素
        Node x = node(index);
        E oldVal = x.item;
        //将指定索引的元素替换成新的元素
        x.item = element;
        /返回指定索引位置原来的元素
        return oldVal;/
    }
4.查找元素

很简单

4.1 getFirst()

返回第一个元素

  public E getFirst() {
            获取头
         final Node f = first;
            判断是否为空
         if (f == null)
             throw new NoSuchElementException();
        元素返回
         return f.item;
     }
4.2 getLast()

返回最后一个元素

public E getLast() {
         final Node l = last;
         if (l == null)
             throw new NoSuchElementException();
         return l.item;
     }
4.3 get

返回指定索引元素

public E get(int index) {
         checkElementIndex(index);
         return node(index).item;
     }
暂时就这么多

原创不易,如果你喜欢本文或者对你有帮助就请转发

文章版权归作者所有,未经允许请勿转载,若此文章存在违规行为,您可以联系管理员删除。

转载请注明本文地址:https://www.ucloud.cn/yun/75325.html

相关文章

  • java源码

    摘要:集合源码解析回归基础,集合源码解析系列,持续更新和源码分析与是两个常用的操作字符串的类。这里我们从源码看下不同状态都是怎么处理的。 Java 集合深入理解:ArrayList 回归基础,Java 集合深入理解系列,持续更新~ JVM 源码分析之 System.currentTimeMillis 及 nanoTime 原理详解 JVM 源码分析之 System.currentTimeMi...

    Freeman 评论0 收藏0
  • JDK源码(容器篇)

    摘要:三系列用于保存键值对,无论是,还是已弃用的或者线程安全的等,都是基于红黑树。是完全基于红黑树的,并在此基础上实现了接口。可以看到,只有红黑树,且红黑树是通过内部类来实现的。 JDK容器 前言 阅读JDK源码有段时间了,准备以博客的形式记录下来,也方便复习时查阅,本文参考JDK1.8源码。 一、Collection Collection是所有容器的基类,定义了一些基础方法。List、Se...

    Soarkey 评论0 收藏0
  • HashMap源码分析(一):JDK源码分析系列

    摘要:当一个值中要存储到的时候会根据的值来计算出他的,通过哈希来确认到数组的位置,如果发生哈希碰撞就以链表的形式存储在源码分析中解释过,但是这样如果链表过长来的话,会把这个链表转换成红黑树来存储。 正文开始 注:JDK版本为1.8 HashMap1.8和1.8之前的源码差别很大 目录 简介 数据结构 类结构 属性 构造方法 增加 删除 修改 总结 1.HashMap简介 H...

    wdzgege 评论0 收藏0
  • LinkedList源码解析

    摘要:我们来看相关源码我们看到封装的和操作其实就是对头结点的操作。迭代器通过指针,能指向下一个节点,无需做额外的遍历,速度非常快。不同的遍历性能差距极大,推荐使用迭代器进行遍历。LinkedList类介绍 上一篇文章我们介绍了JDK中ArrayList的实现,ArrayList底层结构是一个Object[]数组,通过拷贝,复制等一系列封装的操作,将数组封装为一个几乎是无限的容器。今天我们来介绍JD...

    番茄西红柿 评论0 收藏0

发表评论

0条评论

blair

|高级讲师

TA的文章

阅读更多
最新活动
阅读需要支付1元查看
<