How to find the most common element in a custom linked list implementation?

Question

I'm trying to make my own non-STL linked list implementation.

I tried to write a function to find the most common element and print which one it is and how many times we encounter it in the list. I've already added two other functions so that I can add elements in the list and also check if the list works correctly.

For the search function I've thought to search how many times we encounter each of the elements and have a variable that would increase by 1 every time I encounter the the element I'm currently checking. I've managed so far to only have a function that searches for only one element that I have chosen. Not sure how to proceed.

I wanted to be able to modify the function to search for the most common element. Do you have any idea how to achieve what I'm trying to do?

#include <iostream>
using namespace std;

void add_е(int n);
void list();
int search_elem(int n);

 struct elem 
 {
    int key; 

    elem *next; 
 } *start=NULL; 


int main()
    {  
        int ch, num, amount, i, element;
    do
    {   cout<<"\n\t Menu";
        cout<<"\n 1.Add elements";
        cout<<"\n 2.Find the most common element";
        cout<<"\n 3.Print the stack";
        cout<<"\n 4.Exit";
    do
    {   cout<<"\n Your choice is:";
        cin>>ch;
    }
    while (ch<1||ch>4);
    switch(ch)
{

    case 1: 
        cout<<"\n How many elements do you want to add?";
        cin>>amount;
        for(i=0; i<amount; i++)
        {
            cout<<"Input stack elements:\n";
            cin>>num;
            add_е(num);
        }
    break;


    case 2:
        cout<<"\n Which element do you want to find? \n ";
        cin>>element;
        search_elem(element);   
        break;


    case 3: list();
    break;
}

}while(ch!=4); 
}

void add_е(int n) {  elem *p=start, *q=p;
    q=new elem;      
    q->key=n;    
    q->next=NULL;   
if (start)      
    {  
        while (p->next)
        p=p->next;  
        p->next=q;  
    }   
else    
    start=q;    
}       



void list()  
{   
    if (start) 
    { 
        elem *p=start;
        cout<<"\n List is: \n";
        while (p) 

        { 
            cout<<p->key<<"\n"; 
            p=p->next;   
        }   
    }  
    else 
        cout<<"\n Empty list";
} 


int search_elem(int n)   // here's what confuses me
{  
    elem *p=start; 
    if (start) 
    {
        while ((p->key!=n)&&(p->next))   
            p=p->next;  

        if (p->key==n)
    {
        cout<<"p->key"<<"\n";
        return 1; 
    }
    else 
        cout<<"No element found";
        return 0; 
    } 
    return 0; 
}

For starters rewrite your list such a way that the function definitions would not depend on the global variable start. — Vlad from Moscow, Apr 13 '20 at 16:19
You could use an `unordered_map` for counting. If you're not allowed to use that, you could write a map-like container too. — Ted Lyngmo, Apr 13 '20 at 16:24
Does this answer your question? [Error C3861: identifier not found; What to do?](https://stackoverflow.com/questions/61173462/error-c3861-identifier-not-found-what-to-do) — marc_s, Apr 29 '20 at 17:56

Vlad from Moscow · Answer 1 · 2020-04-13T16:57:48.447

For starters it is a bad approach when functions depend on a global variable. In case of your application you can not for example declare two lists in a program.

Without using additional standard containers the function can be defined the following way.

#include <utility>

struct elem 
{
    int key; 
    elem *next; 
} *start=NULL; 

std::pair<int, size_t> most_frequent( const elem *head )
{
    std::pair<int, size_t> max( 0, 0 );

    for ( ; head != nullptr; head = head->next )
    {
        if ( max.second == 0 || max.first != head->key )
        {
            size_t n = 1;

            for ( const elem *current = head->next; current != nullptr; current = current->next )
            {
                if ( current->key == head->key ) ++n;
            }

            if ( max.second < n )
            {
                max = { head->key, n };
            }
        }           
    }

    return max;
}

It does not rely on a global variable and can be called like

auto max = most_frequent( start );

Here is a demonstrative program

#include <iostream>
#include <utility>

struct elem 
{
    int key; 
    elem *next; 
} *start=NULL; 

std::pair<int, size_t> most_frequent( const elem *head )
{
    std::pair<int, size_t> max( 0, 0 );

    for ( ; head != nullptr; head = head->next )
    {
        if ( max.second == 0 || max.first != head->key )
        {
            size_t n = 1;

            for ( const elem *current = head->next; current != nullptr; current = current->next )
            {
                if ( current->key == head->key ) ++n;
            }

            if ( max.second < n )
            {
                max = { head->key, n };
            }
        }           
    }

    return max;
}

int main() 
{
    auto max = most_frequent( start );

    std::cout << "the key " << max.first 
              << " is encountered most frequently "
              << max.second << " times\n";

    return 0;
}

The program output is

the key 0 is encountered most frequently 0 times

Unfortunately my list was empty.:)

How to find the most common element in a custom linked list implementation?

1 Answers1