ListNode vs Array Efficency
I'm not really having a problem, just a question....
I'm reading in a large text file (AKA Hamlet or some other work of literature) and puting them into an array or ListNode Alphebetiaclly. Now shouldn't theoretically the ListNode system run faster than the array system because the ListNode does not require shifting values.
Could someone explain to me why the array is consistently beating the ListNode approach?
Here are my insert methods if it will help:
publicint insertWord(String word){
return ll ? insertWordLL(word) : insertWordAL(word);
}
privateint insertWordLL(String word){
numWords++;
if (head==null){ head =new WordListNode(word,null);return 1;}
WordListNode pos = head;
while (pos.getNext()!=null && pos.getNextNode().getStringValue().compareToIgnoreCase(word)<0)
pos = pos.getNextNode();
if (pos.getNext()!=null&&pos.getNextNode().getStringValue().compareToIgnoreCase(word)==0){
pos.getNextNode().increment();
return pos.getNextNode().getOccurances();
}elseif (pos.getStringValue().compareToIgnoreCase(word)==0){
pos.increment();
return pos.getOccurances();
}else{
pos.setNext(new WordListNode(word,pos.getNextNode()));
return 1;
}
}
privateint insertWordA(String word){
numWords++;
if (array==null){ array=new Word[1]; array[0]=new Word(word);return 1;}
int pos = -1;
Word w2=null;
do{
pos++;
if (!(pos<array.length))break;
w2 = array[pos];
}while (word.compareToIgnoreCase(w2.getWord())><0);
if (pos>=array.length){
Word[] a2 =new Word[array.length+1];
System.arraycopy(array,0,a2,0,array.length);
a2[a2.length-1]=new Word(word);
array = a2;
System.out.println();
return 1;
}elseif (w2!=null&&word.compareToIgnoreCase(w2.getWord())==0){
w2.inc();
return w2.occurences();
}
else{
Word[] a2 =new Word[array.length+1];
if (pos!=0) System.arraycopy(array,0,a2,0,pos);
a2[pos] =new Word(word);
System.arraycopy(array,pos,a2,pos+1,array.length-pos);
array=a2;
return 1;
}
}
Thank you!
