Java LinkedList 指南

1. 简介

LinkedList 是 List 和 Deque 接口的双向链表实现。它实现了所有可选的列表操作，并允许所有元素（包括 null）。

2. 特性

以下是 LinkedList 的重要属性

• 对列表进行索引的操作将从列表的开头或结尾遍历，具体取决于哪个更靠近指定的索引
• 它不是 同步的
• 它的 Iterator 和 ListIterator 迭代器是 快速失败的（这意味着在迭代器的创建之后，如果列表被修改，则会抛出 ConcurrentModificationException）
• 每个元素都是一个节点，它保留对下一个和前一个节点的引用
• 它维护插入顺序

虽然 LinkedList 不是同步的，但我们可以通过调用 Collections.synchronizedList 方法来获取其同步版本，例如

List list = Collections.synchronizedList(new LinkedList(...));

3. 与 ArrayList 的比较

虽然它们都实现了 List 接口，但它们具有不同的语义 - 这将肯定影响选择使用哪个接口的决定。

3.1. 结构

ArrayList 是一个基于索引的数据结构，由 Array 支持。它以 O(1) 的性能提供对其元素的随机访问。

另一方面，LinkedList 将其数据存储为元素列表，并且每个元素都链接到其前一个和下一个元素。在这种情况下，查找项目的操作执行时间等于 O(n)。

3.2. 操作

在一个 LinkedList 中插入、添加和删除项目更快，因为不需要调整数组大小或更新索引，当在集合内的某个任意位置添加元素时，只需要更改周围元素的引用。

3.3. 内存使用

LinkedList 比 ArrayList 消耗更多的内存，因为 LinkedList 中的每个节点都存储两个引用，一个用于其前一个元素，一个用于其下一个元素，而 ArrayList 仅持有数据及其索引。

4. 初始化 LinkedList 的不同方法

我们可以使用两个构造函数之一初始化 LinkedList。此外，我们使用构造函数来初始化类的新的实例。

4.1. 初始化一个空的 LinkedList

我们使用空的 LinkedList() 构造函数来初始化一个空的 LinkedList。

让我们演示一个使用 泛型对 String 参数化的 LinkedList 的示例。

让我们使用 JUnit 5 测试来验证空的 LinkedList

@Test
public void whenInitializingLinkedList_ShouldReturnEmptyList() throws Exception {
    LinkedList<String> linkedList=new LinkedList<String>();     
    Assertions.assertTrue(linkedList.isEmpty());
}

相应地，我们可以将 String 元素添加到此列表中

linkedList.addFirst("one");
linkedList.add("two");
linkedList.add("three");

同样，我们可以初始化任何类类型的 LinkedList。

4.2. 从集合初始化 LinkedList

当我们需要初始化一个 LinkedList 时，其元素是给定 Collection 的元素时，我们也可以使用 LinkedList(Collection<? extends E> c) 构造函数。它以 Collection 的迭代器返回它们的顺序添加元素。

让我们演示一个使用泛型参数化为 Integer 的 LinkedList 的例子。 但是，首先，我们创建一个 Collection，用作我们在调用构造函数时使用的参数。 让我们创建一个参数化为 Integer 的 ArrayList 类型的 Collection，并使用泛型

ArrayList<Integer> arrayList = new ArrayList<Integer>(3);

 arrayList.add(Integer.valueOf(1));
 arrayList.add(Integer.valueOf(2));
 arrayList.add(Integer.valueOf(3));

随后，让我们调用构造函数来初始化一个 LinkedList

LinkedList<Integer> linkedList=new LinkedList<Integer>(arrayList);

再次，让我们使用 JUnit 5 测试来验证 LinkedList 从其构造的 ArrayList 中派生其元素

@Test
public void whenInitializingListFromCollection_ShouldReturnCollectionsElements() throws Exception {
    ArrayList<Integer> arrayList=new ArrayList<Integer>(3);
        
    arrayList.add(Integer.valueOf(1));
    arrayList.add(Integer.valueOf(2));
    arrayList.add(Integer.valueOf(3));
 
    LinkedList<Integer> linkedList=new LinkedList<Integer>(arrayList);

    Object[] linkedListElements = linkedList.toArray();
    Object[] collectionElements = arrayList.toArray();

    Assertions.assertArrayEquals(linkedListElements,collectionElements);
}

同样，我们可以使用任何 Java Collection 来初始化 LinkedList。 因此，从 Collection 初始化 LinkedList 的元素是 Collection 元素的类型。

5. 用法

以下是一些代码示例，展示了如何使用 LinkedList

5.1. 创建

LinkedList<Object> linkedList = new LinkedList<>();

5.2. 添加元素

除了标准的 add() 和 addAll() 方法外，LinkedList 还实现了 List 和 Deque 接口，您还可以找到 addFirst() 和 addLast()，它们分别在开头或结尾添加一个元素。

5.3. 移除元素

与元素添加类似，此列表实现提供了 removeFirst() 和 removeLast()。

此外，还有便捷的方法，例如 removeFirstOccurence() 和 removeLastOccurence()，它们返回一个 boolean（如果集合包含指定的元素，则返回 true）。

5.4. 队列操作

Deque 接口提供类似队列的行为（实际上，Deque 扩展了 Queue 接口）

linkedList.poll();
linkedList.pop();

这些方法检索第一个元素并将其从列表中删除。

poll() 和 pop() 的区别在于，pop 在空列表上会抛出 NoSuchElementException()，而 poll 返回 null。 pollFirst() 和 pollLast() API 也可用。

例如，以下是如何使用 push API 的

linkedList.push(Object o);

它将元素作为集合的头部插入。

LinkedList 还有许多其他方法，其中大部分对于已经使用过 Lists 的用户来说应该很熟悉。 Deque 提供的其他方法可能是“标准”方法的便捷替代方案。

完整的文档可以在 这里 找到。

6. 在 LinkedList 的特定位置插入元素

当我们想在 LinkedList 的特定位置添加元素时，我们有几种方法选择

让我们演示如何使用这些方法中的每一个。 此外，让我们初始化一个空列表

LinkedList<String> linkedList=new LinkedList<String>();

随后，让我们使用方法 addFirst(E e) 添加第一个元素

linkedList.addFirst("one");

虽然我们可以通过重复调用 add(E e) 方法来构建列表，但我们想演示在特定位置添加元素的各种选项。 因此，让我们使用方法 addLast(E e) 在列表末尾添加最后一个元素

linkedList.addLast("three");

让我们调用 add(E e) 方法将一个元素添加到到目前为止构建的列表的末尾

linkedList.add("four");

LinkedList 使用基于 0 的索引，这意味着第一个元素位于索引 0，第二个元素位于索引 1，第三个元素位于索引 2，依此类推。为了创建一个序列，让我们使用 add(int index, E element) 在索引位置 1 处添加元素“two”。

linkedList.add(1,"two");

让我们使用 JUnit 5 测试来验证我们是否在 LinkedList 中添加了元素，且位于特定的各自位置。

@Test
public void whenAddingElementsInLinkedListAtSpecificPosition_ShouldReturnElementsInProperSequence() throws Exception {
    LinkedList<String> linkedList=new LinkedList<String>();
        
    linkedList.addFirst("one");
    linkedList.addLast("three");
    linkedList.add("four");
    linkedList.add(1,"two");

    Object[] linkedListElements = linkedList.toArray();
    Object[] expectedListElements = {"one","two","three","four"};

    Assertions.assertArrayEquals(linkedListElements,expectedListElements);
}

JUnit 测试应该通过，从而验证我们在 LinkedList 中添加了元素到特定的位置。

7. 将数组转换为 LinkedList

在某些情况下，我们可能以数组的形式拥有数据，并且需要将其作为 LinkedList 来处理，以便进行高效的插入或利用 LinkedList 提供的 Deque 操作。在 Java 中，将数组转换为 LinkedList 非常简单。

首先，让我们从一个包含元素的示例数组开始。

String[] array = { "apple", "banana", "cherry", "date" };

我们可以通过 **将数组传递给 Arrays.asList() 方法，然后从结果 List 创建一个新的 LinkedList** 来将此数组转换为 LinkedList。

List<String> list = Arrays.asList(array);  // Convert array to List
LinkedList<String> linkedList = new LinkedList<>(list);

现在 linkedList 包含来自原始数组的所有元素，我们可以对其使用任何 LinkedList 操作。

将数组转换为 LinkedList 的另一种方法是 **使用 Collections.addAll() 方法**。此方法提供了一种简单的方法，可直接将数组中的所有元素添加到 LinkedList 中。

首先，我们创建一个空的 LinkedList。然后，我们使用 Collections.addAll() 方法将数组中的每个元素添加到 LinkedList 中。

LinkedList<String> linkedList = new LinkedList<>();
Collections.addAll(linkedList, array);

完成此操作后，linkedList 将包含来自数组的所有元素，并且它会保留顺序。

8. 结论

ArrayList 通常是默认的 List 实现。

然而，在某些用例中，使用 LinkedList 会更合适，例如优先考虑恒定插入/删除时间（例如，频繁的插入/删除/更新），而不是恒定访问时间和有效的内存使用。