java linkedlist怎么用

Java LinkedList 使用详解

Java 中的 LinkedList 是一个非常重要的数据结构，它实现了 List 接口，并且允许存储重复元素，与 ArrayList 不同，LinkedList 在内部使用双向链表来存储元素，这使得它在插入和删除操作上具有更高的效率，尤其是在频繁操作列表中间元素时，下面我们将详细介绍 LinkedList 的使用方法、常见操作以及一些注意事项。

LinkedList 的基本概念

LinkedList 是一个线性数据结构，由一系列节点组成，每个节点包含两个部分：数据部分和指向前后节点的引用，这种结构使得 LinkedList 在动态增删元素时具有优势，因为不需要像数组那样移动大量元素。

主要特点：

• 双向链表：每个节点包含对前一个节点和后一个节点的引用，便于双向遍历。
• 动态大小：可以根据需要动态增加或减少元素，内存利用率高。
• 高效的插入和删除：在已知位置的情况下，插入和删除操作的时间复杂度为 O(1)。
• 较低的缓存命中率：由于节点在内存中不连续，可能导致缓存命中率较低，影响遍历性能。

LinkedList 的常用构造方法

LinkedList 提供了多种构造方法，以下是常用的几种：

构造方法	描述
LinkedList()	创建一个空的 LinkedList。
LinkedList(Collection<? extends E> c)	使用指定的集合 c 来初始化 LinkedList。

示例代码：

// 创建一个空的 LinkedList
LinkedList<String> list = new LinkedList<>();
// 使用另一个集合初始化 LinkedList
ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("A");
arrayList.add("B");
LinkedList<String> linkedList = new LinkedList<>(arrayList);

LinkedList 的常用方法

LinkedList 继承自 AbstractSequentialList，并实现了 List 接口，因此它拥有 List 接口的所有方法，同时还有一些特有的方法，下面介绍一些常用的方法：

1 添加元素的方法

方法名	描述
add(E e)	将元素 e 添加到列表的末尾。
add(int index, E element)	在指定的位置 index 插入元素 element。
addAll(Collection<? extends E> c)	将集合 c 中的所有元素添加到列表的末尾。
addAll(int index, Collection<? extends E> c)	将集合 c 中的所有元素在指定的位置 index 插入。
addFirst(E e)	将元素 e 添加到列表的开头。
addLast(E e)	将元素 e 添加到列表的末尾。

示例代码：

LinkedList<String> list = new LinkedList<>();
// 添加到末尾
list.add("A");
list.add("B");
// 在指定位置插入
list.add(1, "C"); // 列表变为 [A, C, B]
// 添加到开头和末尾
list.addFirst("D"); // 列表变为 [D, A, C, B]
list.addLast("E");  // 列表变为 [D, A, C, B, E]

2 删除元素的方法

方法名	描述
remove()	移除并返回列表的第一个元素。
remove(int index)	移除指定位置 index 的元素。
remove(Object o)	移除列表中首次出现的指定元素 o。
removeFirst()	移除并返回列表的第一个元素（等同于 remove()）。
removeLast()	移除并返回列表的最后一个元素。
removeAll(Collection<?> c)	移除列表中所有包含在集合 c 中的元素。

示例代码：

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
// 移除第一个元素
String first = list.remove(); // "A"
// 移除指定位置的元素
String removed = list.remove(1); // "B"
// 移除特定元素
boolean isRemoved = list.remove("C"); // true
// 移除第一个和最后一个元素
String firstElement = list.removeFirst(); // "A"
String lastElement = list.removeLast();  // "C"

3 访问元素的方法

方法名	描述
get(int index)	返回指定位置 index 的元素。
getFirst()	返回列表的第一个元素。
getLast()	返回列表的最后一个元素。
peek()	返回列表的第一个元素，但不移除它。
peekFirst()	同 peek()。
peekLast()	返回列表的最后一个元素，但不移除它。

示例代码：

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
// 获取指定位置的元素
String element = list.get(1); // "B"
// 获取第一个和最后一个元素
String first = list.getFirst(); // "A"
String last = list.getLast();   // "C"

4 查找元素的方法

方法名	描述
contains(Object o)	判断列表是否包含元素 o。
indexOf(Object o)	返回元素 o 在列表中第一次出现的位置索引，若不存在则返回 -1。
lastIndexOf(Object o)	返回元素 o 在列表中最后一次出现的位置索引，若不存在则返回 -1。

示例代码：

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("A");
// 判断是否包含元素
boolean hasA = list.contains("A"); // true
// 获取元素第一次出现的位置
int firstIndex = list.indexOf("A"); // 0
// 获取元素最后一次出现的位置
int lastIndex = list.lastIndexOf("A"); // 2

5 修改元素的方法

方法名	描述
set(int index, E element)	将指定位置 index 的元素替换为 element。
replace(E oldElement, E newElement)	用新元素 newElement 替换旧元素 oldElement。

示例代码：

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
// 替换指定位置的元素
list.set(1, "D"); // 列表变为 [A, D, C]
// 替换元素
list.replace("D", "E"); // 列表变为 [A, E, C]

6 其他常用方法

方法名	描述
size()	返回列表中的元素数量。
isEmpty()	判断列表是否为空。
clear()	清空列表中的所有元素。
clone()	返回列表的浅拷贝。
toArray()	将列表转换为数组。
toArray(T[] a)	将列表转换为指定类型的数组。

示例代码：

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
// 获取列表大小
int size = list.size(); // 2
// 判断是否为空
boolean empty = list.isEmpty(); // false
// 清空列表
list.clear();
// 克隆列表
LinkedList<String> cloneList = (LinkedList<String>) list.clone();

LinkedList 的遍历方式

由于 LinkedList 是双向链表，可以通过多种方式进行遍历：

1 使用迭代器（Iterator）

LinkedList<String> list = new LinkedList<>();
list.add("A");
list.add("B");
list.add("C");
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}

2 使用增强 for 循环

for (String element : list) {
    System.out.println(element);
}

3 使用索引遍历（不推荐，效率较低）

for (int i = 0; i < list.size(); i++) {
    String element = list.get(i);
    System.out.println(element);
}

4 使用 forEach 方法（Java 8 及以上）

list.forEach(element -> System.out.println(element));

LinkedList 与 ArrayList 的区别

特性	ArrayList	LinkedList
内部实现	动态数组	双向链表
插入/删除效率	低（需要移动元素）	高（只需调整指针）
访问效率	高（支持随机访问）	低（需要顺序遍历）
内存占用	较低（连续内存）	较高（每个节点有额外引用）
适用场景	频繁读取，较少插入/删除	频繁插入/删除，较少读取

使用 LinkedList 的注意事项

• 随机访问性能差：由于 LinkedList 不支持随机访问，使用 get(index) 方法时需要从头或尾遍历到指定位置，时间复杂度为 O(n)，不适用于频繁的随机访问操作。
• 内存开销较大：每个节点需要存储前后节点的引用，导致额外的内存开销，尤其在存储大量小对象时更为明显。
• 线程不安全：LinkedList 不是线程安全的，如果在多线程环境下使用，需要进行同步处理或使用 Collections.synchronizedList 包装。
• 不适合存储大量数据：由于内存开销和访问效率的原因，对于需要存储大量数据且频繁访问的场景，建议使用 ArrayList 或其他更适合的数据结构。

实际应用案例

1 实现队列和栈

由于 LinkedList 同时支持从头到尾和从尾到头的快速插入和删除操作，因此非常适合用来实现队列和栈，Java 中的 LinkedList 可以作为 Deque（双端队列）的实现基础。

示例：实现一个简单的队列

LinkedList<String> queue = new LinkedList<>();
// 入队
queue.addLast("A");
queue.addLast("B");
queue.addLast("C");
// 出队
String firstElement = queue.removeFirst(); // "A"

示例：实现一个简单的栈

LinkedList<String> stack = new LinkedList<>();
// 压栈
stack.addFirst("A");
stack.addFirst("B");
stack.addFirst("C");
// 弹栈
String topElement = stack.removeFirst(); // "C"

2 频繁插入和删除的场景

假设有一个应用需要频繁在列表的中间位置插入或删除元素,例如实现一个任务调度系统，任务可能会随时被添加或取消，在这种情况下，使用 LinkedList 会比 ArrayList 更高效，因为插入和删除操作的时间复杂度更低。

示例：任务调度系统

LinkedList<String> tasks = new LinkedList<>();
tasks.add("Task1");
tasks.add("Task2");
tasks.add("Task3");
// 在 Task2 之后插入一个新任务
tasks.add(2, "NewTask"); // [Task1, Task2, NewTask, Task3]
// 移除 Task2
tasks.remove("Task2"); // [Task1, NewTask, Task3]

LinkedList 是 Java 中一个非常灵活且功能强大的数据结构，尤其适用于需要频繁插入和删除操作的场景，由于其随机访问性能较差和较高的内存开销，在选择使用时需要根据具体的应用场景权衡利弊，理解并熟练掌握 LinkedList 的各种方法和使用技巧，能够在实际开发中提高代码的效率和可维护性。

FAQs

Q1: LinkedList 和 ArrayList 哪个更适合用于频繁的插入和删除操作？

A1: LinkedList 更适合用于频繁的插入和删除操作，因为 LinkedList 使用双向链表实现，插入和删除操作只需要调整节点的引用，时间复杂度为 O(1)，尤其在列表的开头和结尾操作时效率更高，而 ArrayList 是基于动态数组实现的，插入和删除操作可能需要移动大量元素，时间复杂度为 O(n)，在频繁进行这些操作时性能较低。

Q2: 在使用 LinkedList 时，如何避免因频繁调用 get(index) 导致的性能问题？

A2: 为了避免频繁调用 get(index) 导致的性能问题，可以采用以下策略：

1. 尽量减少随机访问：如果业务逻辑允许，尽量通过迭代器或增强 for 循环进行顺序遍历，而不是随机访问特定索引的元素。

2. 缓存迭代器：在需要多次遍历列表时，可以缓存迭代器，避免每次都创建新的迭代器实例。

3. 考虑使用其他数据结构：如果确实需要频繁的随机访问，可以考虑使用 ArrayList，它在随机访问方面具有更高的效率，也可以根据具体需求选择其他适合的数据结构，如哈希表、树等。