Help choosing the right data structure

Question

I need a data structure with the following requirements:

• You need to be able to get items by index (for example, List).
• I will always add / remove elements from the end of the structure.

I tend to use an ArrayList . In this situation, it seems that O(1) how to read elements (are they always there?), Delete elements (I only need to delete them at the end of the list), and add (I add only to the end of the list).

The only problem is that from time to time the ArrayList will have a performance penalty when it is completely full, and I need to add a few more elements to it.

Is there any other idea? I do not think of a data structure that would break an ArrayList here.

thanks

Answer 1

Sounds good, although in C # you should use List<T> . This is the equivalent of Java ArrayList<E> . The ArrayList class in C # is not generic and is mostly deprecated by the new List<T> class.

There is only a problem that from time to time ArrayList will have a penalty for performance when it is completely full, and I need to add some more elements to it.

That probably won't be a problem, and you probably shouldn't worry about it if you don't have performance. However, if you know (or can guess) in advance the number of elements that your list will contain, you can set Capacity to this value ( ensureCapacity in Java). This will force the list to reserve the required memory in advance. You can also provide the languages list constructor .

Answer 2

Use ArrayList.

This will dynamically change when it reaches the capacity limit, as you say correctly. However, this should not be a problem, since he does it using a smart enough algorithm that the average cost for the add operation is only O (1).

Answer 3

always use List<T> instead of ArrayList

Answer 4

In fact, the addition is probably larger than O (N), since the array must be redistributed and copied as it grows according to distribution limits. Javadocs points out that it is growing at an amortized cost of O (N), no matter what it means, as I would expect O (NlogN), but they seem to have smarter algorithms than I know.

This is O (1) if you select enough elements to contain a complete team at build 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 and write access to List<T> . It should be noted that for most applications it is unlikely that you will notice the cost of resizing ArrayList<T>

However, if you add and remove items one at a time at the end, as you say more than you will get items by index (mainly using a List like Stack or Queue ), and your profiler tells you that ArrayList<T> , where is your performance bottleneck, you should consider using LinkedList<T> , which is designed for this kind of use.