Java List Tutorial

1. What is List in Java?

Java List is a fundamental interface that represents a collection of objects, in a specific order. It inherits from the Collection interface and is part of the java.util package.

The List interface contains methods that can add, remove or search for elements in a list. Elements have an index, like arrays, which can be used to access the elements in the list. It is able to contain duplicate values, as well as, null values. It can be of any type of object, meaning that, for example, a List of integers would have to use the Integer wrapper class and not the primitive type int. Lastly, a List has a dynamic size, unlike the fixed length of arrays.

List can be used with any Object type, through Generics. So, it is possible to use the methods described in the following sections with Integer, String, or our own custom class. We can be sure that these methods will have the expected outcome, no matter the Object used to initialize them, thanks to Generics.

Before moving on, you have two options; read about List in theory, or jump straight to an example if you know the theory already.

2. Java List Interface Methods

The List interface contains several methods, which are in turn implemented by its conforming classes. Some of the most used methods are shown below. A parameter or return value of type E means a Generic Type.

2.1 Modification Methods

This subsection contains the methods that modify the number of elements of a List.

2.2 Information Methods

The methods of this subsection return information about the state of the List.

2.3 Iterator Methods

In this section, we will see a few methods that use Iterators. An Iterator is an object that iterates (or loops) through collections in a forward direction. A ListIterator is an object that iterates (or loops) through collections in both forward and backward directions.

2.4 Collection Creation Methods

Lastly, this section contains methods that create an array or a List from a starting List.

3. Main Implementations of Java List

As it has been mentioned, List is the interface that contains all the methods above. Despite having those tools in its arsenal, we need an implementation of the List interface, if we would like to take advantage of its power. In other words, you cannot use the following assignment: List myList = new List();

You could possibly create a custom class that implements this interface. By doing so, you would have to implement all of the aforementioned methods. So, unless you really need a custom implementation of List, chances are you would be satisfied with any of the existing implementations.

There are four main implementations of List; ArrayList, LinkedList, Vector, and Stack. We will describe how they work and how time-intensive their operations are. In order to achieve this kind of measuring, we will use the Big O notation to compare the operations of accessing (find) and modifying (insertion/deletion).

Before starting, let’s see what those operations mean, so as to have a clear picture.

• An accessing operation refers to the process of finding a specific element in the List. Using our example, that would mean how much time it would take the collection to find the name we wanted.
• A modifying operation is about how fast a an element can be added or removed from the List. In our case, how quickly we would write a new name or erase an existing name from a random position, while mainting the structure of the List (not leaving blank spaces after removals, for example).

3.1 ArrayList

ArrayList is the most widely used class of the four. As their name might imply, they are internally built as arrays but with a catch; their size is dynamic. This trait makes them tremendously useful for a very large variety of applications, where the number of elements of a collection cannot be known. Despite that, they tend to be slightly slower than typical arrays.

In order to measure the time of accessing and modifying the elements of an ArrayList, imagine you have a large list of names with their index and you would like to perform those operations.

Accessing Operations: ArrayList uses indexes to access its elements. Because of that, each element can be randomly accessed at any time, since the collection is always aware of its elements’ position. In our example, we could find the 100th name instantly, since we have noted down the index of the name. Because of this, ArrayList‘s access operation is O(1). This measurement means “constant time”, and is the best time an algorithm/operation can get.

Modifying Operations: The elements of an ArrayList occupy sequential slots in memory. Because of that, if an element is added or removed, the rest of the elements would have to shift one spot in order to make room or fill up blank space, respectively. Imagine we had to add a new name near the beginning of our List. We would have to rewrite the entire List, but with the new name in the beginning.

On the other hand, if we wanted to remove a name near the beginning, we would have to write the list again so as to fill up the free space in the beginning.

As such, a modifying operation would take O(n).

3.2 LinkedList

A LinkedList is a collection of objects that are “linked” by pointers. They have content and a pointer that points to the next or previous element of the List. It is a more linear data structure, as its iteration is more limited but, thanks to the pointers, the elements are not stored in sequential memory addresses, as it happens in ArrayList.

There are two main variations of LinkedList; Singly LinkedList and Doubly LinkedList. Their main difference is that a Singly LinkedList can only move forward…

…while a Doubly LinkedList allows traversal in both directions.

Accessing Operations: Unlike ArrayList, there is no indicator of position in the collection. So if the LinkedList needs to find an element, it would have to traverse through all the elements until it finds it. As such, the access operation of LinkedList is O(n), as we need to check all elements, one by one, in order to find what we want.

Modifying Operations: Here things are much simpler than what happens in ArrayList. Let’s assume that we have found the position where a modification should take place (which is an O(n) operation, as explained above). Since the elements point to other elements, the addition and deletion of an element in the list is only a matter of changing the pointers. For instance, if we wanted to remove the element named “Akis”, the first pointer would have to point to the third (and vice versa, for a Doubly LinkedList), like so:

Similarly, an addition would look like this:

As a result, changing the pointers is a very quick operation so, the modification operation of a LinkedList is O(1).

3.3 Vector

Vector is mostly a legacy collection nowadays. It’s very similar to ArrayList, as it also uses an array internally and grows its size dynamically. However, there are a few differences that set the Vector apart from ArrayList.

The operations of Vector are synchronized, while ArrayList‘s are asynchronized. The impact of this comes in multi-threaded programming where operations can happen concurrently, instead of sequentially. An operation of Vector essentially locks the thread until the operation finishes. Imagine if we wanted to sort a Vector of 10k items. We would have to wait for it to finish, which can be disastrous, depending on the application. An ArrayList does not have this problem, since one thread can sort it and another can do some other operation.

Another major difference comes to play when the Vector has to increase its size. In order to do that, the Vector doubles its size (100% increase), which can be very wasteful. Think about having a Vector of 10000 items and we append a single item; the capacity would become 20000 with the rest 9999 indexes being empty. On the other hand, an ArrayList increases its capacity by half of its current capacity (50% increase), which is more efficient in most applications.

Owning to the fact that Vector is an older relative of ArrayList, its accessing and modifying operations are the same as ArrayList.

3.4 Stack

Stack has the most unique behavior out of the List interfaces we have discussed. As the name implies, its principle is a Last-In-First-Out (LIFO) collection, which means that if an element is inserted into the collection last, then it will be among the first to be accessed. The easiest way to understand Stack is to think of a stack of books on a table.

• You place the first book on top of the table.
• In order to add more books to your stack, then you place them onto the book on top. That’s called a push operation.
• If you wish to remove a book, you remove the one on top of the stack. Otherwise, you risk collapsing your stack of books. This is the pop operation.
• Finally, if you want to search for a book, you would look normally at the side of the books. But in a Stack, you would have to get through all elements, so as to reach the desired element.

Accessing Operations: As discussed, in order to access an element, Stack has to check every element. We can’t search for SQL’s book without going through the rest of the book on top of it. As a result, just like in LinkedList, this operation is O(n).

Modifying Operations: Stack can only operate at the top/end of the list. Because of that, this operation is pretty fast, or O(1), similarly to LinkedList.

2.5 Comparison of Java List Implementations

Let’s summarise the previous four sections in one table:

3. A Java List in Action

Thus far, we have only discussed Java List in theory, so it’s time for an example to see how ArrayList, specifically, shines.

Let’s assume that we have a coin and we keep flipping it until we get 15 Heads in a row. We note down each attempt and, after we eventually make it, we take note of the total coin flips we made. Since we cannot know how many attempts our experiment is going to take us, a dynamic collection like ArrayList is perfect for this task.

The code for this task would look like this:

import java.util.ArrayList;

public class CoinFlipsArrayListExampleClass {

    /* In main method, we repeat the same experiment 10 times. Notice how greatly ArrayList's size differs in each
    * attempt.*/
    public static void main(String[] args) {
        for(int i = 0; i < 10; i++) {
            int totalNumberOfAttempts = flipCoinForFifteenHeads();
            System.out.println("Experiment: " + (i + 1) + ". I got 15 Heads in a row by flipping the coin " + totalNumberOfAttempts + " times.");
        }
    }

    /* This method flips a coin as much as needed, until we get 15 Heads in a row.*/
    private static int flipCoinForFifteenHeads() {
        int numberOfConsecutiveHeads = 0; // used to count the consecutive Heads we got. If we get 15, we stop flipping.
        ArrayList<String> coinFlips = new ArrayList<String>(); // all coinflips so far.

        while(numberOfConsecutiveHeads != 15) {
            String coinFlip = Math.random() < 0.5 ? "Heads" : "Tails"; // 50/50 probability to get heads or tails

            if(coinFlip.equals("Heads")) {
                numberOfConsecutiveHeads += 1; // the Heads streak is still going on
            } else {
                numberOfConsecutiveHeads = 0; // the Heads streak was broken
            }

            coinFlips.add(coinFlip); // add attempt in our ArrayList
        }

        return  coinFlips.size(); // total size of the ArrayList is the total number of attempts we made
    }
}

The method that performs the coin flips is flipCoinForFifteenHeads(). In order to make a coin toss, we call Math.random() and, depending on the result, we decide about the outcome of the flip, [0.0, 0.5) for Heads, [0.5,1) for Tails (equal probability for both outcomes). If we get “Heads” then we increase the counter of numberOfConsecutiveHeads by one otherwise, we reset it to zero. When we finally make it, the ArrayList‘s total size will represent the total number of coin flips we made.

In the main method, we simply repeat the aforementioned experiment ten times, to demonstrate the dynamic size of the ArrayList. Let’s see the output of running the above code (your output could be different, because of how Math.random() operates):

Experiment: 1. I got 15 Heads in a row by flipping the coin 105418 times.
Experiment: 2. I got 15 Heads in a row by flipping the coin 24745 times.
Experiment: 3. I got 15 Heads in a row by flipping the coin 27945 times.
Experiment: 4. I got 15 Heads in a row by flipping the coin 339197 times.
Experiment: 5. I got 15 Heads in a row by flipping the coin 313742 times.
Experiment: 6. I got 15 Heads in a row by flipping the coin 38261 times.
Experiment: 7. I got 15 Heads in a row by flipping the coin 128608 times.
Experiment: 8. I got 15 Heads in a row by flipping the coin 44268 times.
Experiment: 9. I got 15 Heads in a row by flipping the coin 58030 times.
Experiment: 10. I got 15 Heads in a row by flipping the coin 206690 times.

As you can see, we can fill up the ArrayList with a number of items that differ greatly in each experiment, because ArrayList has a dynamic size that does not need to be initialized in the beginning.

5. Conclusion

Summing up, Java List is a very strong interface with a great many applications. Hopefully, you are, now, able to understand how this powerful interface works. You can find the source code of this article on our GitHub page.

6. Sources

[1]: List – Oracle

[2]: Big O notation – Wikipedia