前言
Should array indices start at 0 or 1? My compromise of 0.5 was rejected without, I thought, proper consideration.
— Stan Kelly-Bootle
表 (List)
我们将形如 a0,a1,a2,⋯ ,aN−1 组成的有限序列称为 list，这个 list 的大小是 N(N∈N)，我们将大小为 0 的表称之为 空表 (empty list)。
除空表外的任何表，我们从 0 开始标记元素，最后一个元素的下标为 N−1 ，那么第 i(i∈N∗)个元素是 ai−1，称 ai 是 ai+1 的 前驱 ， ai 是 ai−1 的 后继 。
注意：严蔚敏老师的数据结构中，第 i(i∈N∗) 个元素是 ai
List ADT
template <class T, class Iter> concept sequence_container = requires(T a, const T& b, typename T::const_iterator pos, Iter first, Iter last, typename T::iterator self_first, typename T::iterator self_last, size_type count, const typename T::value_type& value) { requires container<T>; requires input_iterator<Iter>; // iterator { a.rbegin() } -> typename T::reverse_iterator; { a.rend() } -> typename T::reverse_iterator; { b.rbegin() } -> typename T::const_reverse_iterator; { b.rend() } -> typename T::const_reverse_iterator; { a.crbegin() } -> typename T::const_reverse_iterator; { a.crend() } -> typename T::const_reverse_iterator; // access { a.front() } -> typename T::reference; { b.front() } -> typename T::const_reference; { a.back() } -> typename T::reference; { b.back() } -> typename T::const_reference; // capacity a.resize(count, value); // modifier { a.insert(pos, value) } -> typename T::iterator; { a.insert(pos, count, value) } -> typename T::iterator; { a.insert(pos, first, last) } -> typename T::iterator; { a.erase(pos) } -> typename T::iterator; { a.erase(self_first, self_last) } -> typename T::iterator; a.push_front(value); a.pop_front(); a.push_back(value); a.pop_back(); };
线性表的实现
顺序实现
对表的所有操作都可以使用数组实现。数组是静态分配的，无法扩容，常常使用动态分配一段数组，当容量不够时进行生长。可以生长意味着不需要对表的大小的最大值进行估计。
在生长过程中，需要线性表分配一个全新的数组，并将之前的所有元素复制进新的数组中，复制完毕后将原数组释放。因此如果你的线性表频繁要求生长，那么会导致严重的性能开销，因为每次都需要 Θ(N) 来复制每个元素。如果生长系数过大，比如说 100 倍，但是无法使用那么多时，将造成存储空间的大量浪费。因此生长一般选取 2 倍 或 1.5 倍 比例，保证不会过于频繁生长，并使存储空间由不会浪费太多。
下图就是我们根据数组对线性表的实现：
现在思考一个问题，在使用 ADT *_back 与 *_front 时，它们两个有没有差别。
*_back 操作时直接将元素在尾端加入或移除，时间复杂度 Θ(1)
*_front 操作时，由于 push 操作导致前端没有位置可以存储元素，而 pop 操作将导致前端产生一个空缺，因此它们都需要将之后的元素集体后移或前移，时间复杂度 Θ(N)
我们尝试给出一个存储结构，如下。这里并没有采用传统的使用整型变量记录当前长度和分配的容量，而是采用三个指针。其中 start 是该 container 的基址， finish 是后随最后一个元素的指针， end 则是后随数组空间的指针。因此在计算当前长度时只需要 finish−start 即可，当finish=start 意味着当前线性表为空，当 finish=end 时意味着当前线性边需要生长。
template <class Element> struct SequenceList { Element* start; Element* finish; Element* end; };
这里存储结构中并没有给出迭代器，这是因为这是一个数组结构，我们可以将指针当作迭代器使用，这个迭代器是符合 contiguous_iterator 的。因此在实现该结构时，我们可以为其提供随即访问的接口 – operator[] 和 at ，它们接收一个 size_type 类型参数 n 用以 Θ(1) 时间复杂度访问 start+n 的元素。
在使用顺序实现时，应该注意其支持快速的随机访问能力，在尾部具有高效操作，但中间或头部操作很低效。
单链表实现
为了避免插入和删除的线性开销，我们允许线性表可以不连续存储，以避免修改时的整体移动。这种方式被称之为 链表 (linked list)，linked list 由一系列在内存中不必连续的结点组成，每个结点均含有元素域和到指向后继结点的链域。该链的最后一个结点置空 (nullptr 或 NULL) 以避免不必要的麻烦。
由于这样的 linked list 是单向的，因此我们也称其为单链表。由于结点是单向 Traverse 的，我们无法向前 Traverse，因此单链表 iterator 是一个 forward_iterator 。但这也造成了一点点麻烦，我们失去了随机访问元素的能力，只能以 O(N) 的复杂度进行结点的访问，除非你已经拥有了该结点的迭代器。当你拥有一个结点的迭代器时，可以以 O(1) 的时间复杂度对其进行操作，删除或插入一个结点。
如何获取到单链表的长度呢？如果增加一个额外的长度域，对于这些结点来说是不必要的，我们只需要一个记录长度的域就好；而在结点中增加域不止造成了内存的浪费，如果用此记录长度，在对结点操作时，我们将丢失正确的长度信息，除非以 O(N)\mathcal{O}(N)O(N) 的代价修改所有结点上的长度域。我们引入一个特殊的头结点，每个线性表实例只需要一个 head 即可。为了快速在尾部进行插入，我们也需要一个指向尾部的域，方便插入操作，移除操作只能由缓慢的 Traverse 找到前驱结点
最后说明一下 end 迭代器指向 nullptr 的原因，由于我们在遍历时，认为区间是 [first,last) ，因此如果是有 finish field 作为 end 迭代器，那么我们将丢失最后一个结点。
单链表的存储结构
这里的实现使用了 BaseNode ，并在实现 Head 和 Node 时分别继承 BaseNode。由于 BaseNode 只实现关于链表链域的操作，虽然 Head 和 Node 有着不同的操作，但共享其 base class 所提供的链域操作。
struct ForwardListBaseNode { // 单链表基础结点，用于存储并处理链域 ForwardListBaseNode* next; }; struct ForwardListHead : ForwardListBaseNode { // 单链表的头结点，用于存储长度与尾结点 size_t size; ForwardListBaseNode* finish; }; template <class Element> struct ForwardListNode : ForwardListBaseNode { // 单链表的结点，用于存储真正的数据 Element value; };
单链表 BaseNode 的实现
刚刚说了 BaseNode 主要实现对链域的操作，对一个结点，主要有插入、移除结点两种操作。受限于 forward_iterator ，为了运行效率，我们对 ADT 的插入删除进行一些修改。
可以看到修改后，函数主要将该位置 pos 之后的元素进行删除，因此我们可以实现以下四个函数，用以对 insert 与 erase 的支持。但是 erase 与 insert 中都没有实现对边界条件的判定，这应该由具体实现 ForwardList 时完成。
// 将 node 插入到 pos 之后 void insert(ForwardListBaseNode* pos, ForwardListBaseNode* node) { node->next = pos->next; pos->next = node; } // 由实现范围 [first, last) 上迭代器到单链表的构造，接收单链表 [first, last) 并插入 void insert(ForwardListBaseNode* pos, ForwardListBaseNode* first, ForwardListBaseNode* last) { last->next = pos->next; pos->next = first; } // 移除 pos 之后一个的元素，并将其返回 ForwardListBaseNode* erase(ForwardListBaseNode* pos) { ForwardListBaseNode* erase = pos->next; pos->next = erase->next; return erase; } // 移除 [first + 1, last) 的所有元素，并将其 first + 1 返回 ForwardListBaseNode* erase(ForwardListBaseNode* first, ForwardListBaseNode* last) { ForwardListBaseNode* erase = first->next; first->next = last; return erase; }
对于以上的代码进行分析，我们可以得知，一旦位置、端结点确定，从 linked list 中添加或移除任意多的连续结点，其时间复杂度是 O(1) 的。至于构造和析构 [first,last) 上的元素，不再 BaseNode 的讨论范围内，它们不是针对链域的操作。
需要注意的是，我们在实现 erase 的过程中并没有删除 erase 结点指向的 next，也就是说虽然它已经不在链表中，但是通过访问其 next field 依然可以访问曾经的后继。这一操作主要是为了释放结点，erase 移除 (first,last) 后将返回 first 结点的后继，即第一个被移除的结点，我们可以依次对这些结点进行释放，直到准备释放的结点变为 last 为止。当然我们也可以将其设置为 nullptr，只不过判断条件变为了 node!=nullptr ，不过不修改也能完成这样的操作且开销更小。
双链表
单链表如果要删除当前结点，则必须遍历寻找该结点的前驱，才能将其删除。这种方法时间复杂度变成了线性，有什么方法可以让我们更快的查找该结点的前驱吗？既然链表可以指向其后继，那么在其中添加一个前驱域即可，在结点添加进链表时，只需要分别设置结点的前驱与后继即可。这种有两个指针域，一个指向前驱一个指向后继的 linked list 被称之为 双链表。
对于增加元素与删除元素，与单链表类似。不过需要注意的是，在修改时需要将目标结点的前驱、后继的指针域都加以处理，不然就会出现很多问题。
无论使用单链表还是双链表，我们都可以高效的在序列中进行插入和删除操作，不再需要这些不必要的拷贝，且不存在生长问题。但随之而来的是对数据访问的限制，我们失去了随机访问能力。
边界条件
在双链表的实现过程中需要小心处理边界条件， 请小心 代码 node->next->prev = node->prev 和 node->prev->next = node->next ，如果你释放的是最后一个结点或第一个结点，那么 node->next 或 node->prev 将等于 nullptr，而 nullptr 没有 prev 和 next 域供你使用，更不能被修改！这将直接导致程序发生错误。
这个问题同样可以在单链表中出现。但我们的单链表实现将删除 pos 的后继，实现中我们可以首先判断 pos 是不是最后一个结点，如果是的话将不进入 BaseNode 处理。那双链表可以吗？好像并不可以，因为它删除的是当前结点，如果当前结点为最后一个结点，那我们需要在 BaseNode 中添加额外的代码处理这种情况。
没有办法处理了吗？当然是有的，我们的链表实现中还有 head 供第一个结点缓冲；因此只有最后一个结点有问题，那我们为最后一个结点添加一个后随结点就好了！后随结点永远不会被删除，且可以为最后一个结点提供缓冲，防止其修改 nullptr 引发程序错误。那这个后随结点从那里产生呢，还记得我们的 Head 结点吗？它继承了 BaseNode，完全可以当作一个结点使用，这时候 Head 就不再需要其中的 finish 域了。
这样首尾相接的链表被称为之 循环链表 。左边是一个 size=7 的循环链表；右边是一个 size=0 时的循环链表，这个空表所有迭代器都指向 haed，当 traverse 时循环条件 begin≠end 或rbegin≠rend 都不会成功，traverse 直接结束，因此对循环链表的遍历并不会产生任何问题。
双链表的存储结构
双链表的存储结构相比于单链表，只需要给 BaseNode 中添加另一个指针域，并删除 Head 中的无用 finish 即可。
struct BidirectionalListBaseNode { BidirectionalListBaseNode* prev; BidirectionalListBaseNode* next; }; struct ForwardListHead : BidirectionalListBaseNode { size_t size; }; template <class Element> struct BidirectionalListNode : BidirectionalListBaseNode { Element value; };
双链表的 BaseNode 实现
我们可以 O(1) 的访问结点的前驱，因此按照 ADT 的要求来实现相关的插入与移除。同样地，我们在 BaseNode 中仅处理最核心的链域的修改。
// 将 node 插入到 pos 之前 void insert(BidirectionalListBaseNode* pos, BidirectionalListBaseNode* node) { node->prev = pos->prev; node->next = pos; node->prev->next = node->next->prev = node; } // 将 [first, last) 插入到 pos 之前，并将 first - 1 与 last 重新连接 void insert(BidirectionalListBaseNode* pos, BidirectionalListBaseNode* first, BidirectionalListBaseNode* last) { BidirectionalListBaseNode* first_prev = first->prev; first->prev->next = last; last->prev->next = pos; pos->prev->next = first; first->prev = pos->prev; pos->prev = last->prev; last->prev = first_prev; } // 移除 pos 并将 pos 的后继返回 BidirectionalListBaseNode* erase(BidirectionalListBaseNode* pos) { pos->next->prev = pos->prev; pos->prev->next = pos->next; return pos->next; } // 移除 [first, last) 的所有元素 void erase(ForwardListBaseNode* first, ForwardListBaseNode* last) { first->prev->next = last; last->prev = first->prev; }
一些关于表的算法
为了屏蔽一些不必要的实现细节，因此我们约定，使用 iterator 进行 traverse，且 iterator 可以通过 handle 取得底层的链表结点。而函数参数中的引用类型 T& 则表示着对该形式参数的修改将会修改实际参数。
合并两个已排序链表
现在假设两个链表都已按照从小到大排列，将两个链表 a 与 b 合并到 c，且合并后的链表也按照从小到大进行排列。
void __transfer(iterator& pos, iterator& c) { iterator it = pos++; insert(c.handle(), it.handle(), pos.handle()); } void merge(iterator a_begin, iterator a_end, iterator b_begin, iterator b_end, iterator& c) { while (a_begin != a_end && b_begin != b_end) { __transfer(*a_begin < *b_begin ? a_begin : b_begin, c); } if (a_begin != a_end) { insert(c.handle(), a_begin.handle(), a_end.handle()); } if (b_begin != b_end) { insert(c.handle(), b_begin.handle(), b_end.handle()); } }
引入了 __transfer 函数将找到的 a、b 当前最小的元素插入 c 中，并使其迭代器向前步进一。在 a 或 b 结束之后，我们将 a 或 b 剩余的元素全部添加到 c 的后面，这些元素是最大的一批。分析该算法的时间复杂度得 O(sizea+sizeb−1) 。
反转
反转链表是一个很有意思的操作，尤其是针对没有前驱结点的单链表来说。
void reverse(ForwardListBaseNode* head) { ForwardListBaseNode* curr = head->next; head = nullptr; while (curr != nullptr) { ListNode* next = curr->next; curr->next = head; head = curr; curr = next; } }
这个方法直接使用到了 ForwardListHead ，利用 head 指向当前结点的前驱，当 traverse 完成后，head 也顺利指向最终结果。其时间复杂度 O(N) 。我们可以将其改为递归方式，时间复杂度不变：
ForwardListBaseNode* __recursion(ForwardListBaseNode* node, ForwardListBaseNode* head) { if (!node) { return nullptr; } if (node->next == nullptr) { head->next = node; return nullptr; } ForwardListBaseNode* tmp = __recursion(node->next); node->next->next = node; node->next = nullptr; return tmp; } void reverse(ForwardListBaseNode* head) { __recursion(head->next, head); }
双链表的操作也很精彩！由于实现是循环的，因此我们只需要将每个结点的前驱后继按顺序调换位置即可。其时间复杂度同样是 O(N)
void reverse(BidirectionalListBaseNode* head) { BidirectionalListBaseNode* curr = head->next,* temp; while (curr != head) { temp = curr->next; curr->next = curr->prev; curr = curr->prev = temp; } temp = head->next; head->next = head->prev; head->prev = temp; }
