ArrayList vs. LinkedList for Kotlin data structure

Kotlin provides several data collection implementations. Also, thanks to its interoperability with the JVM, you can choose between the many Java collections. Adopting the correct data collection can make all the difference when it comes to performance and resource usage.

This is why you should know the characteristics of each of the most popular data collections offered by the programming language you are using. In detail, ArrayList and LinkedList represent two of the most widely adopted JVM data collection structures.

Here, you will learn how they are implemented behind the scenes in Kotlin, how they work, and what performance benefits they offer. In particular, by the end of this article, you will be able to easily tell when and why it is better to adopt an ArrayList over a LinkedList or vice versa.

Let’s dig into ArrayList and LinkedList in Kotlin!

TL;DR: In this post, you’ll find out everything you need to know about ArrayList and LinkedList to learn how to choose the right data collection structure between the two.

• What is an ArrayList in Kotlin?
• What is a LinkedList?
• Why Kotlin does not provide a LinkedList implementation
• When to use an ArrayList over a LinkedList
• When to use a LinkedList over an ArrayList

What is an ArrayList in Kotlin?

In Kotlin, an ArrayList provides a MutableList implementation that uses an array as backing storage. Specifically, when an element is added to an ArrayList, it is inserted into the array. What happens behind the scene is that a new, larger array is created and replaces the old one, which is removed. In other words, an ArrayList allows you to create a dynamic array whose size can be incremented or decremented.

ArrayList is a nonsynchronized data collection, which means it is not thread-safe. Also, an ArrayList can contain duplicated elements and provides read and write functionality. Note that you can specify the type of elements that the list can contain through a generic.

In detail, the most important methods and properties offered by the ArrayList class are:

• add(): adds a new element to the list

  // initializing an empty ArrayList
  var list = ArrayList<Int>()
  // adding 1 to the list
  list.add(1)
  // adding 2 to the list
  list.add(2)
  println(list) // [1, 2]
  
  // adding 3 in position 1
  list.add(1, 3)
  println(list) // [1, 3, 2]

• addAll(): adds all the elements of a specified collection to the current list

  var list = ArrayList<Int>()
  // adding 1, 2, 3 to the list
  list.addAll(listOf(1, 2, 3))
  println(list) // [1, 2, 3]

• get(): returns the element at the specified index or an IndexOutOfBoundsException

  var list = ArrayList<Int>()
  list.addAll(listOf(1, 2, 3))
  // getting the element of index 1
  println(list.get(1)) // 2

• set(): replaces the element in the specified position with the element passed as a parameter in the list

  var list = ArrayList<Int>()
  list.addAll(listOf(1, 2, 3))
  // setting 4 in position 1
  list.set(1, 4)
  println(list) // [1, 4, 3]

• indexOf(): returns the index of the first occurrence of the specified element in the list, or -1 if the element is not present

  var list = ArrayList<Int>()
  list.addAll(listOf(1, 2, 3))
  println(list.indexOf(1)) // 0
  println(list.indexOf(4)) // -1

• remove(): removes the first occurrence of the specific element in the list

  var list = ArrayList<Int>()
  list.addAll(listOf(1, 2, 3))
  // removing the element 2 from the list
  list.remove(2)
  println(list) // [1, 3]

• removeAt(): removes the element at the specified index in the list

  var list = ArrayList<Int>()
  list.addAll(listOf(1, 2, 3))
  // removing the element of index 0 from the list
  list.removeAt(0)
  println(list) // [2, 3]

• clear(): removes all the elements in the list

  var list = ArrayList<Int>()
  list.addAll(listOf(1, 2, 3))
  // clearing the list
  list.clear()
  println(list) // []

• size: returns the size of the list

  var list = ArrayList<Int>()
  // adding 1, 2, 3 to the list
  list.addAll(listOf(1, 2, 3))
  println(list.size) // 3

Also, you can initialize an ArrayList by passing a collection of elements to its constructor:

// initializing an ArrayList with the [1, 2, 3] list
val list2 = ArrayList<Int>(listOf(1,2,3))
println(list2)

This snippet would print:

[1, 2, 3]

Otherwise, you can write the arrayListOf() Kotlin function to directly get a new ArrayList from a given list of elements:

// getting an ArrayList from the [1, 2, 3] list
val list = arrayListOf(1, 2, 3)
// printing the Class name of list
println(list::class.simpleName) 
println(list)

This would return:

ArrayList
[1, 2, 3]

Note that in this case, you do not have to explicitly specify the generic type of the ArrayList. This will be inferred automatically from the types of the elements passed as a parameter in arrayListOf().

What is a LinkedList?

Kotlin does not provide a LinkedList implementation. However, you can still use LinkedList because of the Kotlin JVM interoperability with Java. This is because LinkedList is a data collection that is part of the JVM implementation. So, let’s understand what a LinkedList is.

In Java, a LinkedList provides a nonsynchronized data collection structure that is based on pointers. A LinkedList does not use an array as backing storage. This means that all its elements are not stored in a contiguous location. Specifically, a LinkedList is a doubly linked list whose elements are linked with a pair of pointers as below:

In detail, a LinkedList stores its elements in nodes. Each node has a pointer to the previous node and one to the next node in the list. To add an element to the list, the element is placed into a new node, which is then linked to the two adjacent elements in the list. You can declare the type of node elements through a generic.

The LinkedList class has the same methods as the ArrayList class because they both implement the List interface. However, the LinkedList class also implements the Deque interface, which provides the following methods:

• getFirst(): returns the element at the beginning of the list
• getLast(): returns the element at the end of the list
• addFirst(): adds an element at the beginning of the list
• addLast(): adds an element at the end of the list
• removeFirst(): removes the element at the beginning of the list
• removeLast(): removes the element at the end of the list

Why Kotlin does not provide a LinkedList implementation

It seems that Kotlin developers decided not to implement LinkedList because the Java implementation of LinkedList is suboptimal in nearly all cases. Also, considering that originally there was only Kotlin JVM, the Kotlin developers preferred to rely on the Java implementation.

Plus, as you are about to learn, LinkedList gets outperformed by ArrayList in nearly every situation. So, they may have thought there is no real need for a Kotlin implementation of LinkedList.

When to use an ArrayList over a LinkedList

ArrayList is the more efficient solution when it comes to random read access. This is because you can grab any element in constant time. That happens since there is an array behind the scenes. So, the get() method simply has to return the element specified by the index passed as a parameter. On the contrary, a LinkedList only provides sequential access, which is more expensive in terms of performance.

Plus, the ArrayList data structure does not involve overhead. On the contrary, a LinkedList defines two pointers for each element. Therefore, a LinkedList will occupy more elements than an ArrayList. This may easily become a problem when dealing with large lists.

Also, considering that an ArrayList is based on an array, the elements are stored sequentially in memory. So, ArrayLists can also take advantage of the principle of locality. This makes ArrayList more cache-friendly than LinkedList, whose elements are spread all over the RAM.

Thus, with ArrayLists you can experience an additional performance boost when nearby elements are accessed in a short time.

In detail, for an ArrayList<E>:

• get(index : Int) is O(1)
• add(element : E) is O(1) amortized, but O(n) when the underlying array has to be resized
• add(index: Int, element : E) is O(n)
• remove(index : Int) is O(n)
• remove() on the corresponding MutableListIterator object is O(n)
• add(element : E) on the corresponding MutableListIterator object is O(n)

Note the O(1) complexity on the get() method. This is the main benefit of ArrayList over LinkedList. Also, do not forget that you can get the MutableListIterator object from an ArrayList by calling the listIterator() method.

When to use a LinkedList over an ArrayList

LinkedList allows constant-time insertions or removals when inserting an element at the beginning or end of the list. This is true also when the current node is known. In other words, when using a LinkedList with an iterator, you can insert an element in O(1). This is the main benefit of LinkedList over an ArrayList.

Also, when using a LinkedList, you can insert elements indefinitely. On the other hand, the array used by an ArrayList will eventually need to be resized. This is an expensive operation that can be avoided in LinkedList. Plus, considering that this operation may not be executed every time a write operation is performed over the ArrayList, the underlying array may become wastefully empty. In this particular scenario, an ArrayList may have more allocated memory than a LinkedList.

In all other scenarios, LinkedList is worse or equal to ArrayList. Specifically, for a LinkedList<E>

• get(index : Int) is O(n)
• getFirst() and getLast() are O(1)
• add(index : Int, element : E) is O(n)
• addFirst(element : E) and addLast(element : E) are O(1)
• remove(index : Int) is O(n)
• removeFirst() and removeLast() are O(n)
• remove() on the corresponding ListIterator object is O(1)
• add(element : E) on the corresponding ListIterator object is O(1)

Just as it happens for ArrayList, you can get a ListIterator object by calling the iteratorList() method.

Conclusion

In this article, you looked at the main differences between ArrayList and LinkedList in Kotlin. As shown, Kotlin offers an inbuilt implementation for ArrayList, while it relies on the Java LinkedList implementation.

Although they offer similar functionality, ArrayList is generally preferred over LinkedList. Kotlin developers tend to opt for ArrayList because of several reasons, and here you learned why this happens.

In detail, you had a look at what ArrayList and LinkedList are and dig into how the two data collection structures behave in terms of performance and memory usage under different worst-case scenarios.

Thanks for reading! I hope that you found this article helpful. Feel free to reach out to me with any questions, comments, or suggestions.