4
\$\begingroup\$

I have been making 2d shooter similar to galaga using xna in C#, where the enemies (2 types) are all in rows above the player's ships, and are supposed to randomly launch attacks. I had previously implemented part of this game using an array to generate the rows of enemies and testing to make sure the other game mechanics worked before implementing the enemy movement system and ai. I was told later that I should use a list instead of an array to generate the rows of enemies. What advantage is there to using a list over using an array?

\$\endgroup\$
  • 1
    \$\begingroup\$ Check out Arrays Considered Somewhat Harmful by Eric Lippert: blogs.msdn.com/b/ericlippert/archive/2008/09/22/… \$\endgroup\$ – Pieter Geerkens Oct 12 '14 at 3:19
  • 1
    \$\begingroup\$ Frankly, in C#, it makes no difference, every object is allocated independently anyway, and the lists/arrays contains just pointers. So if you ask about performance... well just don't ask, it does not make much sense. Or use C++ if you like this levels of considerations. \$\endgroup\$ – v.oddou Oct 15 '14 at 5:14
5
\$\begingroup\$

First of all please read Array versus List: When to use which? for coverage of this issue from a general perspective.

Now to focus on your case, I would recommend a list if:

  1. You don't know how many enemies you will have in advance (and don't want to worry about handling resizing)
  2. You would like to remove enemies from the middle (and don't want to worry about handling fragmentation)

In practice I find that List<T> provides an powerful and efficient implementation that takes care of house keeping and edge cases while allowing a developer to focus on game logic.


There are a differences in usage, mostly changes I consider improvements as they enable a more powerful API.

Here are some usage samples:

using System.Collections.Generic;

Item item = new Item();
int index = 0;

//initialise new list
List<Item> list = new List<Item>();

//add item to last position
list.Add(item);

//retrieve item from indexed postion
item = list[index];

//replace item at indexed postion
list[index] = item;

//remove first occurance of item 
list.Remove(item);

//remove item from indexed position
list.RemoveAt(index);

//remove all occurenece of item
list.RemoveAll(o => o.Equals(item));

//get count of items in list
int count = list.Count;

//iterate through list
foreach (Item item in list) {
    // do work on item
}
| improve this answer | |
\$\endgroup\$
  • \$\begingroup\$ just to clarify, is there any particular difference in how a list is implemented verses an array (is the code mostly the same, just with list used instead of "arrayname"[])? \$\endgroup\$ – cluemein Oct 15 '14 at 1:32
  • \$\begingroup\$ @cluemein No, there isn't. The .NET List is internally handled as an array. The interface pretends to be able to resize dynamically, but the implementation just does an expensive reallocation when the capacity is exceeded. Use LinkedList when you want cheap resizing and don't need index access. My answer explains this in greater detail. \$\endgroup\$ – Philipp Oct 15 '14 at 11:21
1
\$\begingroup\$

The problem with arrays is that they can not resize dynamically. When you exceed the initial capacity, you need to allocate a new array and copy the whole array over. When you want to remove an entry in the middle, you need to move all entries after it down by one. These are both very expensive operations when your array is large.

The List class is an object-oriented wrapper around an array. The API pretends that adding and removing entries is no big deal, but that's not the case. The internal implementation does exactly that. Add calls EnsureCapacity which calls the setter for Capacity which then does

T[] newItems = new T[value];
if (_size > 0) {
      Array.Copy(_items, 0, newItems, 0, _size);
}

When you need

  1. fast dynamic growth when adding items
  2. fast dynamic shrinking when removing items
  3. fast iteration from start to end but you don't need access by index

the data structure you should be using is a LinkedList. For more details about the performance characteristics of List vs. LinkedList see Drew Noakes answer to "When should I use a List vs a LinkedList" on stackoverflow.

When you need both access by index and want dynamic growth and shrinking, you could use a Dictionary with the index numbers as key.

| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ Anyone considering using a LinkedList for performance reasons may find Drew Noakes's answer to When should I use a List vs a LinkedList useful. \$\endgroup\$ – Kelly Thomas Oct 15 '14 at 11:33
  • 1
    \$\begingroup\$ @KellyThomas That answer you linked is indeed very relevant. I added the link to my answer. \$\endgroup\$ – Philipp Oct 15 '14 at 11:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.