Arraylist Issues

I've been studying for the AP CS test and just read that ArrayLists add objects in constant time, which I don't really get. Why would ArrayLists add in constant time when it needs to copy all of the objects in the array to a new array just to allocate a new space for the new object? Wouldn't that mean the ArrayList would run in O(n) time? The only explanation I can come up with is if the ArrayList doesn't change the array right away and instead puts the add function onto some sort of stack and waits until it gets numerous add functions and then performs all the add functions so that it only needs to create a new array once per x number of add functions. I'm rather confused, so any help would be appreciated.

Comment/Reply (w/o sign-up)

According to the Javadoc for ArrayList, the Array list runs in amortized constant time, not constant time. This means that it is almost constant time, but not quite. I do not know the mechanics of it, but it is probably very similar to how a List works. The best part of an ArrayList is random access, which is faster than a List. A List is faster if elements are taken from the beginning or the end of the list.

Both List and ArrayList have constant time adding of elements (just make the end pointer point to a new object and update references), but ArrayList does some extra stuff to make it have random access.

An ArrayList could potentially create additional "overflow" arrays to hold data past its capacity, and then leave an address to that location at the end of the last array, or some other means of expanding capacity without copying the entire array. I am not sure of the specifics.

Sorry for the crappy answer, and it probably didn't answer your question, but that is basically what I know for sure.

Comment/Reply (w/o sign-up)

Thanks for answering.

Ahhh...I'm thinking that this amortized constant time thing is key. I don't really get the mechanics behind it, but according to the dictionary definition for amortized (putting it off to some other time), it probably puts off the add functions so that it creates a new array later, causing an artificial kind of constant time.

By List I'm assuming you mean LinkedList? As looking at the documentation for List, it seems to be rather general...

Comment/Reply (w/o sign-up)

What you need to remember about computers is that nothing is actually instantaneous. The ArrayList needs to steal time away from your CPU. The algorithim for an ArrayList does its transfer in stages. However, realistically this won't have any impact on the function of a program. In my work with arraylists, the time allotted for the transfer is negligible and will have to impact on the function of your program.

Comment/Reply (w/o sign-up)