Java LinkedList(单列集合)

LinkedList 是 Java 中实现了 List 接口的一个类，它属于 java.util 包。与 ArrayList 不同，LinkedList 是基于双向链表实现的，适合于频繁进行插入和删除操作的场景。

1. LinkedList 的基本特性

• 基于链表实现：LinkedList 使用双向链表来存储元素，每个节点包含数据部分和指向前后节点的引用。这样，插入和删除操作的效率较高，尤其是在中间或头部进行操作时。
• 支持所有 List 操作：由于 LinkedList 实现了 List 接口，它支持 List 接口中的所有方法，如添加、删除、访问、查询等。
• 支持 Deque 操作：LinkedList 还实现了 Deque 接口，允许它作为双端队列使用，支持在队列的两端进行插入和删除操作。

2. LinkedList 的构造方法

2.1 默认构造方法：

创建一个空的 LinkedList。

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

2.2 从其他集合创建：

可以通过一个 Collection（如 List、Set）来创建一个新的 LinkedList。

LinkedList<String> list = new LinkedList<>(anotherList);

3. LinkedList 的常用方法

LinkedList 继承了 List 接口，因此它具有与 ArrayList 类似的基本操作方法。除此之外，它还提供了 Deque 接口的方法。

3.1 添加元素

• add(E e)：将元素添加到列表的末尾。

java
LinkedList<String> list = new LinkedList<>();
list.add("Apple");
list.add("Banana");

• addFirst(E e)：将元素添加到链表的头部。

list.addFirst("Orange");  // 在头部插入 "Orange"

• addLast(E e)：将元素添加到链表的尾部。

list.addLast("Grapes");  // 在尾部插入 "Grapes"

3.2 访问元素

• get(int index)：返回指定位置的元素。

 - String fruit = list.get(0);  // 获取索引 0 位置的元素，返回 "Apple"

• getFirst()：返回链表的第一个元素。

String firstFruit = list.getFirst();  // 返回 "Apple"

• getLast()：返回链表的最后一个元素。

String lastFruit = list.getLast();  // 返回 "Grapes"

3.3 删除元素

• remove(int index)：删除指定位置的元素。

list.remove(1);  // 删除索引 1 位置的元素

• removeFirst()：删除链表的第一个元素。

list.removeFirst();  // 删除头部的元素（"Apple"）

• removeLast()：删除链表的最后一个元素。

list.removeLast();  // 删除尾部的元素（"Grapes"）

• remove(Object o)：删除指定元素，删除首次出现的元素。

list.remove("Banana");  // 删除 "Banana"

3.4 查询元素

• contains(Object o)：检查链表中是否包含指定元素。

boolean containsApple = list.contains("Apple");  // 返回 true 或 false

• indexOf(Object o)：返回指定元素首次出现的位置。

int index = list.indexOf("Grapes");  // 返回元素 "Grapes" 的索引位置

• isEmpty()：判断链表是否为空。

boolean isEmpty = list.isEmpty();  // 返回 true 或 false

3.5 其他操作

• size()：返回链表中元素的数量。

int size = list.size();  // 返回链表的元素个数

• clear()：清空链表，删除所有元素。

list.clear();  // 清空链表

• peek()：查看链表的第一个元素但不删除。

String first = list.peek();  // 查看第一个元素，不删除

• peekFirst()：查看链表的第一个元素但不删除。

String first = list.peekFirst();  // 查看第一个元素

• peekLast()：查看链表的最后一个元素但不删除。

String last = list.peekLast();  // 查看最后一个元素

• poll()：查看并删除链表的第一个元素。

String first = list.poll();  // 查看并删除第一个元素

4. LinkedList 的性能特点

• 访问性能：由于 LinkedList 基于链表实现，随机访问元素的时间复杂度是 O(n)，这比 ArrayList 的 O(1) 访问效率要低。因此，在频繁进行元素访问的场景中，LinkedList 性能较差。
• 插入和删除性能：LinkedList 的插入和删除操作比 ArrayList 高效，尤其是在链表的头部或中间进行插入和删除时，时间复杂度是 O(1)，因为仅需要修改前后节点的引用即可。

5. LinkedList 与 ArrayList 的对比

• ArrayList：基于数组实现，适合于频繁随机访问的场景，适合在尾部插入或删除元素，但在头部或中间插入/删除元素时，性能较差。
• LinkedList：基于双向链表实现，适合频繁进行插入和删除的场景，特别是在列表的头部和中间进行操作时更加高效。但访问元素的时间复杂度是O(n)，因此频繁访问时性能较差。

6. 常见的使用场景

• 频繁插入和删除：LinkedList 是一个很好的选择，特别是在头部和中间进行插入和删除时，它的性能优于 ArrayList。
• 双端队列操作：由于 LinkedList 实现了 Deque 接口，可以方便地实现双端队列的操作，如在队列两端插入和删除元素。

7. 总结

• LinkedList 是一个基于双向链表的集合类，适合用于频繁进行插入和删除操作的场景。 它提供了比 ArrayList 更好的插入/删除性能，尤其是在链表的头部和中间。
• 与 ArrayList 相比，LinkedList 的元素访问速度较慢，因为需要遍历链表来找到指定位置的元素。
  适合在需要频繁操作头尾元素的场景下使用，如双端队列（Deque）等。