LinkedList 是 Java 集合框架中实现了 List、Deque 和 Queue 接口的类，它基于双向链表实现，能够高效地支持插入和删除操作。与 ArrayList 基于动态数组不同，LinkedList 在插入和删除元素时，性能较优，但随机访问性能较差。

1. LinkedList 的基本特性

• 基于链表实现：LinkedList 使用双向链表来存储元素，每个节点都包含对前一个和下一个节点的引用。
• 元素插入和删除性能：在头部或尾部插入和删除元素时，LinkedList 比 ArrayList 更加高效，时间复杂度是 O(1)。
• 随机访问性能差：由于链表结构不能直接按索引访问元素，需要遍历链表，因此访问某个元素的时间复杂度是 O(n)。
• 允许存储 null：LinkedList 可以存储 null 元素。
• 双向链表：每个节点包含两个引用：一个指向前一个节点，一个指向下一个节点，这使得 LinkedList 支持从两端操作（如双端队列 Deque）。

2. LinkedList 的常用构造函数

// 默认构造函数，创建一个空的 LinkedList
LinkedList<E> list = new LinkedList<>();

// 基于另一个集合创建 LinkedList
LinkedList<E> list = new LinkedList<>(Collection<? extends E> c);

3. LinkedList 常用方法

3.1 添加元素

• add(E e)：将元素添加到列表的末尾。
• addFirst(E e)：将元素添加到列表的头部。
• addLast(E e)：将元素添加到列表的尾部。
• offer(E e)：将元素插入队列末尾（与 add(E e) 类似，但用于队列接口）。

LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.addFirst("Banana");  // 插入到头部
list.addLast("Orange");   // 插入到尾部

3.2 删除元素

• remove()：移除并返回列表中的第一个元素（队列操作）。
• removeFirst()：移除并返回列表中的第一个元素。
• removeLast()：移除并返回列表中的最后一个元素。
• remove(Object o)：删除第一次出现的指定元素。
• clear()：清空 LinkedList 中的所有元素。

list.remove();          // 删除并返回第一个元素
list.removeFirst();     // 删除并返回第一个元素
list.removeLast();      // 删除并返回最后一个元素
list.remove("Banana");  // 删除 "Banana"
list.clear();           // 清空 LinkedList

3.3 访问元素

• get(int index)：获取指定索引位置的元素。
• getFirst()：获取列表中的第一个元素。
• getLast()：获取列表中的最后一个元素。
• peek()：获取并返回第一个元素，但不删除（用于队列操作）。
• poll()：获取并删除第一个元素（用于队列操作）。

String firstFruit = list.getFirst(); // 获取第一个元素
String lastFruit = list.getLast();  // 获取最后一个元素
String fruit = list.get(1);         // 获取指定索引位置的元素

3.4 查询元素

• contains(Object o)：检查列表是否包含某个元素。
• indexOf(Object o)：返回指定元素首次出现的索引，如果没有找到返回 -1。
• lastIndexOf(Object o)：返回指定元素最后一次出现的索引。
• size()：返回 LinkedList 中的元素个数。
• isEmpty()：判断 LinkedList 是否为空。

boolean containsApple = list.contains("Apple"); // 检查是否包含 "Apple"
int index = list.indexOf("Banana"); // 获取 "Banana" 的索引
int size = list.size(); // 获取 LinkedList 的大小
boolean isEmpty = list.isEmpty(); // 判断是否为空

3.5 遍历元素

• 使用 for-each 循环：

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

• 使用 Iterator：

Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

• 使用 for 循环：

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

3.6 转换为数组

• toArray()：将 LinkedList 转换为数组。

Object[] array = list.toArray();

• toArray(T[] a)：将 LinkedList 转换为指定类型的数组。

String[] array = list.toArray(new String[0]);

3.7 其他常用方法

• removeAll(Collection<?> c)：删除列表中所有与给定集合 c 相同的元素。
• retainAll(Collection<?> c)：保留列表中所有与给定集合 c 相同的元素。
• subList(int fromIndex, int toIndex)：返回指定范围的子列表（不包括 toIndex）。
• offerFirst(E e)：将元素添加到队列头部。
• offerLast(E e)：将元素添加到队列尾部。

4. LinkedList 的性能

• 访问元素：由于 LinkedList 是基于链表结构的，访问指定索引的元素需要遍历链表，因此时间复杂度是 O(n)。
• 插入和删除操作：在链表的头部和尾部插入或删除元素的时间复杂度是 O(1)，而在链表中间插入或删除元素需要遍历链表，时间复杂度是 O(n)。

5. LinkedList 与 ArrayList 的比较

特性	LinkedList	ArrayList
底层实现	双向链表	动态数组
访问元素	随机访问慢，O(n)	随机访问快，O(1)
插入/删除操作	在头部或尾部插入删除快，O(1)	在头部或中间插入删除慢，O(n)
内存占用	每个节点需要额外存储前后节点引用	内存较为紧凑，只需要存储数据
适用场景	频繁插入和删除操作，尤其是在头尾位置	频繁读取操作，少量插入和删除操作

6. 线程安全问题

LinkedList 不是线程安全的。如果需要在多线程环境中使用 LinkedList，你可以通过以下方法保证线程安全：

• 使用 Collections.synchronizedList() 将 LinkedList 包装成线程安全的列表。
• 使用 CopyOnWriteArrayList，它是线程安全的 List 实现，适用于读取频繁、修改较少的场景。

List<String> synchronizedList = Collections.synchronizedList(new LinkedList<>());

7. 使用 LinkedList 的场景

LinkedList 适合以下场景：

• 频繁插入和删除操作：特别是当插入和删除操作发生在链表的头部或尾部时，LinkedList 的性能优于 ArrayList。
• 双端队列操作（Deque）：由于 LinkedList 实现了 Deque 接口，它可以用作双端队列，支持从两端进行插入和删除。
• 队列操作：LinkedList 也实现了 Queue 接口，适用于需要按顺序处理元素的场景，如任务调度、消息队列等。

小结

LinkedList 是一个灵活且高效的集合类，特别适用于需要频繁插入和删除元素的场景。尽管它的随机访问性能较差，但在链表头部和尾部的插入与删除操作非常高效。如果需要优化随机访问性能，可以考虑使用 ArrayList。对于队列、栈和双端队列等应用场景，LinkedList 也是一个很好的选择。更多详细内容请关注其他相关文章。