I had to implement some data structures for my computational geometry class. Deciding whether to implement the data structures myself or using the build-in classes turned out to be a hard decision, as the runtime complexity information is located at the method itself, if present at all. So I went ahead to consolidate all the information in one table, then looked at the source code in Reflector and verified them. Below is my result.

Note:

Update 25 April 2010: Added SortedSet

Internal Implement- ation | Add/insert | Add beyond capacity | Queue/Push | Dequeue/ Pop/Peek | Remove/ RemoveAt | Item[index]/ElementAt(index) | GetEnumerator | Contains(value)/IndexOf/ContainsValue/Find | |

List | Array | O(1) to add, O(n) to insert | O(n) | - | - | O(n) | O(1) | O(1) | O(n) |

LinkedList | Doubly linked list | O(1), before/after given node | O(1) | O(1) | O(1) | O(1), before/after given node | O(n) | O(1) | O(n) |

Stack | Array | O(1) | O(n) | O(1) | O(1) | - | - | O(1) | O(n) |

Queue | Array | O(1) | O(n) | O(1) | O(1) | - | - | O(1) | O(n) |

Dictionary | Hashtable with links to another array index for collision | O(1), O(n) if collision | O(n) | - | - | O(1), O(n) if collision | O(1), O(n) if collision | O(1) | O(n) |

HashSet | Hashtable with links to another array index for collision | O(1), O(n) if collision | O(n) | - | - | O(1), O(n) if collision | O(1), O(n) if collision | O(1) | - |

SortedDictionary | Red-black tree | O(log n) | O(log n) | - | - | O(log n) | O(log n) | O(log n) | O(n) |

SortedList | Array | O(n), O(log n) if added to end of list | O(n) | - | - | O(n) | O(log n) | O(1) | O(n) |

SortedSet | Red-black tree | O(log n) | O(log n) | - | - | O(log n) | O(log n) | O(log n) | - |

Dictionary | Add, remove and item[i] has expected O(1) running time |

HashSet | Add, remove and item[i] has expected O(1) running time |

## 13 comments:

Nice work, very useful.

MSDN should display these information for every data structures they provide.

Thanks! MSDN did for some of the structures, but I did find that the SortedDictionary complexity that they stated is wrong... I guess wrong documentation is worse than no documentation, that is why MSDN didn't want to document it.

Big THANK YOU, for this table!

I think you have two mistakes:

1. LinkedList haven't Item[i], it has Find(T) = O(n)

2. SortedList Item[i] = O(log n)

Thanks Shuisky. Added Find(i) to the heading.

Why do you say SortedList Item[i] = O(log n)? Internally it's an Array, so shouldn't access be instantaneous?

Yes, the array. But when trying to get the Item, is a binary search inside

TValue this[TKey key] {get}=O(log n)You don't know index of item in SortedList, so you take Item by Key. If you want take Item by Index, you need

1) int IndexOfKey(TKey key);

2) TValue GetByIndex(int index);

And it's same O(log n) in sum :)

Would be worth add the .NET4 Concurrent Collections to this table!

Still super useful, 5 years later.

A million dollar worth entry!.

MSDN about List says: "This method performs a linear search; therefore, this method is an O(n) operation, where n is Count."

In your table is O(1).

Did I misunderstood?

@Roberto: MSDN stated that the IndexOf and Contains operations to be O(n). I'm missing those methods in my table...

Let me add them

Sorry: I forgot to say which method! I was speaking about List.Find

https://msdn.microsoft.com/en-us/library/x0b5b5bc.aspx

@Roberto: turns out it's so hard to name the heading. The Find only applies to LinkedList, but turns out that I shouldn't put that in the same column as Item[i]. I've changed the last column MoveNext to finding a value, which would require you to enumerate through the entire collection in the general case

Post a Comment