Ordered Lists

Dictionary:

        
	        ______        
	       |      |
 numberOfWords |      |    MAX_SIZE  ________
               |______|
 _______________________
|                       |
|      DICTIONARY       |
|                       |
|_______________________|
|                       |                
|_______________________|
|                       |
|_______________________|
|                       |                
|_______________________|
|                       |
|_______________________|
|                       |                
|_______________________|
|                       |
|_______________________|
|                       |                
|_______________________|








Dictionary Class


 public class Dictionary {
 
   final int MAX_SIZE = 7;  //Small for testing
   
   String[] words;
   
   int numberOfWords;
   
   public Dictionary() {
   
     numberOfWords = 0;
     
     words = new String[MAX_SIZE];
     
   }
   
   public void addWord(String word) {
     
     //Check if there's room in the array
     if (numberOfWords < words.length) {
     
       //Find the spot to put the word
       for (int i = 0; i < numberOfWords; i++) {
       
         if (word.compareTo(words[i]) < 0) {
	 
	   //Shift the words right
	   for (int j = numberOfWords; j > i; j--)
	   
	     words[j] = words[j-1];
	     
	   //Insert the word
	   words[i] = word;
	   
	   //Increment the number of words
	   numberOfWords++;
	   
	   //We're done!!!
	   return;
	 }
       }
       
       //Never found a spot - add the word to the end
       words[numberOfWords++] = word;
       
       return;
     }
   }

   //QUESTION: How could this method be 
               made more efficient?
   public void removeWord(String word) {
   
     //Look for the word
     for (int i = 0; i < numberOfWords; i++) {
     
       //Found the word
       if (word.equals(words[i])) {
       
         //Shift the words left
	 for ( ; i < numberOfWords - 1; i++)
	 
	   words[i] = words[i+1];
	   
	 //Decrement the number of words
	 numberOfWords--;
	 
	 //We're done!!!
	 return;
       }
     }
   }
   
      
   public void efficientRemoveWord(String word) {
   
     //Look for the word
     for (int i = 0; i < numberOfWords && 
                     
		     word.compareTo(words[i]) >= 0; i++) {
     
       //Found the word
       if (word.equals(words[i])) {
       
         //Shift the words left
	 for ( ; i < numberOfWords - 1; i++)
	 
	   words[i] = words[i+1];
	   
	 //Decrement the number of words
	 numberOfWords--;
	 
	 //We're done!!!
	 return;
       }
     }
   }
   
   public String toString() {
   
     String s = "";
     
     for (int i = 0; i < numberOfWords; i++)
     
       s += words[i] + "\n";
     
     return s;
   }
   
   public static void main(String[] args) {
   
     Dictionary dictionary = new Dictionary();
     
     dictionary.addWord("dog");
     dictionary.addWord("fish");
     dictionary.addWord("apple");
     dictionary.addWord("ball");  
     dictionary.addWord("elephant");
     dictionary.addWord("jelly");
     dictionary.addWord("zebra");
     dictionary.addWord("treasure");
     
     System.out.println("\n" + dictionary); 
     
     dictionary.removeWord("elephant");
     dictionary.removeWord("apple");
     dictionary.removeWord("zebra");
     dictionary.removeWord("goat");
     
     System.out.println("\n" + dictionary);
   }
 }
     
/* PROGRAM OUTPUT:

eos% java Dictionary

apple
ball
dog
elephant
fish
jelly
zebra


ball
dog
fish
jelly

*/