CODEWITHSUNDEEP
c++
matzahboy
matzahboy

Reputation: 3024

Frequency count in a linked list

I have the following struct for a linked list:

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

I want to create a sorted (eventually) linked list that keeps track of how many times each "type" appears. An example node would be:

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

My current algorithm is O(n^2), which is unreasonable because the original linked list can sometimes have over 30,000 elements. Is there a more efficient way to do this?

Note: type can be pretty much any positive integer, so I can't simply make an static array with type as the indexes.

EDIT: The frequency list does not have to be a linked list. I gave that as an example. Later on in the program, I sort the frequency list using a heap. I just need to be able to traverse the frequency list later.

Upvotes: 0

Views: 2027

Answers (4)

sahaj
sahaj

Reputation: 842

Wouldn't it be possible for you to have your original linked list in sorted order itself?

Upvotes: 0

Chris Moschini
Chris Moschini

Reputation: 37967

Is there a reason the sort structure needs to also be a linked list? I'd use a hashtable with a key of "type" and value of frequency. In O(n) time you can run down the list doing:

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

This gets you your index of frequencies. Then you just dump that into a sorted sequence - I'd use a binary tree, but you could use a linked list if you really had to end up with that.

Upvotes: 1

Drew Hall
Drew Hall

Reputation: 29055

Sounds like what you really need is a map or a basic binary search tree. The key type will be your type value, and the value type will hold your frequency.

Upvotes: 2

BeeOnRope
BeeOnRope

Reputation: 64987

Iterate over your original linked list and build up a secondary data structure which is a map from type->count, then use that secondary data structure to build your frequency linked list (if you really need it as a linked list, which seems unusual).

If you use something like a hash map for the secondary map, this should be pretty much O(n) (n the size of your original list) and you won't do better than that asymptotically (or in practice if your hash map is good).

Upvotes: 2

Related Questions