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.
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
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 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.
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
ArrayList collection, with which we've worked before,
actually works this way internally. We can imagine an
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
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.
trueif 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.
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
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:
The code above creates a
ArrayList of the
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
int types. In Java, it's not possible to use
primitive types as generic parameters, such as
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.
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
Comparableinterface, otherwise the method throws an exception. Basic Java classes and structures implement the
Comparableinterface, for our own classes, we have to implement it by ourselves.
Except for few methods, we've described the entire
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.
No one has commented yet - be the first!