NSMutableArray or NSMutableDictionary, which one is a better choice as the model for a turn based game?

I'm making a turn base game, take Civilization as example. All units on the map are instance of Agent class. And I'm designing a AgentQueue class to control the order of units' actions in each turn.

I can come up with two options for the model base, one is NSMutableArray, another one is NSMutableDictionary.

Plan A: NSMutableArray contains the references to each Agent instance. How to get next Agent: in the order of index in this array. Insert and delete Agent: Use NSMutableArray's methods to insert or remove object at a given index. When all the indexes are called in one turn, the flag will be reset and a new turn begins from the index 0.

Plan B: NSMutableDictionary contains the references to each Agent. The keys are Agent ID, which will be generated in order or randomly when a new Agent is inserted. Each Agent instance has two references called PreviousAgent and NextAgent. How to get next Agent: use currentAgent.NextAgent Insert and delete Agent: Add/remove an Agent instance in the dictionary, and modify PreviousAgent/NextAgent of related Agents(actually only three agents will be modified: the one being added/removed, the previous one, and the next one) In the beginning pick one Agent as the last Agent. When this one is called, one turn is done and a new turn begins.

I was planning to use the plan A, however considering the whole array/dictionary will contain around 400 to 90000 agents, and there'll be lots of inserting and deleting happen, efficiency is very important. NSMutableArray will modify every following objects' indexes when you add or remove one that is not the last object. This sounds very expensive to me. Using Array is fast to find the object with a given key, however finding an object in dictionary with a given key is not slow either(I've read that dictionary is actually a hash table, which is very quick in finding). Then I came up with the Plan B, which avoid modifying other objects.

Please help me to figure out which one is better in terms of efficiency. And let me know if I'm having the right thinking during the design process. Thanks!