the add method on ArrayList is not O(1), if it needs memory reallocation is O(n).
In general you are using ArrayLists when you are not add and remove many times and LinkedList when you do not need random access onto the objects
traverse is faster because there is the CPU cache. When you reference a memory location the architectures laods on the cache and some more memory that is near
In fact
adding an item on an ArrayList can’t be considered as O(1) cost since an array list may perform an array re-allocation if the current allocation becomes fullor unsufficient.
This method perform a full instanciation of a new array and a full copy that have a cost that depends of the size of the list.
So, this threads talk about the memory fragmentation of a LinkedList but not the wast space of an ArrayList and the re-allocation process that may be a real penalty in adding operations.
By example,
Create an ArrayList with the default constructor that mean an initial capacity of 10 and you will insert on your list 600 items.
@11th insertion ==> array[10] copied on a new array[15]
@15th insertion ==> array[15] copied on a new array[22]
@23th insertion ==> array[22] copied on a new array[33]
@34th insertion ==> array[33] copied on a new array[49]
@50th insertion ==> array[49] copied on a new array[73]
@74th insertion ==> array[73] copied on a new array[109]
@110th insertion ==> array[109] copied on a new array[163]
@164th insertion ==> array[163] copied on a new array[244]
@245th insertion ==> array[244] copied on a new array[366]
@367th insertion ==> array[366] copied on a new array[549]
@550th insertion ==> array[549] copied on a new array[823]
@600th insertion ==> you have an array of 823 that means a wast of 223 bullets and 11 arrays instanciations and copy.
Hopefully in often/some cases, we can estimate the final size of a list before filling it. When it’s the case, we should consider to use the good one constructor in order to prevent theses reallocations. With a LinkedList you haven’t this issue.
… because you can’t possibly predict an approximate capacity and/or you can’t stand a single 0.01ms spike to copy 100 objects from one array to another with a super-fast natively optimized Arrays.copyOf() called ONCE? Instead you rely on an linked list which is slower to add to, produces garbage when removed from and is slower to traverse? Just create a large enough ArrayList. It’s gonna use a lot less memory than a LinkedList since that one creates a Node object for each entry, and
[quote]a normal object requires 8 bytes of “housekeeping” space
[/quote]
(http://www.javamex.com/tutorials/memory/object_memory_usage.shtml)
plus 3 references * 4 bytes each. That’s 5 times as much data as an ArrayList stores per slot. Add cache inefficiency since the CPU can’t predict which object we’ll read, and it’s seriously not worth it.
add(): O(1) as long as you have a large enough array, which you will eventually get and keep forever. Better than LinkedList’s O(1) since it doesn’t produce garbage
remove(): not needed, we’ll never have to remove an object if we use the double ArrayList technique I’ve linked to over 9000 times by now.
get(index): O(1), much faster than LinkedList.
get in sequence: Faster due to cache coherency, doesn’t need to create an iterator object every time you want to loop over in sequence.
memory usage: 1/5th as much per object.
No, instead we have shitty performance all the time.
Never use LinkedList!
You heard it here first.
Cas 