In this post series, we are going to talk about a common data structure named List, and its implementations ArrayList and LinkedList, and how to choose when to use each of them.

In this particular post, we are going to introduce the bases regarding List and its implementations.

Java Collections List Series

• Part 1: Java Collections: List (You are here)
• Part 2: ArrayList vs LinkedList: Addition
• Part 3: ArrayList vs LinkedList: Deletion
• Part 4: ArrayList vs LinkedList: Sort, Get and Iteration

What is a List?

A List is a collection of elements with the following features:

• An ordered collection (sometimes called a sequence). 
• Lists can contain duplicate elements.
• Precise control over where in the list each element is inserted.
• Can access elements by their integer index (position).

We can see in the example a list of 7 numbers, ordered by insertion sequence, allowing duplicates like 5 and 8, and you can access each element by index, for instance, the number 10 can be access using the 5 index number. Moreover, you can choose a specific position on the list to insert, replace or delete.

NOTE: A List is usually mutable, this means, some operations against a List, will change its internal state.

Now, let’s discuss how Java defines a List.

The List Java Interface

Well, Java has a List interface:

NOTE: We are not showing the whole bunch of methods, only the most used.

List inherits from Collection the following methods:

• add(type): Insert an element to the end of the list.
• contains(object): Search the object in the list and return a boolean.
• remove(object): Search the object in the list and return a boolean. If the object is found, its removed.

NOTE: contains and remove uses the equals method of the elements to compare, you must override it in your classes to get this working correctly.

Now, let’s see the specific List methods:

• add(type, index): An overloaded method defined in the List interface. This allows to insert an element in a specific index.
• get(index): Get an element in the specific index.
• remove(index): Remove an element in the specific index.
• sort(comparator): Sort the list based on the comparator strategy.

NOTE: The index is restrict to the list size, it means, it must be between 0 inclusive and list.size() exclusive.

Now, let’s see some of the Java implementations for the List interface.

The ArrayList Implementation

Well, Java has a List implementation named ArrayList. This implementation looks like this:

As we can see in the example, an ArrayList is an abstraction of a Java array, where each element is in consecutive memory addresses.

NOTE: This example is equivalent to int[] array = {1 , 5, 5, 9, 8, 10, 8};

ArrayList abstracts the complexity of handling a Java array, remember, a pure Java array has a static size, it means, you cannot add, insert or remove dynamically elements.

NOTE: We are going to talk about how ArrayList abstracts that complexity in the following posts.

The LinkedList Implementation

Well, Java has another List implementation named LinkedList. This implementation looks like this:

As we can see, this is a double linked list, this means, the elements are not in consecutive memory addresses, they are dispersed through memory.

Each element links to the next and to previous. Moreover, the list knows which element is its head and which one is its tail, nothing more.

NOTE: This list implementation is not supported by a pure Java array, this is only objects with pointers to other objects.

List Example

Well, let’s see how those lists work:

NOTE: You will see the LinkedList instantiation commented. If you replace the list from an ArrayList to a LinkedList, the code will compile fine and the test will run green. That is the power of Polymorphism….

TRY IT YOURSELF: You can find the source code of this post here.

add(type)

  @Test
  public void add_newElement_listChanged() {
    List list = new ArrayList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));
    /*List list = new LinkedList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));*/

    list.add(9);

    assertThat(list).isEqualTo(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8, 9));
  }

contains(object)

  @Test
  public void contains_element_true() {
    List list = new ArrayList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));
    /*List list = new LinkedList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));*/

    boolean result = list.contains(8);

    assertThat(result).isTrue();
  }

remove(object)

  @Test
  public void remove_element_true() {
    List list = new ArrayList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));
    /*List list = new LinkedList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));*/

    boolean result = list.remove((Object) 8);

    assertThat(result).isTrue();
    assertThat(list).isEqualTo(
            Arrays.asList(1, 5, 5, 9, 10, 8));
  }

NOTE: See line 8? we cast to object the parameter. Remember, we have two methods overloaded, remove(object) and remove(index), to tell the compiler to use the first one, we must cast to an object, due two our List is of Integers, and the remove(index) uses an Integer index.

add(type, index)

  @Test
  public void add_elementToIndex_listChanged() {
    List list = new ArrayList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));
    /*List list = new LinkedList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));*/

    list.add(3, 9);

    assertThat(list).isEqualTo(
            Arrays.asList(1, 5, 5, 9, 9, 8, 10, 8));
  }

get(index)

  @Test
  public void get_elementFromIndex_true() {
    List list = new ArrayList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));
    /*List list = new LinkedList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));*/

    Integer elem = list.get(3);

    assertThat(elem).isEqualTo(9);
  }

remove(index)

  @Test
  public void remove_elementFromIndex_listChanged() {
    List list = new ArrayList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));
    /*List list = new LinkedList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));*/

    Integer elem = list.remove(3);

    assertThat(elem).isEqualTo(9);
    assertThat(list).isEqualTo(
            Arrays.asList(1, 5, 5, 8, 10, 8));
  }

sort(comparator)

  @Test
  public void sort_naturalOrder_listChanged() {
    List list = new ArrayList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));
    /*List list = new LinkedList(
            Arrays.asList(1, 5, 5, 9, 8, 10, 8));*/

    list.sort(Comparator.naturalOrder());

    assertThat(list).isEqualTo(
            Arrays.asList(1, 5, 5, 8, 8, 9, 10));
  }

Final Thought

We always need List in our projects, doesn’t matter if the project is huge or small. Understanding how the lists’ implementations work is pretty useful when you need to pay attention to performance or memory issues.

There is not a right or wrong list, there are only some advantages or disadvantages regarding different use cases.

In the following posts, we are going to talk about different uses cases and how an ArrayList and LinkedList behave.

If you liked this post and are interested in hearing more about my journey as a Software Engineer, you can follow me on Twitter and travel together.