LinkedList特性
底层数据结构
LinkedList不同于ArrayList的数组,它基于链表。
效率
LinkedList的插入删除快,遍历慢(ArrayList正好相反)
实现的接口
1 | public class LinkedList<E> |
LinkedList实现了List接口、Deque双向队列接口(既可以当作FILO队列也可以当作FIFO栈)、Cloneable接口、序列化接口。
值得注意的是,LinkedList继承自AbstractSequentialList(AbstractSequentialList和ArrayList一样继承自AbstractList),也就是说,LinkedList比ArrayList更细化了一层。
细化的那层AbstractSequentialList实现了“链表”版的get
/set
/add
/remove
方法,这使得LinkedList和ArrayList有了质的差别(毕竟彼此的基因遗传都不同)。
同步机制
与ArrayList一样,LinkedList也是不同步的,可以用包装器来创造一个支持同步的List:1
List list = Collections.synchronizedList(new LinkedList(...));
LinkedList字段
1 | transient int size = 0; |
很明显,LinkedList用了first
节点和last
节点来保存整个链表(ArrayList用的是数组)。
注:transient关键字的作用是防止该字段被序列化(一些敏感的信息不能序列化然后在网络上传输)。
LinkedList方法分析
linkFirst(E e) (将一个元素插入链表头部)
1 | private void linkFirst(E e) { |
先建立一个以first
为后继的新节点,令first
为该新节点;然后再修改第二个节点的prev
变量使其指向新头部(如果没有第二个节点就修改last
)
linkLast(E e)(将一个元素插入链表尾部)
机制与linkFirst(E e)
相似,只需将first
替换为last
linkBefore(E e, Node succ) (将一个元素插到一个节点之前)
1 | void linkBefore(E e, Node<E> succ) { |
该方法会判断另一个节点之前是否有节点存在,没有就修改first
。
unlinkFirst(Node f)(将链表头部节点剔除)
1 | private E unlinkFirst(Node<E> f) { |
该方法中有条垃圾回收优化的语句:1
f.next = null; // help GC
强行令变量为null,不再引用该对象,该对象便会在下一轮的GC中被回收。
此外,该方法会判断第二个元素是否存在,没有就修改last
。
unlinkLast(Node l)(将链表尾部节点剔除)
与unlinkFirst(Node<E> f)
类似
unlink(Node x)(剔除某个特定的节点)
1 | E unlink(Node<E> x) { |
该方法需要判断前面的元素和后面的元素是否存在。
getFirst/getLast/removeFirst/removeLast/addFirst/addLast(会抛异常的获取增加与删除)
1 | public E getFirst() { |
以上方法调用了之前的linkFirst
、linkLast
、unlinkFirst
、unlinkLast
等方法。
remove(Object o)(删除某个特定对象)
根据该对象是否为空分2种情况处理:
- 为空,从头扫到尾,利用==null来判断
- 不为空,从头扫到尾,利用equals来判断
注:删除的时候,最终都是要找到要删除的节点,利用链表的解绑来删除。
addAll(int index, Collection<? extends E> c)(插入一个集合到特定的位置)
1 | public boolean addAll(int index, Collection<? extends E> c) { |
使用node(index)找到插入时的后继节点和前继节点(如果是插到尾部则后继节点为空而前继节点为last
),中一一插入元素(根据前继节点来做关联),最后加入后继节点。
get(int index)(获取某个位置的数据)
该方法表现得很像数组有没有,可以获取特定位置的元素!
该方法调用了node(index)来获取该位置的节点,再获取该节点的数据,那么node(index)的原理是什么呢?
node(index)(获取某个位置的节点)
1 | Node<E> node(int index) { |
这个方法很巧妙,先判断下标大小,超过一半就从后面开始遍历,否则从前面开始遍历!
add(int index, E element)(往某个位置插入一个数据)
1 | 先判断是否是尾部,是就调用linkLast(element),不是就调用linkBefore(element, node(index)) |
isPositionIndex(int index) (判断一个位置是否能合法地插入数据)
1 | private boolean isPositionIndex(int index) { |
indexOf(Object o)(查找某个对象的下标)
1 | public int indexOf(Object o) { |
从头往后遍历,复杂度较高。
peek()(获取头部数据,不会抛出异常只会返回null)
poll()(获取并移除头部数据,不会抛出异常只会返回null)
offer(E e)(将数据插入尾部)
针对双向队列实现的方法
1 | public boolean offerFirst(E e) { |
以上方法均不会抛出异常,offer是添加,peek是获取,poll是获取并移除。
针对栈实现的方法
1 | public void push(E e) { |
Iterator详解
java中的Iterator是神奇的东西,主要有hasNext()
和next()
方法供使用,前者判断是否还有元素可以遍历,后者将返回下一个元素。
Iterarot字段
1 | private Node<E> lastReturned = null; |
lastReturned
是上一个返回的节点,next
则是下一个将返回的节点。
Iterator方法
next()(返回下一个节点)
1 | public E next() { |
从这里可以看出,每次调用next()
方法时,next字段相当于current
,我们将返回这个current
节点,令lastReturned
指向current
节点,最后,让next指向下一个准备返回的节点。
所以总结地说:该方法返回当前next指向的节点,并让next指向下一个节点。
previous()
1 | public E previous() { |
该方法和next()
类似,让next指向上一个节点,返回当前next指向的节点。
在该方法执行后,lastReturned
和next
指向同一个节点。
似乎next()方法和previous()方法的实现不太一致,原理不一样?
previous()方法并不会返回next指向的节点,而是返回next前面的节点。似乎把下标定义在previous和next之间会比较好一点。
比如有队列:
0 1 2 3 4 5 6
再定义一个iterator:1
ListIterator<Integer> iterator = list.listIterator(3);
该iterator其实并不是指向第四个元素(因为从0开始计,所以参数是3而实际上是第四个元素),也就是3,而是指向2和3之间的空隙。
下标指向的位置如下:
0 1 2 ‘下标在这里(距离右边的3更近一点)’ 3 4 5 6
此时我们若调用next()者则返回右边的3,并将下标往右移动;若调用previous()则返回左边的2,并将下标往左移动。
remove
1 | public void remove() { |
删除之前被返回的节点,if (next == lastReturned)处理调用previous()方法后的情况。
内部类DescendingIterator(反向的iterator)
调用next()实际上会调用previous(),所以它实际上是个单向的,从后向前的iterator(虽然语法上它一直在调用next())
toArray(T[] a)(将内容放到特定的数组中去)
1 | public <T> T[] toArray(T[] a) { |
该方法中,如果目标数码长度不够,就利用反射的方法重新创建一个足够大的数组。
writeObject(java.io.ObjectOutputStream s)
将LinkedList内容写入到流中去。
readObject(java.io.ObjectInputStream s)
从流中读出一个LinkedList。
静态内部类LLSpliterator
该类有待继续深入研究。