DEV Community: José Ramón (JR)

What's in a List

José Ramón (JR) — Thu, 17 Apr 2025 14:42:09 +0000

NOTE: Originally published on my blog ----> What's in a List

Introduction

List is an interface in Java Collections that represents an ordered sequence of elements.

Features of a List:

Access elements by position (index).
Store duplicate elements, because a Set does not store duplicates.
Insert or remove elements at any position.

This is the canonical definition of a List in Java.

The most common implementation

List being an interface, the most used implementation is the java.util.ArrayList class:

List<String> list = new ArrayList<>();
list.add("This");
list.add("is");
list.add("a");
list.add("list");

we can access elements by index:

String element = list.get(1);
System.out.println(element); // prints "is"

It is also possible to remove elements by index:

list.remove(2);
for (String element : list) {
    System.out.println(element);  // prints "This", "is", "list"
}

It is quite simple. It is like an array, but we do not have to worry about resizing it. The ArrayList class takes care of that.
The notation is also different. We use get() instead of [] to access elements by index.

List Methods

Most of the methods are self-explanatory. The main ones are:

add(): adds an element to the end of the list.
remove(): removes an element from the list.
get(): returns the element at the specified index.
size(): returns the number of elements in the list.
isEmpty(): returns true if the list is empty, false otherwise.
contains(): returns true if the list contains the specified element, false otherwise.
indexOf(): returns the index of the first occurrence of the specified element in the list, or -1 if the element is not found.
lastIndexOf(): returns the index of the last occurrence of the specified element in the list, or -1 if the element is not found.

Two methods are going to be explained, because they are a bit confusing.

add()

add() is an overloaded method. It has two versions:

list.add(element);
list.add(index, element);

The first version adds the element to the end of the list, while the second version adds the element at the specified index. The second one would have rather been called insertAt().

set()

set(int index, E element) replaces the element at the specified index with the given element. It return the element that was previously at the specified position.

The list must have an element at the specified index, otherwise it throws an exception.
It changes the element in place, so it does not change the size of the list.

The LinkedList class

Why not use the ArrayList implementation always?

The ArrayList class is a good choice for most cases, in fact most of the programmers have only used that class when creating a List.

But there is one thing that the ArrayList class does not do very well: inserting and removing elements in random list positions. Why? Because every time an element is inserted or removed, the remaining elements starting from the modified position have to be shifted, since all the array elements must be stored in contiguous memory.

As a consequence, an LinkedList should be faster than an ArrayList for adding or removing elements in the middle of the list.
Unless you have to use a cache memory, in which case you will prefer a list whose elements are contiguous in memory.

List<String> list = new LinkedList<>();
list.add("This");
list.add("is");
list.add("a");
list.add("list");

Since both classes implement the List interface, we can use them interchangeably.

Let's see how a simplified LinkedList looks like:

class LinkedList {
    private Node head = null;  // Start of the list
    private int size = 0;      // Number of nodes
    private int index = 0;
}

class Node {
    private String data;        // Element stored in this node
    private Node next = null;     // Link to the next node
    private Node previous = null; // Link to the previous node
}

As we can see, it is a doubly linked list. A node has three attributes: the data itself, and references to the next and previous nodes.

These nodes are not contiguous in memory. Therefore, when an element is inserted or removed, the remaining elements do not have to be shifted. A node has to modify only its two references, resulting in much faster operations.

+-------+ +-------+ +-------+
| 10 |-->--| 20 |-->--| 30 |
+-------+ +-------+ +-------+
Node A Node B Node C

After removing 20:

+-------+ +-------+
| 10 |-->--| 30 |
+-------+ +-------+
Node A Node C

ArrayList vs LinkedList

The ArrayList class is faster for adding and removing elements in the middle of the list, while the LinkedList class is faster for adding and removing elements at the beginning or end of the list.

Let's see an example for measuring the time it takes to add and remove elements in the middle of the list:

import java.util.List;
import java.util.ArrayList;
import java.util.LinkedList;

public class ListInsertionBenchmark {
    public static void main(String[] args) {
        final int ELEMENT_COUNT = 10_000; // Number of insertions to test

        // Test ArrayList
        List<Integer> arrayList = new ArrayList<>();
        long arrayListTime = timeInsertInMiddle(arrayList, ELEMENT_COUNT);

        // Test LinkedList
        List<Integer> linkedList = new LinkedList<>();
        long linkedListTime = timeInsertInMiddle(linkedList, ELEMENT_COUNT);

        System.out.println("\nResults:");
        System.out.printf("ArrayList insertion time: %d ms\n", arrayListTime);
        System.out.printf("LinkedList insertion time: %d ms\n", linkedListTime);
    }

    private static long timeInsertInMiddle(List<Integer> list, int insertions) {
        // Pre-fill the list to avoid starting empty
        for (int i = 0; i < 1_000_000; i++) {
            list.add(i);
        }

        long startTime = System.currentTimeMillis();
        for (int i = 0; i < insertions; i++) {
            int middleIndex = list.size() / 2;
            list.add(middleIndex, i); // Insert at middle
        }
        long endTime = System.currentTimeMillis();

        return endTime - startTime;
    }
}

If we run this program, it turns out that the LinkedList insertion time is much greater than the ArrayList one, although all the insertions are done in the middle of the list.

It seems that the time it takes to traverse the list from head/tail to reach a middle index is higher for the LinkedList.
This happens because the ArrayList data structure is optimized for shifting contiguous elements by using System.arraycopy(); whereas traversing all the nodes is slow because nodes are scattered in memory. Each pointer access can result in a memory cache miss, which makes the process even slower.
In other words, insertion in a LinkedList without an iterator is a O(n) operation.

System.arraycopy() copies memory blocks from one part of an array to another. It's a native method, that is, its core logic is implemented in a lower-level language like C (or C++) for performance reasons.
If a traditional loop were used to copy every single list element, the traversing time would be much higher.

ArrayList is faster due to contiguous memory and optimized block copying, not because it's a faster algorithm in terms of complexity.

The benchmark highlights that algorithmic complexity alone does not determine real-world performance. ArrayList’s optimized memory operations make it a strong contender even for middle insertions.
We should profile our specific use case to make the most informed decision.

The missing piece: ListIterator

We said

The LinkedList class is faster for adding and removing elements at the middle of the list.

but the results obtained in the benchmark did not match that statement.

We can use a ListIterator and move it to a position once and then do many insertions/removals at that spot. In this way, we don't need to traverse the list each time.

    public static void main(String[] args) {
        final int ELEMENT_COUNT_WITH_ITERATOR = 3000;

        long arrayListIteratorTime = timeInsertUsingAnIterator(arrayList, ELEMENT_COUNT_WITH_ITERATOR);

        long linkedListIteratorTime = timeInsertUsingAnIterator(linkedList, ELEMENT_COUNT_WITH_ITERATOR);
        // ArrayList vs LinkedList
        System.out.println("\nResults:");
        System.out.printf("ArrayList insertion time: %d ms\n", arrayListTime);
        System.out.printf("LinkedList insertion time: %d ms\n", linkedListTime);

        System.out.printf("ArrayList iterator insertion time: %d ms\n", arrayListIteratorTime);
        System.out.printf("LinkedList iterator insertion time: %d ms\n", linkedListIteratorTime);
    }

    private static long timeInsertUsingAnIterator(List<Integer> list, int insertions) {
        // Pre-fill the list to avoid starting empty
        for (int i = 0; i < 10_000; i++) {
            list.add(i);
        }

        long startTime = System.currentTimeMillis();
        ListIterator<Integer> iterator = list.listIterator(5000);
        for (int i = 0; i < insertions; i++) {
            iterator.add(i);
        }
        long endTime = System.currentTimeMillis();

        return endTime - startTime;
    }
}

The insertions time for the LinkedList is very close to zero, and it's much faster than the ones for the ArrayList.

Multiple insertion and removals are faster when using a LinkedList, provided an iterator at the correct position is used.
In these cases, insertion in a LinkedList is a O(1) operation.

A LinkedList is suitable for use cases where we need to add and remove elements at a known same position and we don't need to access elements by index often. Examples are undo/redo stacks and managing history.

LinkedList implements both the Queue and Deque interfaces, which means that it is a good choice for use cases where we need to add and remove elements from both ends of the list.

Conclusion

The Java List is an interface with methods for adding, removing, and accessing elements. It has two different implementations: ArrayList and LinkedList.

ArrayList offers excellent general-purpose performance, especially for random access and adding/removing at the end.
LinkedList provides faster insertion and deletion if an iterator at the correct position is used.
As always, the optimal choice depends on your application's specific needs and access patterns.

Java and Kotlin: A Practical comparison (part II)

José Ramón (JR) — Thu, 04 Jan 2024 01:26:26 +0000

Design Patterns

We will analyze how some design patterns are implemented in both languages.

1.- Optional Pattern

In Java, Optional doesn't solve the Null Pointer Exception or NPE problem. It just wraps it and "protects" our return values.

Optional<String> getCity(String user) {
  var city = getOptionalCity(user);
  if (city != null) 
    return Optional.of(city);
  else
    return Optional.empty();
}

Optional.ofNullable(null)
        .ifPresentOrElse(
                email -> System.out.println("Sending email to " + email),
                ()    -> System.out.println("Cannot send email"));

Optional is useful for returning types, but it should not be used on parameters or properties.

getPermissions(user, null);
getPermissions(user, Optional.empty());  // Not recommended

KOTLIN

Solution: Nullability is built into the type system. Kotlin embraces null.
String? and String are different types. T is a subtype of T?.

val myString: String = "hello"
val nullableString: String? = null   // correct!!

In Kotlin, all regular types are non-nullable by default unless you explicitly mark them as nullable. If you don't expect a function argument to be null, declare the function as follows:

fun stringLength(a: String) = a.length

The parameter a has the String type, which in Kotlin means it must always contain a String instance and it cannot contain null.
An attempt to pass a null value to the stringLength(a: String) function will result in a compile-time error.

This works for parameters, return types, properties and generics.

val list: List<String>
list.add(null)   // Compiler error

2.- Overloading Methods

void log(String msg) { ......... };
void log(String msg, String level) { ......... };
void log(String msg, String level, String ctx) { ......... };

KOTLIN

In kotlin we declare only one function, because we have default arguments and named arguments.

fun log(
    msg: String, 
    level: String = "INFO", 
    ctx: String = "main"
) { 
......... 
}

log(level="DEBUG", msg="trace B")

3.- Utility static methods

final class NumberUtils {
  public static boolean isEven(final int i) {
    return i % 2 == 0;
  }
}

In some projects we may end up declaring the same utility function more than once.

KOTLIN

fun Int.isEven() = this % 2 == 0  // Extension function

2.isEven()

4.- Factory

public class NotificationFactory {

  public static Notification createNotification(
        final NotificationType type
  ) {
      return switch(type) {
        case Email -> new EmailNotification();
        case SMS -> new SmsNotification();
      };
  }
}

KOTLIN

In Kotlin a function is used instead of an interface.

//  This would be a code smell in Java
fun Notification(type: NotificationType) = when(type) {
    NotificationType.Email -> EmailNotification()
    NotificationType.SMS -> SmsNotification()
  }
}

val notification = Notification(NotificationType.Email)

5.- Singleton

// Much code, it's not even thread-safe
public final class MySingleton {
    private static final MySingleton INSTANCE;

    private MySingleton() {}

    public static MySingleton getInstance() {
        if (INSTANCE == null) {
            INSTANCE = new MySingleton();
        }
        return INSTANCE;
    }
}

KOTLIN

This pattern is built into the Kotlin language. It's lazy and thread-safe.

object Singleton {
  val myProperty......
  fun myInstanceMethod() {
    ...............
  }
}

6.- Iterator

This can be applied only to collections, not to user defined classes.

List<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

var iterator = list.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);   // A, B, C
}

KOTLIN

val list = listOf("A", "B", "C")
for (elem in list) {
  println(elem)
}

This can be applied to any class that has the iterator operator function defined.

class School(
  val students: List<Student> = listOf(),
  val teachers: List<Teacher> = listOf()
)

operator fun School.iterator() = iterator<Person> {  // Extension function
  yieldAll(teachers)
  yieldAll(students)
}

val mySchool = School()
for (person in mySchool) {
  println(person)
}

Likewise, the operator function compareTo must be used to compare objects.

7.- Comparable

class School(val students: List<Student>, val teachers: List<Teacher>) 

override fun School.compareTo(other: School) =
    students.size.compareTo(other.students.size)

fun main() {
    val school1 = School(listOf(Student("John"), Student("Alice")), listOf(Teacher("Mr. Smith")))
    val school2 = School(listOf(Student("Bob"), Student("Eve"), Student("Carol")), listOf(Teacher("Mrs. Johnson")))

    if (school1 > school2) {
        println("$school1 has more students than $school1")
    }
}

8.- Strategy pattern

Implementation with interfaces

This is the classical approach, shown in Kotlin.

fun interface PaymentStrategy {
    fun charge(amount: BigDecimal) : PaymentState
}

Next, we implement the interface for all the different payment methods we want to support:

class CreditCardPaymentStrategy : PaymentStrategy {
    override fun charge(amount: BigDecimal) : PaymentState = PaymentState.PAID
}

class PayPalPaymentStrategy : PaymentStrategy {
    override fun charge(amount: BigDecimal) = PaymentState.PAID
}

This is the resulting class:

class ShoppingCart2(private val paymentStrategy: PaymentStrategy) {
    fun process(totalPrice: BigDecimal) = paymentStrategy.charge(totalPrice)
}

Implementation with Function Types

This implementation is easier to read than the previous one, but it's less reusable and less maintainable.

class ShoppingCart(private val paymentProcessor: (BigDecimal) -> PaymentState) {
    fun process(totalPrice: BigDecimal) = paymentProcessor(totalPrice)
}

typealias PaymentStrategy = (BigDecimal) -> PaymentState
class ShoppingCart(private val paymentProcessor: PaymentStrategy) {
    fun process(totalPrice: BigDecimal) = paymentProcessor(totalPrice)
}

This is how it's used:

val creditCardPaymentProcessor = { amount: BigDecimal -> ... }

val payPalPaymentProcessor = { amount: BigDecimal -> ... }

**JAVA

In Java, function types have a strange syntax.

interface PaymentProcessor {
    public Function<BigDecimal, PaymentState> process;
};

This is how it's used:

class creditCardPaymentProcessor implements PaymentProcessor {
    @Override
    public Function<BigDecimal, PaymentState> process = .....;
};

It's quite annoying having to create a class per strategy.

Java and Kotlin: A Practical comparison (part I)

José Ramón (JR) — Sat, 25 Nov 2023 22:57:35 +0000

Brief History of Kotlin

Kotlin was developed by JetBrains in 2010 and released in 2016. JetBrains open-sourced the project under the Apache 2 license in 2012, and Kotlin v1.0 was released on 2016.
The company behind IntelliJ IDEA, needed a language that was concise, elegant, expressive, and interoperable with Java, as most of their products were developed in Java. They aimed to reduce the amount of boilerplate code. As a result, although Kotlin is less powerful than Scala, it is much simpler and more importantly, communicates easily with Java code.
Spring Framework 5.0 introduced dedicated Kotlin support and it is the recommended language for Android development since 2017.

Language Philosophy

Purely Object-oriented with functions as first class citizens.
Safety through null-types and immutability.
Extensibility through extension functions.
Good tooling support.

It allows a gradual migration from Java. That does not happen with Scala.

Object Orientation

Java code

public class Person {

    private final String name;
    private int age;

    // Constructor with name and age
    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

    // Constructor with name only
    public Person(String name) {
        this(name, 0); // Default age is 0
    }

    public void plus(int lifetime) {
        this.age += lifetime;
    }

    // Getters
    public String getName() {
        return name;
    }

    public int getAge() {
        return age;
    }

    // Factory method
    static Person newBorn(String name) {
        return new Person(name);
    }
}

Kotlin code

data class Person(val name: String,
             var age: Int = 0) {

    companion object {       // Factory method
        fun newBorn(name: String) = Person(name)
    }
}

Default arguments allow to have only one constructor in Kotlin.
Kotlin has no primitives. Everything is an Object.
Every Kotlin method has a return type, which can be inferred. If the method is void, the return type is Unit. This is taken from Scala.
An object in Kotlin is a singleton. The functions defined inside are equivalent to static Java methods.
A data class generates the corresponding getters (and setters for mutable fields), as well as the hashCode, toString and equals methods. Also a copy method.
This is taken from case class in Scala.

val alice = Person("Alice", 42)

alice == Person("Alice", 42)  // Equality by value, not by reference
res1: true

This copy method is not generated by the Lombok annotations.
Named arguments allows to use any parameters order

val john = alice.copy(name = "John")

Destructuring, like in Javascript and in Python

val (name, age) = alice

A record class, introduced in the latest Java versions, generates most of the methods shown above. The final code is almost equivalent to that obtained with Lombok annotations.

Java 14 and higher

public record Person(String name, int age) {

    public Person(String name) {
        this(name, 0); // Default age is 0
    }

    static Person newBorn(String name, int age) {
        return new Person(name, age);
    }
}

final var alice = new Person("Alice", 42)
alice == new Person("Alice", 42)  

// copy() does not exist

// destructuring does not exist either

// The new keyword is required.
// The semicolons are required.

NOTE: this article is the first one of a long series comparing Java and Kotlin. Please stay tuned for the next part.
I will try to post once a week.