本文共 13548 字，大约阅读时间需要 45 分钟。

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

3.1 向量与数组

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

3.1.1 向量 ADT

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

一种直截了当的方法就是采用数组来实现向量：下标为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类的对比

向量 ADT 中的方法	java.util.ArrayList 类的方法
getSize()	getSize()
isEmpty()	isEmpty()
getAtRank()	get()
replaceAtRank()	set()
insertAtRank()	add()
removeAtRank()	remove()

---

3.2 列表

3.2.1 基于节点的操作

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

3.2.2 由秩到位置

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

3.2.3 列表 ADT

列表ADT支持的方法:

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

上述列表 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); }}

3.3 序列

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

3.3.1 序列 ADT

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

/** 序列接口*/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

---

3.4 迭代器

迭代器是软件设计的一种模式，它是对“逐一访问所有元素”这类操作的抽象。

迭代器本身也是一个序列S，在任何时候，迭代器中都有唯一的当前元素。迭代器还必须提供某种机制，使得我们可以不断转向S中的下一元素，并将其置为新的当前元素。

3.4.1 简单迭代器的 ADT

迭代器ADT支持的操作:

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

Java 中的简单迭代器

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

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

对象集合ADT支持的操作:

操作方法	功能描述
elements()：	返回集合中所有元素的一个迭代器 输入：无 输出：迭代器

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

操作方法	功能描述
positions()：	返回集合中所有位置的一个迭代器 输入：无 输出：迭代器

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数据结构,邓俊辉