Java集合框架中的列表与队列

# Java集合框架中的列表与队列 在Java编程中，集合框架是一个非常重要的部分，它提供了各种数据结构来存储和操作数据。本文将重点介绍Java集合框架中的列表（List）和队列（Queue），包括它们的实现类、特点以及使用示例。 ## 1. 列表（List）的实现类 在`java.util`包中，提供了`List`接口的三种实现：`ArrayList`、`LinkedList`和`Vector`。 ### 1.1 `ArrayList`和`Vector` - **实现方式**：`ArrayList`和`Vector`都使用动态可调整大小的数组实现，提供快速的随机访问（即基于位置的访问）和列表遍历，类似于普通数组。 - **线程安全性**：`Vector`是线程安全的，意味着对`Vector`的并发调用不会损害其完整性，而`ArrayList`不是线程安全的。 - **性能比较**：`ArrayList`和`Vector`的性能相当，但由于`Vector`的同步机制，会有轻微的性能损失。基于位置的访问对于`ArrayList`和`Vector`具有常数时间性能。 ### 1.2 `LinkedList` - **实现方式**：`LinkedList`使用双向链表实现，在双向链表中进行插入和删除操作非常高效。 - **基于位置的访问**：由于需要遍历双向链表，`LinkedList`的基于位置的访问是线性时间的。 - **其他接口实现**：除了`List`接口，`LinkedList`还实现了另外两个接口，使其可以用作栈和不同类型的队列。 ### 1.3 列表迭代器（ListIterator） `ListIterator`是一个双向迭代器，它扩展了`Iterator`接口，允许列表在两个方向上进行遍历。以下是`ListIterator`的主要方法： | 方法 | 描述 | | --- | --- | | `boolean hasNext()` | 判断是否有下一个元素 | | `boolean hasPrevious()` | 判断是否有前一个元素 | | `E next()` | 返回下一个元素 | | `E previous()` | 返回前一个元素 | | `int nextIndex()` | 返回下一个元素的索引 | | `int previousIndex()` | 返回前一个元素的索引 | | `void remove()` | 移除最后通过的元素（可选操作） | | `void set(E o)` | 替换最后通过的元素（可选操作） | | `void add(E o)` | 在迭代器位置插入元素（可选操作） | ### 1.4 `ArrayList`的构造函数 - `ArrayList()`：创建一个新的空`ArrayList`。 - `ArrayList(Collection<? extends E> c)`：创建一个包含指定集合元素的新`ArrayList`，新的`ArrayList`将保留任何重复项，其顺序由传递的集合的迭代器的遍历顺序决定。 - `ArrayList(int initialCapacity)`：创建一个具有指定初始容量的新的空`ArrayList`。 ### 1.5 列表操作示例 以下是一个简单的示例，展示了如何使用列表进行猜数字游戏： ```java import java.util.ArrayList; import java.util.List; import java.util.ListIterator; public class TakeAGuess { final static int NUM_DIGITS = 5; public static void main(String[] args) { try { if (args.length != 1 || args[0].length() != NUM_DIGITS) throw new IllegalArgumentException(); Integer.parseInt(args[0]); } catch (IllegalArgumentException nfe) { System.err.println("Guess should be " + NUM_DIGITS + " digits."); return; } String guessStr = args[0]; System.out.println("Guess: " + guessStr); List<Integer> secretSolution = new ArrayList<Integer>(); secretSolution.add(5); secretSolution.add(3); secretSolution.add(2); secretSolution.add(7); secretSolution.add(2); List<Integer> guess = new ArrayList<Integer>(); for (int i = 0; i < guessStr.length(); i++) guess.add(Character.getNumericValue(guessStr.charAt(i))); List<Integer> duplicate = new ArrayList<Integer>(secretSolution); int numOfDigitsIncluded = 0; for (int i = 0; i < NUM_DIGITS; i++) if (duplicate.remove(guess.get(i))) numOfDigitsIncluded++; ListIterator<Integer> correct = secretSolution.listIterator(); ListIterator<Integer> attempt = guess.listIterator(); int numOfDigitsPlaced = 0; while (correct.hasNext()) if (correct.next().equals(attempt.next())) numOfDigitsPlaced++; System.out.println(numOfDigitsIncluded + " digit(s) correctly included."); System.out.println(numOfDigitsPlaced + " digit(s) correctly placed."); } } ``` 运行该程序： ``` >java TakeAGuess 32227 Guess: 32227 4 digit(s) correctly included. 1 digit(s) correctly placed. ``` ### 1.6