0

I am making an app where I need to process lots of strings, and I really need the O(1) performance of the hashmap (I use dictionary), for instance aDictionary["aString"]. The only slight problem is that I need to keep track of the order of things.

Basicly I need the linkedList attribute go-to-next, also O(1). I could just have a list and a dictionay, the way things work, but it is more appealing to have one collection that give me both attributes in one. Do you know of any?

I hope this is an understandable description.

Thanks for any and all help :)

Automatico
  • 12,420
  • 9
  • 82
  • 110

1 Answers1

1

There is an Ordered Dictionary that does what you're describing.

However, the complexity when inserting isn't what you're asking for - but I do not think it can be improved upon (and ends up being the same as your list/dictionary implementation). See codeproject & SO.

Community
  • 1
  • 1
Jonas
  • 342
  • 2
  • 13
  • It in unfortunate that it has high insert cost. In an ideal world i want O(1): Insert, Next-element and, whats it called, "is this element in the list?"-ability. – Automatico May 12 '11 at 19:39
  • @Cort3z, yes, in ideal world, all operations are O(1). – svick May 12 '11 at 22:49