数据结构(六) -- 列表

一，列表

实际上，除了通过秩，我们还可以通过其它途径来确定元素在序列中的位置。我们希望能够为序列扩充若干新的方法，使之能够直接以某些节点做为参数，找到所需的节点并对其实施操作。

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

按照这一思路，依然可以将列表看作是存放元素的容器，其中的元素各有自己的存放位置，我们只是将它们的位置组织为一个线性的结构。

由秩到位置

---

二，列表ADT(AbstractDataType)

在引入位置概念对列表“节点”进行封装之后，就可以得到一个新的序列ADT，称作列表（List）。该ADT 支持对列表S 的以下方法：

操作方法	功能描述
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(p)	删除S 中位置p 处的元素 输入：一个位置 输出：对象

---

三，基于双向链表实现的列表

举一个实现插入的例子

接口

package dsa.List;

import dsa.Vector.ExceptionBoundaryViolation;
import other.Position;

/*
 * 列表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();
}

package dsa.List;

/*
 * 当作为参数的数组下标、向量的秩或列表的位置非法时，本意外将被抛出
 */

public class ExceptionPositionInvalid extends RuntimeException {
    public ExceptionPositionInvalid(String err) {
        super(err);
    }
}

package dsa.List;

public class ExceptionListEmpty extends RuntimeException {

    public ExceptionListEmpty(String err) {
        super(err);
    }

}

实现：

package dsa.List;

import other.Position;
import dsa.Deque.DLNode;
import dsa.Vector.ExceptionBoundaryViolation;

/*
 * 基于双向链表实现列表结构
 */

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 isNULL!!!");
        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);
    }
}