本文共 5261 字,大约阅读时间需要 17 分钟。
java.util.List
接口java.io.Serializable
接口java.lang.Cloneable
接口 如下1个接口 ArrayList 有LinkedList中没有的:java.util.RandomAccess
接口,LinkedList 不同于 ArrayList 的很大一点,不支持随机访问。 如下1个接口是LinkedList有但是ArrayList没有的:java.util.Deque
接口,提供双端队列的功能,LinkedList 支持快速的在头尾添加元素和读取元素,所以很容易实现该特性。 注意,以为 LinkedList 实现了 Deque 接口,所以我们在 「5. 添加单个元素」 和 「7. 移除单个元素」 中,会看到多种方法
也因为实现 Deque 即可以作为队列使用,也可以作为栈使用。当然,作为双端队列,也是可以的
继承了 java.util.AbstractSequentialList
抽象类,它是 AbstractList 的子类,实现了只能连续访问“数据存储”(例如说链表)的 get(int index) ``add(int index, E element)
等等随机操作的方法。可能这样表述有点抽象,点到 java.util.AbstractSequentialList
抽象类中看看这几个方法,基于迭代器顺序遍历后,从而实现后续的操作。
LinkedList属性同样很少 只有三个。如下图所示:环境是1.8双向链表实现(1.6及以前使用的是环形链表实现)
first
和 last
指向 null
,因为此时暂时没有 Node 节点。node1
,前后指向 null
。此时,first
和 last
指向该 Node 节点。node2
,其 prev = node1
和 next = null
,而 node1
的 prev = null
和 next = node2
。此时,first
保持不变,指向 node1
,last
发生改变,指向 node2
。size
属性链表的节点数量。通过它进行计数,避免每次需要 List 大小时,需要从头到尾的遍历LinkedList 一共有两个构造方法(相比 ArrayList 来说,因为没有容量一说,所以不需要提供 ArrayList(int initialCapacity)
)这个构造方法,代码如下:
add(E e)
方法,顺序添加单个元素到链表。代码如下:
<X>
处,调用 linkLast(E e)
方法,将新元素添加到链表的尾巴。所以,add(E e)
方法,实际就是 linkLast(E e)
方法。
总体来说,代码实现比较简单。重点就是对 last
的处理。
相比 ArrayList 来说,无需考虑容量不够时的扩容
看懂这个方法后,我们来看看add(int index, E element)
方法,插入单个元素到指定位置。代码如下: <1>
处,如果刚好等于链表大小,直接调用 linkLast(E element)
方法,添加到尾部即可。
<2>
处,先调用 node(int index)
方法,获得第 index
位置的 Node 节点 node
。然后,调用 linkBefore(E element, Node node)
方法,将新节点添加到 node
的前面。相当于说,node
的前一个节点的 next
指向新节点,node
的 prev
指向新节点。
node(int index)
方法,获得第 index
个 Node 节点。(思考题:LinkedList使用双向链表而不是使用单向链表的原因是什么?看完下面的代码相信会有答案)代码如下:
linkBefore(E e, Node<E> succ)
方法,添加元素 e
到 succ
节点的前面。代码如下: LinkedList实现了 Queue 接口,所以它实现了 push(E e)
和 offer(E e)
方法,添加元素到链表的头尾 这个不是重点不细说 addAll(Collection<? extends E> c)
方法,批量添加多个元素,内部调用的是 addAll(int index, Collection<? extends E> c)
方法,表示在队列之后,继续添加 c
集合。代码如下:
<2>
处,获得第 index
位置的节点 succ
,和其前一个节点 pred
。分成两种情况,看注释。实际上,ArrayList 在添加 c
集合的时候,也是分成跟 LinkedList 一样的两种情况,只是说 LinkedList 在一个方法统一实现了。<3>
处,遍历 a
数组,添加到 pred
的后面。其实,我们可以把 pred
理解成“尾巴”,然后不断的指向新节点,而新节点又称为新的 pred
尾巴。如此反复插入~<4>
处,修改 succ
和 pred
的指向。根据 <2>
处分的两种情况,通过判断succ是有为null进行处理remove(int index)
方法,移除指定位置的元素,并返回该位置的原元素。代码如下:
node(int index)
方法,获得第 index
的 Node 节点。然后,调用 unlink(Node<E> x)
方法,移除该节点 unlink(Node<E> x)
方法,代码如下: remove(Object o)
方法,移除首个为 o
的元素,并返回是否移除到(相比 remove(int index)
方法来说,需要去寻找首个等于 o
的节点进行移除。当然,最终还是调用 unlink(Node<E> x)
方法,移除该节点)代码如下: removeFirstOccurrence(Object o)
和 removeLastOccurrence(Object o)
方法,分别实现移除链表首个或者是最后一个为o的节点。代码如下: remove()
方法,移除链表首个节点。代码如下: removeLast()
方法,移除链表末尾节点。代码如下:和上面的一个方法实现差不多 poll()
和 pop() 方法,移除链表的头或尾,差异点在于链表为空时候,会不会抛出 NoSuchElementException 异常 removeAll(Collection<?> c)
方法,批量移除指定的多个元素。代码如下:该方法,是通过父类 AbstractCollection 来实现的,通过迭代器来遍历 LinkedList ,然后判断 c
中如果包含,则进行移除。
retainAll(Collection<?> c)
方法,求 LinkedList 和指定多个元素的交集。简单来说,恰好和 removeAll(Collection<?> c)
相反,移除不在 c
中的元素 在 处判断条件不同,代码如下: indexOf(Object o)
方法,查找首个为指定元素的位置。代码如下:
contains(Object o)
方法,就是基于该方法实现。代码如下 有时我们需要查找最后一个为指定元素的位置,所以会使用到 lastIndexOf(Object o)
方法 (上述的三个方法本质上实现的逻辑是一样的 不进行赘述)代码如下: get(int index)
方法,获得指定位置的元素。代码如下:随机访问 index
位置的元素,时间复杂度为 O(n)
#peekFirst()
和 #peekLast()
方法,分别获得元素到链表的头尾。代码如下 因为 LinkedList 实现了 Queue 接口,所以它实现了 #peek()
和 #peek()
和 #element()
方法,分别获得元素到链表的头。代码如下 LinkedList 实现了 Deque 接口,所以它实现了 peekFirst()
和 peekLast()
方法,分别获得元素到链表的头尾。代码如下:
peek()
和 element()
方法,分别获得元素到链表的头 set(int index, E element)
方法,设置指定位置的元素。代码如下:
toArray()
方法,将 LinkedList转换成 []
数组。代码如下:需要注意的一点就是返回的是Object[] 数组
hashCode()
方法,求 LinkedList的哈希值。该方法,是通过父类 AbstractList 来实现的,通过 for
来遍历 LinkedList ,然后进行求哈希,代码如下:(这里为什么使用31就不说了 没有看过上一篇的可以看一下上一篇:ArrayList源码分析)
equals(Object o)
方法,判断是否相等 代码如下 该方法是通过父类 AbstractList 来实现的,通过迭代器,实现遍历比对
clear()
方法,清空链表。代码如下:
writeObject(java.io.ObjectOutputStream s)
方法,实现 LinkedList 的序列化,readObject(java.io.ObjectInputStream s)` 方法,反序列化为链表。代码如下:
clone()
方法,克隆 LinkedList 对象。代码如下:
first
、last
等都是重新初始化进来,不与原 LinkedList 共享。 LinkedList 做一个简单的小结
因为
first
节点,所以提供了队列的功能的实现的功能。因为last
节点,所以提供了栈的功能的实现的功能。因为同时具有first
+last
节点,所以提供了双端队列的功能。
最好时间复杂度发生在头部、或尾部移除的情况。
最好时间复杂度发生在头部移除的情况。
最好时间复杂度发生在头部、或尾部添加的情况。
因为 LinkedList 提供了多种添加、删除、查找的方法,会根据是否能够找到对应的元素进行操作,抛出 NoSuchElementException 异常 常用的方法详见下表:
返回结果 | 抛出异常 | |
---|---|---|
添加 | add(…) 、offset(...) | |
删除 | remove(int index) 、remove(E e) 、poll(E E) | remove() |
查找 | get(int index) 、peek() | poll() |
这个表主要整理了 List 和 Queue 的操作,暂时没有整理 Deque 的操作。因为,Deque 相同前缀的方法,表现结果同 Queue。
转载地址:http://bbxrn.baihongyu.com/