【Java 基础篇】Java LinkedList 详解：数据结构的灵活伙伴_new linkedlist<>()

在 Java 编程中，数据结构起着至关重要的作用。这些数据结构可以帮助我们组织和管理数据，使我们的代码更加高效和可维护。其中之一是 LinkedList，它是一个灵活的数据结构，允许我们高效地进行插入和删除操作。本篇博客将深入探讨 Java 中的 LinkedList，从基础概念到高级用法，为您呈现全面的信息。

1. 什么是 LinkedList？

LinkedList 是 Java 中的一个双向链表数据结构。它由一系列节点组成，每个节点包含数据元素和指向前一个节点和后一个节点的引用。这种结构使 LinkedList 在插入和删除操作方面非常高效，因为它不需要像数组一样重新分配内存空间。

2. 创建和初始化 LinkedList

在 Java 中，可以使用以下方式创建和初始化 LinkedList：

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

这将创建一个空的 LinkedList 对象，用于存储字符串元素。您还可以使用现有集合来初始化 LinkedList，例如：

List<String> stringList = new ArrayList<>();
stringList.add("苹果");
stringList.add("香蕉");

LinkedList<String> linkedList = new LinkedList<>(stringList);
1
2
3
4
5

这将创建一个包含 “苹果” 和 “香蕉” 两个元素的 LinkedList。

3. 基本操作

3.1 添加元素

3.1.1 add 方法

要向 LinkedList 中添加元素，您可以使用 add 方法。它将元素添加到列表的末尾。

linkedList.add("橙子");
1

3.1.2 在指定位置添加元素

您还可以使用 add 方法在指定位置插入元素。指定位置是通过索引来确定的，索引从 0 开始。

linkedList.add(1, "葡萄"); // 在索引 1 处插入 "葡萄"
1

3.2 获取元素

3.2.1 get 方法

要获取 LinkedList 中的元素，可以使用 get 方法，指定元素的索引。

String fruit = linkedList.get(0); // 获取第一个元素
1

3.3 删除元素

3.3.1 remove 方法

要删除 LinkedList 中的元素，可以使用 remove 方法。可以指定要删除的元素或要删除的元素的索引。

linkedList.remove("香蕉"); // 删除 "香蕉"
linkedList.remove(1); // 删除索引 1 处的元素
1
2

4. 遍历 LinkedList

遍历 LinkedList 可以使用不同的方式，最常见的是使用 for-each 循环或迭代器。

4.1 使用 for-each 循环

for (String fruit : linkedList) {
    System.out.println(fruit);
}
1
2
3

4.2 使用迭代器

Iterator<String> iterator = linkedList.iterator();
while (iterator.hasNext()) {
    String fruit = iterator.next();
    System.out.println(fruit);
}
1
2
3
4
5

5. 特殊操作

5.1 在开头和末尾添加元素

LinkedList 允许在开头和末尾高效添加元素。

5.1.1 在开头添加元素

linkedList.addFirst("草莓");
1

5.1.2 在末尾添加元素

linkedList.addLast("樱桃");
1

5.2 在特定位置插入元素

LinkedList 也允许在特定位置插入元素。

linkedList.add(2, "葡萄"); // 在索引 2 处插入 "葡萄"
1

5.3 替换元素

您可以使用 set 方法来替换 LinkedList 中的元素。

linkedList.set(1, "蓝莓"); // 将索引 1 处的元素替换为 "蓝莓"
1

6. 性能考虑

6.1 与 ArrayList 的比较

在考虑使用 LinkedList 时，需要权衡性能。与 ArrayList 相比，LinkedList 在插入和删除操作方面通常更快，因为它不需要移动大量元素。然而，它在随机访问元素时的性能较差，因为需要从头部或尾部开始遍历链表。

6.2 时间复杂度

• 添加和删除元素：平均时间复杂度为 O(1)（在已知位置的情况下），最坏情况下为 O(n)（如果需要遍历整个链表）。
• 获取元素：平均时间复杂度为 O(n/2)（在平均情况下，需要遍历一半的链表）。
• 随机访问元素：最坏情况下为 O(n)（需要从头或尾遍历整个链表）。

7. 使用注意事项

在使用 LinkedList 时，需要注意以下事项：

• LinkedList 不是线程安全的。如果在多个线程中使用，必须采取适当的同步措施，或者考虑使用线程安全的替代品。
• 避免过多的随机访问，因为它的性能较差。如果需要频繁的随机访问，请考虑使用 ArrayList。
• 谨慎使用大型 LinkedList，因为它可能会占用大量内存。

8. 高级用法

8.1 双向链表

LinkedList 是一种双向链表的实现，这意味着每个节点都包含指向前一个节点和后一个节点的引用。这种双向连接使得在链表中向前和向后遍历都非常高效。以下是关于双向链表的高级用法示例：

8.1.1 逆序遍历链表

LinkedList 的双向性质使得逆序遍历变得容易。您可以从链表的尾部开始遍历，不断跟随前一个节点的引用，直到达到链表的头部。

LinkedList<String> linkedList = new LinkedList<>();
// 添加元素到链表
// ...
// 逆序遍历链表
ListIterator<String> iterator = linkedList.listIterator(linkedList.size());
while (iterator.hasPrevious()) {
    String item = iterator.previous();
    System.out.println(item);
}
1
2
3
4
5
6
7
8
9

8.1.2 在特定位置插入元素

双向链表的特性使得在特定位置插入元素更加高效，因为您可以从两个方向进行遍历。这可以在需要在链表中间插入元素时提供性能优势。

LinkedList<String> linkedList = new LinkedList<>();
// 添加元素到链表
// ...
// 在中间位置插入元素
ListIterator<String> iterator = linkedList.listIterator(linkedList.size() / 2); // 在中间位置开始
iterator.add("新元素");
1
2
3
4
5
6

8.2 循环链表

LinkedList 也可以用作循环链表，即链表的最后一个节点指向第一个节点，形成一个闭环。这种结构在某些算法和数据结构中非常有用，例如循环队列。

LinkedList<String> circularList = new LinkedList<>();
circularList.add("元素1");
circularList.add("元素2");
circularList.add("元素3");

// 构建循环链表，将最后一个元素指向第一个元素
circularList.getLast().setNext(circularList.getFirst());

// 遍历循环链表
Node<String> currentNode = circularList.getFirst();
do {
    System.out.println(currentNode.getData());
    currentNode = currentNode.getNext();
} while (currentNode != circularList.getFirst());
1
2
3
4
5
6
7
8
9
10
11
12
13
14

8.3 链表作为队列和栈

LinkedList 可以用作队列和栈的实现。它支持队列的先进先出（FIFO）和栈的后进先出（LIFO）操作。以下是如何使用 LinkedList 实现队列和栈的示例：

8.3.1 使用链表实现队列

LinkedList<String> queue = new LinkedList<>();
// 入队
queue.offer("元素1");
queue.offer("元素2");
// 出队
String item = queue.poll();
1
2
3
4
5
6

8.3.2 使用链表实现栈

LinkedList<String> stack = new LinkedList<>();
// 入栈
stack.push("元素1");
stack.push("元素2");
// 出栈
String item = stack.pop();
1
2
3
4
5
6

这些高级用法展示了 LinkedList 在各种场景下的灵活性和功能。根据您的需求，您可以充分利用其双向链表的特性来解决问题。

9. 示例代码

以下是一些使用 LinkedList 的示例代码：

// 创建一个 LinkedList
LinkedList<String> linkedList = new LinkedList<>();

// 添加元素
linkedList.add("苹果");
linkedList.add("香蕉");

// 获取元素
String fruit = linkedList.get(0);

// 删除元素
linkedList.remove("香蕉");

// 遍历 LinkedList
for (String item : linkedList) {
    System.out.println(item);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

10. 总结

LinkedList 是 Java 中强大的数据结构，它在插入和删除操作方面非常高效。但是，在随机访问元素时性能较差，因此需要谨慎选择使用。希望本篇博客能够帮助您更好地理解和使用 LinkedList，并在编写 Java 代码时做出明智的选择。无论您是初学者还是有经验的开发者，掌握 LinkedList 都将为您的编程旅程增添新的工具和技巧。