Is the design of 'ArrayList' good ?  
Author Message
Red Orchid





PostPosted: 2006-5-6 14:17:00 Top

java-programmer, Is the design of 'ArrayList' good ?
Occasionally I think that the design of 'ArrayList' is not good.

Because ...
The access modifier of 'E[] elementData' in 'ArrayList'
is 'private'. That is, Java do not allow a programmer
to access 'E[] elementData'.

Therefore, he will write the following statements to
sort 'ArrayList'.

<example>
List<String> strList = new ArrayList<String>();
Collections.sort(strList); // <- #1
</example>


By the way, the source of #1 is as follows.

<Quote>
public static <T extends Comparable<? super T>> void sort(List<T> list) {

Object[] a = list.toArray(); // <- #2
Arrays.sort(a); // <- #3
ListIterator<T> i = list.listIterator();

for (int j=0; j<a.length; j++) { // <- #4
i.next();
i.set((T)a[j]);
}
}
</Quote>

If 'strList' is large array, #3 is merge sort.
Merge sort requires 2 * M when M is the memory
size of 'strList'.

Because the memory size of 'a' in #2 is M,
'Collections.sort' requires 3 * M and has to execute #4.
It seems inefficient. (note that 'strList' is large array)

If the access modifier of 'E[] elementData' is 'protected',
he can sort 'strList' with 2 * M and without #4.

What is your comment ?
Thanks.








 
Chris Uppal





PostPosted: 2006-5-6 17:45:00 Top

java-programmer >> Is the design of 'ArrayList' good ? Red Orchid wrote:

> Because the memory size of 'a' in #2 is M,
> 'Collections.sort' requires 3 * M and has to execute #4.
> It seems inefficient. (note that 'strList' is large array)

It's not ideal, I agree. I think it would be better if ArrayList included the
ability to sort itself in-place (or rather, as close to in place as it can
given the requirement for a stable sort). However there is then the
"problem"[*] of ever-widening APIs, and Java traditionally tends to avoid wide
classes, so ArrayList lacks this feature.

But note that there is nothing stopping you creating your own array-backed
implementation of java.util.List which /does/ have this ability. The existing
java.util.* classes are handy, but they are not intended to be a complete set
of all possible useful utility classes. We are expected to be able to
recognise when the pre-defined stuff is inadequate and to be able to create our
own versions at need.

-- chris

[*] Not actually a problem, IMO, difficulties with wide interfaces are more a
symptom of deficiencies in the support tools than of poorly designed classes.


 
Mike Schilling





PostPosted: 2006-5-6 22:21:00 Top

java-programmer >> Is the design of 'ArrayList' good ?
"Chris Uppal" <email***@***.com> wrote in message
news:445c756a$2$25453$email***@***.com...

> But note that there is nothing stopping you creating your own array-backed
> implementation of java.util.List which /does/ have this ability. The
> existing
> java.util.* classes are handy, but they are not intended to be a complete
> set
> of all possible useful utility classes. We are expected to be able to
> recognise when the pre-defined stuff is inadequate and to be able to
> create our
> own versions at need.

And the existence of AbstractList and AbstractSequentialList are a big help
here.


 
 
Chris Uppal





PostPosted: 2006-5-7 17:41:00 Top

java-programmer >> Is the design of 'ArrayList' good ? Mike Schilling wrote:

[me:]
> > We are expected to be able to
> > recognise when the pre-defined stuff is inadequate and to be able to
> > create our
> > own versions at need.
>
> And the existence of AbstractList and AbstractSequentialList are a big
> help here.

True, and I would have mentioned that myself if I hadn't forgotten all about it
;-)

Thanks.

-- chris


 
 
Robert Klemme





PostPosted: 2006-5-8 15:39:00 Top

java-programmer >> Is the design of 'ArrayList' good ? Red Orchid wrote:
> Occasionally I think that the design of 'ArrayList' is not good.
>
> Because ...
> The access modifier of 'E[] elementData' in 'ArrayList'
> is 'private'. That is, Java do not allow a programmer
> to access 'E[] elementData'.

The reason is encapsulation. You cannot likely satisfy all design goals
that one might want to establish for a standard library and that are
desirable in a single class - in this case encapsulation and error
safety won. Note that there are classes that support continuous
ordering and with a special Comparator implementation you can even have
non set like behavior. Or you use a TreeMap and stuff collections into
the value fields. Or... Chris and Mike have demonstrated other very
valid points.

Kind regards

robert