14.3 LinkedList 简介

LinkedList 的概念

LinkedList 是 Java 中另一个常用的集合类，它实现了 List 和 Deque 接口，基于双向链表实现。LinkedList 允许存储重复元素，并且可以高效地进行插入和删除操作。

LinkedList 的特点

1. 基于双向链表：底层使用双向链表实现，每个节点包含前驱和后继引用
2. 动态大小：容量会根据需要自动增长
3. 允许重复元素：可以存储相同的元素
4. 有序：保持元素的插入顺序
5. 非线程安全：在多线程环境中需要额外的同步措施
6. 实现了 Deque 接口：可以作为队列、栈或双端队列使用

LinkedList 的创建

1. 无参构造方法

创建一个空的 LinkedList。

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

2. 从其他集合创建

通过其他集合创建 LinkedList。

List<String> otherList = Arrays.asList("Java", "Python", "C++");
LinkedList<String> list = new LinkedList<>(otherList);

LinkedList 的常用方法

1. 添加元素

add(E e)

功能：在列表末尾添加元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

add(int index, E element)

功能：在指定位置添加元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("C++");
list.add(1, "Python"); // 在索引 1 处添加 "Python"

addFirst(E e)

功能：在列表开头添加元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Python");
list.add("C++");
list.addFirst("Java"); // 在开头添加 "Java"

addLast(E e)

功能：在列表末尾添加元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.addLast("C++"); // 在末尾添加 "C++"

offer(E e)

功能：在列表末尾添加元素（队列操作）

示例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Java");
queue.offer("Python");
queue.offer("C++");

offerFirst(E e)

功能：在列表开头添加元素（双端队列操作）

示例：

LinkedList<String> deque = new LinkedList<>();
deque.offerFirst("Java");
deque.offerFirst("Python");
deque.offerFirst("C++");

offerLast(E e)

功能：在列表末尾添加元素（双端队列操作）

示例：

LinkedList<String> deque = new LinkedList<>();
deque.offerLast("Java");
deque.offerLast("Python");
deque.offerLast("C++");

2. 删除元素

remove(int index)

功能：删除指定索引处的元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

list.remove(1); // 删除索引 1 处的元素 "Python"

remove(Object o)

功能：删除指定的元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

list.remove("Python"); // 删除元素 "Python"

removeFirst()

功能：删除列表开头的元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

list.removeFirst(); // 删除开头的元素 "Java"

removeLast()

功能：删除列表末尾的元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

list.removeLast(); // 删除末尾的元素 "C++"

poll()

功能：删除并返回列表开头的元素（队列操作）

示例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Java");
queue.offer("Python");
queue.offer("C++");

String element = queue.poll(); // 删除并返回 "Java"

pollFirst()

功能：删除并返回列表开头的元素（双端队列操作）

示例：

LinkedList<String> deque = new LinkedList<>();
deque.offer("Java");
deque.offer("Python");
deque.offer("C++");

String element = deque.pollFirst(); // 删除并返回 "Java"

pollLast()

功能：删除并返回列表末尾的元素（双端队列操作）

示例：

LinkedList<String> deque = new LinkedList<>();
deque.offer("Java");
deque.offer("Python");
deque.offer("C++");

String element = deque.pollLast(); // 删除并返回 "C++"

3. 修改元素

set(int index, E element)

功能：修改指定索引处的元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

list.set(1, "JavaScript"); // 将索引 1 处的元素修改为 "JavaScript"

4. 查找元素

get(int index)

功能：获取指定索引处的元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

String element = list.get(0); // 获取索引 0 处的元素 "Java"

getFirst()

功能：获取列表开头的元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

String first = list.getFirst(); // 获取开头的元素 "Java"

getLast()

功能：获取列表末尾的元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

String last = list.getLast(); // 获取末尾的元素 "C++"

peek()

功能：获取列表开头的元素（队列操作）

示例：

LinkedList<String> queue = new LinkedList<>();
queue.offer("Java");
queue.offer("Python");
queue.offer("C++");

String element = queue.peek(); // 获取开头的元素 "Java"

peekFirst()

功能：获取列表开头的元素（双端队列操作）

示例：

LinkedList<String> deque = new LinkedList<>();
deque.offer("Java");
deque.offer("Python");
deque.offer("C++");

String element = deque.peekFirst(); // 获取开头的元素 "Java"

peekLast()

功能：获取列表末尾的元素（双端队列操作）

示例：

LinkedList<String> deque = new LinkedList<>();
deque.offer("Java");
deque.offer("Python");
deque.offer("C++");

String element = deque.peekLast(); // 获取末尾的元素 "C++"

5. 其他方法

size()

功能：获取集合的大小

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

int size = list.size(); // 返回 3

isEmpty()

功能：检查集合是否为空

示例：

LinkedList<String> list = new LinkedList<>();
boolean isEmpty = list.isEmpty(); // 返回 true

list.add("Java");
isEmpty = list.isEmpty(); // 返回 false

contains(Object o)

功能：检查集合是否包含指定元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

boolean contains = list.contains("Python"); // 返回 true

clear()

功能：清空集合中的所有元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

list.clear(); // 清空集合

LinkedList 的遍历

1. for 循环

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

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

2. 增强 for 循环

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

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

3. 迭代器

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

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

4. 双向迭代器

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

// 正向遍历
ListIterator<String> iterator = list.listIterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}

// 反向遍历
ListIterator<String> reverseIterator = list.listIterator(list.size());
while (reverseIterator.hasPrevious()) {
    String element = reverseIterator.previous();
    System.out.println(element);
}

5. forEach 方法（Java 8+）

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

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

LinkedList 的性能

时间复杂度

操作	时间复杂度
随机访问（get/set）	O(n)
头部插入/删除	O(1)
尾部插入/删除	O(1)
中间插入/删除	O(n)
搜索	O(n)

空间复杂度

• 空间复杂度：O(n)，其中 n 是元素数量

ArrayList 与 LinkedList 的比较

特性	ArrayList	LinkedList
底层实现	数组	双向链表
随机访问	O(1)	O(n)
头部插入/删除	O(n)	O(1)
尾部插入/删除	O(1)	O(1)
中间插入/删除	O(n)	O(n)
内存占用	较低（连续内存）	较高（每个节点需要额外的引用）
适用场景	频繁随机访问	频繁插入和删除

示例：LinkedList 的使用

示例 1：基本操作

import java.util.LinkedList;

public class LinkedListBasicExample {
    public static void main(String[] args) {
        // 创建 LinkedList
        LinkedList<String> languages = new LinkedList<>();
        
        // 添加元素
        languages.add("Java");
        languages.add("Python");
        languages.add("C++");
        System.out.println("添加元素后: " + languages);
        
        // 在指定位置添加元素
        languages.add(1, "JavaScript");
        System.out.println("在指定位置添加元素后: " + languages);
        
        // 在开头添加元素
        languages.addFirst("Ruby");
        System.out.println("在开头添加元素后: " + languages);
        
        // 在末尾添加元素
        languages.addLast("Go");
        System.out.println("在末尾添加元素后: " + languages);
        
        // 修改元素
        languages.set(2, "TypeScript");
        System.out.println("修改元素后: " + languages);
        
        // 删除元素
        languages.remove(3);
        System.out.println("删除元素后: " + languages);
        
        // 删除开头元素
        languages.removeFirst();
        System.out.println("删除开头元素后: " + languages);
        
        // 删除末尾元素
        languages.removeLast();
        System.out.println("删除末尾元素后: " + languages);
        
        // 获取元素
        String first = languages.get(0);
        System.out.println("第一个元素: " + first);
        
        // 获取开头元素
        String head = languages.getFirst();
        System.out.println("开头元素: " + head);
        
        // 获取末尾元素
        String tail = languages.getLast();
        System.out.println("末尾元素: " + tail);
        
        // 检查元素是否存在
        boolean contains = languages.contains("Java");
        System.out.println("是否包含 Java: " + contains);
        
        // 获取集合大小
        int size = languages.size();
        System.out.println("集合大小: " + size);
        
        // 遍历集合
        System.out.println("遍历集合:");
        for (String language : languages) {
            System.out.println("- " + language);
        }
        
        // 清空集合
        languages.clear();
        System.out.println("清空后: " + languages);
        System.out.println("清空后大小: " + languages.size());
    }
}

示例 2：作为队列使用

import java.util.LinkedList;
import java.util.Queue;

public class LinkedListQueueExample {
    public static void main(String[] args) {
        // 创建队列
        Queue<String> queue = new LinkedList<>();
        
        // 入队
        queue.offer("Java");
        queue.offer("Python");
        queue.offer("C++");
        System.out.println("入队后: " + queue);
        
        // 查看队首元素
        String head = queue.peek();
        System.out.println("队首元素: " + head);
        
        // 出队
        String element = queue.poll();
        System.out.println("出队元素: " + element);
        System.out.println("出队后: " + queue);
        
        // 再次出队
        element = queue.poll();
        System.out.println("出队元素: " + element);
        System.out.println("出队后: " + queue);
        
        // 再次出队
        element = queue.poll();
        System.out.println("出队元素: " + element);
        System.out.println("出队后: " + queue);
        
        // 队列为空时出队
        element = queue.poll();
        System.out.println("队列为空时出队: " + element);
    }
}

示例 3：作为栈使用

import java.util.LinkedList;
import java.util.Stack;

public class LinkedListStackExample {
    public static void main(String[] args) {
        // 方法 1：使用 Stack 类
        Stack<String> stack = new Stack<>();
        
        // 入栈
        stack.push("Java");
        stack.push("Python");
        stack.push("C++");
        System.out.println("入栈后: " + stack);
        
        // 查看栈顶元素
        String top = stack.peek();
        System.out.println("栈顶元素: " + top);
        
        // 出栈
        String element = stack.pop();
        System.out.println("出栈元素: " + element);
        System.out.println("出栈后: " + stack);
        
        // 方法 2：使用 LinkedList 作为栈
        LinkedList<String> stack2 = new LinkedList<>();
        
        // 入栈（添加到开头）
        stack2.push("Java");
        stack2.push("Python");
        stack2.push("C++");
        System.out.println("入栈后: " + stack2);
        
        // 查看栈顶元素
        top = stack2.peek();
        System.out.println("栈顶元素: " + top);
        
        // 出栈（从开头删除）
        element = stack2.pop();
        System.out.println("出栈元素: " + element);
        System.out.println("出栈后: " + stack2);
    }
}

示例 4：作为双端队列使用

import java.util.LinkedList;
import java.util.Deque;

public class LinkedListDequeExample {
    public static void main(String[] args) {
        // 创建双端队列
        Deque<String> deque = new LinkedList<>();
        
        // 从末尾添加元素
        deque.offerLast("Java");
        deque.offerLast("Python");
        deque.offerLast("C++");
        System.out.println("从末尾添加元素后: " + deque);
        
        // 从开头添加元素
        deque.offerFirst("Ruby");
        deque.offerFirst("Go");
        System.out.println("从开头添加元素后: " + deque);
        
        // 查看开头元素
        String first = deque.peekFirst();
        System.out.println("开头元素: " + first);
        
        // 查看末尾元素
        String last = deque.peekLast();
        System.out.println("末尾元素: " + last);
        
        // 从开头删除元素
        String element = deque.pollFirst();
        System.out.println("从开头删除元素: " + element);
        System.out.println("删除后: " + deque);
        
        // 从末尾删除元素
        element = deque.pollLast();
        System.out.println("从末尾删除元素: " + element);
        System.out.println("删除后: " + deque);
    }
}

常见问题

1. 随机访问性能

症状：LinkedList 的随机访问速度慢

解决方案：对于需要频繁随机访问的场景，使用 ArrayList

示例：

// 需要频繁随机访问时，使用 ArrayList
List<String> list = new ArrayList<>();

// 需要频繁插入删除时，使用 LinkedList
List<String> list = new LinkedList<>();

2. 内存占用

症状：LinkedList 占用较多内存

解决方案：对于内存受限的场景，考虑使用 ArrayList

示例：

// 内存受限场景，使用 ArrayList
List<String> list = new ArrayList<>();

3. 线程安全问题

症状：在多线程环境中，LinkedList 操作导致数据不一致

解决方案：使用线程安全的集合或同步机制

示例：

// 使用线程安全的集合
List<String> list = Collections.synchronizedList(new LinkedList<>());

// 或使用同步代码块
LinkedList<String> list = new LinkedList<>();
synchronized (list) {
    list.add("Java");
}

4. 迭代器并发修改

症状：在迭代过程中修改 LinkedList，导致 ConcurrentModificationException

解决方案：使用迭代器的 remove() 方法，或使用 ListIterator 进行修改

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.add("Python");
list.add("C++");

// 错误：在增强 for 循环中修改集合
// for (String element : list) {
//     if (element.equals("Python")) {
//         list.remove(element);
//     }
// }

// 正确：使用迭代器
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    if (element.equals("Python")) {
        iterator.remove(); // 使用迭代器的 remove 方法
    }
}

// 正确：使用 ListIterator
ListIterator<String> listIterator = list.listIterator();
while (listIterator.hasNext()) {
    String element = listIterator.next();
    if (element.equals("Python")) {
        listIterator.remove();
        listIterator.add("JavaScript"); // 可以添加元素
    }
}

最佳实践

1. 选择合适的集合：对于频繁的插入和删除操作，使用 LinkedList；对于频繁的随机访问，使用 ArrayList

2. 使用泛型：使用泛型确保类型安全，避免运行时异常

3. 注意线程安全：在多线程环境中，使用线程安全的集合或同步机制

4. 避免随机访问：尽量避免对 LinkedList 进行随机访问，因为时间复杂度为 O(n)

5. 使用合适的遍历方式：对于 LinkedList，使用增强 for 循环或迭代器，避免使用索引遍历

6. 利用双端队列特性：当需要实现队列、栈或双端队列时，考虑使用 LinkedList

7. 合理使用方法：根据具体需求，选择合适的方法，如 addFirst()、addLast()、offer()、poll() 等

总结

LinkedList 是 Java 中另一个常用的集合类，它基于双向链表实现，具有以下特点：

1. 基于双向链表：每个节点包含前驱和后继引用
2. 动态大小：容量会根据需要自动增长
3. 允许重复元素：可以存储相同的元素
4. 有序：保持元素的插入顺序
5. 非线程安全：在多线程环境中需要额外的同步措施
6. 实现了 Deque 接口：可以作为队列、栈或双端队列使用

LinkedList 适用于需要频繁插入和删除操作的场景，而对于频繁随机访问的场景，建议使用 ArrayList。

通过合理使用 LinkedList，可以提高代码的效率和可维护性。