Jump to content
xisto Community
Sign in to follow this  
Arbitrary

Arraylist Issues

Recommended Posts

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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

Thanks for answering. :ph34r: 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...

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×
×
  • Create New...

Important Information

Terms of Use | Privacy Policy | Guidelines | We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.