CODEWITHSUNDEEP
c#
Ajay Kelkar
Ajay Kelkar

Reputation: 4621

which is collection or list is fastest for too many additions & deletions?

I have a list in which large number of elements are added & deleted every second
also i need to find elements in the list at the same time .

Also i need key/value pair comparison for searching.

Additions rate is higher than deletion .

Thanks In Advance.

Upvotes: 0

Views: 176

Answers (2)

Jon Skeet
Jon Skeet

Reputation: 1500795

Dictionary<TKey, TValue> is generally very quick - amortized O(1) insert and delete. Basically it's O(1) unless it needs to restructure itself, at which point it's O(n).

What counts as a "large" number of elements being inserted and deleted?

Given that Dictionary<TKey, TValue> is in some ways the standard "I need a key/value mapping" data structure in .NET, I'd at least benchmark it to see whether it performs well enough for your needs before looking at anything more esoteric.

However, the "list" reference from your questions suggests you might require ordering as well - is that actually the case or not? i.e. do you need to be able to iterate over entries in the order they were added? If so, you'll probably need to create your own (Linked)List<T>/Dictionary<TKey, TValue> composition (with appropriate care).

While SortedList<TKey, TValue> and SortedDictionary<TKey, TValue> do provide a guaranteed ordering, it's not insertion ordering - it's key ordering. In other words, if you write:

sortedDictionary["c"] = ...;
sortedDictionary["a"] = ...;
sortedDictionary["b"] = ...;

and then iterate over it, you'll get the entries in order "a", "b", "c".

Contrary to what you might think from their names, both of these types are dictionaries really (in that they're key/value mappings) - they're just implemented differently which gives different performance characteristics. See the MSDN documentation for details.

Upvotes: 2

Thomas
Thomas

Reputation: 181785

Try Dictionary.

Additions, deletions and lookups are pretty much O(1). I'm not sure what you mean by "key/value comparison for searching", but a Dictionary maps keys to values and has fast searching.

If you do really need a list (that is, an ordering on the elements), then a SortedDictionary will serve you better.

Upvotes: 2

Related Questions