Which data structure is best for an auto complete drop down that learns?

Question

I made an auto complete text box for an application I'm working on. The text box basically has an associated list that it searches each time you enter something in the box.

If you enter something that is not in the box and hit 'OK', the item is added to that associated list in it's sorted position using a binary insert (basically binary search for the correct position).

Right now I'm using an ArrayList to store the data and a binary search to search. My question is this: in terms of time complexity, is ArrayList the best option for for this situation? Or am I better off using some kind of binary search tree?

Answer 1

What you are looking for is a variant of the Radix Tree, more precisely you want a Prefix Tree.

This is a hierarchical data structure, sorted by "prefixes" of the words (hence the name). The valid words are the leaves.

Search time would still match the complexity of the binary search (O(log n)), but insertion and deletion time would also better (O(log n)) compared with the ArrayList (amortized O(n)) because, the ArrayList need to move items around in the underlaying array (or allocate a new one on growth).

Insertion and deletion time might or might not be a concern, depending on how often those operation happen.

---

As far as I know there is no standard Prefix Tree in Java. Yet the interface NavigableMap seem to be a good alternative since you can query for the closest item (using the ceiling and floor methods), and TreeMap would have similar complexities being also a tree.

You can use a TreeMap<String, Boolean> and just put true and work on the set of keys.

Answer 2

Consider TreeSet.

From javatpoint.com : treeset

import java.util.*;  

class TestCollection11{  

     public static void main(String args[]) {  

          //Creating and adding elements  
          TreeSet<String> al = new TreeSet<String>();  
          al.add("Ravi");  
          al.add("Vijay");  
          al.add("Ravi");  
          al.add("Ajay");  

          //Traversing elements  
          Iterator<String> itr = al.iterator();  
          while( itr.hasNext() ) {  
               System.out.println(itr.next());  
          }  
     }  
}  

outputs

Ajay
Ravi
Vijay

Indeed, choosing the best data structure makes life easier.

Answer 3

In general, it's a good idea to choose the best data structure for the job.

That said, as long as you're dealing with data that are intended to be used for manual selection by humans and that originate from manual entry, the amount of data is almost certainly so small (for a computer) that it doesn't matter which type of container you're using. On present-day machines, any old data structure can deal with a couple of thousand items and you'll never notice the speed difference. It's almost certainly not worth spending time on doing anything non-obvious here.