List接口概述

List是Java集合框架中有序、可重复元素的集合，提供精确的位置控制

核心特征

List接口继承自Collection接口，具有以下核心特性：

有序集合

List中的元素具有明确的顺序，可通过索引访问任意位置的元素

允许重复元素

List中可以包含重复的元素，这与Set集合不同

索引操作

提供基于索引的get、set、add、remove等操作方法

LinkedList

节点A
节点B
节点C

双向链表实现

Vector

元素1
元素2
元素3
动态数组实现

Stack

栈顶元素
中间元素
栈底元素
后进先出(LIFO)

LinkedList详解

双向链表实现的List，支持高效头尾操作

核心特性

  • 基于双向链表实现，每个节点包含前驱和后继指针
  • 在列表头尾的操作性能高，时间复杂度O(1)
  • 任意位置插入/删除时间复杂度O(n)
  • 实现了List和Deque接口，可用作列表、栈或队列
1

创建与基本操作

import java.util.LinkedList; import java.util.List; // 创建LinkedList List<String> linkedList = new LinkedList<>(); // 添加元素 - 尾部添加 linkedList.add("Java"); linkedList.add("Python"); // 在指定位置插入元素 linkedList.add(1, "C++"); // [Java, C++, Python] // 获取指定位置元素 String lang = linkedList.get(0); // "Java" // 删除指定位置元素 linkedList.remove(2); // 删除"Python"
2

特殊操作（实现Deque接口）

// 创建LinkedList作为双端队列 LinkedList<String> deque = new LinkedList<>(); // 头部操作 deque.addFirst("First"); // 或 offerFirst() deque.removeFirst(); // 或 pollFirst() // 尾部操作 deque.addLast("Last"); // 或 offerLast() deque.removeLast(); // 或 pollLast() // 获取但不移除元素 String first = deque.peekFirst(); String last = deque.peekLast(); // 作为堆栈使用 deque.push("StackItem"); // 相当于addFirst String top = deque.pop(); // 相当于removeFirst

使用场景

LinkedList在以下场景中有优势：

  • 需要频繁在列表头尾进行添加/删除操作
  • 需要将集合用作双端队列或堆栈
  • 元素数量不确定且需要高效插入
  • 不需要随机访问或随机访问频率较低

Vector详解

线程安全的动态数组，Java早期集合类

核心特性

  • 基于动态数组实现，类似ArrayList但线程安全
  • 默认容量为10，增长因子为100%（默认）
  • 通过synchronized方法实现线程安全
  • 提供了遍历集合的Enumeration接口
1

创建与基本操作

import java.util.Vector; import java.util.Enumeration; // 创建Vector并指定初始容量和增长因子 Vector<String> vector = new Vector<>(20, 5); // 添加元素 vector.add("Element 1"); vector.addElement("Element 2"); // 历史遗留方法 // 插入元素到指定位置 vector.add(1, "New Element"); // 获取元素 String elem = vector.get(0); String elemOld = vector.elementAt(0); // 历史方法 // 遍历 - 使用Enumeration Enumeration<String> en = vector.elements(); while (en.hasMoreElements()) { System.out.println(en.nextElement()); }
2

线程安全与替代方案

// Vector是线程安全的，但考虑以下替代方案: // 1. Collections.synchronizedList List<String> syncedList = Collections.synchronizedList(new ArrayList<>()); // 2. CopyOnWriteArrayList (适合读多写少) import java.util.concurrent.CopyOnWriteArrayList; List<String> copyOnWriteList = new CopyOnWriteArrayList<>(); // 多线程环境下Vector的使用 Vector<Integer> safeVector = new Vector<>(); Runnable task = () -> { for (int i = 0; i < 1000; i++) { safeVector.add(i); } }; // 创建多个线程访问Vector Thread t1 = new Thread(task); Thread t2 = new Thread(task); t1.start(); t2.start();

遗留类注意事项

Vector是Java 1.0的遗留类，虽然提供线程安全，但同步粒度较粗可能影响性能。在Java 5+中，考虑使用并发集合类如CopyOnWriteArrayList或Collections.synchronizedList()包装的ArrayList替代。

Stack详解

后进先出(LIFO)的堆栈实现，继承自Vector

核心特性

  • 继承自Vector类，线程安全
  • 后进先出(LIFO)结构，只允许在栈顶操作
  • 提供push、pop、peek等标准堆栈操作
  • 不建议使用，已标记为遗留类
1

基本操作

import java.util.Stack; // 创建Stack Stack<String> stack = new Stack<>(); // 压栈操作 stack.push("First"); stack.push("Second"); stack.push("Third"); // 查看栈顶元素 String top = stack.peek(); // "Third" // 出栈操作 String element = stack.pop(); // "Third" // 检查是否为空 boolean isEmpty = stack.empty(); // 查找元素位置 int pos = stack.search("First"); // 1 (从栈顶开始)
2

现代替代方案

// 1. 使用ArrayDeque作为堆栈 (推荐) import java.util.ArrayDeque; import java.util.Deque; Deque<String> dequeStack = new ArrayDeque<>(); // 压栈 dequeStack.push("First"); dequeStack.push("Second"); // 查看栈顶 String topElement = dequeStack.peek(); // 出栈 String popped = dequeStack.pop(); // 2. 使用LinkedList作为堆栈 Deque<String> linkedStack = new LinkedList<>(); linkedStack.push("Item1"); // 3. 使用Collections API创建同步堆栈 Deque<String> syncedStack = Collections.synchronizedDeque(new ArrayDeque<>());

Stack类的使用警告

Stack类从Java 1.0开始存在，由于设计问题已被标记为遗留类（legacy class）：

  • 继承自Vector暴露了过多非堆栈操作方法（如insertElementAt）
  • 性能较差，同步操作在单线程环境是负担
  • 在Java 6之后，推荐使用Deque接口的实现类代替Stack
  • 新代码应优先使用ArrayDeque

LinkedList、Vector与Stack对比

全面比较三种集合的实现机制、性能差异与适用场景

特性 LinkedList Vector Stack
实现方式 双向链表 动态数组 继承自Vector
线程安全 否 是（通过synchronized） 是（继承Vector）
效率特点 头尾操作O(1)，随机访问O(n) 随机访问O(1)，插入删除O(n) 仅栈顶操作O(1)
继承关系 实现List和Deque 实现List 继承Vector
空值处理 允许null元素 允许null元素 允许null元素
现代替代品 无，仍是主流实现 Collections.synchronizedList
CopyOnWriteArrayList		 ArrayDeque
适用场景 双端操作、队列、栈
低随机访问频率		 遗留系统维护
简单线程安全需求		 基本不使用
O(1)
LinkedList头尾操作
O(1)
Vector随机访问
O(1)
Stack栈顶操作

添加操作

LinkedList： addFirst/addLast O(1)

Vector： add O(1) 均摊, 扩容时O(n)

Stack： push O(1) 均摊

删除操作

LinkedList： removeFirst/removeLast O(1)

Vector： remove O(n)

Stack： pop O(1)

访问操作

LinkedList： get O(n)

Vector： get O(1)

Stack： peek O(1)

常见错误与最佳实践

避免集合使用中的陷阱，掌握高效正确使用方法

常见错误

  • 误用Vector的线程安全特性：跨多个方法组合操作仍需额外同步
  • 在LinkedList中进行大量随机访问操作
  • 在多线程环境下直接使用LinkedList
  • 在新项目中使用Stack类
  • 没有考虑Vector扩容导致的性能问题
  • 对LinkedList使用索引遍历而非迭代器

最佳实践

  • LinkedList适合频繁头尾操作和插入删除的场景
  • 使用ArrayDeque代替Stack实现LIFO结构
  • 在单线程环境下优先使用ArrayList而非Vector
  • 对LinkedList使用Iterator进行遍历而非索引
  • 使用Collections.synchronizedList替代Vector
  • 多线程场景考虑CopyOnWriteArrayList

动手练习

  • 使用LinkedList实现LRU缓存淘汰算法
  • 用ArrayDeque实现逆波兰表达式计算器
  • 比较LinkedList和ArrayList在10万次头部插入的性能差异
  • 使用Vector和CopyOnWriteArrayList实现线程安全的计数器
  • 使用栈结构解决括号匹配问题