Lesson 3 - Lists with arrays in Java

In the previous lesson, Java Collections Framework, we peeked at how the Java language implements various collections within the Java Collections Framework. In today's Java tutorial, we're going to learn more about Lists, which represent one type of collection that we've already encountered before.

Array

First and foremost, let's take a quick peek back to arrays, which were the first collection we learned about throughout the courses. One of the main characteristics of an array is that it has a fixed number of elements. For this reason, it's not even considered as a collection by some sources, because it doesn't meet part of its definition. The elements in an array are indexed numerically, starting from zero.

The main disadvantage to using arrays is that we can't add or delete items during runtime. Unfortunately, we often need to do this. However, there are situations where an array is the perfect choice. This "disadvantage" is the price paid for the high speed that comes with accessing array items. Since the data is of the same type (either exactly the same or of a common ancestor) they take up the same space in memory. Individual array items are stored in memory as an uninterrupted sequence, like in a row. We can imagine an array of integers as something like this:

If we wanted to access the 5th item, we'd simply access the beginning of the array and then jump forward by 4 times the type size (in this case, the size of an int). Reading and writing at array indexes are done within a constant time complexity. If you are confused by this term, you may see it as a way of writing into array indexes immediately and so that we can read them.

Note: If we create an empty numeric array in Java, it's automatically filled with zeros.

Lists

Lists are collections that allow us to add and delete items at runtime. They can be indexed numerically as arrays, but they don't have to. There are basically two types of lists.

ArrayLists

Lists often take advantage of the fact that although we cannot change the size of an array during runtime, we are able to create new arrays at runtime.

In this case, the list is a class that contains methods for adding and removing elements (and many other useful methods, which aren't relevant to us at the moment). The class essentially wraps an array and contains an extra variable where the number of elements is stored. When an instance is being created, an array of a given amount of elements is created inside, and the variable carrying the number of elements is set to 0. When we add the first element, it's stored at the 1st index in the array and the number of elements is incremented. We'd be able to add elements like this until we fill the array. Once the array is full, we simply create a new array, let's say, twice as big. We copy the elements from the old array into the new array and then throw away the old one. Once this new array is filled as well, the process will be repeated. The ArrayList collection, with which we've worked before, actually works this way internally. We can imagine an ArrayList using an array internally sort of like this:

The list in the picture contains eight elements. The elements are stored in an internal array of the size of 12 elements. The last four elements are unused and from the outside look as if they aren't even there.

The advantage here is the fast random access to the elements using numeric indexes thanks to the inner array. The downside to it is the time required to create the new array and copy the elements into it, although this process doesn't occur too often. Another less painful drawback is that the collection occupies more memory than necessary. Anyway, this list type is still the most used collection in Java and is fairly well optimized.

Furthermore, a list using arrays is represented in Java as the ArrayList class. The picture below shows the complete ArrayList class hierarchy:

As you can see, ArrayList also implements the List interface.

List methods

Let's describe important methods on this interface. List is the basis for all Java lists and contains the following methods:

• add() - Adds a new element into the list.
• addAll() - Adds multiple new elements into the list.
• clear() - Deletes all of the elements.
• contains() - Returns true if the list contains the given element.
• toArray() - Copies elements from the list into an array.
• remove() - Removes the given element. This feature is very useful when we store some class instances in the list (e.g. users). We don't have to keep their numerical indexes, we just call: list.Remove(carl). We pass the exact instance of the element, we want to remove from the list.
• removeAll() - Removes multiple given elements.
• count() - Returns number of elements in the list.

The add() method has two overloads. In one case, it only accepts the object being added, in the second case it also accepts the index to which the element is to be inserted. The remove() method also has two overloads. The first one receives the object to be deleted, in the other one it receives the index at which to remove the element.

Despite the fact that we've already used the ArrayList class like 1000 times, for completeness' sake, here's an example of its use:

List<Integer> list = new ArrayList<>();
list.add(5);
list.add(10);
System.out.println(list.get(0));

The program's output:

5

The code above creates a ArrayList of the Integer type, adds two numbers to it, and then prints the first element to the console. We work with indexes like we worked with an array. However, we're also able to add elements and remove them during runtime.

Note, that we use a list of the Integer type to store int types. In Java, it's not possible to use primitive types as generic parameters, such as byte, short, int, long, boolean, char, float, or double. Instead, we need to use wrapper classes, that have been created for the purpose of using these types in collections. Conversion between primitive data types and their wrapping classes is automatic.

Furthermore, List offers these methods:

• indexOf() - Returns the index of the first occurrence of a given element in the list.
• lastIndexOf() - Similar to the indexOf() method, returns the index of the last occurrence of a given element in the list.
• removeIf() - Deletes all elements that match a given condition (a predicate, see below).
• sort() - Sorts the list. It's important that its elements implement the Comparable interface, otherwise the method throws an exception. Basic Java classes and structures implement the Comparable interface, for our own classes, we have to implement it by ourselves.

Except for few methods, we've described the entire ArrayList.

Try other methods like sort() and so on. We'll continue to work with collections in more detail when we get to Stream API.

In the next lesson, Linked Lists in Java, we'll introduce the second type of list, which is the linked list.

Did you have a problem with anything? Download the sample application below and compare it with your project, you will find the error easily.