Doing a binary search with Linked Lists?

[lamentofking]

I'm doing a word sensor program with linked lists. I have message and dictionary .cpp/.h pairs linked together but I can only modify dictionary.cpp by adding/deleting code in the function bodies:

dictionary.h

#ifndef DICTIONARY_H
#define DICTIONARY_H

#include <string>
#include <vector>

/**
 * A Dictionary is a collection of words. The primary operations
 * are adding new words to the dictionary and checking to see if some
 * word is already in there.
 */


class Dictionary {

public:

  Dictionary();
  

  /*
   *  Add a word to the dictionary
   */
  void add (std::string word);


  /*
   *  Check to see if a word is in the dictionary
   */
  bool contains (std::string word) const;



private:

  struct LinkedListNode {
    std::string data;
    LinkedListNode* next;
  };

  
  LinkedListNode* first;


};


#endif 

dictionary.cpp

#include "dictionary.h"
#include "vectorUtils.h"

using namespace std;


string toLowerCase (string word)
{
  string result = word;
  for (int i = 0; i < word.length(); ++i)
    if (word[i] >= 'A' && word[i] <= 'Z')
      result[i] = result[i] + 'a' - 'A';
  return result;
}

/*
 *  Add a word to the dictionary
 */
void Dictionary::add (std::string word)
{
  if (first == NULL)
    {
        first = new LinkedListNode;
        first->data = word;
        first->next = NULL;
    }
    else
    {
        LinkedListNode * temp = first; 
        first = new LinkedListNode;   
        first->data = word;            
        first->next = temp;
    }
}


/*
 *  Check to see if a word is in the dictionary
 */
bool Dictionary::contains (std::string word) const
{
  int k = binarySearch (words, toLowerCase(word));
  return k >= 0; // binarySearch returns -1 if not found
}

I was able to modify void Dictionary::add (std::string word) correctly to work with linked lists . Having trouble modifying the bool Dictionary::contains (std::string word) const . Not sure exactly how to modify it. Can someone help please?

[h9uest]

I don't think it's the right way to implement the contains() method using binarySearch():
1, binary search needs your list to be sorted and I don't see any code you listed did sorting.
2, you try to apply binary search algorithm on a linked list, which sounds to me like eating rice with chopsticks - no offence to smart Asian guys! As a hint, I would imagine using b-search on an array, for example. (Question: why? I hope you can think for yourself.)
3, in terms of algorithm time complexity, binary search is O(logN), which is worse than the performance of, say, a hash table. In C++, you could use unordered map. However, I've heard that some (bad) implementation of unordered map actually gives you O(logN).

Last but not least, if you're somehow required to implement your dictionary using linkedlist(suggesting your tutor/boss is an idiot or he just wants you to look like an idiot), then you probably don't need to worry about time complexity at all. In that case, why not giving him/her the simplest implementation?(iterate through the list and check using a loop)

[lamentofking]

Well I was thinking something like this then for searching an unordered list (does it matter if the list is ordered or unordered for this type of program?)

bool Dictionary::contains (std::string word) const
{
LinkedListNode * current = first;
  while (current != NULL)
    current = current->next;
  return current;
}

Compiles successfully. But doesn't censor any keywords (the program is supposed to censor all sentences that contain certain keywords).

[lamentofking]

I can't seem to figure this one out and am stuck. Can anyone steer me in the right direction?