前言
本文开始分析LinkedList
。ArrayList
和LinkedList
都实现了List接口,但内部数据结构有所区别,LinkedList
内部是基于链表实现的,所以其插入和删除操作效率较高,但是随机访问效率就相对较低。其定义如下:
|
|
可以看到LinkedList
继承AbstractSequentialList
,实现了List
,Deque
,Cloneable
,java.io.Serializable
四个接口。
AbstractSequenceList
实现了大部分List
接口的方法,Deque
接口定义了双端队列的操作。
本文源码分析基于jdk 1.8.0_121
继承关系
LinkedList继承关系
|
|
关系图
LinkedList
的本质是双向链表,LinkedList
中first,last,size
等成员比较重要,first
是链表的头指针,last
是尾指针,size
是双向链表中节点的个数,链表的节点对应Node
类数据结构如下:
AbstractSequenceList
AbstractSequentialList
继承自 AbstractList
,是 LinkedList
的父类,提供了List接口大部分实现。AbstractSequentialList
实现了“随机访问”方法get(int index)、set(int index, E element)、add(int index, E element)、remove(int index)
。
要实现一个列表,我们只需要扩展此类,并提供 listIterator
和 size
方法的实现即可。对于不可修改的列表,我们只需要实现列表迭代器的 hasNext、next、hasPrevious、previous、index
方法即可。
API
|
|
源码分析
首先我们知道LinkedList
是一个双向链表,但是同时也实现了List接口,因此也可以根据索引值(index
)来获取,更改,删除节点等。
那么是如何把链表和索引值联系的呢?LinkedList
是通过一个计数索引值来实现的,当我们调用get(int index)
时,
我们会把index
和链表长度的1/2比较,如果index
值小,则从链表头向后遍历;反之,如果index
值大,则从链表尾遍历。其余方法原理类似。
成员对象
|
|
构造函数
|
|
增加元素
|
|
设置元素
|
|
获取元素
|
|
删除元素
|
|
toArray
|
|
克隆函数
|
|
其余函数
|
|
小结
LinkedList
是通过双向链表实现的,内部有节点的数据结构LinkedList
实现了Deque
,而Deque
接口定义了在队列两端访问元素的方法,有增加,删除,获取第一个元素等方法。LinkedList
可以作为FIFO
先进先出的队列,下列方法等效
队列方法 | 等效方法 |
---|---|
add(e) | addLast(e) |
offer(e) | offerLast(e) |
remove() | removeFirst() |
poll() | pollFirst() |
element() | getFirst() |
peek() | peekFirst() |
LinkedList
可以作为LIFO
后进先出的栈,下列方法等效
栈方法 | 等效方法 |
---|---|
push(e) | addFirst(e) |
pop() | removeFirst() |
peek() | peekFirst() |
遍历方式
迭代器遍历
|
|
随机访问
|
|
foreach循环
|
|
pollFirst
|
|
pollLast
|
|
removeFirst
|
|
removeLast
|
|
通过随机访问的方式遍历LinkedList
时,效率很低,因此需要尽量避免这种方式。