Skip to content

Lists in Java and Vavr

Hi again! Without any doubs, lists are most popular data structure among Java developers. Last year I did a series of posts devoted to Java collections as well to their Vavr counterparts. The only missed thing was a post about lists. This article should change it.

As it was with arrays, maps, sets and queues before, we will start from a theoretical overview of [array-based] lists and then go through most important methods. Next, we will compare Java array lists with immutable Vavr lists.

Table of contents

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. Take a look on the graph below:

Image 1. Array-based list

Here we have a list of numbers with capacity of 4 and size of 3. Therefore 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 allocates memory cells for prospective elements as needed.

Java Collection Framework supplies array-based lists as its part. Lists in Java inherit java.util.List interface. Another – immutable – alternative to built-in Java collections is Vavr library and Vavr Lists, which we also will observe in this post.

Lists in Java Collections Framework

As it was mentioned before, Java lists implement java.util.List as well have all core collection methods. 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:

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

Let now go through most important methods.

Add new elements

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:

  1. add(E e) = the basic collection’s method, that inserts a new element to the end of the list
  2. addAll(Collection c) = an another method from java.util.Collection that appends all elements of Collection c to the end of the list
  3. 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
  4. 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 () {
    List<Integer> numbers = new ArrayList<>();
    numbers.add(10);
    numbers.add(15);
    numbers.add(20);
    numbers.add(25);
    numbers.add(30);
    assertEquals(5, numbers.size());
}

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 ArrayList:

  • 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.

This is a very important to learn, as it is very common questions in interviews and Oracle Java certifications. For example, you have a list of numbers:

List<Integer> numbers = new ArrayList<>();
numbers.add(12);
numbers.add(2);
numbers.add(3);
numbers.add(51);
numbers.remove(2);

When you run this code, you will see that Java removed element with index 2, e.g. 3. To delete element 2 we need to explicitly provide an Integer:

numbers.remove(Integer.valueOf(2));

The code snippet below demonstates a deletion of elements from lists:

@Test
public void removeElementFromListTest() {
    List<String> names = new ArrayList<>();
    names.add("Agata");
    names.add("Emma");
    names.add("Daniela");
    names.add("Katarina");
    names.add("Zsuzsi");

    assertEquals(5, names.size());

    // Approach 1. Remove by INDEX
    names.remove(1); // Emma
    assertFalse(names.contains("Emma"));
    assertEquals(4, names.size());

    // Approach 2. Remove ELEMENT
    names.remove("Daniela");
    assertFalse(names.contains("Daniela"));
    assertEquals(3, names.size());
}

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:

int element = numbers.get(3);

Create sublists

Another valuable operation is a creation of sublists. Technically, sublist is a part of the original collection in a specific bounds (this operation is sometimes called slicing in some programming languages, as well in Vavr as we will see later).

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("Agata", "Emma", "Daniela", "Katarina", "Zsuzsi");
    List<String> sublist = original.subList(0, 4);
    assertTrue(sublist.contains("Katarina"));
    assertFalse(sublist.contains("Zsuzsi"));
}

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);

    // using indexOf
    int positionOf45 = numbers.indexOf(45);
    assertEquals(4, positionOf45);

    // using lastIndexOf
    List<Integer> numbers2 = Arrays.asList(1, 52, 12, 39, 45, 98, 100, 565, 45, 6, 13);
    // we have 2x 45
    int positionLast = numbers2.lastIndexOf(45);
    assertEquals(8, positionLast);
}

Filter lists

When we filter a list, we basically create a new list, which contains elements that satisfy some condition (predicate). Lists itself don’t have a filter() method (like in JS), so for this 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());

    assertEquals(3, evenNumbers.size());
}

Note, we create here a pipeline that consits of an intermediate operation filter and a terminate operation collect that gathers filtered elements to a new list. I recommend you to check my post on streams, if you’re not familiar with them.

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("Agata");
    names.add("Emma");
    names.add("Daniela");
    names.add("Katarina");
    names.add("Zsuzsi");

    // Appraoch 1 By index

    assertEquals("Emma", names.get(1));
    names.set(1, "Eva");
    assertEquals("Eva", names.get(1));

    // Approach 2 With Collections.replaceAll

    assertEquals("Daniela", names.get(2));
    Collections.replaceAll(names, "Daniela", "Darina");
    assertEquals("Darina", names.get(2));
}

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
    boolean areEqual = list1.equals(list2);
    assertTrue(areEqual);

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

    // list3 has same selements in the different order
    boolean areEqual2 = list1.equals(list3);
    assertFalse(areEqual2);

    boolean allMatch = list3.stream().allMatch(number -> list1.contains(number));
    assertTrue(allMatch);
}

Lists in Vavr

Vavr provides lists as a io.vavr.collection.List interface. It defines list as a immutable List is an eager sequence of elements. From a technical point of view, list in Vavr consists of head element and tail list. As well arrays, lists also inherit Seq. Take a look on the place of lists among Vavr data structures:

Image 2. Vavr lists place in Vavr collections hierarchy

NB that Vavr data structures are immutable, so all list manipulations return a new list, while the old one is not modified

Add new elements

The first operation we will do with Vavr lists is an insertion. You remember, that Vavr lists are immutable, so the original collection would not be modified. Opposite, as a result is returned a new list that contains the appended element. To add new element we use append(E e) method:

@Test
public void addElementsToListTest(){
    List<String> names = List.of("Adriana", "Darina", "Maria", "Karla", "Zuzana", "Yeliz");

        // Vavr collections are IMMUTABLE
        // adding of new name DOES NOT modify original collection

    List<String> result = names.append("Stela");
    assertFalse(names.contains("Stela"));
    assertEquals(names.size() + 1, result.size());
}

Remove elements

Like with insertion, deletion does not change the original list. There are two approaches to remove an element:

  • By its index using removeAt(int index)
  • Using remove(E e)

Take a look on the code snippet below:

@Test
public void removeElementFromListTest(){
    List<String> names = List.of("Adriana", "Darina", "Maria", "Karla", "Zuzana", "Yeliz");

    List<String> results = names.remove("Darina");
    assertEquals(names.size() - 1, results.size());

    List<String> results2 = names.removeAt(3);
    assertFalse(results2.contains("Karla"));
}

Access an individual element

Similar to Java array lists, Vavr supports an index-based access. You can use get(int index) method to do it:

String name = names.get(2);
assertEquals("Maria", name);

Create sublists

To create a sublist (a part of the original list) we use slice(start, end) method. Like in Java, the end index is not included, so we can say it is range = [start; end). This code demonstrates how to create sublists in Vavr:

@Test
public void createSublistTest(){
    List<Integer> original = List.of(54, 12, 29, 13, 95, 65, 285, 90, 5431);
    List<Integer> sublist = original.slice(0, 5); // end index not inlcuded

    assertFalse(sublist.contains(65));
    assertTrue(sublist.contains(12));
}

To obtain an index (position) of the specific element, we generally use indexOf method. It works in a same way as in Java. BUT as Vavr collections are heavily incorporated with streams we can use more functionality:

  • indexOfOption(E e) = returns an index of the first occurance as Vavr Option, e.g. Option<Integer>
  • lastIndexOfOption(E e) = returns an index of the last occurance as Vavr Option

Take a look on the code snippet below:

@Test
public void searchForElementTest(){
    List<String> names = List.of("Adriana", "Darina", "Maria", "Karla", "Zuzana", "Yeliz");
    int position = names.indexOf("Maria");
    Option<Integer> positionOption = names.indexOfOption("Karla");
    assertEquals(2, position);
    assertTrue(positionOption.isDefined());
}

Filter lists

Unlike “vanila” Java where we have to use streams, Vavr provides a built-in filter method. Likewise, it accepts as an argument a predicate, e.g. a logical condition and returns a new list with elements that satisfy this condition:

@Test
public void filterListTest(){
    List<Integer> numbers = List.of(12, 33, 65, 19, 72, 14, 2, 99, 40, 30, 27);
    List<Integer> evenNumbers = numbers.filter(number -> number%2==0);
    assertEquals(6, evenNumbers.size());
}

Replace an element

To change a value of an element, we use in Vavr replace(old, new) method, that accepts an old value and a new value. Take a look on the following example below:

@Test
public void replaceElementTest(){
    List<String> names = List.of("Adriana", "Darina", "Maria", "Karla", "Zuzana", "Yeliz");
    List<String> results = names.replace("Darina", "Denisa");
    assertFalse(results.contains("Darina"));
}

Compare two lists

Vavr lists uses equals() method to do comparison of two collections. The contract is similar to the Java one:

  1. Both collections are lists
  2. Both lists have contain same elements
  3. Order is same

NB, that this implementation comes from Traversable and idea is same for all Vavr collection (although, the order is considered for Seq only).

@Test
public void compareListsTest(){
    List<Integer> numbers1 = List.of(12, 33, 65, 19, 72, 14, 2, 99, 40, 30, 27);
    List<Integer> numbers2 = List.of(12, 33, 65, 19, 72, 14, 2, 99, 40, 30, 27);

    boolean areEqual = numbers1.equals(numbers2);
    assertTrue(areEqual);
}

Conclusion

Wow! Such a long post! Here we observed lists – most popular data structures in Java. We started with some theory on array-based lists, and then moved to concrete java.util.ArrayList implementation and supported operations. Next, we also compared it with immutable Vavr lists. By the way, the source code for this series is at your disposal on my github

References

  • Lars Vogel How to implement an ArrayList structure in Java (2019) Vogella, read here
  • Mincong Huang Vavr List vs Java List (2019) read here
  • Sedgewick Robert and Wayne Kevin. Introduction to Programming in Java: An Interdisciplinary Approach 2nd edn. Addison-Wesley Professional. 2017
Copy link
Powered by Social Snap