If I'm adding items to a list, can I check in O(1) time if an element already exists using a dictionary?

[curiousaboutcsharp]

I have a list L
I am adding a bunch of integers to L
The integers can come in any sequence, but I can't add a duplicate

I know for each integer coming into L, I can run a O(m) loop over L to check if the integer already exists. m = number of integers in sequence

But if I keep a dictionary that maps an integer to a true boolean, can I refer to this dictionary and avoid having to loop over the entire list L?

Basically for each integer that wants to enter L, I check if the integer already exists in the dictionary. If it doesn't exist, then add the integer to both the list L and the dictionary. If the integer does exist in the dictionary, then do not put it in the list L

I think this reduces the time complexity to O(m) m = number of integers, rather than O(m * k) k = number of integers in L so far; k < m

Thank you!

 

[jmcilhinney]

You should use a Hashset<T> rather than a List<T>. It operates in basically the same way as the keys of a dictionary.

 

[jmcilhinney]

Note that Hashset<T> only implements ICollection<T>. If you need IList<T> functionality then you'd need to call ToList when the hashset is full.

 

[cjard]

Agree that hashset seems the most appropriate collection here, but did want to point out that sets are unordered by default; if you enumerate the hashset you should not expect the numbers to come out in any particular order. In contrast a list would emit them in the order they were added when enumerated forwards

 

[Skydiver]

If you are willing to use undocumented behavior that can potentially change at any time in the future, I believe that the current version of the .NET Dictionary<TKey, TValue> will retain the order of the keys as they are inserted into the dictionary as long as you don't remove any items in the dictionary. E.g. You can enumerate Keys collection and it'll give you back the keys in the order that you inserted them.

using System;
using System.Collections.Generic;
using System.Linq;
                   
public class Program
{
    static Random _random = new Random();

    static void Shuffle<T>(IList<T> list)
    {
        for(int i = list.Count - 1; i > 0; i--)
        {
            var j = _random.Next(i + 1);
            T temp = list[i];
            list[i] = list[j];
            list[j] = temp;
        }
    }
   
    public static void Main()
    {
        const int MaxItems = 65536;
        var list = Enumerable.Range(0, MaxItems).ToList();

        Shuffle(list);

        Dictionary<int, int> dict = new();
        for(int i = 0; i < list.Count; i++)
            dict[list[i]] = i;

        Console.WriteLine(list.SequenceEqual(dict.Keys));
        Console.WriteLine(dict.Keys
                              .Select(k => dict[k])
                              .SequenceEqual(Enumerable.Range(0, MaxItems)));
    }
}