Is there a fundamental difference in Java between an ArrayList, and a class that uses regular arrays to store items, has an index to keep track of the number of items in the list, and automatically increases the size of the array when it runs out of space?

class myArrayList {
    private int[] array = new int[10];
    private int itemsInArray = 0;

    private void increaseArraySize() {
        int[] newArray = new int[array.length   10];
        System.arraycopy(array, 0, newArray, 0, array.length);
        array = newArray;
    }

    public void put(int i) {
        if (itemsInArray == array.length)
        {
            increaseArraySize();
        }
        array[itemsInArray] = i;
        itemsInArray  ;
    }

    public int get(int idx) {
        return array[idx];
    }

    public int size() {
        return itemsInArray;
    }
}

An ArrayList has some additional methods my class doesn't have (that I could add), and implements the List interface, but other than that, is ArrayList just for convenience? Do both use the heap to store data?

CodePudding user response：

Is there a fundamental difference in Java between an ArrayList, and a class that uses regular arrays to store items, has an index to keep track of the number of items in the list, and automatically increases the size of the array when it runs out of space?

In general no. Under the hood, ArrayList is just an ordinary pure Java class i.e. no native code. It is (roughly speaking!) doing what your code does.

But (as the comments say) it already exists. You don't need to design it, code it, debug it, tune it ... You just use it! Also read Basil's answer!

However, I would note that your version is different from ArrayList in some (other) important respects:

• A myArrayList holds only int values. It is not generic.
• An ArrayList holds objects. If you needed a list of integers you would need to use Integer as the type parameter rather than int. (Because that's the way that Java generic classes work.)
• In myArrayList, a set call beyond the end of the list will grow the list. It is behaving more like a dynamic array than a list.
• In ArrayList, a set call beyond the end of the list will throw an exception.

If you want a Java "list" type that is specialized for int or some other primitive type, there are existing 3rd party libraries; e.g. the GNU Trove library.

Do both use the heap to store data?

Yes. In fact, if you look at the source code of ArrayList you will see that it does something like what you code is doing. But it is doing it "smarter" and this will result in better "big O" performance in certain operations.

Consider this:

myArrayList list = new myArrayList();
for (int i = 0; i < N; i  ) {
    list.put(i, 1);
}

The computational complexity of this is O(N²).

Each call to list.put(i, 1) will cause a resize, creating a new array of size i and will then copy i - 1 values to the new array. That adds up to 0 1 ... N - 1 or N * (N - 1) / 2 copies. That is O(N²) for the N calls.

By contrast, ArrayList uses a resize strategy of growing the list by 50% of its current size. If you do the analysis, it turns out that the average amortized cost for N calls to ArrayList.append is O(N) ... not O(N²).

Lesson: Don't go trying to re-implement standard Java utility classes. It is usually a waste of time and there is a good chance that your efforts will actually make things worse!

There are exceptions to this lesson, but you need a lot of Java programming experience (and / or use of profiling tools) to identify them. Even then, there is a good chance that there is an existing a 3rd-party alternative that addresses the problem.

CodePudding user response：

You asked:

What's the difference between using ArrayList, or dynamically growing an array in Java?

Looking at the Collections Framework Overview, the very first bullet item says:

The primary advantages of a collections framework are that it:

• Reduces programming effort by providing data structures and algorithms so you don't have to write them yourself.

You asked:

Is there a fundamental difference in Java between an ArrayList, and a class that uses regular arrays

In terms of behavior, no fundamental difference. As the name implies, the current implementation of ArrayList is a class that uses regular arrays. So there is no point to you writing your own.

Keep in mind that future versions of ArrayList implementations are free to use some other approach besides actual arrays provided the contract promised in the Javadoc is met.

is ArrayList just for convenience?

Yes, as stated above. Rather than have every individual programmer write their own implementation, why not share one single well-written, well-debugged, and well-documented implementation?

Most implementations of Java are based on the OpenJDK open-source codebase. You are free to peruse the source code.