Simplest way to find most frequently occurring element in linked list of int

user_18749257 0
Viewed 76

I have a linked list of integers in C, and I am trying to find an efficient way to find the most common element in the list.

So far I have thought of creating a new node structure that stores a counter, but I would like to avoid this if there is a simpler way to go about it.

Is there a more straightforward way to do this?

linked-list c algorithm
1 Answers

Here are four solutions:

  1. If you have a good hash table implementation, you can achieve linear time by storing the count with each value in the hash table, incrementing the count if the value is already in the table. One final scan of the hash table will find the element(s) with the largest count. This has linear time and space complexity. This solution would be used in languages with built-in hashmaps, but C does not provide any in the Standard library so you must implement it and it is a non trivial task.

  2. You can sort a copy of the list:

  • If you cannot modify the list, make a copy of the list (linear time and space complexity).
  • Sort the list using mergesort for linked lists (time complexity O(n.log(n))).
  • Scan the list, counting the number of occurrences of the current element, keep track of the value and count for the largest count (linear time).
  • free the copy (linear time).
  • Done.
  1. Even simpler but with quadratic time and no space overhead: as you iterate in the list, count the number of occurrences of the value in the current node in the rest of the list, keep track of the value and count for the largest count:
int most_common_value(const node *p) {
    int best_count = 0, best_value = 0;
    for (; p; p = p->next) {
        int count = 1;
        for (const node *q = p->next; q; q = q->next) {
            count += (q->value == p->value);
        }
        if (best_count < count) {
            best_count = count;
            best_value = value;
        }
    }
    return best_value;
}
  1. If the data is an integer with a relatively small range of values, you can use an array of counts and achieve linear time and space:
int most_common_value(const node *p) {
    if (!p)
        return 0;

    int best_count = 0, best_value = 0;
    int min = p->value, max = p->value, length = 1;

    for (const node *q = p->next; q; q = q->next) {
        if (min > q->value)
            min = q->value;
        if (max < q->value)
            max = q->value;
        length++;
    }
    int range = max / 2 - min / 2;
    if (range <= 1000 && range / length > length) {
        int count[max - min + 1];
        for (int i = 0; i <= max - min; i++) {
            count[i] = 0;
        }
        for (const node *q = p; q; q = q->next) {
            count[q->value - min]++;
        }
        for (int i = 0; i <= max - min; i++) {
            if (best_count < count[i]) {
                best_count = count[i];
                best_value = min + i;
            }
        }
    } else {
        /* use some other method */
        for (; p; p = p->next) {
            int count = 1;
            for (const node *q = p->next; q; q = q->next) {
                count += (q->value == p->value);
            }
            if (best_count < count) {
                best_count = count;
                best_value = value;
            }
        }
    }
    return best_value;
}
user_45932670
Related