List.size() != List.capacity();

[Timo Nentwig]

Hi!

I need a list to which I progressively add data to - at random indices.
So I set a List which ensures to have enough space for all items:

list = new ArrayList(max);

This does internally create an Object[] array of size <max>.
Unfortunately I cannot add at arbitrary indices as size() reflects only
the count of items already in the list and any access to an index
greater than size() throws an IndexOutOfBoundsException - despite the
index is not out bounds of the backing Object[] array.

So i do have to manually "initiliaze" the list *again*:

for (int i = 0; i < max; i++)
list.add(null);

Quite stupid... :-(

Timo

 

[Timo Nentwig]

Even worse!

List l = new ArrayList(10);
for (int i=0;i<10;i++)l.add(null);
System.out.println("this will output 10:" + l.size());
l.add(1, "blah");
System.out.println("this will output 11:" + l.size());

Can somebody explain this behaviour? To me it is totally idiotic :-(

 

[Christophe Vanfleteren]

Even worse!

List l = new ArrayList(10);
for (int i=0;i<10;i++)l.add(null);
System.out.println("this will output 10:" + l.size());
l.add(1, "blah");
System.out.println("this will output 11:" + l.size());

Can somebody explain this behaviour? To me it is totally idiotic :-(

You should think of a List as a resizable array.

When you add 10 nulls, the size of that array will be 10 (as it holds 10
elements, a List that hasn't had any elements added to it yet has size 0).

When you add another element, the List will grow by 1 more, so the size
will be 11. The fact that you added the element at index 1 makes no
difference. What happened is that all the elements after the newly added
element have moved to the right by one. So what was the element at index 5
is now the element at index 6.

If you actually want to replace the element at a certain index, use the
set(int index, Object o) method instead.

The 10 you use in the constructor is just an initial size that the ArrayList
implementation uses to create the initial array that is used to implement
the List interface and in which the objects you add to it are stored. It in
now way limits the maximum size that the List will have.

 

[Timo Nentwig]

If you actually want to replace the element at a certain index, use the
set(int index, Object o) method instead.

Yes, I just noticed that on my own a couple of minutes ago (it's
actually me who's stupid - unfortunately too late to effectively
cancel the posting.

Sorry...
Timo

 

[Sudsy]

Even worse!

List l = new ArrayList(10);
for (int i=0;i<10;i++)l.add(null);
System.out.println("this will output 10:" + l.size());
l.add(1, "blah");
System.out.println("this will output 11:" + l.size());

Can somebody explain this behaviour? To me it is totally idiotic :-(

This is perfectly understandable and acceptable. When you
want to add elements but you're already at capacity then
additional space is provided for you automagically. It's
all there in the javadocs... ;-)
There you'll also find this method:
add( int index, Object element )
This allows you to insert an element at any index which is
greater than or equal to 0 and less than or equal to size().
Seems to me that the class does everything you need.

 

[Collin VanDyck]

Yes, I just noticed that on my own a couple of minutes ago (it's

actually me who's stupid - unfortunately too late to effectively
cancel the posting.

Yeah, unfortunately most of my posts end up with the same conclusion

 

[Eric Sosman]

Hi!

I need a list to which I progressively add data to - at random indices.
So I set a List which ensures to have enough space for all items:

list = new ArrayList(max);

This does internally create an Object[] array of size <max>.
Unfortunately I cannot add at arbitrary indices as size() reflects only
the count of items already in the list and any access to an index
greater than size() throws an IndexOutOfBoundsException - despite the
index is not out bounds of the backing Object[] array.

So i do have to manually "initiliaze" the list *again*:

for (int i = 0; i < max; i++)
list.add(null);

Perhaps a List is not the right choice of data structure.
The requirement to add data "at random indices" seems odd; it
suggests that your application cares about the "gaps" in the
sequence of listed items, which seems un-List like ... You
might be better served by a HashMap or a TreeSet, or even by
a simple array ... what are you trying to do?

 

[Timo Nentwig]

Yeah, unfortunately most of my posts end up with the same conclusion

....but I still don't understand why there's no List.capacity() and I
have to reinitialize the array. I probably didn't see the wood for the
trees regarding the add() matter because I was to frustrated by this one

 

[Christophe Vanfleteren]

...but I still don't understand why there's no List.capacity() and I
have to reinitialize the array. I probably didn't see the wood for the
trees regarding the add() matter because I was to frustrated by this one

There's no list.capacity() because a list is unlimited in size. What should
capacity return then?
A List is not a good way of creating a sparse array, which seemed to be what
you wanted to do. You're going to need another datastructure for that.

 

[Joona I Palaste]

...but I still don't understand why there's no List.capacity() and I
have to reinitialize the array. I probably didn't see the wood for the
trees regarding the add() matter because I was to frustrated by this one

There is no List.capacity() because not all Lists have the concept of
capacity. For example LinkedList is only made up of element objects that
link to each other. There is no "master" object that would have
references to all of the element objects.

 

[Roedy Green]

Can somebody explain this behaviour? To me it is totally idiotic :-(

I will give you two rationalisations, but I agree with you the current
behaviour is not what I would have implemented. I suspect it was a bit
of programmer laziness that influenced the existing design choice.

1. it catches accidental subscript out of bounds. You effectively
have to declare your increased size dynamically by adding dummy
elements before you use the array, unless you grow by one.

2. It makes the code slightly faster and simpler since it does not
have to deal with putting in the dummy intermediate elements on
growth. It does not have to deal with deciding on allocation for
growth other than growing by one. That code is invoked by you only in
the rarer instances when you need it.

 

[Larry Coon]

I will give you two rationalisations, but I agree with you the current
behaviour is not what I would have implemented. I suspect it was a bit
of programmer laziness that influenced the existing design choice.

1. it catches accidental subscript out of bounds. You effectively
have to declare your increased size dynamically by adding dummy
elements before you use the array, unless you grow by one.

2. It makes the code slightly faster and simpler since it does not
have to deal with putting in the dummy intermediate elements on
growth. It does not have to deal with deciding on allocation for
growth other than growing by one. That code is invoked by you only in
the rarer instances when you need it.

Wouldn't it have been a reasonable compromise to provide a
method ensureSize(int desiredSize)? It'd just be something
like:

public void ensureSize(int desiredSize) {
ensureCapacity(desiredSize);

int amtToAdd = desiredSize - size();
for (int i = 0; i < amtToAdd; i++)
add(null);
}