对于图实现 API，使用 Bag 数据结构与其他数据结构（如 Set 或 Linkedlist）相比有哪些优势？

Question

这是与问题相关的示例代码。这个 API 试图实现一个具有邻接表表示的图，该图是由图中每个顶点索引的 Bags 数组。

public class Graph{

private final int V;          //no. of vertices
private Bag<Integer>[] adj;  // A bag for each vertex to store all adjacent vertices
.
.
.
}

在这里使用 Bag 比链表或 Set 有什么优势。我知道袋子是无序的，但是当它们不能节省我们的时间或空间时，为什么要使用无序列表呢？

Answer 1

每种数据结构都可以在不同的情况下使用：

Set（特别是HashSet）可以是无序唯一元素的列表。另一方面，Bags是多重集（可能包含重复元素的无序集合）。

至于LinkedList它们提供更简单的链接操作，即在不同的地方添加元素，要容易得多（恒定时间）。

Answer 2

Bag 可能是用二叉搜索树或哈希表实现的，为我们提供了 O(log n) 或 O(1) 搜索。链表将提供 O(n) 搜索。

Set 只允许唯一的元素，因此如果您需要存储重复项，则需要 Bag。Java Collections 库中的 TreeSet 或 HashSet 将分别为我们提供 O(log n) 或 O(1) 搜索。

一般来说，当您经常需要执行搜索或删除操作时，Set 或 Bag 接口会更适合。如果您只需要添加到集合的末尾并对其进行迭代，则不会有太大区别。