Remove duplicates from generic list<T>

I have came with solution to remove duplicates from generic list<T> in .NET 2.0 as follows:

List<CaseStudy> caseStudies = CaseStudyDAO.FindCaseStudiesByDate(DateTime.Now.Date, DateTime.Now.Date.AddDays(1));
caseStudies.RemoveAll(
        delegate(CaseStudy c)
        {
            return caseStudies.IndexOf(c) != caseStudies.FindIndex(
                delegate(CaseStudy f) { return c.Str == f.Str; });
        });

My questions are:

Is there more efficient way to do this? Only .NET 2.0 solution

What is the complexity of the above solution?

Thanks,

jan2k10

The time complexity of RemoveAll is O(n). The time complexity of the indexing is O(n), so that's a grand total of O(n^2) time complexity. The space complexity is, I think, O(1).

Is there a more efficient way to do it? Yes. You can do it in O(n) time complexity provided you're willing to spend more space on it.

Just to expand on Eric's comment about O(n) time if you're happy to use more space, I'd do something like this:

Dictionary<string, CaseStudy> lookup = new Dictionary<string, CaseStudy>();
foreach (CaseStudy cs in caseStudies)
{
    lookup[cs.Str] = cs;
}
caseStudies = new List<CaseStudy>(lookup.Values);

A couple of notes:

• This changes the value of caseStudies to refer to a new list. If you wanted it to be within the same List<T>, you could use:

  caseStudies.Clear();
  caseStudies.AddRange(lookup.Values);
  

• This keeps the last element in the list with each distinct Str value. That was just to make it as short as possible. If you want the first element, use:

  foreach (CaseStudy cs in caseStudies)
  {
      if (!lookup.ContainsKey(cs.Str))
      {
          lookup[cs.Str] = cs;
      }
  }