概览
同 ArrayList 一样,LinkedList 也是对 List 接口的一种具体实现。不同的是,ArrayList 是基于数组来实现的,而 LinkedList 是基于双向链表实现的。LinkedList 类的声明如下:
1 2 3
|
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
|
LinkedList 继承自 AbstractSequentialList,实现了 List 接口,同时还实现了 Deque 接口。AbstractSequentialList 是 AbstractList 的子类,为基于顺序访问的链表提供了一些基本的实现。LinkedList 实现了 Deque 接口,Deque 接口是一种双端队列,可以作为 FIFO 队列和 LIFO 队列(栈)来使用。LinkedList 支持所有元素,包括 null。
下面基于JDK 8 中的代码对LinkedList的实现加以分析。
底层结构
LinkedList 基于双向链表进行实现,并使用两个引用 first 和 last 分别指向双向链表的头尾元素。同 ArrayList 一样,使用 modCount 来记录结构化修改的次数,并依此实现 fail-fast 机制。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
transient int size = 0;
|
双向链表的节点结构如下,分别用 prev 和 next 指向该节点的前驱和后继结点。
1 2 3 4 5 6 7 8 9 10 11
|
private static class Node<E> { E item; Node<E> next; Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
|
双向链表操作
LinkedList 提供的所有操作都是在双向链表的基础上完成的。Dqeue 接口的一些实现就是在 双向链表的两端进行操作,也是基于对头和尾部元素的操作。总的来说,双向链表的操作并不复杂,下面简单地进行解析,大部分操作都是对以下几种操作的封装。
向头部添加元素
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
|
向尾部添加元素
1 2 3 4 5 6 7 8 9 10 11
|
void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
|
从中间插入元素
移除头部节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
|
移除尾部节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
|
private E unlinkLast(Node<E> l) { |
移除任意一个非空节点
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
|
|
清空链表
主要是为了方便垃圾回收器进行垃圾回收。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
|
public void clear() { |
根据索引获取元素
因为是双向链表,可向前遍历,也可向后遍历。查找时双向进行,靠近头节点则从前向后查找;靠近尾部,则从后向前查找。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
|
|
反查一个元素的索引
第一次出现:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
public int indexOf(Object o) { int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
|
最后一次出现,从后向前查找:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
|
public int lastIndexOf(Object o) { int index = size; if (o == null) { for (Node<E> x = last; x != null; x = x.prev) { index--; if (x.item == null) return index; } } else { for (Node<E> x = last; x != null; x = x.prev) { index--; if (o.equals(x.item)) return index; } } return -1; }
|
迭代器
通过 next 的指向依次进行遍历。还提供了反向的迭代(从尾部到头部),通过 prev 的指向依次遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102
|
private class ListItr implements ListIterator<E> { private Node<E> lastReturned; private Node<E> next; private int nextIndex; |
小结
LinkedList 是 List 接口基于双向链表的一种实现,同时还实现了 Deque 接口,可以作为 FIFO 和 LIFO 队列使用。双向链表的实现使得插入和删除操作的代价降低,可以在常数时间内完成;然而查找操作需要遍历列表,尽管双向列表使得可以从两端进行查找,但在长度较长时仍然需要较长的时间。
在大多数情况下会选择使用 ArrayList,尽管插入和删除代价相较于 LinkedList 更高,但随机访问的特性使得在查找方面 ArrayList 比 LinkedList 具有更多的优势。关于 ArrayList 和 LinkedList 的使用选择上可以参考 * 上的这个问答。