Java集合框架剖析(4)——LinkedList

时间:2022-01-13 21:30:22

Java集合框架剖析(4)——LinkedList

  • LinkedList是一个继承与AbatractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
  • LinkedList实现了List接口,能对它进行队列操作。
  • LinkedList实现了Deque接口,即能将LinkedList当作双端队列使用。
  • LinkedList实现了java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。

顺便说一下LinkedList的父类AbstractSequentialList
Java集合框架剖析(4)——LinkedList
虽然LinkedList没有实现RandomAccess接口,但是其父类AbstractSequentialList实现了get、set、add、remove方法

这些接口都是随机访问List的,LinkedList是双向链表,既然它继承与AbstractSequentialList,就相当于已经实现了“get(int index)”这些接口,可以支持随机访问了。

此外,如果我们需要通过AbstractSequentialList实现一个自己的列表,只需要扩展此类,并提供listIterator()和size()方法的实现即可。若要实现不可修改的列表,则需要实现列表迭代器的hashNext、next、hashPrevious、previous和index方法即可。

下面先总览一下LinkedList的构造函数和API:
Java集合框架剖析(4)——LinkedList

LinkedList包含三个重要的成员:first、last和size:first是双向链表的表头,last是双向链表的尾节点,size是双向链表中的节点个数。
Java集合框架剖析(4)——LinkedList

这里先说一下transient关键字的用法:
一个对象只要实现了Serilizable接口,这个对象就可以被序列化,java的这种序列化模式为开发者提供了很多便利,可以不必关系具体序列化的过程,
只要这个类实现了Serilizable接口,这个的所有属性和方法都会自动序列化。但是有种情况是有些属性是不需要序列号的,所以就用到这个关键字。
只需要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。

源码剖析

属性

Java集合框架剖析(4)——LinkedList
其中Node是一个内部类:
Java集合框架剖析(4)——LinkedList
参数为前一个节点,元素,后一个节点

构造函数

Java集合框架剖析(4)——LinkedList
依然是规范了两种构造函数

头尾节点的添加

Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList
其中的判定f==null表示此时的链表为空, modCount为Modified Count的缩写,表示修改次数。

头尾节点的删除

Java集合框架剖析(4)——LinkedList
public接口,供外部调用
Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList

获取头尾节点

Java集合框架剖析(4)——LinkedList

判定是否在链表中,以及index获取

Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList
循环遍历,O(1)时间复杂度

add、remove

Java集合框架剖析(4)——LinkedList
都是已元素为参数的,并且满足一个即返回

addAll、clear

Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList

随机位置操作

Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList
都是循环遍历的方式,所以如果用随机位置循环来遍历LinkedList的话,那真是脑门被门夹了。

搜索操作

Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList

Queue操作

Java集合框架剖析(4)——LinkedList

DeQueue操作

Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList

迭代器

LinkedList的迭代器分为双向迭代器(ListItr)和前向迭代器(DescendingIterator)

双向迭代器

Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList
Java集合框架剖析(4)——LinkedList
都是链表的基本操作

前向迭代器

Java集合框架剖析(4)——LinkedList
前向迭代器的next其实获取的是previous

总结

  1. LinkedList是通过双向链表去实现的。 从LinkedList的实现方式中可以看出,它不存在容量不足的问题,因为是链表
  2. LinkedList实现java.io.Serializable的方式。当写入到输出流时,先写入“容量”,再依次写出“每一个元素”;当读出输入流时,先读取“容量”,再依次读取“每一个元素”。
  3. LinkdedList的克隆函数,即是将全部元素克隆到一个新的LinkedList中。
  4. 由于LinkedList实现了Deque,而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。
  5. LinkedList可以作为FIFO(先进先出)的队列,作为FIFO的队列时,下标的方法等价:
    Java集合框架剖析(4)——LinkedList
    1. LinkedList可以作为LIFO(后进先出)的栈,作为LIFO的栈时,下表的方法等价:
      Java集合框架剖析(4)——LinkedList

遍历方式

1 .for方式
2. 迭代器方式
3. 快速随机访问

LinkedList适合for和迭代器,如果用快速随机访问的话那么复杂度是O(n)
再次强调一遍不要用随机访问遍历LinkedList