文档章节

Java集合源码分析之LinkedList

须臾之余
 须臾之余
发布于 08/09 17:11
字数 4052
阅读 9
收藏 0

前言

前面一篇我们分析了ArrayList的源码,这一篇分享的是LinkedList。我们都知道它的底层是由链表实现的,所以我们要明白什么是链表?

一、LinkedList简介

1.1、LinkedList概述

  •   LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列,它是基于双向链表实现的。
  •   LinkedList 是一个继承于AbstractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
  •   LinkedList 实现 List 接口,能对它进行队列操作。
  •   LinkedList 实现 Deque 接口,即能将LinkedList当作双端队列使用。
  •   LinkedList 实现了Cloneable接口,即覆盖了函数clone(),能克隆。
  •   LinkedList 实现java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
  •   LinkedList 是非同步的。

1.2、LinkedList的数据结构

1)基础知识补充

1.1)单向链表:通过每个结点的指针指向下一个结点从而链接起来的结构,最后一个节点的next指向null。

element:用来存放元素

next:用来指向下一个节点元素

1.2)单向循环链表

element、next 跟前面一样

在单向链表的最后一个节点的next会指向头节点,而不是指向null,这样存成一个环

1.3)双向链表:包含两个指针的,pre指向前一个节点,next指向后一个节点,但是第一个节点head的pre指向null,最后一个节点的tail也指向null。

element:存放元素

pre:用来指向前一个元素

next:指向后一个元素

1.4)双向循环链表

element、pre、next 跟前面的一样

第一个节点的pre指向最后一个节点,最后一个节点的next指向第一个节点,也形成一个“环”。

2)LinkedList的数据结构

如上图所示:LinkedList底层使用的是双向链表结构,有一个头结点和一个尾结点,双向链表意味着我们可以从头开始正向遍历,或者是从尾开始逆向遍历,并且可以针对头部和尾部进行相应的操作。

1.3、LinkedList的特性

  • 异步,也就是非线程安全
  • 双向链表,由于实现了list和Deque接口,能够当作队列来使用。链表:查询效率不高,但是插入和删除这种操作性能好。
  • 是顺序存储结构(注意和随机存取结构两个概念搞清楚)

二、LinkedList源码分析

2.1、LinkedList的继承结构以及层次关系

分析:我们可以看到,linkedList在最底层,说明他的功能最为强大,并且细心的还会发现,arrayList只有四层,这里多了一层AbstractSequentialList的抽象类,为什么呢?

通过API我们会发现:

  • 减少实现顺序存取(例如LinkedList)这种类的工作,就是方便,抽象出类似LinkedList这种类的一些共同的方法
  • 那么如果想自己实现顺序存取这种特性的类(就是链表形式),那么就继承这个AbstractSequentialList抽象类,如果想像数组那样的随机存取的类,那么就去实现AbstractList抽象类。
  • 这样的分层,就很符合我们抽象的概念,越往高处的类,就越抽象,越往底层的类,就越有自己独特的个性。
  • 实现了Deque接口,那么也就意味着LinkedList是双端队列的一种实现,所以,基于双端队列的操作在LinkedList中全部有效。

实现接口分析:

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

1)List接口:列表,add、set、等一些对列表进行操作的方法

2)Deque接口:有队列的各种特性,

3)Cloneable接口:能够复制,使用那个copy方法。

4)Serializable接口:能够序列化。

5)应该注意到没有RandomAccess:那么就推荐使用iterator,在其中就有一个foreach,增强的for循环,其中原理也就是iterator,我们在使用的时候,使用foreach或者iterator都可以。

2.2、类的属性 

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    transient int size = 0;//实际元素个数

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

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

LinkedList属性非常简单,一个头结点、一个尾结点、一个表示链表中实际元素的变量。注意,头尾结点都有transient关键字修饰,这也意味着在序列化时该域是不会序列化的。

2.3、LinkedList的构造方法

两个构造方法(两个构造方法都是规范规定需要写的)

1)空参构造函数

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

2)有参构造函数

//将集合中的元素构建成LinkedList链表
public LinkedList(Collection<? extends E> c) {
    //调用无参构造函数
    this();
    //添加集合中所有的元素
    addAll(c);
}

2.4、内部类(Node)

//根据前面介绍双向链表就知道这个代表什么了,linkedList的奥秘就在这里
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;
    }
}

2.5、核心方法

2.5.1、add()方法

1)add(E)

public boolean add(E e) {
    //添加到末尾
    linkLast(e);
    return true;
}

说明:add函数用于向LinkedList中添加一个元素,并且添加到链表尾部。具体添加到尾部的逻辑是由linkLast函数完成的。

分析:LinkLast(XXXXX)

/**
 * Links e as last element.
 */
void linkLast(E e) {
    final Node<E> l = last;//临时结点保存last,也就是l指向了最后一个结点
    final Node<E> newNode = new Node<>(l, e, null);//将e封装为结点,并且e.prev指向了最后一个结点
    last = newNode;//newNode成为最后一个结点,所以last指向了它
    if (l == null)//判断是不是一开始链表中就什么都没有,如果没有,则newNode就成为了第一个结点,first和last都要指向它
        first = newNode;
    else//正常的在最后一个结点追加,那么原先的最后一个结点的next就要指向现在真正最后一个结点,原先的最后一个结点就变成了倒数第二个结点
        l.next = newNode;
    size++;//添加一个结点,size自增
    modCount++;
}

说明:对于添加一个元素至链表中会调用add方法->LinkLast方法

举例一:

LinkedList<Integer> lists = new LinkedList<Integer>();
lists.add(5);
lists.add(6);

首先调用无参构造函数,之后添加元素5,之后再添加元素6。具体的示意图如下:

2.5.2、addAll方法

addAll有两个重载函数,addAll(Collection<? extends E>)型和addAll(int, Collection<? extends E>)型,我们平时习惯调用的addAll(Collection<? extends E>)型会转化为addAll(int, Collection<? extends E>)型。

1)addAll(c);

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);
    //将集合c转换为Object数组a
    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        //集合为空,则什么都不做,返回false
        return false;
    //定义两个结点(内部类),每个结点都有三个属性,item,next,prev.
    Node<E> pred, succ;
    //如果不指定添加结点位置,index=0,size=添加的结点个数,若结点个数为0,则succ=null,pred=last=null
    //如果指定添加结点位置,且添加结点位置和要添加的结点size相等
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    //将遍历数组a中的元素,封装为一个个结点
    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        //pred就是之前构建好的,可能为null,也可能不为null
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}

说明:参数中的index表示在索引下标为index的结点(实际上是第index + 1个结点)的前面插入。     

在addAll函数中,addAll函数中还会调用到node函数,get函数也会调用到node函数,此函数是根据索引下标找到该结点并返回,具体代码如下:

Node<E> node(int index) {
    // assert isElementIndex(index);

    //判断插入的位置在链表的前半段或者后半段
    if (index < (size >> 1)) {//插入位置在前半段
        Node<E> x = first;
        for (int i = 0; i < index; i++)//从头结点开始正向遍历
            x = x.next;
        return x;//返回该节点
    //插入位置在后半段
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)//从尾结点开始反向遍历
            x = x.prev;
        return x;//返回该结点
    }
}

说明:在根据索引查找结点时,会有一个小优化,结点在前半段则从头开始遍历,在后半段则从尾开始遍历,这样就保证了只需要遍历最多一半结点就可以找到指定索引的结点。

举例说明调用addAll函数后的链表状态:

 List<Integer> lists = new LinkedList<Integer>();
    lists.add(5);
    lists.addAll(0, Arrays.asList(2, 3, 4, 5));

上述代码内部的链表结构如下:

addAll()中的一个问题:    

在addAll函数中,传入一个集合参数和插入位置,然后将集合转化为数组,然后再遍历数组,挨个添加数组的元素,但是问题来了,为什么要先转化为数组再进行遍历,而不是直接遍历集合呢?

从效果上两者是完全等价的,都可以达到遍历的效果。关于为什么要转化为数组的问题,我的思考如下:

1. 如果直接遍历集合的话,那么在遍历过程中需要插入元素,在堆上分配内存空间,修改指针域,这个过程中就会一直占用着这个集合,考虑正确同步的话,其他线程只能一直等待。

2. 如果转化为数组,只需要遍历数组,而遍历数组过程中不需要额外的操作,

所以占用的时间相对是较短的,这样就利于其他线程尽快的使用这个集合。说白了,就是有利于提高多线程访问该集合的效率,尽可能短时间的阻塞。

2.5.3、remove(Object o)

//如果我们要移除的值在链表中存在多个一样的值,那么我们会移除index最小的那个,也就是最先找到的那个值,如果不存在这个值,那么什么也不做
public boolean remove(Object o) {
    //这里可以知道,linkedList也能存储null
    if (o == null) {
        //循环遍历链表。直到找到null值,然后使用unlink移除该值。
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null) {
                unlink(x);
                return true;
            }
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

unlink(xxxx)

E unlink(Node<E> x) {
    // assert x != null;
    //拿到结点x的三个属性
    final E element = x.item;
    final Node<E> next = x.next;
    final Node<E> prev = x.prev;

    //这里开始往下就进行移除该元素的操作,也就是把指向那个结点搞定
    if (prev == null) {
        //说明移除的结点是头结点,则first头结点应该指向下一个结点
        first = next;
    } else {
        //不是头结点,prev.next=next:
        prev.next = next;
        //然后解除x结点的指向
        x.prev = null;
    }

    if (next == null) {
        //说明移除的结点是尾结点
        last = prev;
    } else {
        //不是尾结点
        next.prev = prev;
        x.next = null;
    }
    //x的前后都指向为null,也把item为null,让gc回收它
    x.item = null;
    //移除一个结点,size自减
    size--;
    modCount++;
    return element;//由于一开始保存了x的值到element,所以返回
}

2.5.4、get(index)

get(index)查询元素的方法

public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}
Node<E> node(int index) {
    // assert isElementIndex(index);

    if (index < (size >> 1)) {
        Node<E> x = first;
        for (int i = 0; i < index; i++)
            x = x.next;
        return x;
    } else {
        Node<E> x = last;
        for (int i = size - 1; i > index; i--)
            x = x.prev;
        return x;
    }
}

2.5.5、indexOf(Object o)

//这个很简单,就是通过实体元素来查找到该元素在链表中的位置
public int indexOf(Object o) {
    int index = 0;
    if (o == null) {
        for (Node<E> x = first; x != null; x = x.next) {
            if (x.item == null)
                return index;
            index++;
        }
    } else {
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item))
                return index;
            index++;
        }
    }
    return -1;
}

三、LinkedList的迭代器

在LinkedList中除了有一个Node的内部类外,应该还能看到另外两个内部类,那就是ListItr,还有一个是DescendingIterator。

3.1、ListItr内部类

public ListIterator<E> listIterator(int index) {
    checkPositionIndex(index);
    return new ListItr(index);
}

看一下他的继承结构,发现只继承了一个ListIterator,到ListIterator中一看:

看到方法名之后,就发现不止有向后迭代的方法,还有向前迭代的方法,所以我们就知道了这个ListItr这个内部类干嘛用的了,就是能让linkedList不光能像后迭代,也能向前迭代。

看一下ListItr中的方法,可以发现,在迭代的过程中,还能移除、修改、添加值得操作。

3.2、DescendingIterator内部类    

private class DescendingIterator implements Iterator<E> {
    private final ListItr itr = new ListItr(size());
    public boolean hasNext() {
        return itr.hasPrevious();
    }
    public E next() {
        return itr.previous();
    }
    public void remove() {
        itr.remove();
    }
}

看下这个类,还是调用ListItr,作用是封装一下Itr中几个方法,让使用者以正常的思维去写代码,例如,在从后往前遍历的时候,也是跟从前往后遍历一样,使用next等操作,而不使用previous。

微软面试题:

掌握LinkedList的特殊方法,用LinkedList实现字符串反转输出,实现字符串0到k 和k+1到2k反转,再合并输出

public class Linked001 {
    public static void main(String[] args) {
        String str="abcdefgh";
        System.out.println("要反转的字符串:"+str);
        LinkedList<Character> list = new LinkedList<>();
        for (int i = 0; i < (str.length()>>1); i++) {
            char c=str.charAt(i);
            list.addFirst(c);
        }
        System.out.println("list,0->k之间:"+list);

        LinkedList<Character> list2 = new LinkedList<>();
        for (int i = str.length()>>1; i < str.length(); i++) {
            char c=str.charAt(i);
            list2.addFirst(c);
        }
        System.out.println("list2,k+1->2k之间:"+list2);
        list.addAll(list2);
        System.out.println("合并后,2k:"+list);
        String newStr="";
        while (list.size()>0){
            newStr+=list.removeFirst();
        }
        System.out.println("newStr:"+newStr);
    }
}
public void addFirst(E e) {
    linkFirst(e);
}
private void linkFirst(E e) {
    //先记录first结点,若第一次添加,first=null,则f=null
    final Node<E> f = first;
    //创建一个新的结点,prev=null,item=e,next=f,若f=null.则结点为,[null,e,null],若f结点不为null,则[null,e,next]
    final Node<E> newNode = new Node<>(null, e, f);
    //first指向newNode
    first = newNode;
    //判断f是否为null,若是第一次添加则为null,否则不为null
    if (f == null)
        //last指向新结点
        last = newNode;
    else
        //f的前结点,也就是第一个结点指向了新的结点
        f.prev = newNode;
    //链表长度加1
    size++;
    modCount++;
}
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    //获取第一个结点的值
    final E element = f.item;
    //获取第一个节点的下一个结点
    final Node<E> next = f.next;
    //将第一个结点的值置为null
    f.item = null;
    //将第一个结点的next指向null
    f.next = null; // help GC
    //first指向第一个要删除的结点的下一个结点
    first = next;
    //如果第一个结点的下一个结点为null,说明只有一个结点,则last指向null,删了这个结点就没了
    if (next == null)
        last = null;
    else
        //说明还有下一个结点,则下一个结点的前置置为null,说明这个结点是首结点
        next.prev = null;
    //链表长度减少1
    size--;
    modCount++;
    //返回删除的第一个节点的值
    return element;
}

输出结果:

四、总结

  1)linkedList本质上是一个双向链表,通过一个Node内部类实现的这种链表结构。
  2)能存储null值
  3)跟arrayList相比较,就真正的知道了,LinkedList在删除和增加等操作上性能好,而ArrayList在查询的性能上好
  4)从源码中看,它不存在容量不足的情况
  5)linkedList不光能够向前迭代,还能像后迭代,并且在迭代的过程中,可以修改值、添加值、还能移除值。
  6)linkedList不光能当链表,还能当队列使用,这个就是因为实现了Deque接口

 

本文参考:https://www.cnblogs.com/zhangyinhua/p/7688304.html

© 著作权归作者所有

须臾之余
粉丝 125
博文 67
码字总数 178724
作品 0
吉安
程序员
私信 提问
一份关于 Java、Kotlin 与 Android 的学习笔记

JavaKotlinAndroidLearn 这是一份关于 Java 、Kotlin 、Android 的学习笔记,既包含对基础知识点的介绍,也包含对一些重要知识点的源码解析,笔记的大纲如下所示: Java 重拾Java(0)-基础知...

叶应是叶
2018/08/08
0
0
从 Java 代码到 Java 堆

从 Java 代码到 Java 堆 分析是一种美德,PS原文地址:http://www.ibm.com/developerworks/cn/java/j-codetoheap/ 理解和优化您的应用程序的内存使用 本文将为您提供 Java™ 代码内存使用情况...

北极之北
2016/03/10
764
3
ArrayList和LinkedList的几种循环遍历方式及性能对比分析

最新最准确内容建议直接访问原文:ArrayList和LinkedList的几种循环遍历方式及性能对比分析 主要介绍ArrayList和LinkedList这两种list的五种循环遍历方式,各种方式的性能测试对比,根据Arr...

Trinea
2013/10/31
640
1
泥沙砖瓦浆木匠/java-core-learning-example

感谢赞助的ta们 Java 核心系列教程,关于Java核心技术学习积累的例子,是初学者及核心技术巩固的最佳实践。 包括基础语法,OOP,字符串,集合,IO,反射,线程,网络等。 未完成模块:阿里J...

泥沙砖瓦浆木匠
04/02
0
0
搞懂 HashSet & LinkedHashSet 源码以及集合常见面试题目

HashSet & LinkedHashSet 源码分析以及集合常见面试题目 经过上两篇的 HashMap 和 LinkedHashMap 源码分析以后,本文将继续分析 JDK 集合之 Set 源码,由于有了之前的 Map 源码分析的铺垫,S...

群星纪元
03/31
40
0

没有更多内容

加载失败,请刷新页面

加载更多

JS实现使用Math.random()函数生成n到m间的随机数字

Math.random()函数返回0和1之间的伪随机数,可能为0,但总是小于1,[0,1) 生成n-m,包含n但不包含m的整数: 第一步算出 m-n的值,假设等于w 第二步Math.random()*w 第三步Math.random()*w+n...

张兴华ZHero
21分钟前
3
0
入门了解Service Mesh + Istio?从本文开始

下周六,深圳,阔别已久的线下技术沙龙要和你见面啦! 现场有Rancher Labs研发经理demo刚刚发布的Rancher 2.3中的Istio、Windows容器、集群模板等功能及使用,还有k3s首次线下workshop,由R...

RancherLabs
22分钟前
3
0
Gradle 发布 Jar 到 Archiva 时提示不能 Overwriting released artifacts is not allowed

系统提示错误信息: Received status code 409 from server: Overwriting released artifacts is not allowed. 这是在 Archiva 默认的配置下如果你不是使用 snapshot 配置的话,是不允许对仓...

honeymoose
23分钟前
3
0
二维码插件之qrcode.min.js

文件链接百度云地址 https://pan.baidu.com/s/1nWiBuT4Z7WOAMoUEFL8PZg 入门 http://www.jq22.com/jquery-info294 使用jquery.qrcode.min.js实现前台二维码生成(带Logo) https://blog.csd......

木九天
33分钟前
3
0
开源 java CMS - FreeCMS2.8 自定义标签 commentPage

项目地址:http://www.freeteam.cn/ commentPage 根据参数提取评论对象。 参数 说明 siteid 站点id objtype 评论对象类型 objid 评论对象id membername 会员名称 isanonymous 是否匿名 1是 ...

freeteam
34分钟前
3
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部