[Mono-list] Checking for identical items in an ArrayList

[Martin Baulig]

"Gaurav Vaish" <gaurav.vaish@amsoft.net> writes:

> > I'm trying to implement a few methods in the System.Data namespace but I
> > have the following question.
> >
> > When creating a DataTable and populating it, the values of each column
> > are stored in an ArrayList.
> >
> > If after populating the DataTable I try to set one of the columns to be
> > unique, the classes need to check if there is any repeated value in the
> > ArrayList.
> 
> 
>     Though not quite sure, but a binary sort followed by matching adjacent
> elements. Sorting and searching on the basis of their hashcodes.
> 
>     If someone finds better, please do let me know. I will overhaul quite a
> few of my programs. ;-)

One (very easy to implement, but very expensive) way of doing this is storing all array
elements in a hash table:

        Hashtable hash = new Hashtable ();
        foreach (Element e in list) {
                if (hash.Contains (e)) {
                        // You have a duplicate
                } else
                        hash.Add (e, some_value);
                }
        }

I think the optimal way of doing this is using a binary search like you suggested.
However, you should implement the search algorithm yourself since you may be able to avoid
the additional searching pass.  The sorting algorithm needs to compare elements anyways,
so it could easily detect duplicates.

-- 
Martin Baulig
martin@gnome.org