链表在图的邻接表示中的优势
Advantages of linked lists in adjacency representation of a graph
Skiena 的 Algorithm Design Manual（第 3 版，第 204 页）引用 邻接列表 而不是一般的邻接表示，定义它们为每个顶点 a 分配一个单链表 L_a 和底层集合 set(L_a) = {b | (x, b) <- edges, x == a}.
令我惊讶的是，Skiena 将单向链表作为实现集合的最终数据结构呈现 L_a。我的印象是，与数组和散列table相比，链表普遍失宠，因为：
- 它们不是缓存友好的迭代（就像数组一样），处理器速度和主内存访问之间的差距变得更加重要。 （例如 Stroustrup 的 this 视频 (7m)。）
- 它们对 table 的影响不大，尤其是在顺序不重要的情况下。链表优于数组的优点是它们允许恒定时间添加和删除。但在我们不关心顺序的情况下，这些也可以是对数组的常量时间操作，使用“交换和弹出”进行删除。散列 table 将具有恒定时间搜索的额外优势。我的理解是 hash tables 比链表或者数组更耗内存，但是这个考虑已经变得相对不那么重要了。 （在没有具体应用的情况下，这个说法可能没有意义。）
其他来源以不同方式处理邻接表。例如 Wikipedia 提供了一个实现，其中 L_a 是数组。在 Stone 的 函数式编程算法 中，L_a 是无序集合，最终实现为 Scheme 列表（反过来让我觉得很奇怪）。
My Question: Is there a consideration I'm missing which gives singly linked lists a significant advantage in adjacency representations?
我郑重请求，在您投票关闭此问题之前，或 post 以不加理会的语气评论 table 之前，您问问自己是否真的在帮助该网站实现其目标通过这样做。
我认为在大多数现实世界的用例中，单链表作为邻接表的默认表示形式没有任何普遍共识。
但是，单链表几乎是您可能拥有的最限制邻接表的实现，因此在一本关于“算法设计”的书中，它使得在这种表示中考虑邻接列表是有意义的，除非你需要从它们中得到一些特殊的东西，比如随机访问、双向迭代、二进制搜索等。
当谈到算法在显式图上的实际实现时（大多数实现是在隐式图上），我认为单链表通常不是一个好的选择。
我的首选邻接表图形表示是一对平行数组：
- 顶点编号从 0 到 n-1
- 有一个 边数组，其中包含按源顶点编号排序的所有边。对于无向图，每条边在这里出现两次。源顶点通常不需要存储在这里。
- 有一个顶点数组，它为每个顶点存储其边在边数组中的结束位置。
这是一个很好的、紧凑的、缓存友好的表示，易于使用并且只需要两次分配。
我通常可以找到一种简单的方法来在线性时间内构建这样的图，首先用计数填充顶点数组，然后将计数更改为起始位置（移位累积和），然后填充边数组，随着边缘的添加推进这些位置。
Skiena 的 Algorithm Design Manual（第 3 版，第 204 页）引用 邻接列表 而不是一般的邻接表示，定义它们为每个顶点 a 分配一个单链表 L_a 和底层集合 set(L_a) = {b | (x, b) <- edges, x == a}.
令我惊讶的是，Skiena 将单向链表作为实现集合的最终数据结构呈现 L_a。我的印象是，与数组和散列table相比，链表普遍失宠，因为：
- 它们不是缓存友好的迭代（就像数组一样），处理器速度和主内存访问之间的差距变得更加重要。 （例如 Stroustrup 的 this 视频 (7m)。）
- 它们对 table 的影响不大，尤其是在顺序不重要的情况下。链表优于数组的优点是它们允许恒定时间添加和删除。但在我们不关心顺序的情况下，这些也可以是对数组的常量时间操作，使用“交换和弹出”进行删除。散列 table 将具有恒定时间搜索的额外优势。我的理解是 hash tables 比链表或者数组更耗内存，但是这个考虑已经变得相对不那么重要了。 （在没有具体应用的情况下，这个说法可能没有意义。）
其他来源以不同方式处理邻接表。例如 Wikipedia 提供了一个实现，其中 L_a 是数组。在 Stone 的 函数式编程算法 中，L_a 是无序集合，最终实现为 Scheme 列表（反过来让我觉得很奇怪）。
My Question: Is there a consideration I'm missing which gives singly linked lists a significant advantage in adjacency representations?
我郑重请求，在您投票关闭此问题之前，或 post 以不加理会的语气评论 table 之前，您问问自己是否真的在帮助该网站实现其目标通过这样做。
我认为在大多数现实世界的用例中，单链表作为邻接表的默认表示形式没有任何普遍共识。
但是，单链表几乎是您可能拥有的最限制邻接表的实现，因此在一本关于“算法设计”的书中，它使得在这种表示中考虑邻接列表是有意义的，除非你需要从它们中得到一些特殊的东西，比如随机访问、双向迭代、二进制搜索等。
当谈到算法在显式图上的实际实现时（大多数实现是在隐式图上），我认为单链表通常不是一个好的选择。
我的首选邻接表图形表示是一对平行数组：
- 顶点编号从 0 到 n-1
- 有一个 边数组，其中包含按源顶点编号排序的所有边。对于无向图，每条边在这里出现两次。源顶点通常不需要存储在这里。
- 有一个顶点数组，它为每个顶点存储其边在边数组中的结束位置。
这是一个很好的、紧凑的、缓存友好的表示，易于使用并且只需要两次分配。
我通常可以找到一种简单的方法来在线性时间内构建这样的图，首先用计数填充顶点数组，然后将计数更改为起始位置（移位累积和），然后填充边数组，随着边缘的添加推进这些位置。