LinkedList

2020-04-29

2025-03-25

LinkedList是基于双向链表实现的有序集合，~~其不能像ArrayList一样通过索引(index)访问元素~~，同时LinkedList还实现了Deque接口，意味着LinkedList可以实现双端队列的操作。

LinkedList继承关系图

链表将每个对象存放在独立的节点(Node)中，节点中还保存对序列中前、后节点的引用。理论上，LinkedList没有容量限制（取决于你的物理内存大小）。

LinkedList的基本数据结构^{from Core Java}

Node(节点) #

Node（节点）是LinkedList的存储载体，每向LinkedList中增加/删除一个元素，就会增加/减少一个Node，Node定义了3个字段，其含义分别是：

E item：存入LinkedList的内容
Node<E> prev：前一个节点的引用
Node<E> next：后一个节点的引用

结合LinkedList的字段来看，LinkedList定义了两个个Node相关的引用：

transient Node<E> first：总是指向LinkedList的第一个节点
transient Node<E> last：总是指向LinkedList的最后一个节点

LinkedList有如下规律：

first.prev总是为null
last.next总是为null
当LinkedList只有一个元素时，first == last

下面的代码验证了上述推论：

 1static void initializeTest() throws Exception {
 2  List<String> a = new LinkedList<>();
 3  a.add("google");
 4  //        a.add("chrome");
 5  //        a.add("photos");
 6
 7  Class<?> cls = LinkedList.class;
 8  // LinkedList field
 9  Field ff = cls.getDeclaredField("first");
10  Field lf = cls.getDeclaredField("last");
11  ff.setAccessible(true);
12  lf.setAccessible(true);
13  Object first =  ff.get(a);
14  Object last = lf.get(a);
15  Class<?> node = Class.forName("java.util.LinkedList$Node");
16  // LinkedList$Node field
17  Field item = node.getDeclaredField("item");
18  Field next = node.getDeclaredField("next");
19  Field prev = node.getDeclaredField("prev");
20  item.setAccessible(true);
21  next.setAccessible(true);
22  prev.setAccessible(true);
23  // first
24  System.out.println("first: " + first);
25  Object firstItem = item.get(first);
26  Object firstPrev = prev.get(first); // Node
27  Object firstNext = next.get(first); // Node
28  System.out.println("\t" + "item: " + firstItem +"\n\t" +
29                     "prev: " + firstPrev + "\n\t" +
30                     "next: " + firstNext + "\n");
31  // last
32  System.out.println("last: " + last);
33  Object lastItem = item.get(last);
34  Object lastPrev = prev.get(last);
35  Object lastNext = next.get(last);
36  System.out.println("\t" + "item: " + lastItem +"\n\t" +
37                     "prev: " + lastPrev + "\n\t" +
38                     "next: " + lastNext);
39}
40/* output:
41first: java.util.LinkedList$Node@512ddf17
42  item: google
43  prev: null
44  next: null
45
46last: java.util.LinkedList$Node@512ddf17
47  item: google
48  prev: null
49  next: null
50
51// 当有3个元素时，first的next == last的prev
52first: java.util.LinkedList$Node@512ddf17
53  item: google
54  prev: null
55  next: java.util.LinkedList$Node@2c13da15
56
57last: java.util.LinkedList$Node@77556fd
58  item: photos
59  prev: java.util.LinkedList$Node@2c13da15
60  next: null
61*///:~

利用Node，对链表中的元素的删除和插入操作将变得便利，只需要同时修改自身及前后节点的引用即可将元素置入链中。

参考如下源码：

 1/**
 2 * Inserts element e before non-null Node succ.
 3 */
 4void linkBefore(E e, Node<E> succ) {
 5  // assert succ != null;
 6  final Node<E> pred = succ.prev;
 7  final Node<E> newNode = new Node<>(pred, e, succ);
 8  succ.prev = newNode;
 9  if (pred == null)
10    first = newNode;
11  else
12    pred.next = newNode;
13  size++;
14  modCount++;
15}

上述源码解释了如何将一个新的元素插入到链表中。

迭代器 #

LinkedList没有 Iterator 的实现，只有 ListIterator 的实现，里面定义了相当充分的操作元素的方法，由于LinkedList也是List的实现类，故也可调用接口定义的iterator()方法¹，不过其实际上返回的是 LinkedList.ListIterator 实例。

LinkedList调用iterator()的时序图

尽管如此，由于使用LinkedList.iterator()方法返回的是Iterator，其对集合的操作性降低到只有4个方法。由于我们知道其实际返回的是Listiterator，我们可以将该返回值向下转型：

1ListIterator<String> i = (ListIterator<String>) list.iterator();
2// 等价于
3ListIterator<String> listIterator = list.listIterator();
4// 等价于
5ListIterator<String> listIterator1 = list.listIterator(0);

参考如下示例：

 1static void iteratorTest(){
 2  List<String> list = new LinkedList<String>(){{
 3    add("Java");
 4    add("Python");
 5    add("JavaScript");
 6    add("C");
 7  }};
 8  ListIterator<String> i = (ListIterator<String>) list.iterator();
 9  while (i.hasNext()){
10    if (i.next().equals("JavaScript")){
11      i.set("JS");
12    }
13  }
14  i.remove();
15  i.add("C++");
16  // 反向迭代
17  while (i.hasPrevious()){
18    System.out.println(i.previous());
19  }
20  System.out.println("-------");
21  ListIterator<String> iterator = list.listIterator(2);
22  iterator.forEachRemaining(System.out::println);
23}
24/* output:
25C++
26JS
27Python
28Java
29-------
30JS
31C++
32*///:~

ListIterator<E> listIterator(int index);
此方法用于获取 index （含）之后的元素的迭代器

与ArrayList对比 #

ArrayList的优势在于可以利用 index 快速访问集合中的元素，劣势在于对于容量大的集合，插入和删除的效率稍低。

LinkedList基于链表，~~插入和删除操作效率高~~^{并不总这样}；但由于没有元素索引( index )，使用get(int index)和set(int index , E e)的效率稍低²

在LinkedList中，和索引相关的操作有：

 1public E get(int index)
 2
 3public E set(int index, E element)
 4
 5public void add(int index, E element)
 6
 7public E remove(int index)
 8
 9public int indexOf(Object o)  //获取对象首次出现的位置
10
11public int lastIndexOf(Object o)  //获取对象最后出现的位置

除了indexOf和lastIndexOf方法之外，其他的四个方法的实现都和这个方法有关：

 1public void add(int index, E element) {
 2  checkPositionIndex(index);
 3
 4  if (index == size)
 5    linkLast(element);
 6  else
 7    linkBefore(element, node(index));
 8}
 9/**
10 * Returns the (non-null) Node at the specified element index.
11 */
12Node<E> node(int index) {
13  // assert isElementIndex(index);
14
15  if (index < (size >> 1)) {
16    Node<E> x = first;
17    for (int i = 0; i < index; i++)
18      x = x.next;
19    return x;
20  } else {
21    Node<E> x = last;
22    for (int i = size - 1; i > index; i--)
23      x = x.prev;
24    return x;
25  }
26}

可以看到，node(int index)总是从头/尾开始逐一遍历，当集合较大时，这种操作的效率是很低的。

既然如此，LinkedList插入和删除的效率如何高呢？答案就是使用迭代器，由于迭代器持有指针(cursor)，免去了遍历集合获取节点的时间消耗，因而插入和删除只需要修改前后节点的引用即可：

从LinkedList删除一个元素^{from Core Java}

所以，不要在LinkedList中使用带有索引(index)参数的操作，这会大大降低程序的运行效率，若要使用索引，请使用ArrayList。

作为双端队列 #

LinkedList除了实现了List接口之外，还实现了Deque接口，也就是说，LinkedList还是一个双端队列，具体请参照 Queue

这和ArrayList的ListIterator没有实现hasNext()一样，实际上也是可以使用的(接口动态绑定超类方法)，这种情况在集合框架中很常见 ↩︎
LinkedList使用和索引相关的操作get()/set()/add()/remove()的效率是一致的 ↩︎

xf&pl

LinkedList

Node(节点) #

迭代器 #

与ArrayList对比 #

作为双端队列 #