Help choosing the right data structure

Question

I need a data structure with the following requirements:

1. Needs to be able to get elements by index (like a List).
2. I will always just add / remove elements from the end of the structure.

I am inclined to use an ArrayList. In this situation, it seems to be O(1) both to read elements (they always are?), remove elements (I only need to remove them at the end of the list) and to add(I only add to the end of the list).

There is only the problem that time to time the ArrayList will have a performance penalty when it's completly full and I need to add more elements to it.

Is there any other better idea? I don't think of a data structure that'd beat the ArrayList here.

Thanks

Answer 1

Sounds good, though in C# you should use a List<T>. It's the Java equivalent of ArrayList<E>. The ArrayList class in C# is not generic and is basically made obsolete by the new List<T> class.

There is only the problem that time to time the ArrayList will have a performance penalty when it's completely full and I need to add more elements to it.

This probably won't be a problem and you probably shouldn't worry about it unless you've performance profiled. However if you know (or can guess) in advance the number of elements that your list will contain you can set its Capacity to that value (ensureCapacity in Java). This will cause the list to reserve the required memory in advance. You can also give the capacity to the list constructor in both languages.

Answer 2

always use List<T> instead of ArrayList

Answer 3

Use an ArrayList.

This will dynamically resize when it hits its capacity limit as you rightly say. However this should not be a problem as it does so using a sufficiently clever algorithm that the average cost per append operation is still only O(1).

Answer 4

Actually adding is probably more O(N) as the array must be reallocated and copied when it grows over the allocation limits. The Javadocs specify it grows at a amortized cost of O(N) whatever that means, as I would expect O(NlogN) but apparently they have smarter algorithms than I am aware of.

It is O(1) if you allocate enough elements to contain the complete colleciton at construction time.

see : http://java.sun.com/j2se/1.4.2/docs/api/java/util/ArrayList.html

Answer 5

You need to balance the relative frequency of your read access versus your write access to the List<T>. It must be noted that for most uses it is unlikely that you will notice the cost of resizing an ArrayList<T>

However if you are adding and removing items one at time at the end as you say more than you will be getting items by index (basically using the List as a Stack or Queue) and your profiler tells you that ArrayList<T> is where your performance bottleneck is, you should consider using a LinkedList<T> which is intended for just this sort of usage.