What is the point of ArrayLists?

Question

I am looking at some code, and I've come across this thing called ArrayLists? What exactly is the point of using ArrayLists as oppose to regular lists? And if you look at the code, before the methods names you have <T> ArrayList<T>. Is it because these are ArrayLists? And why the <T>?

class MergeAlgorithm{

    //ArrayLists
    <T> ArrayList<T> merge(ArrayList<T> list1, ArrayList<T> list2, 
            Comparator<T> comp, ArrayList<T> acc){
        if(list1.isEmpty())
            return append(acc, list2);
        else if(list2.isEmpty())
            return append(acc, list1);
        else if(comp.compare(list1.get(0), list2.get(0)) <= 0){
            acc.add(list1.get(0));
            list1.remove(0);
            return merge(list1, list2, comp, acc);
        }
        else{
            acc.add(list2.get(0));
            list2.remove(0);
            return merge(list1, list2, comp, acc);
        }



    }



<T> ArrayList<T> append(ArrayList<T> list1, ArrayList<T> list2){
    for (T t: list2){
        list1.add(t);
    }
    return list1;
}
}


class CharComp implements Comparator<Character>{
    public int compare(Character c1, Character c2){
        return c1.compareTo(c2);
    }
}

Answer 1

What exactly is the point of using ArrayLists as oppose to regular lists?

It depends on what you mean by a "regular list".

• If you mean java.util.List, then the point is that you cannot create an instance of that List type ... because it is an interface not a class.

• If you mean some other list class such as java.util.LinkedList ... then you need to realize that each of the different list classes have their own behavioural / performance characteristics. For example:

  • The LinkedList has fast insertion at the start of the list, but a slow get(int) operation compared to ArrayList

  • The ArrayList class has fast get, and uses less memory on average¹ than an equivalent LinkedList.

---

And if you look at the code, before the methods names you have <T> ArrayList<T>. Is it because these are ArrayLists? And why the <T>

The <T> denotes a type parameter of the generic merge and append methods. Read the Java Tutorial section on Generics ... and then you should be able to understand what this code is saying.

No, it is not "because these are ArrayLists". You'd need to use the a generic type parameter for other list classes as well. The List interface and all of the standard list classes are generic types.

---

^{1 - The space usage of ArrayList is a bit rubbery, because it depends on the sequence of operations used to get to the list whose space usage you are measuring. But an optimal ArrayList occupies much less space than a LinkedList with the same elements. And this is true for typical use-cases as well.}