Is the design of 'ArrayList' good ?

[Red Orchid]

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]

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]

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]

Mike Schilling wrote:

[me:]

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]

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