链表中的频率计数

Question

我有下面的链表结构：

struct Node {
    int type;
    int otherInfo;
    Node * next;
}

我想创建一个排序的(最终)链表，跟踪每个"type“出现的次数。示例节点为：

struct Node2 {
    int type;
    int frequency;
    //A linked list to keep track of the "otherInfo"
    Node2 * next;
}

我目前的算法是O(n^2)，这是不合理的，因为原始链表有时可以有超过30,000个元素。有没有更有效的方法来做到这一点？

注意: type几乎可以是任何正整数，所以我不能简单地创建一个以type作为索引的静态数组。

编辑:频率列表不必是链表。我举了个例子。在程序的后面，我使用堆对频率列表进行排序。我只需要能够稍后遍历频率列表。

Answer 1

听起来你真正需要的是一张地图或者一个基本的二进制搜索树。键类型将是您的type值，值类型将保存您的frequency。

Answer 2

迭代您的原始链表并构建一个辅助数据结构，它是type->count的映射，然后使用该辅助数据结构来构建您的频率链表(如果您确实需要它作为一个链表，这似乎不常见)。

如果您对二级映射使用类似于散列映射的东西，那么这个值应该相当于O (n ) (n是原始列表的大小)，并且渐近地(或者在实践中，如果您的散列映射是好的)不会比这个值更好。

Answer 3

排序结构也需要是链表有什么原因吗？我会使用一个哈希表，它的键是"type“，频率值是。在O(n)时间内，你可以遍历列表：

while(node.next != null)
    hashtable[type]++;

这就得到了你的频率索引。然后，您只需将其转储到一个排序的序列中-我将使用二叉树，但如果您真的必须使用二叉树，您也可以使用链表。