3.2 无序列表

模仿向量循秩访问，通过重载下标操作符实现

template <typename T> // assert: 0 <= r < size
T List<T>::operator[] (Rank r) const { // 效率低
    Posi(T) p = first(); // 从首节点出发
    while (0 < r--) p = p -> succ; // 顺数第r个节点
    return p -> data; // 目标节点
} // 作一节点的秩，即其前驱总数

查找
在节点p（可能是trailer）的n个（真）前驱中，找到等于e的最后者

template <typename T> // 从外部调用时，0 <= n <= rank(p) < _size
Posi(T) List<T>::find(T const & e, int n, Posi(T) p) const { // 顺序查找
    while (0 < n--) // 从右向左，逐个将p的前驱与e比对
        if (e == (p = p -> pred) -> data)
            return p; // 直至命中或范围越界
    return NULL; // 若越出左边界，则查找失败
} // header的存在使处理更简洁

插入

template <typename T> Posi(T) List<T>::insertBefore(Posi(T) p, T const& e) {
    _size++;
    return p -> insertAsPred(e); // e作为p的前驱插入
}

template <typename T> // 前插入算法（后插入算法完全对称）
Posi(T) ListNode<T>:: insertAsPred(T const& e) {
    Posi(T) x = new ListNode(e, pred, this); // 创建
    pred -> succ = x;
    pred = x;
    return x; // 建立链接，返回新节点的位置
}

基于复制的构造

template <typename T> // 基本接口
void List<T>::copyNodes(Posi(T) p, int) {
    init(); // 创建头、尾哨兵节点并初始化
    while (n--) { // 将起自p的n项依次作为末节点插入
        insertAsLast(p -> data);
        p = p -> succ;
    }
}

删除

template <typename T> // 删除合法位置p处节点，返回数值
T List<T>::remove (Posi(T) p) {
    T e = p -> data; // 备份待删除节点数值（设类型T可直接赋值）
    p -> pred -> succ = p -> succ;
    p -> succ -> pred = p -> pred;
    delete p;
    _size--;
    return e; // 返回备份数值
}

析构

template <typename T> List<T>::~List() { // 列表析构
    clear(); // 清空列表
    delete header; // 释放头哨兵节点
    delete trailer; // 释放尾哨兵节点
}

template <typename T> int List<T>::clear() { // 清空列表
    int oldSize = _size;
    while (0 < _size) // 反复删除首节点，直至列表为空
        remove(header -> succ);
    return oldSize;
}

唯一化

template <typename T> int List<T>::deduplicate() { // 剔除无序列表中的重复节点
    if (_size < 2)
        return 0; // 平凡列表自然无重复
    int oldSize = _size; // 记录原规模
    Posi(T) p = first();
    Rank r = 1; // p从首节点起
    while (trailer != (p = p -> succ)) { // 依次直至末节点
        Posi(T) q = find(p -> data, r, p); // 在p的r个（真）前驱中，查找与之相同者
        q ? remove(q) : r++; // 若的确存在，则删除之，否则秩递增
    } // assert: 循环过程中任意时刻，p的所有前驱互不相同
    return oldSize - _size; // 列表规模变化量，即被删除元素总数
}