数据结构(六) -- 列表

一，列表

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

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

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

由秩到位置

二，列表ADT(AbstractDataType)

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

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

举一个实现插入的例子

接口

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);
    }
}