When when an arraylist's logical size reaches its capacity, does it link a new array on to the end or does it make a new array and copy all the values into the new array?
Asked
Active
Viewed 268 times
2 Answers
1
You may get a better answer (i.e., more targeted, more useful to you) if you specify which language(s) you're interested in. Many common implementations use a block of values (including pointers, if an array of pointers); when the space in the block runs out, a larger block is allocated, the existing values copied forward to the new space, and the old space released. You can sometimes have some effect on how this happens (e.g., how much bigger is the new space compared to the old), but (of course) it's implementation dependent. Most implementations work at making sure each time you add or remove one item that reallocation of the space does not occur. This implies there is unused space in such implementations.
Again if you have a more specific interest, suggest you try editing your post to focus it a bit.
If you are just looking to learn, I'd suggest playing with Python. Lots of stuff on StackOverflow you may find interesting; here's just a couple: array size, performance.
0
That second one -- it creates a new array and copies the old one over. If you want to avoid the copying, then you can use LinkedList instead, which does just add new links to a chain; but of course then you don't get the fast indexing that a single array of elements provides.
Ernest Friedman-Hill
- 80,601
- 10
- 150
- 186
-
I thought a linked list uses linked nodes? – Tyler Petrochko Feb 20 '12 at 23:26
-
That's what I said, `LinkedList` uses a chain of linked nodes, while `ArrayList` uses an array. – Ernest Friedman-Hill Feb 21 '12 at 01:53