- LinkedList是一个继承与AbatractSequentialList的双向链表。它也可以被当作堆栈、队列或双端队列进行操作。
- LinkedList实现了List接口,能对它进行队列操作。
- LinkedList实现了Deque接口,即能将LinkedList当作双端队列使用。
- LinkedList实现了java.io.Serializable接口,这意味着LinkedList支持序列化,能通过序列化去传输。
顺便说一下LinkedList的父类AbstractSequentialList
虽然LinkedList没有实现RandomAccess接口,但是其父类AbstractSequentialList实现了get、set、add、remove方法
这些接口都是随机访问List的,LinkedList是双向链表,既然它继承与AbstractSequentialList,就相当于已经实现了“get(int index)”这些接口,可以支持随机访问了。
此外,如果我们需要通过AbstractSequentialList实现一个自己的列表,只需要扩展此类,并提供listIterator()和size()方法的实现即可。若要实现不可修改的列表,则需要实现列表迭代器的hashNext、next、hashPrevious、previous和index方法即可。
下面先总览一下LinkedList的构造函数和API:
LinkedList包含三个重要的成员:first、last和size:first是双向链表的表头,last是双向链表的尾节点,size是双向链表中的节点个数。
这里先说一下transient关键字
的用法:
一个对象只要实现了Serilizable接口,这个对象就可以被序列化,java的这种序列化模式为开发者提供了很多便利,可以不必关系具体序列化的过程,
只要这个类实现了Serilizable接口,这个的所有属性和方法都会自动序列化。但是有种情况是有些属性是不需要序列号的,所以就用到这个关键字。
只需要实现Serilizable接口,将不需要序列化的属性前添加关键字transient,序列化对象的时候,这个属性就不会序列化到指定的目的地中。
源码剖析
属性
其中Node是一个内部类:
参数为前一个节点,元素,后一个节点
构造函数
依然是规范了两种构造函数
头尾节点的添加
其中的判定f==null
表示此时的链表为空, modCount为Modified Count的缩写,表示修改次数。
头尾节点的删除
public接口,供外部调用
获取头尾节点
判定是否在链表中,以及index获取
循环遍历,O(1)时间复杂度
add、remove
都是已元素为参数的,并且满足一个即返回
addAll、clear
随机位置操作
都是循环遍历的方式,所以如果用随机位置循环来遍历LinkedList的话,那真是脑门被门夹了。
搜索操作
Queue操作
DeQueue操作
迭代器
LinkedList的迭代器分为双向迭代器(ListItr)和前向迭代器(DescendingIterator)
双向迭代器
都是链表的基本操作
前向迭代器
前向迭代器的next其实获取的是previous
总结
- LinkedList是通过双向链表去实现的。 从LinkedList的实现方式中可以看出,它不存在容量不足的问题,因为是链表
- LinkedList实现java.io.Serializable的方式。当写入到输出流时,先写入“容量”,再依次写出“每一个元素”;当读出输入流时,先读取“容量”,再依次读取“每一个元素”。
- LinkdedList的克隆函数,即是将全部元素克隆到一个新的LinkedList中。
- 由于LinkedList实现了Deque,而Deque接口定义了在双端队列两端访问元素的方法。提供插入、移除和检查元素的方法。
- LinkedList可以作为FIFO(先进先出)的队列,作为FIFO的队列时,下标的方法等价:
- LinkedList可以作为LIFO(后进先出)的栈,作为LIFO的栈时,下表的方法等价:
- LinkedList可以作为LIFO(后进先出)的栈,作为LIFO的栈时,下表的方法等价:
遍历方式
1 .for方式
2. 迭代器方式
3. 快速随机访问
LinkedList适合for和迭代器,如果用快速随机访问的话那么复杂度是O(n)
再次强调一遍不要用随机访问遍历LinkedList