jdk1.8-LinkedList源码分析

一:类的继承关系

我们看下类的继承关系

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

继承抽象的AbstractSequentiaList类,供了一个基本的List接口实现,为实现序列访问的数据储存结构的提供了所需要的最小化的接口实现。.

同时LinkedList也实现了Cloneable、java.io.Serializable、Deque(双端队列)等接口

二:类的成员属性

1.成员属性比较简单

/** * 当前链表长度 */transient int size = 0;

/** * 头结点 */transient Node<E> first;

/** * 尾结点 */transient Node<E> last;

2.这里我们要看Node这个实体类,因为java是没有指针这一说的,所以用Node自己来模拟实现

/** * 静态内部类,它的创建是不需要依赖于外围类,可以被实例化 * @param <E> */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;    }}

分析:我们知道java的LinkedList是个双向链表,java没有指针,那么是怎么找到前一个元素结点和后一个元素结点呢?从上面的代码很容易就可以看出,其实就是在Node类的成员属性下直接记录了下一个结点Node<E> next 和 上一个结点 Node<E> prev,从而达到模拟指针的效果。

三:构造方法

1.不带参的构造方法,啥也没做

/** * Constructs an empty list. */public LinkedList() {}

2.带参构造方法

/** * 带参构造方法,传入集合 */public LinkedList(Collection<? extends E> c) {    //构造方法    this();    //添加方法    addAll(c);}

分析:这里将集合直接传入addAll()方法

/** * 参数为前链表长度和集合  */public boolean addAll(Collection<? extends E> c) {    return addAll(size, c);}

分析:这里传入了当前链表长度和集合

/** * 从索引为index结点的尾部,开始插入所有集合的元素 */public boolean addAll(int index, Collection<? extends E> c) {    //检验长度是否在链表长度区间    checkPositionIndex(index);    //将集合转为数组    Object[] a = c.toArray();    //数组长度    int numNew = a.length;    //如果等于0直接返回false    if (numNew == 0)        return false;

//两个记录结点    Node<E> pred, succ;    //如果当前传入的长度等于链表当前最大长度    if (index == size) {        //succ结点等于null        succ = null;        //pred结点等于尾结点        pred = last;    } else {        //返回index索引的结点        succ = node(index);        //pred记录等于index索引结点的上一个结点        pred = succ.prev;    }

//遍历数组    for (Object o : a) {        //将值强转为E类型        @SuppressWarnings("unchecked") E e = (E) o;        //每次循环new一个newNode结点,newNode结点的值等于e,newNode上一结点prev等于pred记录结点,newNode下一节点等于null        //其实这个newNode就是pred的下一个结点,因为newNode的上一节点等于pred        Node<E> newNode = new Node<>(pred, e, null);        //如果当前记录结点pred等于null        if (pred == null)            //则头结点等于newNode            first = newNode;        else            //当前记录pred的下一节点等于newNode,相当于把succ记录结点给覆盖了            pred.next = newNode;        //当前记录结点更新为newNode,也就是相当于链表往后移动一位        pred = newNode;    }

if (succ == null) {        //尾结点等于当前记录结点pred        last = pred;    } else {        //重新把pred结点下一个结点赋值为succ记录结点        pred.next = succ;        //并且让succ记录结点的上一个结点等于最新的pred记录结点        succ.prev = pred;    }

//链表的长度加上集合的长度    size += numNew;    //修改次数加1    modCount++;    return true;}

分析:首先我们要知道这个addAll()方法是从索引为index结点开始向后插入元素的,链表的索引是从0开始的。那么到底是怎么插入元素的呢?我们来逐步分析下:

//检验长度是否在链表长度区间checkPositionIndex(index);//将集合转为数组Object[] a = c.toArray();//数组长度int numNew = a.length;//如果等于0直接返回falseif (numNew == 0)    return false;

分析:这里这先校验下传入的index长度是否在链表区间(0到size),然后将集合转为数组,如果数组长度等于0的话,直接返回了。

//两个记录结点Node<E> pred, succ;//如果当前传入的索引等于链表当前最大长度if (index == size) {    //succ结点等于null    succ = null;    //pred结点等于尾结点    pred = last;} else {    //返回index索引的结点    succ = node(index);    //pred记录等于index索引结点的上一个结点    pred = succ.prev;}

分析:两个记录结点Node<E> pred,succ非常重要,它是为了方便我们我们操作链表的。

如果,当前传进来的索引index等于链表长度size,那么succ结点等于null,为什么呢?因为index=size下标已经超出链表了,所以值肯定为null了。也因此,我们可以理解succ其实就是索引为index的结点,也就是我们要开始插入元素的结点,然后pred结点等于尾结点。从这可以看出,我们前面构造方法传入当前链表长度和集合是从链表的尾部开始添加的(也就是尾结点的下一个结点),符合逻辑。

如果当前传入的索引不大于链表长度size,succ等于index索引的结点,pred还是等于index索引的上一个结点。我们看下这个node(index)方法,看完之后我们明白它确实是返回index索引的结点,然后遍历的时候有个小技巧,如果索引小于链表长度的一半从头结点开始往后遍历,否则从尾结点往前开始遍历,节省时间。

/** * 传入index长度,链表返回索引为index的node结点(注意这里的链表索引也是从0开始) * 如果传入的长度小于链表长度一遍,那么从链表头结点开始遍历 * 如果传入的长度大于或等于链表长度的一半,那么从链表的尾结点开始遍历 */Node<E> node(int index) {    //如果传入的长度小于链表长度的一半(size >> 1链表长度除以2,这种写法运算速度稍快,可以根据实际需求应用)    if (index < (size >> 1)) {        //当前记录结点等于头结点        Node<E> x = first;        //从下表为0开始遍历到索引为index-1        //这里注意下从0到index-1需要迭代7次        for (int i = 0; i < index; i++)            //当前记录结点等于下一节点            x = x.next;        //所以返回的是索引为indx的点!!        return x;    } else {        //如果传入的长度大于或者等于当前链表长度的一半        //当前记录结点等于尾结点        Node<E> x = last;        //从链表末尾开始往前遍历        for (int i = size - 1; i > index; i--)            //当前记录结点等于上一节点            x = x.prev;        //返回索引为index的点!        return x;    }}

到此我们搞明白了,

//两个记录结点Node<E> pred, succ;

这两个结点的含义,succ代表当前传入索引index的结点,pred代表索引index结点的上一个结点,这两个结点是为了我们方便操作链表。

接下来,我们继续往下分析:

//遍历数组for (Object o : a) {    //将值强转为E类型    @SuppressWarnings("unchecked") E e = (E) o;    //每次循环new一个newNode结点,newNode结点的值等于e,newNode上一结点prev等于pred记录结点,newNode下一节点等于null    //其实这个newNode就是pred的下一个结点,因为newNode的上一节点等于pred    Node<E> newNode = new Node<>(pred, e, null);    //如果当前记录结点pred等于null    if (pred == null)        //则头结点等于newNode        first = newNode;    else        //当前记录pred的下一节点等于newNode,相当于把succ记录结点给覆盖了        pred.next = newNode;    //当前记录结点更新为newNode,也就是相当于链表往后移动一位    pred = newNode;}

分析:前面将集合转为了数组,这里遍历数组,每次循环将遍历的值转为类型E(泛型)。new一个名为newNode的结点,构造函数初始化,newNode结点的上一结点等于pred结点(pred代表索引index结点的上一个结点),newNode结点的值为e,newNode结点的下一节点为null。看懂了没,哈哈,其实这个newNode相当于“覆盖”了succ结点(当前索引为index的结点),这里画个图给大家理解下吧。

newNode结点的上一结点等于pred结点,下一节点此时为null

if (pred == null)    //则头结点等于newNode    first = newNode;else    //当前记录pred的下一节点等于newNode,相当于把succ记录结点给覆盖了    pred.next = newNode;

当pred == null时,链表的头结点等于newNode。因为如果当前传入索引index的结点succ为头结点,那么上一个结点pred就肯定会null,如下图:

pred不等于null时,pred结点的下一节点更改为newNode结点,如下图:

然后pred.next = newNode也就是当前传入索引index的结点succ的上一个结点变为了newNode结点,以便下次再添加时,pred变为newNode,for循环一次结束,第二次循环的话,添加效果图如下:

如此,直至for循环结束。

然后,再往下看代码

if (succ == null) {    //尾结点等于当前记录结点pred    last = pred;} else {    //重新把pred结点下一个结点赋值为succ记录结点    pred.next = succ;    //并且让succ记录结点的上一个结点等于最新的pred记录结点    succ.prev = pred;}

分析:当传入的index等于链表长度size时,链表索引是从0开始的,所以超出链表索引,那么当前索引succ == null,则直接让pred等于尾结点(很好理解吧?succ的上一个结点不就是索引为index-1的尾结点)。如果不等于null,把pred(此时的pred等于最后一个newNode结点)下一个结点指向succ结点,succ的上一个结点指向pred,效果如下图:

最后:

//链表的长度加上集合的长度size += numNew;//修改次数加1modCount++;return true;

分析:链表长度加上集合的长度,修改次数加1,返回

到此,addAll()方法分析结束了,总结下,我们明白了在添加链表元素时并不是真正所谓上的“添加”,这里的添加其实是改变指针的指向从而达到往链表添加的目的,删除链表元素也类似。

四:我们看下最常用的几个方法

1.往链表末尾添加单个元素方法

/** * 往链表末尾添加元素 */public boolean add(E e) {    linkLast(e);    return true;}

分析:传入元素的值,调用linkLast()方法

/** * Links e as last element. */void linkLast(E e) {    //尾结点    final Node<E> l = last;    //new一个新结点,上一个结点等于尾结点,结点值等于e,下一个结点等于null    final Node<E> newNode = new Node<>(l, e, null);    //尾结点等于新结点    last = newNode;    //链表没有元素,则尾结点为null    if (l == null)        //让头结点等于新结点        first = newNode;    else        //否则,尾结点的下一个结点等于新结点        l.next = newNode;    //链表长度加1    size++;    //修改次数加1    modCount++;}

分析:这里添加和上面思想其实是一致的,所以就不详解了和画图了,直接看上面我写的注释。

2.根据索引删除元素

/** * 根据索引删除结点 */public E remove(int index) {    //检查索引是否越界    checkElementIndex(index);    //node(index)索引为index的node结点,传入unLink()方法    return unlink(node(index));}

继续往下看unlink()方法,传入的是索引为index的node结点对象

/** * 删除指定节点元素 */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;

//如果当前节点的上一节点prev为null    if (prev == null) {        //头节点等于下一节点        first = next;    } else {        //上一节点成员变量下一节点改为next        prev.next = next;        //当前节点的上一节点置为null方便回收        x.prev = null;    }

//如果当前节点的下一节点next为null(也就是链表最后一个元素)    if (next == null) {        //链表的尾节点等于当前节点的上一节点prev        last = prev;    } else {        //当前节点的下一节点next的成员变量prev等于当前节点的上一节点prev        next.prev = prev;        //当前节点的下一节点置为null        x.next = null;    }

//当前节点的值置为null    x.item = null;    //当前链表长度减1    size--;    //修改次数加1    modCount++;    //返回当前节点元素值    return element;}

分析:这里的删除指定节点,其实道理也是类似,通过改变上一节点和下一节点各自的成员变量引用从而达到删除当前元素节点的效果。

到此为止,LinkedList其它常用方法源码不再进行分析了,基本掌握了核心的原理,其它的都是类似。

这样我们就简单的看了下LinkedList源码。

下一篇分析HashMap源码

原文地址:https://www.cnblogs.com/lizb0907/p/10364982.html

时间: 02-12

jdk1.8-LinkedList源码分析的相关文章

Java集合系列之LinkedList源码分析

一.LinkedList简介 LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列,它是基于双向链表实现的. ps:这里有一个问题,就是关于实现LinkedList的数据结构是否为循环的双向链表,上网搜了有很多文章都说是循环的,并且有的文章中但是我看了源代码觉得应该不是循环的? 例如在删除列表尾部节点的代码: private E unlinkLast(Node<E> l) { final E element = l.item; final Node<E> pr

Java - LinkedList源码分析

java提高篇(二二)---LinkedList 一.概述 LinkedList与ArrayList一样实现List接口,只是ArrayList是List接口的大小可变数组的实现,LinkedList是List接口链表的实现.基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList,而随机访问则比ArrayList逊色些. LinkedList实现所有可选的列表操作,并允许所有的元素包括null. 除了实现 List 接口外,LinkedList 类还为在列表的开头及结尾

JDK1.7 HashMap 源码分析

概述 HashMap是Java里基本的存储Key.Value的一个数据类型,了解它的内部实现,可以帮我们编写出更高效的Java代码. 本文主要分析JDK1.7中HashMap实现,JDK1.8中的HashMap已经和这个不一样了,后面会再总结. 正文 HashMap概述 HashMap根据键的hashCode值获取存储位置,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的. HashMap最多只允许一条记录的键为null,允许多条记录的值为null.HashMap

Java 集合之LinkedList源码分析

1.介绍 链表是数据结构中一种很重要的数据结构,一个链表含有一个或者多个节点,每个节点处理保存自己的信息之外还需要保存上一个节点以及下一个节点的指针信息.通过链表的表头就可以访问整个链表的信息.Java API中提供了链表的Java实现---LinkedList下.LinkedList是通过节点的连接实现链表的数据结构,向linkedList中插入或删除元素的速度是特别快,而随机访问的速度相对较慢,这个是由于链表本身的性质造成的,在链表中,每个节点都包含了前一个节点的引用,后一个节点的引用和节点

LinkedList源码分析

LinkedList的声明 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable 基本和ArrayList一样,除了实现了Deque<E>接口以及没有实现RandomAccess接口. Deque是double ended queue(双端队列)的缩写,表示

jdk 1.7 LinkedList 源码分析

1 linkedList 的定义 public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable 从这段代码中我们可以清晰地看出LinkedList继承AbstractSequentialList,实现List.Deque.Cloneable.Serializable.其中Abs

java集合框架04——LinkedList和源码分析

上一章学习了ArrayList,并分析了其源码,这一章我们将对LinkedList的具体实现进行详细的学习.依然遵循上一章的步骤,先对LinkedList有个整体的认识,然后学习它的源码,深入剖析LinkedList. LinkedList简介 首先看看LinkedList与Collection的关系: LinkedList的继承关系如下: java.lang.Object ? java.util.AbstractCollection<E> ? java.util.AbstractList&l

List 接口以及实现类和相关类源码分析

List 接口以及实现类和相关类源码分析 List接口分析 接口描述 用户可以对列表进行随机的读取(get),插入(add),删除(remove),修改(set),也可批量增加(addAll),删除(removeAll,retainAll),获取(subList). 还有一些判定操作:包含(contains[All]),相等(equals),索引(indexOf,lastIndexOf),大小(size). 还有获取元素类型数组的操作:toArray() 注意事项 两种迭代器Iterator和L

基于JDK1.8的LinkedList源码学习笔记

LinkedList作为一种常用的List,是除了ArrayList之外最有用的List.其同样实现了List接口,但是除此之外它同样实现了Deque接口,而Deque是一个双端队列接口,其继承自Queue,所以LinkedList同样可以用来模拟队列,栈以及双端队列. 一.基本用法 因为LinkedList是基于链表实现的,所以注定其插入和删除操作速度要快于ArrayList,但是由于其是链表结构,所以其随机访问查找检索速度慢于基于数组的ArrayList. 这里先主要说一下LinkedLis

【JUC】JDK1.8源码分析之ConcurrentHashMap(一)

一.前言 最近几天忙着做点别的东西,今天终于有时间分析源码了,看源码感觉很爽,并且发现ConcurrentHashMap在JDK1.8版本与之前的版本在并发控制上存在很大的差别,很有必要进行认真的分析,下面进行源码分析. 二.ConcurrentHashMap数据结构 之前已经提及过,ConcurrentHashMap相比HashMap而言,是多线程安全的,其底层数据与HashMap的数据结构相同,数据结构如下 说明:ConcurrentHashMap的数据结构(数组+链表+红黑树),桶中的结构