C++程序设计：原理与实践（基础篇）（原书第2版）

12.9.3　实例：链表

链表是最普通、最有用的数据结构之一。列表通常由一些“链接”组成，每个链接会保存一些信息和指向其他链接的指针。这是指针的典型用途之一。例如，一个挪威众神的短链表可图示如下：

一个像这样的链表被称为双向链表（doubly-linked list），对每个链接，我们都可以获得其前驱与后继。一个只能找到后继的列表被称为单向链表（singly-linked list）。当我们希望很容易地移除一个元素时，应使用双向链表。我们可以定义链接如下：

如果获得一个链接，我们可以使用succ指针到达它的后继，或者使用prev指针到达它的前驱。我们使用空指针来表示一个没有后继或前驱的链接。我们可以构造自己的挪威众神链表如下：

我们构建链表的方式是创建多个Link，并如图中所示将它们连接起来：首先是Thor，然后是Odin，它是Thor的前驱，最后是Freia，它是Odin的前驱。你可以沿着指针查看，我们构建了正确的链表，每个后继和前驱都指向正确的神。但是，这段代码有些混乱晦涩，因为我们没有明确地定义和命名插入操作。 ...