Return to Revisions

Data Structure

I think what you're looking for is simply just a List. Looking up the time complexities for List, we can see here:

• Add O(1) [note: amortized, the O(n) on 'beyond capacity' is negligible]
• Remove/RemoveAt O(n)
• Item[i]/Find(i) O(1)

Just a note: you can verify these complexities in the MSDN(for example, going to List<T>.Add, one of the remarks will tell you the complexities), but I found the above table to be a nice and succinct way of showing multiple collections.

Not to attack Heslacher's implementation, but I found IndexOf to be O(n). I'm always dubious of roll-your-own array implementations.

Based on your problem description, though, the two main things you're going to be using are Add and Item[], and since those are O(1) I think List is an easy and efficient candidate.

Alternative - Unique Elements

If you want to guarantee uniqueness(no duplicates), then there's HashSet<T>. Here's an SO question on it. The time complexities are essentially the same. The catch is that if T hashes poorly and there's a lot of collision, the lookup is up to O(n)(this would mean all objects in the collection have the same hash and you essentially have an array). Strings typically hash well, so this shouldn't be a problem.

Code Review

I hate to say it but I just don't have anything to review. To be honest this question would do just as well or better on the Programmers SE. You covered the coding style with Heslacher, so other than that your code is well-formed, easily understood and there's not a whole lot of it. I could nitpick that Pool seems to be an Add and a Get, but the way you use it makes sense, and separating them would probably make the code more complex and ugly. At this point I'm just rambling because this is the code review SE...but I got nothing.

I focused a bit on complexities because your original problem included space complexity(double the strings, double the memory), and time complexities may not actually make a huge difference at run-time for you. So what you choose - array, list, hashset, etc - is really up to you and your environment.