Array based lists in Java (java.util.List)

March 31, 2020

by — Posted in Core Java

Hello! This post provides a comprehensive review of array-based lists in Java Collections Framework and presents important lists operations.

List as a data structure

Before we will progress to concrete list implementations, let take a moment and understand what is a list. From a technical point of view, list is finite sequence of elements, where each element has its own position. In computer science we distinguish array-based lists and linked lists. Only the first type is a topic for this post – we will not cover linked lists here.

An array-based list is called this way, because under the hood it stores elements in an array. We already talked about arrays, and determined that one of important features of arrays is a fixed size, however, when we use let say ArrayList we can add as many elements as we want. Here we need to take a closer look on two concepts – size and capacity. We can say, that:

  • Capacity = is the the total number of cells for data storage
  • Size = is the number of cells that have data

Technically, when size becomes equal to capacity, in order to add new elements, Java has to increase a capacity. It is performed via a mechanism called dynamic memory allocation, which reserve memory cells for prospective elements as needed.

Work with lists in Java

Array-based list implementation is defined in java.util.ArrayList class. Java defines it as a resizable-array list implementation. The capacity of array lists is grown automatically, and is always at least large as its size (e.g. number of elements).

It is important to note here, that while Java collections are basically mutable, there are two main ways to create ArrayList – one mutable and one immutable approach:

  • Using constructor, like List<Integer> numbers = new ArrayList<>(); – creates mutable lists
  • Using Arrays.asList() static method – creates immutable lists

Let now go through most important methods.

Add new elements

Advice

Code examples in this post use AssertJ library to write fluent assertions. You can learn more on how to utilize AssertJ with Java Collections in this tutorial

The first operation we will observe is an insertion of new elements. Array lists inherit from java.util.Collection interface two methods for adding elements (add(E e) and addAll(Collection c)), as well provides two list-specific methods to insert elements to the specified position. Let sum this methods:

  • add(E e) = the basic collection’s method, that inserts a new element to the end of the list
  • addAll(Collection c) = an another method from java.util.Collection that appends all elements of Collection c to the end of the list
  • add(int position, E e) = this method inserts a new element E to the specified position position. It shifts the element currently at that position and any subsequent elements to the right. Also, can throw IndexOutOfBoundsException in case the position value is higher than the size of list
  • addAll(int position, Collection c) = the operation which is similar to the previous one, but adds all elements from collection c starting from position position. Can throw IndexOutOfBoundsException with same conditions.

The code snippet below demonstrates how to insert elements to Java array-based lists:

@Test
public void addElementsToListTest () {
    // Approach 1. Create new list and use add() MUTABLE!
    List<Integer> numbers = new ArrayList<>();
    numbers.add(10);
    numbers.add(15);
    numbers.add(20);
    numbers.add(25);
    numbers.add(30);
    assertThat(numbers.add(66)).isTrue();

    //Approach 2. Use Arrays.asList. IMMUTABLE!
    List<String> names = Arrays.asList("Alejandra", "Beatriz", "Carmen", "Dolores", "Juanita");
    assertThatExceptionThrownBy(() -> names.add("Maria")).isInstanceOf(UnsupportedOperationException.class);
}

Remove elements

Deletion of elements is an another important thing we need to do on the day-to-day basis. There are two overloaded remove methods to delete elements from list:

  • remove(E e) = removes a single instance of the specified element e from the list (if that element is presented)
  • remove(int position) = remove an element in index position.

Take a look on the code snippet below:

@Test
public void removeElementFromListTest() {
    List<String> names = new ArrayList<>();
    names.add("Alejandra");
    names.add("Beatriz");
    names.add("Carmen");
    names.add("Dolores");
    names.add("Juanita");

    // Approach 1. Remove by INDEX
    assertThat(names.remove(1)).isEqualToIgnoringCase("Beatriz");

    // Approach 2. Remove ELEMENT
    assertThat(names.remove("Juanita")).isTrue();
}

Access an individual element

Like arrays, lists also allow to access the individual element with its index, which is in bounds [0; size - 1] using get() method:

@Test
public void accessElementTest() {
    List<Integer> numbers = Arrays.asList(1, 52, 12, 39, 45, 98, 100, 565, 6, 13);
    int beginning = numbers.get(0);
    int value = numbers.get(5);
    int end = numbers.get(numbers.size()-1);
    assertThat(beginning).isEqualTo(1);
    assertThat(value).isEqualTo(98);
    assertThat(end).isEqualTo(13);
}

Create sublists

Another valuable operation is a creation of sublists. Technically, sublist is a part of the original collection in a specific bounds.

In order to obtain a sublist, we use sublist(start, end) method, which returns a portion of the original list between start and end position (start is included, end is not included):

@Test
public void createSublistTest(){
    List<String> original = Arrays.asList("Alejandra", "Beatriz", "Carmen", "Dolores", "Juanita", "Katarina", "Maria");
    List<String> sublist = original.subList(0, 5);
    assertThat(sublist).contains("Juanita").doesNotContain("Katarina");
}

Search for elements

By searching we understand a getting of the element’s index. Arraylist has two ways to perform this operation:

  • indexOf(E e) = returns an index of the first occurance of e or -1 if nothing found
  • lastIndexOf(E e) = returns an index of the last occurance of e or -1 if nothing found

Take a look on this code snippet:

@Test
public void searchForElementTest(){
    List<Integer> numbers = Arrays.asList(1, 52, 12, 39, 45, 98, 100, 565, 6, 13);
    assertThat(numbers.indexOf(45)).isEqualTo(4);

    // using lastIndexOf
    List<Integer> numbers2 = Arrays.asList(1, 52, 12, 39, 45, 98, 100, 565, 45, 6, 13);
    assertThat(numbers2.lastIndexOf(45)).isEqualTo(8);
}

Filter lists

Advice

In this section I use Java streams. If you’re not familiar with them, feel free to check my guide on Java Streams API

When we filter a list, we basically create a new list, which contains elements that satisfy the necessary condition. Lists in Java itself don’t have a dedicated filter() method (like, for example, in JS), so for filtering we need to utilize streams. Here is an example of list filtering in Java:

@Test
public void filterListTest(){
    List<Integer> numbers = new ArrayList<>();
    numbers.add(45);
    numbers.add(12);
    numbers.add(80);
    numbers.add(77);
    numbers.add(95);
    numbers.add(4);

    List<Integer> evenNumbers = numbers.stream()
        .filter(number->number%2==0)
        .collect(Collectors.toList());

    assertThat(evenNumbers).hasSize(3);
}

Note, we create here a pipeline that consists of an intermediate operation filter and a terminate operation collect that gathers filtered elements to a new list.

Replace an element

Next, let observe how to replace (change) a specific element. Recall, that array lists store items in arrays, so by replacing we understand changing a value of the cell with concrete index. To do it we can use two approaches:

  • set(int position, E e) = it replaces the element at the specified position in this list with the value e
  • With static method Collections.replaceAll(collection, old, new) which accepts three arguments: a list itself, old value and a new element.

Take a look on the code snippet below:

@Test
public void replaceElementTest(){
    List<String> names = new ArrayList<>();
    names.add("Alejandra");
    names.add("Beatriz");
    names.add("Carmen");
    names.add("Dolores");
    names.add("Juanita");

    // Appraoch 1 By index
    names.set(1, "Maria");
    assertThat(names.get(1)).isEqualToIgnoringCase("Maria");

    // Approach 2 With Collections.replaceAll
    Collections.replaceAll(names, "Carmen", "Sofia");
    assertThat(names).containsExactly("Alejandra", "Maria", "Sofia", "Dolores", "Juanita");
}

Compare two lists

And finally let look on how to compare two Java array lists. Technically, as every Java object, lists overrides equals() method. The contract is following:

  1. Both objects are lists
  2. Both lists have same size
  3. Both lists contain same elements (e.g. equal) in same order

There is an another approach though. In case we want to check that lists contain same elements, but the order is different we can again use streams. Here is how to use both ways:

@Test
public void compareListsTest(){
    List<Integer> list1 = Arrays.asList(1, 52, 12, 39, 45, 98, 100, 565, 6, 13);
    List<Integer> list2 = Arrays.asList(1, 52, 12, 39, 45, 98, 100, 565, 6, 13);

    // Approach 1. with equals
    assertThat(list1).isEqualTo(list2);

    // Approach 2. with streams
    List<Integer> list3 = Arrays.asList(1, 12, 52, 39, 45, 100, 98, 6, 13, 565);
    assertThat(list1).isNotEqualTo(list3);

    // boolean allMatch = list3.stream().allMatch(number -> list1.contains(number));;
    assertThat(list3.stream().allMatch(number -> list1.contains(number))).isTrue();
}

Source code

You can find the full source code for this post in this github repository. If you have questions regarding this post, don’t hesitate to contact me. Have a nice day!