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.