0.概述

介绍下无序列表相关接口，相关接口需要依赖ListNode类，接口如下：

using Rank = unsigned int; //秩

template <typename T> struct ListNode;
template <typename T> using ListNodePosi = ListNode<T>*; //列表节点位置
template <typename T> struct ListNode { //列表节点模板类（以双向链表形式实现）
// 成员
   T data; ListNodePosi<T> pred, succ; //数值、前驱、后继
// 构造函数
   ListNode() {} //针对header和trailer的构造
   ListNode ( T e, ListNodePosi<T> p = NULL, ListNodePosi<T> s = NULL )
      : data( e ), pred( p ), succ( s ) {} //默认构造器
// 操作接口
   ListNodePosi<T> insertAsPred( T const& e ); //紧靠当前节点之前插入新节点
   ListNodePosi<T> insertAsSucc( T const& e ); //紧随当前节点之后插入新节点
};

1.插入与构造

1.1 插入

将节点插至列表的插入算法接口多种，

template <typename T> 
ListNodePosi<T> List<T>::insertAsFirst( T const& e )
   { _size++; return header->insertAsSucc( e ); } // e当作首节点插入

template <typename T> 
ListNodePosi<T> List<T>::insertAsLast( T const& e )
   { _size++; return trailer->insertAsPred( e ); } // e当作末节点插入

template <typename T> 
ListNodePosi<T> List<T>::insert( ListNodePosi<T> p, T const& e )
   { _size++; return p->insertAsSucc( e ); } // e当作p的后继插入

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

但都可转化为列表节点对象的前插入或后插入接口。

1.1.1 前插入

拓扑连接关系如图a,b,c,d。

注意：列表规模记录的更新由上层调用者负责。另外，得益于头哨兵节点（头尾节点）的存在，即便当前节点为列表的首节点也适用。

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

template <typename T> //将e紧靠当前节点之前插入于当前节点所属列表（设有哨兵头节点header）
ListNodePosi<T> ListNode<T>::insertAsPred( T const& e ) {
   ListNodePosi<T> x = new ListNode( e, pred, this ); //创建新节点
   pred->succ = x; pred = x; //设置正向链接
   return x; //返回新节点的位置
}

参数e在参数p前，以方便理解接口语义。insert(e,p)，节点p前插入元素e。

1.1.2后插入

template <typename T> 
ListNodePosi<T> List<T>::insert( ListNodePosi<T> p, T const& e )//接口与语义对应，参数e在p后
   { _size++; return p->insertAsSucc( e ); } // e当作p的后继插入

template <typename T> //将e紧随当前节点之后插入于当前节点所属列表（设有哨兵尾节点trailer）
ListNodePosi<T> ListNode<T>::insertAsSucc( T const& e ) {
   ListNodePosi<T> x = new ListNode( e, this, succ ); //创建新节点
   succ->pred = x; succ = x; //设置逆向链接
   return x; //返回新节点的位置
}

1.1.3 复杂度

上述两种插入操作过程，仅涉及局部的两个原有节点和一个新节点，且不含任何迭代或递归。若假设当前节点已经定位，不计入此前的查找所消耗的时间，则它们都可在常数时间内完成。

1.2 基于复制构造

1.2.1 copyNodes()

尽管这里提供了多种形式，以允许对原列表的整体或局部复制，但其实质过程均大同小异，都可概括和转化为底层内部方法copyNodes()。

template <typename T> //列表内部方法：复制列表中自位置p起的n项
void List<T>::copyNodes( ListNodePosi<T> p, Rank n ) { // p合法，且至少有n-1个真后继
   init(); //创建头、尾哨兵节点并做初始化
   while ( n-- ) { insertAsLast( p->data ); p = p->succ; } //将起自p的n项依次作为末节点插入
}

1.2.2 基于复制构造

基于上述copyNodes()方法可以实现多种接口，通过复制已有列表的区间或整体，构造出新列表。

template <typename T> //复制列表中自位置p起的n项（assert: p为合法位置，且至少有n-1个后继节点）
List<T>::List( ListNodePosi<T> p, Rank n ) { copyNodes( p, n ); }

template <typename T> //整体复制列表L
List<T>::List( List<T> const& L ) { copyNodes( L.first(), L._size ); }

template <typename T> //复制L中自第r项起的n项（assert: r+n <= L._size）
List<T>::List( List<T> const& L, Rank r, Rank n ) {
   ListNodePosi<T> p = L.first();
   while ( 0 < r-- ) p = p->succ;
   copyNodes ( p, n );
}

1.2.3 复杂度

复制接口的总体复杂度应为O(r + n + 1)。

2.删除与析构

2.1 删除

2.1.1 实现

删除节点后，列表的拓扑连接关系如图a,b,c,d。

template <typename T> 
T List<T>::remove( ListNodePosi<T> p ) { //删除合法节点p
   T e = p->data; //备份待删除节点的数值（假定T类型可直接赋值）
   p->pred->succ = p->succ; p->succ->pred = p->pred; //短路联接
   delete p; _size--; //释放节点，更新规模
   return e; //返回备份的数值
} //O(1)

2.1.2 复杂度

以上过程仅涉及常数次基本操作，故若不计入此前为查找并确定位置p所消耗的时间，列表的节点删除操作可在常数时间内完成。

2.2 析构

2.2.1 释放资源及清除节点

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

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

列表的析构需首先调用clear()接口删除并释放所有对外部有效的节点，然后释放内部的头、尾哨兵节点。

2.2.2 复杂度

这里的时间消耗主要来自clear()操作，该操作通过remove()接口反复删除列表的首节点。因此，clear()方法以及整个析构方法的运行时间应为O(n)，线性正比于列表原先的规模。

3.查找

3.1 实现

template <typename T> //在无序列表内节点p（可能是trailer）的n个（真）前驱中，找到等于e的最后者
ListNodePosi<T> List<T>::find( T const& e, Rank n, ListNodePosi<T> p ) const {
   while ( 0 < n-- ) //（0 <= n <= Rank(p) < _size）对于p的最近的n个前驱，从右向左
      if ( e == ( p = p->pred )->data ) return p; //逐个比对，直至命中或范围越界
   return NULL; //p越出左边界意味着区间内不含e，查找失败
} //失败时，返回NULL

注意：若列表中待查找的元素e有多个，返回秩最大者。

3.2 复杂度

以上算法的思路及过程，与无序向量的顺序查找算法Vector::find()相仿，故时间复杂度也应是O(n)，线性正比于查找区间的宽度。

4.唯一化

4.1 实现

与算法Vector::deduplicate()类似，这里也是自前向后依次处理各节点p，一旦通过find()接口在p的前驱中查到雷同者，则随即调用remove()接口将其删除。

4.2 复杂度

与无序向量的去重算法一样，该算法总共需做O(n)步迭代。每一步迭代中find()操作所需的时间线性正比于查找区间宽度，即当前节点的秩；列表节点每次remove()操作仅需常数时间。因此，总体执行时间应为：
1 + 2 + 3 + … + n = n∙(n + 1) / 2 = O$(n^2)$
相对于无序向量，尽管此处节点删除操作所需的时间减少，但总体渐进复杂度并无改进。

5.遍历

template <typename T> 
void List<T>::traverse( void ( *visit )( T& ) ) //借助函数指针机制遍历
{  for ( ListNodePosi<T> p = header->succ; p != trailer; p = p->succ ) visit ( p->data );  }


template <typename T> template <typename VST> //元素类型、操作器
void List<T>::traverse( VST& visit ) //借助函数对象机制遍历
{  for ( ListNodePosi<T> p = header->succ; p != trailer; p = p->succ ) visit ( p->data );  }

该接口的设计思路与实现方式，与向量的对应接口如出一辙，复杂度也相同O(n)。