Arrays VS linked-lists

[jacobo]

Most of the code i have seen uses arrays rather then linked lists is there a speed or other issue behind this? The main reason I ask is I am planning to make a storage for all the treaty classes(see Diplomacy thread) and am wondering what method to use.

[Mark_Everson]

I haven't done any detailed tradeoff calculations... However, arrays mean that a map square can know what its index in a provinces' squares array is, making removing it from that array Much quicker that finding it in a linked list that could have around 1000 entries late in the game. (Most of the other arrays shouldn't grow that big.) However, on the downside I need to check for array size, and sometime resize the arrays. What do the experienced programmers think about this?

[mca]

jacobo: I don't know what your experience level is, so I'll just give the lecture

It all depends on what operations you are going to use on the storage:

If the number of elements in the storage never changes, use an array. Indexing (element=storage[i] or storage[i]=element) is cheapest with arrays.

If the number of elements change over time, you may need something else.

Linked lists are cheap to iterate through, and removing/inserting elements is usually cheap, but indexing is really expensive.

Vectors (resizable arrays) feature cheap indexing and removing and inserting elements at the end of the vector is cheap, but removing/inserting elements in the middle of the vector is really expensive.

Hashtables feature somewhat cheap indexing, insert/remove, and iteration, but the elements are unordered. (They are my favorite when I want high flexibility and not high performance, and when I need to index by Strings and not ints).

The above is not the whole truth, but I think it comes close enough.

Also, you might want to take a look at the Java 2 Collection API in java.util.

Martin

[JimC]

Quick note:

Speed issue (may be important, may not be)....

Vector class is synchronized, ArrayList is identical but unsynchronized.

ArrayList is usually a lot faster, if you aren't using threads.

Jim