数据结构和算法(3)-向量,列表与序列

旧城等待， 2022-05-10 04:18 144阅读 0赞

序列（ Sequence），就是依次排列的多个对象。两种典型的序列：向量（ Vector）和列表（ List）。

## 3.1 向量与数组 ##

通过\[0, n-1\]之间的每一个整数，都可以直接访问到唯一的元素 e，而这个整数就等于 S 中位于 e 之前的元素个数⎯⎯在此，我们称之为该元素的秩（ Rank）。

### 3.1.1 向量 ADT ###

<table> 
 <thead> 
  <tr> 
   <th>操作方法</th> 
   <th>功能描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>getSize()：</td> 
   <td>报告向量中的元素数目<br> 输入：无 <br> 输出：非负整数</td> 
  </tr> 
  <tr> 
   <td>isEmpty()：</td> 
   <td>判断向量是否为空<br>输入：无<br>输出：布尔量</td> 
  </tr> 
  <tr> 
   <td>getAtRank®：</td> 
   <td>若 0 ≤ r &lt; getSize()，则返回秩为 r 的那个元素<br> 否则，报错<br> 输入：一个整数<br> 输出：对象</td> 
  </tr> 
  <tr> 
   <td>replaceAtRank(r, e)：</td> 
   <td>若 0 ≤ r &lt; getSize()，则将秩为 r 的元素替换为 e，并返回原来的元素<br>否则，报错<br>输入：一个整数和一个对象<br>输出：对象</td> 
  </tr> 
  <tr> 
   <td>insertAtRank(r, e)：</td> 
   <td>若 0 ≤ r ≤ getSize()，则将 e 插入向量中，作为秩为 r 的元素（原秩不小于 r 的元素顺次后移）；并返回该元素<br> 否则，报错<br> 输入：一个整数和一个对象<br> 输出：对象</td> 
  </tr> 
  <tr> 
   <td>removeAtRank®：</td> 
   <td>若 0 ≤ r &lt; getSize()，则删除秩为 r 的那个元素并返回之（原秩大于 r 的元素顺次前移）<br>否则，报错<br>输入：一个整数<br>输出：对象</td> 
  </tr> 
 </tbody> 
</table>

一种直截了当的方法就是采用数组来实现向量：下标为r的数组项，就对应于秩为r的元素。

### 3.1.2 基于数组的简单实现 ###

public class ExceptionBoundaryViolation extends RuntimeException { public ExceptionBoundaryViolation(String message) { super(message); } }

向量接口:

public interface Vector { // 返回向量中元素数目 public int getSize(); // 判断向量是否为空 public boolean isEmpty(); /**查改增删*/ // 取秩为r的元素 public Object getAtRank(int r) throws ExceptionBoundaryViolation; // 将秩为r的元素替换为obj public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation; // 插入obj，作为秩为r的元素；返回该元素 public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation; // 删除秩为r的元素 public Object removeAtRank(int r) throws ExceptionBoundaryViolation; }

/* * 基于数组的向量实现 */ public class Vector_ExtArray implements Vector { private int N = 8;// 数组的容量，可不断增加 private int n;// 向量的实际规模 private Object A[];// 对象数组 public Vector_ExtArray() { A = new Object[N]; n = 0; } @Override public int getSize() { // TODO Auto-generated method stub return n; } @Override public boolean isEmpty() { // TODO Auto-generated method stub return (0 == n) ? true : false; } @Override public Object getAtRank(int r) throws ExceptionBoundaryViolation { if (0 > r || r >= n) throw new ExceptionBoundaryViolation("意外：秩越界"); return A[r]; } @Override public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation { if (0 > r || r >= n) throw new ExceptionBoundaryViolation("意外：秩越界"); /* * A[r] = obj; return A[r]; */ Object bak = A[r]; A[r] = obj; return bak; } @Override public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation { if (0 > r || r > n) throw new ExceptionBoundaryViolation("意外：秩越界"); if (N < n) { // 数组容量小于实际规模 N *= 2; Object B[] = new Object[N];// 开辟一个容量加倍的数组 for (int i = 0; i < n; i++) { B[i] = A[i]; } A = B;// 用B替换A（原A[]将被自动回收） } for (int i = n; i > r; i--) A[i] = A[i - 1];// 后续元素顺次后移 A[r] = obj;// 插入 n++;// 更新当前规模 return obj; } @Override public Object removeAtRank(int r) throws ExceptionBoundaryViolation { if (0 > r || r >= n) throw new ExceptionBoundaryViolation("意外：秩越界"); Object bak = A[r]; for (int i = r; i < n - 1; i++) A[i] = A[i + 1];// 后续元素顺次前移 n--;// 更新当前规模 return bak; } }

基于可扩充数组实现的向量，每次数组扩容的分摊运行时间为 O(1)。

### 3.1.4 java.util.ArrayList 类和 java.util.Vector 类 ###

向量ADT与java.util.ArrayList类的对比

<table> 
 <thead> 
  <tr> 
   <th>向量 ADT 中的方法</th> 
   <th>java.util.ArrayList 类的方法</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>getSize()</td> 
   <td>getSize()</td> 
  </tr> 
  <tr> 
   <td>isEmpty()</td> 
   <td>isEmpty()</td> 
  </tr> 
  <tr> 
   <td>getAtRank()</td> 
   <td>get()</td> 
  </tr> 
  <tr> 
   <td>replaceAtRank()</td> 
   <td>set()</td> 
  </tr> 
  <tr> 
   <td>insertAtRank()</td> 
   <td>add()</td> 
  </tr> 
  <tr> 
   <td>removeAtRank()</td> 
   <td>remove()</td> 
  </tr> 
 </tbody> 
</table>

--------------------

## 3.2 列表 ##

### 3.2.1 基于节点的操作 ###

试考察一个（单向或双向）链表 S。如果直接照搬秩的概念，对链表的访问速度会很慢⎯⎯为了在链表结构中确定特定元素的秩，我们不得不顺着元素间的 next（或 prev）引用，从前端（双向链表也可以从后端）开始逐一扫描各个元素，直到发现目标元素。在最坏情况下，这需要线性的时间。

### 3.2.2 由秩到位置 ###

位置（ Position）的概念就是对元素的不同形式的抽象和统一，也是对列表元素之间相对“位置”的形式化刻画。正是在这种抽象的基础上，我们才可以安全地为列表扩充一整套基于节点的操作。

### 3.2.3 列表 ADT ###

列表ADT支持的方法:

<table> 
 <thead> 
  <tr> 
   <th>操作方法</th> 
   <th>功能与描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>first()：</td> 
   <td>若 S 非空，则给出其中第一个元素的位置<br>否则，报错<br>输入：无<br>输出：位置</td> 
  </tr> 
  <tr> 
   <td>last()：</td> 
   <td>若 S 非空，则给出其中最后一个元素的位置<br>否则，报错<br>输入：无<br>输出：位置</td> 
  </tr> 
  <tr> 
   <td>getPrev(p)：</td> 
   <td>若 p 不是第一个位置，则给出 S 中 p 的前驱所在的位置<br>否则，报错<br>输入：位置<br>输出：位置</td> 
  </tr> 
  <tr> 
   <td>getNext(p)：</td> 
   <td>若 p 不是最后一个位置，则给出 S 中 p 的前驱所在的位置<br>否则，报错<br>输入：位置<br>输出：位置</td> 
  </tr> 
  <tr> 
   <td>列表支持的动态修改操作</td> 
   <td></td> 
  </tr> 
  <tr> 
   <td>replace(p, e)：</td> 
   <td>将处于位置 p 处的元素替换为 e，并返回被替换的元素<br>输入：一个位置和一个对象<br>输出：对象</td> 
  </tr> 
  <tr> 
   <td>insertFirst(e)：</td> 
   <td>将元素 e 作为第一个元素插入 S 中，并返回 e 的位置<br>输入：一个对象<br>输出：位置</td> 
  </tr> 
  <tr> 
   <td>insertLast(e)：</td> 
   <td>将元素 e 作为最后一个元素插入 S 中，并返回 e 的位置<br>输入：一个对象<br>输出：位置</td> 
  </tr> 
  <tr> 
   <td>insertBefore(p, e)：</td> 
   <td>将元素 e 插入于 S 中位置 p 之前，并返回 e 的位置<br>输入：一个位置和一个对象<br>输出：位置</td> 
  </tr> 
  <tr> 
   <td>insertAfter(p, e)：</td> 
   <td>将元素 e 插入于 S 中位置 p 之后，并返回 e 的位置<br>输入：一个位置和一个对象<br>输出：位置</td> 
  </tr> 
  <tr> 
   <td>remove§：</td> 
   <td>删除 S 中位置 p 处的元素<br>输入：一个位置<br>输出：对象</td> 
  </tr> 
 </tbody> 
</table>

上述列表 ADT 的定义中，有些操作的功能是重复的。比如，insertBefore(first(), e) 的效果与 insertFirst(e)完全相同， insertAfter(last(), e) 的效果与 insertLast(e)也完全相同。之所以允许这类功能的冗余，是为了增加代码的可读性。

#### 列表 ADT 接口 ####

/* * 列表ADT接口 */ public interface List { //查询列表当前的规模 public int getSize(); //判断列表是否为空 public boolean isEmpty(); //返回第一个元素（的位置） public Position first(); //返回最后一个元素（的位置） public Position last(); //返回紧接给定位置之后的元素（的位置） public Position getNext(Position p) throws ExceptionPositionInvalid, ExceptionBoundaryViolation; //返回紧靠给定位置之前的元素（的位置） public Position getPrev(Position p) throws ExceptionPositionInvalid, ExceptionBoundaryViolation; //将e作为第一个元素插入列表 public Position insertFirst(Object e); //将e作为最后一个元素插入列表 public Position insertLast(Object e); //将e插入至紧接给定位置之后的位置 public Position insertAfter(Position p, Object e) throws ExceptionPositionInvalid; //将e插入至紧靠给定位置之前的位置 public Position insertBefore(Position p, Object e) throws ExceptionPositionInvalid; //删除给定位置处的元素，并返回之 public Object remove(Position p) throws ExceptionPositionInvalid; //删除首元素，并返回之 public Object removeFirst(); //删除末元素，并返回之 public Object removeLast(); //将处于给定位置的元素替换为新元素，并返回被替换的元素 public Object replace(Position p, Object e) throws ExceptionPositionInvalid; //位置迭代器 public Iterator positions(); //元素迭代器 public Iterator elements(); }

### 3.2.4 基于双向链表实现的列表 ###

在第 2.5.3 节中，为了实现双向链表结构，我们曾经基于位置ADT实现了双向链表节点类型DLNode（ 代码二.16）。 在那里，每一节点对应于一个位置，而getElem()方法只需返回该节点所保存的元素。也就是说，节点本身就担当了位置的角色：那里并没有直接使用变量prev和next，而是通过方法getPrev()、 getNext()、 setPrev()和setNext()间接地对它们进行访问或修改。

#### List\_DLNode 类⎯⎯List 接口的实现 ####

空列表也有首末节点,首末节点并不真正存储数据;只是为了方便结构的表达;

/* * 基于双向链表实现列表结构 */ public class List_DLNode implements List { protected int numElem;//列表的实际规模 protected DLNode header, trailer;//哨兵：首节点+末节点 //构造函数 public List_DLNode() { numElem = 0;//空表 header = new DLNode(null, null, null);//首节点 trailer = new DLNode(null, header, null);//末节点 header.setNext(trailer);//首、末节点相互链接 } /**************************** 辅助方法 ****************************/ //检查给定位置在列表中是否合法，若是，则将其转换为*DLNode protected DLNode checkPosition(Position p) throws ExceptionPositionInvalid { if (null == p) throw new ExceptionPositionInvalid("意外：传递给List_DLNode的位置是null"); if (header == p) throw new ExceptionPositionInvalid("意外：头节点哨兵位置非法"); if (trailer == p) throw new ExceptionPositionInvalid("意外：尾结点哨兵位置非法"); DLNode temp = (DLNode)p; return temp; } /**************************** ADT方法 ****************************/ //查询列表当前的规模 public int getSize() { return numElem; } //判断列表是否为空 public boolean isEmpty() { return (numElem == 0); } //返回第一个元素（的位置） public Position first() throws ExceptionListEmpty { if (isEmpty()) throw new ExceptionListEmpty("意外：列表空"); return header.getNext(); } //返回最后一个元素（的位置） public Position last() throws ExceptionListEmpty { if (isEmpty()) throw new ExceptionListEmpty("意外：列表空"); return trailer.getPrev(); } //返回紧靠给定位置之前的元素（的位置） public Position getPrev(Position p) throws ExceptionPositionInvalid, ExceptionBoundaryViolation { DLNode v = checkPosition(p); DLNode prev = v.getPrev(); if (prev == header) throw new ExceptionBoundaryViolation("意外：企图越过列表前端"); return prev; } //返回紧接给定位置之后的元素（的位置） public Position getNext(Position p) throws ExceptionPositionInvalid, ExceptionBoundaryViolation { DLNode v = checkPosition(p); DLNode next = v.getNext(); if (next == trailer) throw new ExceptionBoundaryViolation("意外：企图越过列表后端"); return next; } //将e插入至紧靠给定位置之前的位置 public Position insertBefore(Position p, Object element) throws ExceptionPositionInvalid { DLNode v = checkPosition(p); numElem++; DLNode newNode = new DLNode(element, v.getPrev(), v); v.getPrev().setNext(newNode); v.setPrev(newNode); return newNode; } //将e插入至紧接给定位置之后的位置 public Position insertAfter(Position p, Object element) throws ExceptionPositionInvalid { DLNode v = checkPosition(p); numElem++; DLNode newNode = new DLNode(element, v, v.getNext()); v.getNext().setPrev(newNode); v.setNext(newNode); return newNode; } //将e作为第一个元素插入列表 public Position insertFirst(Object e) { numElem++; DLNode newNode = new DLNode(e, header, header.getNext()); header.getNext().setPrev(newNode); header.setNext(newNode); return newNode; } //将e作为最后一个元素插入列表 public Position insertLast(Object e) { numElem++; DLNode newNode = new DLNode(e, trailer.getPrev(), trailer); if (null == trailer.getPrev()) System.out.println("!!!Prev of trailer is NULL!!!"); trailer.getPrev().setNext(newNode); trailer.setPrev(newNode); return newNode; } //删除给定位置处的元素，并返回之 public Object remove(Position p) throws ExceptionPositionInvalid { DLNode v = checkPosition(p); numElem--; DLNode vPrev = v.getPrev(); DLNode vNext = v.getNext(); vPrev.setNext(vNext); vNext.setPrev(vPrev); Object vElem = v.getElem(); //将该位置（节点）从列表中摘出，以便系统回收其占用的空间 v.setNext(null); v.setPrev(null); return vElem; } //删除首元素，并返回之 public Object removeFirst() { return remove(header.getNext()); } //删除末元素，并返回之 public Object removeLast() { return remove(trailer.getPrev()); } //将处于给定位置的元素替换为新元素，并返回被替换的元素 public Object replace(Position p, Object obj) throws ExceptionPositionInvalid { DLNode v = checkPosition(p); Object oldElem = v.getElem(); v.setElem(obj); return oldElem; } //位置迭代器 public Iterator positions() { return new IteratorPosition(this); } //元素迭代器 public Iterator elements() { return new IteratorElement(this); } }

## ![在这里插入图片描述][70] ##

## 3.3 序列 ##

通用的序列 ADT:将向量 ADT 与列表 ADT 中的所有方法集成起来

### 3.3.1 序列 ADT ###

<table> 
 <thead> 
  <tr> 
   <th>操作方法</th> 
   <th>功能描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>rank2Pos(r)：</td> 
   <td>若 0 ≤ r &lt; getSize()，则返回秩为 r 的元素所在的位置；否则，报错<br>输入：一个（作为秩的）整数<br>输出：位置</td> 
  </tr> 
  <tr> 
   <td>pos2Rank(p)：</td> 
   <td>若 p 是序列中的合法位置，则返回存放于 p 处的元素的秩；否则，报错<br>输入：一个位置<br>输出：（作为秩的）整数</td> 
  </tr> 
 </tbody> 
</table>

/* * 序列接口 */ public interface Sequence extends Vector, List { //若0 <= r < getSize()，则返回秩为r的元素所在的位置；否则，报错 public Position rank2Pos(int r) throws ExceptionBoundaryViolation; //若p是序列中的合法位置，则返回存放于p处的元素的秩；否则，报错 public int pos2Rank(Position p) throws ExceptionPositionInvalid; }

### 3.3.2 基于双向链表实现序列 ###

实现序列最自然、最直接的方式，就是利用双向链表。这样，**来自列表 ADT 的每个方法都依然可以保持原先 O(1)的时间复杂度**。当然，来自向量 ADT 的方法尽管也可以借助双向链表来实现，但其效率却会受到影响。实际上，如果希望保持原列表 ADT 中各方法的高效率（即通过位置类来确定操作元素的位置），**就不可能显式地在序列中保留和维护各元素的秩**。为了完成诸如 getAtRank(r)之类的操作，我们不得不从列表的某一端起逐一扫描各个元素，直到发现秩为 r 的元素。于是，在最坏情况下，这些操作的时间复杂度将注定为Ω(n)。

**r <= getSize()/2,从前往后;否则从后往前**  
**注意首末节点,头尾节点**

/* * 基于双向链表实现序列 */ public class Sequence_DLNode extends List_DLNode implements Sequence { //检查秩r是否在[0, n)之间 protected void checkRank(int r, int n) throws ExceptionBoundaryViolation { if (r < 0 || r >= n) throw new ExceptionBoundaryViolation("意外：非法的秩" + r + "，应该属于[0, " + n +")"); } //若0 <= r < getSize()，则返回秩为r的元素所在的位置；否则，报错--O(n) public Position rank2Pos(int r) throws ExceptionBoundaryViolation { DLNode node; checkRank(r, getSize()); if (r <= getSize()/2) { //若秩较小，则 node = header.getNext( );//从前端开始 for (int i=0; i<r; i++) node = node.getNext();//逐一扫描 } else { //若秩较大，则 node = trailer.getPrev();//从后端开始 for (int i=1; i<getSize()-r; i++) node = node.getPrev();//逐一扫描 } return node; } //若p是序列中的合法位置，则返回存放于p处的元素的秩；否则，报错--O(n) public int pos2Rank(Position p) throws ExceptionPositionInvalid { DLNode node = header.getNext(); int r = 0; while (node != trailer) { if (node == p) return(r); node = node.getNext(); r++; } throw new ExceptionPositionInvalid("意外：作为参数的位置不属于序列"); } //取秩为r的元素--O(n) public Object getAtRank(int r) throws ExceptionBoundaryViolation { checkRank(r, getSize()); return rank2Pos(r).getElem(); } //将秩为r的元素替换为obj--O(n) public Object replaceAtRank(int r, Object obj) throws ExceptionBoundaryViolation { checkRank(r, getSize()); return replace(rank2Pos(r), obj); } //插入obj，作为秩为r的元素--O(n)；返回该元素 public Object insertAtRank(int r, Object obj) throws ExceptionBoundaryViolation { checkRank(r, getSize()+1); if (getSize() == r) insertLast(obj); else insertBefore(rank2Pos(r), obj); return obj; } //删除秩为r的元素--O(n) public Object removeAtRank(int r) throws ExceptionBoundaryViolation { checkRank(r, getSize()); return remove(rank2Pos(r)); } }

--------------------

## 3.4 迭代器 ##

迭代器是软件设计的一种模式，它是对“逐一访问所有元素”这类操作的抽象。  
迭代器本身也是一个序列S，在任何时候，迭代器中都有唯一的当前元素。迭代器还必须提供某种机制，使得我们可以不断转向S中的下一元素，并将其置为新的当前元素。

### 3.4.1 简单迭代器的 ADT ###

迭代器ADT支持的操作:

<table> 
 <thead> 
  <tr> 
   <th>操作方法</th> 
   <th>功能描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>hasNext()：</td> 
   <td>检查迭代器中是否还有剩余的元素<br>输入：无<br>输出：布尔标志</td> 
  </tr> 
  <tr> 
   <td>getNext()：</td> 
   <td>返回迭代器中的下一元素<br>输入：无<br>输出：对象</td> 
  </tr> 
 </tbody> 
</table>

#### Java 中的简单迭代器 ####

Java 已经通过 java.util.Iterator 接口提供了一个迭代器。这一接口还有一个额外的功能⎯⎯一旦转向新的对象，就将此前的对象从集合中删除。

#### 在列表和其它 ADT 中引入迭代器 ####

对象集合ADT支持的操作:

<table> 
 <thead> 
  <tr> 
   <th>操作方法</th> 
   <th>功能描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>elements()：</td> 
   <td>返回集合中所有元素的一个迭代器<br>输入：无<br>输出：迭代器</td> 
  </tr> 
 </tbody> 
</table>

对于列表、序列之类支持位置概念的 ADT，我们还提供如下方法：

<table> 
 <thead> 
  <tr> 
   <th>操作方法</th> 
   <th>功能描述</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td>positions()：</td> 
   <td>返回集合中所有位置的一个迭代器<br>输入：无<br>输出：迭代器</td> 
  </tr> 
 </tbody> 
</table>

### 3.4.2 迭代器接口 ###

/* * 迭代器ADT接口 */ public interface Iterator { boolean hasNext();//检查迭代器中是否还有剩余的元素 Object getNext();//返回迭代器中的下一元素 }

### 3.4.3 迭代器的实现 ###

#### 利用快照建立迭代器 ####

实现迭代器的一种直接办法，就是给容器中的所有元素照张“快照”，并用某一数据结构将其记录下来，当然，这种数据结构必须支持后续对这些元素的遍历操作。比如，**可以借助栈结构来存放“快照” ⎯⎯将所有元素（的引用）压入某一栈中**。于是，!isEmpty()方法就等效于 hasNext()方法，而 pop()操作则等效于 getNext()操作。

#### IteratorPosition()的实现 ####

借助列表类本身⎯⎯来实现IteratorPosition():这种实现只需保留并跟踪迭代器的当前元素，因此无论是构造方法还是hasNext()和getNext()方法，都可以在O(1)时间内完成。

/* * 基于列表实现的位置迭代器 */ public class IteratorPosition implements Iterator { private List list;//列表 private Position nextPosition;//当前（下一个）位置 //默认构造方法 public IteratorPosition() { list = null; } //构造方法 public IteratorPosition(List L) { list = L; if (list.isEmpty())//若列表为空，则 nextPosition = null;//当前位置置空 else//否则 nextPosition = list.first();//从第一个位置开始 } //检查迭代器中是否还有剩余的位置 public boolean hasNext() { return (nextPosition != null); } //返回迭代器中的下一位置 public Object getNext() throws ExceptionNoSuchElement { if (!hasNext()) throw new ExceptionNoSuchElement("意外：没有下一位置"); Position currentPosition = nextPosition; if (currentPosition == list.last())//若已到达尾位置，则 nextPosition = null;//不再有下一个位置 else//否则 nextPosition = list.getNext(currentPosition);//转向下一位置 return currentPosition; } }

#### IteratorElement() 的实现 ####

/* * 基于列表实现的元素迭代器 */ public class IteratorElement implements Iterator { private List list;//列表 private Position nextPosition;//当前（下一个）元素的位置 //默认构造方法 public IteratorElement() { list = null; } //构造方法 public IteratorElement(List L) { list = L; if (list.isEmpty())//若列表为空，则 nextPosition = null;//当前元素置空 else//否则 nextPosition = list.first();//从第一个元素开始 } //检查迭代器中是否还有剩余的元素 public boolean hasNext() { return (null != nextPosition); } //返回迭代器中的下一元素 public Object getNext() throws ExceptionNoSuchElement { if (!hasNext()) throw new ExceptionNoSuchElement("意外：没有下一元素"); Position currentPosition = nextPosition; if (currentPosition == list.last())//若已到达尾元素，则 nextPosition = null;//不再有下一元素 else//否则 nextPosition = list.getNext(currentPosition);//转向下一元素 return currentPosition.getElem(); } }

### 3.4.4 Java 中的列表及迭代器 ###

在使用迭代器的过程中，如果原容器中的内容正在被（比如另一个线程）修改，就很可能会造成危险的后果。若需在容器中的某一“位置”进行插入、删除或替换之类的操作，最好是通过一个位置对象来指明。实际上， **java.util.Iterator 的大多数实现都提供了故障快速修复（ Fail-fast）的机制⎯⎯在利用迭代器遍历某一容器的过程中，一旦发现该容器的内容有所改变，迭代器就会抛出ConcurrentModificationException 意外错并立刻退出。**

--------------------

来源于:Java数据结构,邓俊辉

[70]: /images/20220510/b1b0a485968348bda905549a08a5dd17.png