Java集合(二)——LinkedList的源码解读

前言

本文为序列文章:

对于Java中的集合,大致可以分为Set、List、Queue和Map,其中Set是不重复且无序的集合,List是有序,可重复的集合,而Map则代表的是具有映射关系的集合,Java5后增加了Queue集合,代表一种队列集合的实现。

本文主要介绍总结List集合。List是一个有序(插入有序)的Collection(序列),可以包含重复的元素。

List是实现了Collection接口的,所以实现了Collection的方法:

Collection的方法:

QQ截图20180917203606-2018917

List中的方法

QQ截图20180917203750-2018917

操作总结:

  • 位置访问:基于元素的位置来操作元素:如get、set、add、remove等;
  • 搜索:从List中搜索指定的位置,并且返回其位置的索引:如indexOf等;
  • 迭代:Collection继承自Iterable,由于继承的传递性,可以通过Iterable来实现一些遍历操作。listIteratorf方法返回迭代器用于迭代;

Java中的有两种常见的List的实现:ArrayListLinkedList

LinkedList

我们知道ArrayList底层是以动态数组的方式实现的,在遍历的时候直接修改的是数组下标,没有其他额外的空间消耗,但是在插入,删除的时候,都需要进行移动,即数组的拷贝,效率略差。

当时LinkedList的底层是以链表的方式进行实现,插入和删除的时候只需要改变pre和next节点的指向,在插入和删除的时候效率较高。

LinkedList实现

构造函数

LinkedList有两个构造函数:

默认的无参构造器:

  • public LinkedList()

以集合为参数的有参构造器:

  • public LinkedList(Collection<? extends E> c)
    QQ截图20180919151947-2018919
    调用addAll()方法进行初始化。
    其中allALL方法如下:
    QQ截图20180919155330-2018919
    这个 函数的解释如下:
    首先检查index是否合法,如果是初始化的话,那么这个index=size=0,使用Collection接口的方法toArray将Collection转为数组。接下来的if判断,作用是保存pred和succ两个变量,你想呀,在进行插入的时候,肯定要得到具体的位置呀,具体的位置就是前后嘛。接下来一个for循环,将循环将数组的元素转为node结构,然后挂到链表上。

存储

对于LinkedList,在底层是采用Node的方式进行存储,Node是定义在LinkedList内部的内部类:

QQ截图20180919152453-2018919

仅有一个有参构造器,其中第一个参数是前置节点,第二个参数是需要插入的元素,第三个是后置节点。

对于LinkedList来说,有以下几种插入数据的方式:

在链表的最后一个位置插入元素:

  • public boolean add(E e)
    QQ截图20180919152222-2018919

其中使用到了一个linkLast函数将该元素链接到链表的最后面:

QQ截图20180919152759-2018919

注意到是创建了一个Node实例,last是使用transient关键字修饰了的,保证了进程之间的可见性。然后是将新节点链接到原链表的最后一个节点上,size也是使用transient关键字修饰了的,size代表的是链表的长度。modCount的 作用如上,保证迭代的准确性,使用的是Fail-Fast机制。

在链表的指定位置插入元素

  • public void add(int index, E element)

QQ截图20180919153434-2018919

这里首先会对这个index进行合法性校验,如果这个index等于size,那么就证明是在链表的最后一个位置插入element(linklast方法见上),如果不是,就是在这个index之前插入element。

这里看下node(index)这个函数,如下:

QQ截图20180919153804-2018919

这个函数首先做了一个判断,(size>>1)是位运算,表示的是size/2。
如果是小于size/2的,表示在链表的前半截;然后使用x=x.next进行遍历。else方法同理,最终返回node;

对于LinkedBefore函数:

QQ截图20180919151947-2018919

首先找到我们刚才通过index查询到的node的前置节点保存起来,将这个node的前置节点改为新的element,这样就完成了新节点和其之后的节点链接。

然后需要将后面的链表和前面的链表链接起来。这个时候分为两种情况了,这个时候就体现了我们之前记录下node的前置节点的作用了。如果这个node本来就是头结点了,那么需要在LinkedList中修改first节点的值。如果不是,那么就直接将node的next和新节点连接起来,这样就完成了插入工作。

  • public boolean addAll(Collection<? extends E> c)
  • public boolean addAll(int index, Collection<? extends E> c)
    QQ截图20180919154932-2018919

这两个合在一起,public boolean addAll(Collection<? extends E> c)这个是调用的public boolean addAll(int index, Collection<? extends E> c)方法。而这个方法在有参构造器中有用到,在那里有讲解。

读取

对于链表的遍历的效率不高,尽管在遍历的时候会采用到除以二以判断从头开始遍历还是从尾开始遍历的方法。

LInkedList获取元素有以下几种方式

  • public E get(int index)

QQ截图20180919160316-2018919

获取链表的第一个元素

  • public E getFirst()
    QQ截图20180919160349-2018919

有获取第一个元素,那么也有获取最后一个元素

  • public E getLast()
    QQ截图20180919160637-2018919

获取元素在链表中的位置

QQ截图20180919161008-2018919

删除

  • public E remove()
    删除第一个元素

QQ截图20180919161438-2018919

  • public E remove(int index)
    删除index位置的元素

    QQ截图20180919161627-2018919

  • public boolean remove(Object o)
    删除第一个出现o的位置的元素

QQ截图20180919161748-2018919

  • public boolean removeFirstOccurrence(Object o)
  • public boolean removeLastOccurrence(Object o)

分别移除第一次或者最后一次出现在链表中的元素

修改

  • public E set(int index, E element)

QQ截图20180919162219-2018919

将index位置的原element设置为新的element

总结

LinkedList

  • 基于双端链表,添加/删除元素只会影响周围的两个节点,开销很低;
  • 只能顺序遍历,无法按照索引获得元素,因此查询效率不高;
  • 没有固定容量,不需要扩容;
  • 需要更多的内存,每个节点中需要多存储前后节点的信息,占用空间更多些。
-------------The End-------------

本文标题:Java集合(二)——LinkedList的源码解读

文章作者:Dimple

发布时间:2018年09月20日 - 10:09

最后更新:2018年09月28日 - 17:09

原始链接:http://www.bianxiaofeng.com/2018/09/20/2018-9-20-10-38-49/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

na,给我一个棒棒糖!
0%