java 中 LinkedList 类

LinkedList 是 Java 集合框架中的一个类，它实现了 List 和 Deque 接口，提供了一个双向链表的实现。与其他集合类（如 ArrayList）不同，LinkedList 使用链表结构来存储元素，因此它在插入和删除操作上比数组结构（如 ArrayList）有一定优势，特别是在涉及到中间插入或删除时。

1. LinkedList 类概述

LinkedList 是 Java 中常用的集合类之一，它是一个基于双向链表的实现，支持：

List 接口的所有操作，如添加、删除、查找、遍历等。
Deque 接口的操作，允许将元素添加到队列的两端（即头部或尾部），支持栈和队列的操作。

2. LinkedList 常见的构造方法

LinkedList()：创建一个空的链表。
LinkedList(Collection<? extends E> c)：通过将指定集合中的元素加入到链表中来创建链表。

例如：

LinkedList<Integer> list = new LinkedList<>();
LinkedList<Integer> listFromCollection = new LinkedList<>(Arrays.asList(1, 2, 3, 4));

3. LinkedList 的常见操作

(1) 添加元素

add(E e)：将元素添加到链表的尾部。
addFirst(E e)：将元素添加到链表的头部。
addLast(E e)：将元素添加到链表的尾部（add() 的默认行为）。
offer(E e)：与 add() 类似，但如果队列满了，返回 false，而 add() 会抛出异常。
offerFirst(E e)：将元素添加到链表的头部。
offerLast(E e)：将元素添加到链表的尾部。

LinkedList<Integer> list = new LinkedList<>();
list.add(10);      // 添加到尾部
list.addFirst(5);  // 添加到头部
list.addLast(15);  // 添加到尾部

(2) 删除元素

remove()：删除并返回链表的头部元素。
remove(int index)：移除此列表中指定位置处的元素。
removeFirst()：删除并返回链表的头部元素。
removeLast()：删除并返回链表的尾部元素。
poll()：删除并返回链表的头部元素，若链表为空，则返回 null。
pollFirst()：删除并返回链表的头部元素，若链表为空，则返回 null。
pollLast()：删除并返回链表的尾部元素，若链表为空，则返回 null。

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.addFirst(5);
list.addLast(15);

System.out.println(list.remove());    // 删除并返回头部元素 5
System.out.println(list.removeFirst());  // 删除并返回头部元素 10
System.out.println(list.removeLast());   // 删除并返回尾部元素 15

(3) 访问元素

get(int index)：返回指定位置的元素。
getFirst()：返回链表的第一个元素。
getLast()：返回链表的最后一个元素。
peek()：返回链表的头部元素，但不删除它。如果链表为空，返回 null。
peekFirst()：返回链表的头部元素，但不删除它。如果链表为空，返回 null。
peekLast()：返回链表的尾部元素，但不删除它。如果链表为空，返回 null。

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.addFirst(5);
list.addLast(15);

System.out.println(list.getFirst());  // 获取头部元素 5
System.out.println(list.getLast());   // 获取尾部元素 15
System.out.println(list.peek());      // 获取头部元素 5

(4) 插入元素

add(int index, E element)：将元素插入到指定位置。
addFirst(E e)：将元素添加到链表的头部。
addLast(E e)：将元素添加到链表的尾部。

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(1, 15);   // 将 15 插入到位置 1
System.out.println(list);  // 输出：[10, 15]

(5) 更新元素

set(int index, E element)：替换指定位置的元素。

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(15);
list.set(1, 20);  // 替换位置 1 的元素为 20
System.out.println(list);  // 输出：[10, 20]

(6) 查找元素

contains(Object o)：检查链表是否包含指定的元素。
indexOf(Object o)：返回指定元素首次出现的索引。如果元素不存在，返回 -1。
lastIndexOf(Object o)：返回指定元素最后一次出现的索引。如果元素不存在，返回 -1。

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(20);
list.add(10);

System.out.println(list.contains(10));  // true
System.out.println(list.indexOf(10));   // 0
System.out.println(list.lastIndexOf(10));  // 2

(7) 清空链表

clear()：清空链表中的所有元素。

LinkedList<Integer> list = new LinkedList<>();
list.add(10);
list.add(15);
list.clear();
System.out.println(list);  // 输出: []

4. 双端队列（Deque）功能

LinkedList 实现了 Deque 接口，因此它既支持栈（LIFO）操作，又支持队列（FIFO）操作。

栈操作（LIFO）：
- push(E e)：将元素添加到链表的头部（与 addFirst 类似）。
- pop()：移除并返回链表的头部元素（与 removeFirst 类似）。
队列操作（FIFO）：
- offer(E e)：将元素添加到链表的尾部（与 addLast 类似）。
- poll()：移除并返回链表的头部元素（与 removeFirst 类似）。

例如：

// 使用 LinkedList 作为栈
LinkedList<Integer> stack = new LinkedList<>();
stack.push(10);   // 添加到栈顶
stack.push(20);
System.out.println(stack.pop());  // 输出 20

// 使用 LinkedList 作为队列
LinkedList<Integer> queue = new LinkedList<>();
queue.offer(10);  // 添加到队列尾部
queue.offer(20);
System.out.println(queue.poll());  // 输出 10

5. 性能特点

添加和删除操作：LinkedList 在头部或尾部进行插入和删除时具有 O(1) 的时间复杂度。这是因为链表结构中插入和删除操作不需要移动其他元素。
查找操作：访问链表的元素需要从头节点开始遍历，因此时间复杂度是 O(n)，这比 ArrayList 慢，因为 ArrayList 可以直接通过索引访问元素。
空间开销：与数组相比，LinkedList 需要额外的内存来存储每个节点的 next 和 previous 引用。

6. 使用场景

需要频繁插入或删除操作的场景：如模拟队列、栈、双端队列等。
不需要频繁随机访问的场景：链表对于顺序遍历和插入删除操作更有效。
需要双向遍历的场景：LinkedList 提供了双向链表，因此可以高效地从两端进行操作。

总结

LinkedList 是一个非常强大的数据结构，特别适用于需要频繁进行插入、删除操作的场景。它是一个双向链表，支持双端队列（Deque）操作，可以用作栈、队列、双端队列等。在使用时，值得注意的是链表的查找效率较低，因此如果对随机访问有较高要求，ArrayList 可能是更好的选择。

LinkedList类