15.4 链表
下面让我们再回顾一下序列概念的图形表示：
将它与我们描绘vector内存结构的示意图相比较：
下标0本质上与迭代器v.begin()一样都指向同一个元素，并且下标v.size()与v.end()一样都指向最后一个元素之后的位置。
vector的元素在内存中是连续存储的。这并非STL序列概念所要求的特性，因此在STL中，很多算法在将一个元素插入两个已有元素的中间时都不需要移动已有的元素。上面序列抽象概念的图示意味着，在不移动其他元素的前提下进行元素插入（或元素删除）操作是可能的。STL迭代器概念支持上述操作。
直接体现上述STL序列概念的数据结构是链表（linked list）。在抽象模型中的箭头通常由指针实现。链表中的一个元素是“链接”的一部分，一个“链接”由这一元素以及一个或多个指针组成。如果链表的一个链接只包含一个指针（指向下一个链接），我们称这样的链表为单向链表，如果一个链接包含一个指向前驱链接的指针以及一个指向后继链接的指针，则这样的链表为双向链表。在后续小节中，我们将勾勒一个双向链表的实现，且该实现与C++标准库list的实现相同。双向链表的概念可图示如下：
上述概念可由代码实现：
一个Link的内存布局如下所示：
链表的实现方法和呈现给用户的方法有多种。附录C中给出了标准库所采用的一种方法。在本节中，我们将只概述链表的关键属性——能够在不影响其他已有元素的前提下插入和删除元素，展示如何遍历一个链表，以及给出链表使用的一个示例。
当你考虑使用链表时，我们强烈建议你将自己所考虑的链表操作绘图表示。图形是描绘链表操作的一种十分有效的方法。
15.4.1 链表操作
对于链表，我们需要使用哪些操作呢？
对vector所实现的操作（构造函数、大小等），除了下标。
插入（添加一个元素）和删除（移除一个元素）。
访问元素以及遍历链表：迭代器。
在STL中，上述的迭代器类型是list类的一个成员，因此我们也会这样设计：
就像“我们的”vector并没有完全实现标准库vector一样，上述list定义与标准库list定义也不完全相同。但上述list中没有任何错误，它仅仅是不完全而已。“我们的”list的目的在于加深你对链表的理解：链表是什么，list应该如何实现，以及如何使用list的关键特性。如果读者想获得更多的信息，请参考附录C或其他专家级别的C++书籍。
迭代器是STL list定义中的核心部分。迭代器被用于标示元素插入的位置以及待删除（擦除）的元素。它们也可被用于在链表中进行“导航”。迭代器的这一用途与我们在15.1节和15.3.1节中使用指针遍历数组和向量十分相似。迭代器的这一风格对于标准库算法而言十分关键（见16.1～16.3节）。
为什么不在list中使用下标操作呢？我们可以为list实现下标操作，但它会是一种极为缓慢的操作：list[1000]操作将会从第一个元素开始访问每个元素，直到访问到第1000个元素为止。如果我们希望这么做，那么可以自己实现这一操作（或使用advance()，参见15.6.2节）。因此，标准库list并没有提供下标语法。
我们将迭代器的类型作为list的成员（一个嵌套类）的原因在于，我们没有任何理由将迭代器的类型实现为全局类。这一迭代器的类型将只会由list类使用。另外，这也使得我们能够将每一容器的迭代器都命名为iterator。在标准库中存在着list<T>::iterator、vector<T>::iterator、map<K,V>::iterator等迭代器类型。
15.4.2 遍历
list迭代器必须提供*、++、==和!=操作。因为标准库中的链表为双向链表，因此该链表还提供了--操作，以实现链表的“从后”向前的遍历操作：
这些函数十分简明且极具效率：函数实现中不存在循环，不存在复杂的表达式，不存在“可疑的”函数调用。如果你还不清楚这些实现的意义，请再快速回顾一下前面的示意图。这一list迭代器只是一个指向链接的指针。注意，即使list<Elem>::iterator的实现（代码）与我们在vector和数组中用作迭代器的简单指针的实现极为不同，两者操作的意义（语义）是相同的。基本上，list迭代器提供了对Link指针的++、--、*、==和!=操作。
现在让我们再次回顾high()的实现：
我们可以将其用于list：
在上述代码中，Iterator参数的“取值”为list<int>::iterator，并且++、*和!=操作的实现都与数组的代码有很大不同，但操作的意义是相同的。模板函数high()仍然遍历数据（在这里是list）和查找最大取值。我们可以在list的任何位置插入一个元素，因此使用了push_front()在链表首部添加元素，而这一操作的目的仅仅是为了显示我们确实能够这么做。当然，我们也可以像对vector一样对list使用push_back()函数。
试一试
标准库vector不提供push_front()。为什么？为vector实现push_front()并将其与push_back()进行比较。
现在，是时候提出这样的问题了：“如果list为空会怎样？”换句话说，“如果lst.begin() == lst.end()会怎样？”在这种情况下，*p将会试图对最后一个元素ls.end()之后的位置进行解引用，这是一个灾难！或者——可能更糟地——结果可能是一个错误的随机值。
此问题的最后一种描述形式给我们带来了一个提示：可以通过比较begin()和end()测试一个链表是否为空——实际上，可以通过比较序列的开始和结束判断任何STL序列是否为空：
这是令序列的end指向最后一个元素之后的位置而不是指向最后一个元素的一个更深层次的原因：空序列不再是一种特殊情况。我们不喜欢特殊情况，因为——根据定义——我们不得不为这些特殊情况编写特殊的代码。
在我们的例子中，可以按如下方式对list进行测试：
我们采用这种形式的测试方法系统地测试STL算法。
因为标准库提供了链表，我们在这里不再继续深入探讨它的具体实现。取而代之的是，我们将简要讨论链表适用的场合（如果你对链表的实现细节感兴趣，参考习题12～14）。