Faster data structure for searching a string

Question

I have this code that determines whether a word (ignoring case) is included in a wordList text file. However, the wordList text file may have 65000++ lines, and to just search a word using my implementation below takes nearly a minute. Could you think of any better implementation?

Thanks!

import java.io.*;
import java.util.*;

public class WordSearch 
{
    LinkedList<String> lxx;
    FileReader fxx;
    BufferedReader bxx;

    public WordSearch(String wordlist) 
        throws IOException
    {
        fxx = new FileReader(wordlist);
        bxx = new BufferedReader(fxx);
        lxx = new LinkedList<String>();
        String word;

        while ( (word = bxx.readLine()) != null) 
            {
            lxx.add(word);
        }

        bxx.close();
    }

    public boolean inTheList (String theWord)
    {
        for(int i =0 ; i < lxx.size(); i++)
            {
            if (theWord.compareToIgnoreCase(lxx.get(i)) == 0)
                    {
                return true;
            }
        }

        return false;
    }
}

Answer 1

Use a HashSet into which you put a lowercase version of each word. Checking if a HashSet contains a specified string is, on average, a constant-time (read: extremely fast) operation.

Answer 2

Since you're searching, you may want to consider sorting the list before searching; then you can do binary search which is much faster than linear search. That can help if you'll perform multiple searches on the same list, otherwise the penalty you pay to sort the list isn't worth it for searching only once.

Also, doing linear search on a linked list using "lxx.get(i)" is asking for trouble. LinkedList.get() is O(n). You can either use an Iterator (easy way: for (String s : lxx)) or switch to a list type that has O(1) access time, such as ArrayList.