本文主要涵盖列表(双向链表)的设计及其排序算法的总结。列表是一种典型的动态存储结构。其中的数据，分散为一系列称作节点(node)的单位，节点之间通过指针相互索引和访问。为了引入新节点或删除原有节点，只需在局部调整少量相关节点之间的指针。这就意味着，采用动态存储策略，可以大大降低动态操作的成本。
1.1 结点的设计
列表是由一个个结点链接而成，其基本结构便是节点(下文称节点为Node)。Node的良好设计可以减少列表的设计难度。根据列表的特性，一个Node一般包括数据、指向前驱的指针和指向后继的指针。很显然我们需要将其封装入一个结构体(C++增强了结构体的功能，可以作为类使用)或类内，为了优化列表的设计、简化Node的使用，
1）我们可以设计Node的构造函数并在构造函数内为其指定前驱和后继；
2）除此以外，我们还可以定义插入当前节点之前和之后的插入函数，这可以简化列表的Node的插入操作。
Node的设计函数如下所示：
//列表结点的设计
struct MyListNode
{
//数据定义
T m_data;
//指向前驱的指针
MyListNode<T>* m_pred;
//指向后继的指针
MyListNode<T>* m_succ;
//构造函数
//默认构造函数，前驱和后继为nullptr
MyListNode() { m_pred = nullptr; m_succ = nullptr; }
//可以指向前驱和后继的构造函数
MyListNode(T data, MyListNode<T>* pred=nullptr, MyListNode<T>* succ= nullptr)
:m_data(data),m_pred(pred),m_succ(succ){}
//操作接口
//由于创建新节点时已经创建好一条链接关系
//若作为当前节点的前驱插入，则注意：1谁作为当前节点的前驱 2谁的后继是当前节点
//若作为当前节点的后继插入，则注意：1当前节点是谁的前驱 2当前节点的后继是谁
//作为当前节点前驱插入
MyListNode<T>* InsertAsPred(const T& data)
{
//创建新节点，以当前节点的前驱作为前驱，以当前节点作为后继 则 pred<-- new node -->this
MyListNode<T>* p_node = new MyListNode<T>(data, m_pred, this);
//由于构造新结点时已经为新结点指定了前驱和后继
//故这里只需将当前节点的前驱后继设为新节点，当前节点的前驱设为新节点
// pred--> new node <-- this
//将当前节点的后继设为新节点
m_pred->m_succ = p_node;
//将当前节点的前驱设为新节点
m_pred = p_node;
return p_node;
}
//作为当前节点后继插入
MyListNode<T>* InsertAsSucc(const T& data)
{
//插入原理 与InsertAsPred 类似
//创建新节点，以当前节点作为前驱，当前节点的后继作为后继 this <-- new node --> succ
MyListNode<T>* p_node = new MyListNode<T>(data, this, m_succ);
// 由于构造新结点时已经为新结点指定了前驱和后继
//故这里只需将当前节点的前驱后继设为新节点，当前节点的前驱设为新节点
// this <-- new node <-- succ
//当前节点的后继指向新节点
m_succ = p_node;
//当前节点的后继指向新节点
m_succ->m_pred = p_node;
return p_node;
}
};
1.2 列表的设计
列表是在节点的基础上设计的，良好的节点设计可以大大简化列表的设计。
列表的设计包括一个私有的头节点(header)和尾节点(tailer)，二者对外不可见，仅用于对数据的管理和跟踪，不用于数据的存储。
列表的第1个元素为header的后继，最后1个元素为tailer的前驱。若列表内没有元素则header的后继为tailer，tailer的前驱为header。
综上，列表的结构如下：
由于列表不可随机存取，故列表只能根据提供的起始节点进行逐一对比查找，故其查找的复杂度O(n).
但是根据其查找的用途不同，我们根据列表是否有序进行不同的查找，返回不同的结果。
1）对于无序列表，若找不到需要的数据，则直接返回nullptr即可；
2）但是对于有序列表的查找，我们一般需要使用其返回结果进行插入、排序之类的操作，所以对其返回结果有特别的要求。
2.1 无序列表的查找
找到直接返回对应节点的地址，找不到直接返回nullptr.
//对无序列表进行查找，若没有找到则直接返回nullptr
//该查找向前查找，向后查找与此类似
// data ：需要查找的数据
// num ：向前查找的数据数目
// p_node ：查找的起始点
//若查找整个序列 则为 Find(data,myList.Size(),myList.Last());
template<typename T>
MyListNode<T>* MyList<T>::Find(T data,int num, MyListNode<T>* p_node)
{
//依次向前查找逐一比对
while ((num--) && ((p_node =p_node->m_pred)!= m_header))
{
if (data == p_node->m_data)
{
return p_node;
}
}
//若找不到则返回nullptr
return nullptr;
}
2.2 有序列表的查找
对于有序列表的查找，我们一般需要使用其查找结果。假设有序列表升序排列(也就是从小到大排列，也可能有重复数据)，如果我们需要将一数据A插入到当前列表List且仍保持List有序，那么
1）如果能在列表中找到该数据A，则我们希望其插入到重复数据的最后一个；
2）如果不能找到该数据A，则我们希望返回小于该数据的第一个数据B的位置Addr_B，那么我们可以将数据A插入数据B的后面而保持List有序。
为了满足上述要求，则有序列表的查找算法的返回值应为上述情况对应的值，查找算法如下设计：
//适合有序列表的查找方法,返回小于当前元素的第一个位置
//或者返回等于该元素的重复元素的最后一个位置
//如果没有找到小于或等于当前元素的元素，则返回左边界的前驱.有可能是m_header
//该查找向前查找，向后查找与此类似
// data ：需要查找的数据
// num ：向前查找的数据数目
// p_node ：查找的起始点
//若查找整个序列 则为 Find(data,myList.Size(),myList.Last());
template<typename T>
MyListNode<T>* MyList<T>::Search(T data, int num, MyListNode<T>* p_node)
{
while (num-- >= 0)
{
if ((p_node = p_node->m_pred)->m_data <= data)
break;
//找到小于等于指定元素的元素则终止查找，返回小于当前元素的第一个位置
//或者返回重复元素的最后一个位置
}
return p_node;
}
列表的排序算法主要包括插入排序、选择排序和归并排序
3.1 插入排序
插入排序的算法的思路为：
1）设当前节点p_node之前的数据为有序的(设为front_list)，之后为无序的；
2）利用有序查找Search函数，找到当前节点p_node在front_list中的位置，将当前节点插入到front_list;
3)p_node移动到下一节点，删除已经插入到front_list的节点。
示意图如下
实现如下：
/插入排序实现
//p_node ：开始排序的起点
//num ：要排序的节点数目
//example：对全列表排序InsertionSort(myList.First(),myList.Size();
template<typename T>
void MyList<T>::InsertionSort(MyListNode<T>* p_node,int num)
{
for (int i = 0; i < num; i++)
{
//查找当前节点p_node在p_node之前的(有序)数据中应在的位置insert_index
MyListNode<T*> insert_index = Search(p_node->m_data, i, p_node);
//将当前节点插入 insert_index
InsertAsAfter(insert_index, p_node->m_data);
//移至下一节点
p_node = p_node->m_succ;
//删除已插入有序数据的原节点
Remove(p_node->m_pred);
}
}
3.2 选择排序
选择排序的基本思路为:
1）将列表分为两部分，前半部分的数据为无序的(设为front_list)，后半部分的数据为有序的(设为rear_list)；
2) 查找front_list中的的最大值max_node并将其从front_list中移除；
3）将max_node插入到front_list的最后端，也是有序列表第一位之前；
4）front_list减少1节点，rear_list增加1节点，再循环2-4步骤；
示意图如下：
代码实现如下：
/选择排序
//p_node :排序的起点
//num :要排序的节点的数目
//示例 :对全list排序 SeletcionSort(myList.First(),myList.Size());
template<typename T>
void MyList<T>::SelectionSort(MyListNode<T>* p_node, int num)
{
//定义有序列表的第一个元素位置
MyListNode<T>* tailer = p_node;
//定义无序列表的第一个位置的前驱
MyListNode<T>* header = p_node->m_pred;
//显然，选择排序需要从后往前排序
//该步骤循环往后，定义有序列表的第一个元素位置
//若当前有序列表为空，则为待排序列表最后一个元素的后继，可能为m_tailer
for (int i = 0; i < num; i++)
tailer = tailer->m_succ;
for (int i = num; i >1; i--)
{
//寻找无序列表的最大值
MyListNode<T>* max_node = SelectMax(header->m_succ, i);
//移除无序列表中的最大值max_node，并将最大值插入到无序列表的最后一位，也是有序列表第一位之前
//相当于交换二者的值
InsertAsBefore(tailer,Remove(max_node));
//有序列表的第一位元素向前移动一位
//有序序列增加一个节点
tailer = tailer->m_pred;
//for循环中的i-- 表示无序序列减少1个节点，SelectMax查找的节点数目减少1个
}
}
3.3归并排序
归并排序的基本思路为：
1）分而治之，将无序列表逐次分为前列表(front_list)和后列表(rear_list)，直至两个列表只有一个元素;
2)将front_list与rear_list按照顺序合并,由于列表分割是从大到小，故合并后仍为列表的一部分设为half_list，然后与对应的另一半other_half_list进行有序合并，循环往复直至归并完成，排序也相应完成。
示意图如下所示：
代码实现如下所示：
//p_node ：需要归并的列表P(当前列表)的起始点
//p_num ：需要归并的列表P(当前列表)的节点数目
//src_list ：需要归并的列表Q
//q_node ：需要归并的列表Q的起始点
//q_num ：需要归并的列表Q的节点数目
//该函数是将q_node开始的q_num个节点归并到p_node开始的列表内
template<typename T>
void MyList<T>::Merge(MyListNode<T>* &p_node, int p_num, MyList<T> &src_list,MyListNode<T>* q_node, int q_num)
{
//保存当前列表P的起始点p_node的前驱作为归并后列表的前驱
//这一点很重要，因为后边列表的变更可能修改第一项从而导致无法寻项
MyListNode<T>* header = p_node->m_pred;
//下列程序中将p_node作为归并列表(MergeList)中最后一个元素的后继来使用
//q_num==0 表示Q列表归并完成
while (0<q_num)
{
//如果P列表未归并完成且p_node->m_data <= q_node->m_data则p_node插入到归并列表MergeList
if ((0 < p_num) && (p_node->m_data <= q_node->m_data))
{
//p_node被归并后移动到下一节点
p_node = p_node->m_succ;
//若干p_node==q_node,则P列表已归并完成
if(q_node==p_node)
break;
//P列表虚归并的节点数目减1
p_num--;
}
else
{
//若P列表归并完成或者p_node->m_data > q_node->m_data则q_node插入到汇报列表MergeList
InsertAsBefore(p_node, q_node->m_data);
//q_node被归并后移动到下一节点
q_node = q_node->m_succ;
//移除已经归并后的q_node
src_list.Remove(q_node->m_pred);
//Q列表需归并的节点数目减1
q_num--;
}
}
p_node = header->m_succ;
}
//归并排序的实现
//p_node ：要排序列表的起始节点
//num ：要排序节点的数目
template<typename T>
void MyList<T>::MergeSort(MyListNode<T>* &p_node, int num)
{
if (num < 2)
return;
//求出列表的中点
int mid = num >> 1;
//求出后半列表的起始节点
MyListNode<T>* q_node = p_node;
for (int i = 0; i < mid; i++)
{
q_node = q_node->m_succ;
}
MergeSort(p_node, mid); //对前半部分列表进行递归划分
MergeSort(q_node, num - mid); //对后半部分列表进行递归划分
Merge(p_node, mid, *this, q_node, num - mid); //对划分好的前后列表进行归并，依次迭代直至归并完成，排序也完成
}