Is the design of 'ArrayList' good ?

Discussion in 'Java' started by Red Orchid, May 6, 2006.

  1. Red Orchid

    Red Orchid Guest

    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.
     
    Red Orchid, May 6, 2006
    #1
    1. Advertisements

  2. Red Orchid

    Chris Uppal Guest

    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.
     
    Chris Uppal, May 6, 2006
    #2
    1. Advertisements

  3. And the existence of AbstractList and AbstractSequentialList are a big help
    here.
     
    Mike Schilling, May 6, 2006
    #3
  4. Red Orchid

    Chris Uppal Guest

    Mike Schilling wrote:

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

    Thanks.

    -- chris
     
    Chris Uppal, May 7, 2006
    #4
  5. 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
     
    Robert Klemme, May 8, 2006
    #5
    1. Advertisements

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments (here). After that, you can post your question and our members will help you out.