c# - 从 SQL 数据库加载双向链表

Question

我有一个 QueueList 表：

{Id, Queue_Instance_ID, Parent_Queue_Instance_ID, Child_Queue_Instance_ID}

什么是最有效的方法把它塞进一个LinkedList<QueueList>？你觉得我能低于o(n^2)吗？

Answer 1

O(n) 比 O(n^2) 好，对吧？;)

我假设父 ID 和子 ID 实际上是列表中的上一个和下一个 ID。

首先将这些项目放入字典中，以便您可以轻松地在QueueInstanceId. 在此循环中，您还可以找到第一项。然后，您只需将项目添加到链表并使用字典获取下一个项目。C# 中的示例：

Dictionary<int, QueueList> lookup = new Dictionary<int, QueueList>();
QueueList first = null;
foreach (QueueList item in source) {
    lookup.Add(item.QueueInstanceId, item);
    if (item.ParentQueueInstanceId == -1) {
        first = item;
    }
}
LinkedList<QueueList> list = new LinkedList<QueueList>();
do {
    list.AddLast(first);
} while (lookup.TryGetValue(first.ChildQueueInstanceId, out first));

向字典中添加项并通过key获取它们是O(1)的操作，每个循环都是源列表的长度，所以都是O(n)的操作。

Answer 2

稍微考虑一下，您可以在 O(n) 时间内完成，尽管这需要一些额外的东西，会增加一些开销。（仍然是 O(n)）。

您可以使用某种通用哈希方案，以便您可以构建一个好的哈希表。本质上，通过实例 id 散列。

- 取出每个队列，并将其放入某种双向链接的节点中。- 将每个节点插入哈希表。- 插入时，检查父项和/或子项是否在哈希表中并进行相应链接。_ 完成后，从头开始（您应该能够在第一遍中弄清楚），遍历列表并将其添加到您的 LinkedList 或仅使用生成的双向链表。

这需要 O(n) 一次，哈希表需要 O(n) 来初始化，插入是 O(1)。

留给您的问题是选择一个可以为您提供这些结果的良好哈希表实现。

此外，您必须考虑内存开销，因为我不知道您期望多少结果。希望足以留在记忆中。

我不知道也不认为有基于 SQL 查询的解决方案，但我的 SQL 知识非常有限。

希望这可以帮助！