Get word frequency of a txt file and save it to linked list

Question

I'm a novice in C++. I want to do three things:

1. Get the number of lines in the file
2. Get the number of total words in the file
3. Get each frequency of each "unique word".

Here, "unique word" is simply the same set of characters delimited by whitespace; different punctuation and casing are considered different.

I am using a linked list to achieve this.

I want to ask improvements on a number of things:

1. If there's a better way to get whitespace delimitation than using getline and converting the results to a stringstream

2. If there's a better way to automatically add nodes to the the linked list if I haven't found a node with the matching word.

3. I have to initialize the linked list with a null head, and therefore have to remove it when I'm printing results. Surely there must be a better way of initialization

I realize repeated searches through the linked list is not efficient, but that is not the concern currently, I am just trying to get used to using things in C++.

Code:

# include <iostream>
# include <fstream>
# include <sstream>
# include <string>
# include <algorithm>
using namespace std;

// Node
struct Node {
    string word;
    int count = 1;
    Node * next;
};

// Checks if string is whitespace
bool whiteSpace(const string& str){
    return (str == "\r" || str=="\n" || str ==" " || str == "" || str == "\t");
}

// Prints contents of linked list
void printList(Node* head){
    Node * search = head;
    while(search->next != nullptr){
        cout << search->word << " : " << search->count << endl;
        search = search->next;
    }
}

int main(int argc, char* argv[]){

    // Initiliazation of file I/O
    ifstream inFile;
    string fileName;
    cout << "Enter file name: ";
    getline(cin, fileName);
    inFile.open(fileName.c_str());
    string str;
    int lineNum = 0;
    int wordCount = 0;

    // Initialization of linked list
    Node * head = new Node();
    head-> next = nullptr;

    // For each line
    while(getline(inFile, str)){
        /*
        ###############CODE REVIEW:#################
        THIS PART SEEMS OVERLY REDUNDANT AND INEFFICIENT!! 
        Going from a fstream to read each line, and then to convert each string into a 
        stringstream. Better options?
        */
        stringstream ss;
        ss << str;

        // For each word in the line
        while(ss){
            string s;
            ss >> s;

            // Ignore whitespace as words
            if (!whiteSpace(s)){
                wordCount ++;

                Node * search = head;
                /*
                ###############CODE REVIEW:#################
                This FOUND boolean seems inefficient! 
                Refer to below. 
                */
                bool found = false;

                // Search the entire linked list 
                while(search->next != nullptr){
                    // If we've found the word in the linked list, update its count
                    if(search->word == s){
                       search->count ++;
                       found = true;
                       break;
                    }
                    search = search->next;
                }
                 /*
                ###############CODE REVIEW:#################
                This FOUND boolean seems inefficient! 
                For each word, I need to check if it's found or not -- even if it's found!
                There must be a better way to increase the length of the linked list if we haven't
                found a node with the appropriate data. 
                */
                if(!found){
                    Node * newNode = new Node();
                    search->next = newNode;
                    newNode->word = s;
                }
            }
        }
        // Update line number for each getline
        lineNum ++;
    }
    cout << "Number of lines: " << lineNum << endl;
    cout << "Number of words: " << wordCount << endl;
    /*
    ###############CODE REVIEW:#################
    Because I initialized with a null head, I have to start at the 2nd node instead of the first one.
    */
    head = head->next;
    printList(head);
    inFile.close();
    return 0;
}

Answer 1

String parsing

You are right that C++ slightly lacks some convenient features for string parsing. If you were not trying to count lines as well as find words, then a single while loop with:

  inFile >> s;

would have sufficed, because streaming will terminate on whitespace by default. But because you want to count lines, you need the 2 loops and therefore you need to the stream => str => stringstream => s logic. You can gain some syntactic effeciencies, see code below.

However you do not need (most of) the "whitespace" logic, because, as mentioned, stream >> s will be delimited by (and will eliminate) whitespace.

I ended up with just a if (!s.empty) as the only check.

Style

• Try to get into the habit of not using namespace std;. This is considered bad practice. Getting into this habit now will help you as you progress.
• Don't use std::endl; unless you explicitly want to flush the output buffer.
• If you are not using argv and argc you can omit them from main()'s signature. This is cleaner and prevents "unused variable warnings in some IDE's and compiler (And you should have these warnings turned on with -Wall -Wextra).
• Increment operator ++ should be used as pre-increment rather than post most of the time. get in the habit of doing that, it can be faster in some situations. Almost always ++i not i++.

Linked list - memory

You are using a self implemented linked list to store the unique words. More on that below. Here I would like to comment on how you implemented that list.

There are a few issues, but the biggest issue I can see, is that you are allocating Nodes on the heap with new but you are never deleteing them. That means your application leaks memory. You can confirm this with a tool like valgrind.

The guidelines are:

1. Never write new without writing delete
2. Never write new or delete => instead use smart_pointers like std::unique_ptr
3. Don't implement you own containers, use the ones from the standard library

Choosing a container

Firstly, as mentioned above, don't implement your own containers, let alone write new and delete yourself. Use the ones from the standard library.

1. There is a rich choice. You could just use std::list or std::forward_list, which behave similarly to what you use here. More speficically it would be a std::list<std::pair<std::string, int>>.
2. You are doing a linear search for each word. Linked lists are slow at linear search because they have to "pointer-hop" through random parts of memory. For a linear search (and probably most of the time) you should be using a std::vector<std::pair<std::string, int>>
3. Any linear search is the wrong solution for this problem because you are making the algorithm O(n^2), ie for each word found, you are walking through all the words found already. Use an "associative container" which optimises this process by using a hash_map under the hood. std::unordered_map<std::string, int> would be good and that's what I have used.

Using std::unordered_map massively reduces your code both in lines of code, and also runtime. It makes it easier to understand and more robust and more maintainable.

RAII

Resource Acquisition is initialisation in an important concept in C++. Read up about it. In your code specifically, you don't need: inFile.close();

Bonus#1

If you did want to "lowercase" and remove "non-alpha" characters, I have included that code, because it is non-obvious if you're new to C++ string fiddling.

Bonus#2

If you wanted to find out the "10 most common words", I have shown how you can easily achieve that by using std::partial_sort_copy to copy the top10 into a std::vector.

Hope that helps. Come back in the comments if I have misunderstood something, or you have questions.

Here is the refactored code:

#include <algorithm>
#include <fstream>
#include <iostream>
#include <sstream>
#include <string>
#include <unordered_map>

int main() {
  std::string fileName;
  std::cout << "Enter file name: ";
  getline(std::cin, fileName);
  std::ifstream inFile(fileName);

  int wordCount = 0;
  int lineNum   = 0;

  std::unordered_map<std::string, int> words;

  std::string str;
  while (getline(inFile, str)) {
    std::stringstream ss(str);
    while (ss) {
      std::string s;
      ss >> s;
      // bonus#1: lowercase and remove/erase non-alpha
      std::transform(s.begin(), s.end(), s.begin(),
                     [](unsigned char c) { return std::tolower(c); });
      s.erase(
          std::remove_if(s.begin(), s.end(),
                         [](unsigned char c) { return std::isalpha(c) == 0; }),
          s.end());
      if (!s.empty()) {
        ++wordCount;
        ++words[s];
      }
    }
    ++lineNum;
  }
  std::cout << "Number of lines: " << lineNum << '\n';
  std::cout << "Number of words: " << wordCount << '\n';

  std::cout << "Word list\n";
  for (auto& pair: words)
    std::cout << pair.first << " : " << pair.second << "\n";

  // bonus#2: top10 words
  std::vector<std::pair<std::string, int>> top10(10, {"", 0});
  std::partial_sort_copy(words.begin(), words.end(), top10.begin(), top10.end(),
                         [](auto& a, auto& b) { return a.second > b.second; });
  std::cout << "\nTop 10 words\n";
  for (auto& pair: top10)
    std::cout << pair.first << " : " << pair.second << "\n";
}