Data Structures in Kotlin: List — [PartII]

As mentioned in the previous article, we will continue our series on data structures. In this article, our focus will be on the list data structure. We will explore both array-based lists and linked lists. These two variations of lists offer different characteristics and benefits.

Let’s now delve into the world of lists and explore their inner workings and advantages.

What is a List?

A list is a data structure that represents an ordered collection of elements. It allows you to store and organize multiple items of the same or different types. The list maintains the order in which the elements are added, which means that each element has a specific position or index within the list.

In programming languages, there are different implementations of lists, which can be broadly categorized into two main types: array-based lists and linked lists. These implementations have their own unique characteristics and performance trade-offs, but at their core, they all represent the fundamental concept of a list — an ordered collection of elements.

Array-based lists vs Linked Lists

Array-based lists, such as ArrayList in Kotlin, utilize arrays as the underlying data structure to store and manage elements. They offer fast access to elements by index, making it efficient to retrieve elements at specific positions. Array-based lists have a fixed size once created but can automatically resize themselves when needed. However, inserting or removing elements in the middle of the list may require shifting subsequent elements, which can be less efficient.

On the other hand, linked lists, such as LinkedList, are built using nodes that contain both data and references to the next node in the list. Linked lists excel at inserting and removing elements at any position. This is because these operations involve updating only a few pointers, rather than shifting a large number of elements as in array-based lists. However, accessing elements by index in a linked list is slower since it requires traversing the list from the beginning or end.

Let’s delve deeper into each of these structures.

What is a array-based lists?

Imagine you have a to-do list for your day, where each item on the list represents a task or activity that needs to be completed. This to-do list can be seen as an example of an array-based list.

In this case, the order of the tasks is important because you want to complete them in a specific sequence. Just like in an array-based list, the tasks are stored in a particular order, starting from the first task, then moving on to the second task, and so on.

For example, let’s consider the following to-do list:

1. Walk the dog
2. Finish the project
3. Buy groceries
4. Watch a movie

In this array-based list, each task is associated with an index. The first task, “Walk the dog,” is at index 0, the second task, “Finish the project,” is at index 1, and so on. This allows you to access each task directly by its index, similar to accessing elements in an array.

You can perform various operations on the array-based list, such as adding new tasks at specific positions, modifying existing tasks, or removing tasks. For example, if you complete the first task, you can remove it from the list, causing the remaining tasks to shift up in the order.

In programming, array-based lists are implemented using arrays as the underlying data structure. These lists provide fast access to elements by index, making it efficient to retrieve elements at specific positions.

Characteristics

Let’s explore some characteristics of an array-based list:

• Ordered Collection: A List is an ordered collection of elements, meaning that the elements are stored in a specific sequence or order.
• Index-Based Access: Elements in a List can be accessed using their index positions. The index of the first element is 0, the second element is 1, and so on.
• Duplicate Elements: A List allows duplicate elements, meaning that you can have multiple elements with the same value in the List.
• Dynamic Resizing: Unlike an array with a fixed size, array-based lists automatically resize themselves as elements are added or removed. This means that the list can grow or shrink dynamically based on the number of elements it holds. The resizing process ensures that the list can accommodate new elements without exceeding its capacity.
• Common Operations: A List provides common operations such as adding elements, removing elements, accessing elements by index, getting the size of the List, checking if it contains a specific element, and iterating over the elements.
• Strong Typing: Array-based lists enforce strong typing, which means that you can only store elements of a specific type in the list. This helps maintain data integrity and provides compile-time type checking.

Performance considerations

• 🚀 Efficient Random Access: Array-based provides efficient random access to elements using index-based access. The time complexity for accessing an element by index is constant-time (O(1)). This makes it a good choice for scenarios where frequent random access to elements is required.
• 🚀 Efficient Iteration: Array-based lists provide efficient iteration over elements using loops or other iteration mechanisms. You can easily traverse the list and perform operations on each element sequentially.
• 🚀 Fixed Memory Allocation: Array-based lists allocate contiguous memory blocks to store elements. This memory allocation is done upfront and remains fixed throughout the lifetime of the list. It allows for efficient memory management and access to elements based on their indices.
• 🚀 Insertion and Removal Efficiency: Adding or removing elements at the end of an array-based list is generally efficient. When you add or remove elements at the end of the list, it does not require shifting existing elements. This means the operation can be done in constant time (O(1)), providing fast and efficient performance. It is especially useful when you frequently add or remove elements at the end of the list, as it allows for quick updates without affecting other elements.
• 🔻 Insertion and Removal Efficiency: When you insert or remove an element in the middle, it may involve shifting subsequent elements to accommodate the change. This shifting operation requires updating the indices and moving the elements in memory, resulting in a slower and less efficient operation. The time complexity of these operations becomes O(n), where n is the number of elements in the list. This can have an impact on performance, especially for larger lists, as the time taken is proportional to the number of elements that need to be shifted.

What is a linked list?

Imagine a playlist of songs that you enjoy listening to. After one song finishes playing, the next song in the list begins. But how does the playlist know which song comes next? It’s as if each song has a “link” to the next one.

That’s essentially how a linked list operates. In the case of our playlist example, the playlist itself serves as the linked list, while each song in the playlist is represented by an individual node.

A node consists of two main parts: the data or information of the item, and a reference or link to the next item in the list.

In the context of the playlist example, think of each node as a container that holds a song and a reference to the next song in the playlist. The song itself represents the data stored within the node, while the reference points to the next node, indicating the next song in the playlist.

The linked list is formed by connecting these nodes, with the last node pointing to null to indicate the end of the sequence.

This arrangement allows for the sequential organization of songs in the playlist. To navigate through the playlist, you start at the head of the linked list, which points to the first song. From there, you can follow the references from one song to the next, playing the songs in the order they appear.

When adding or removing elements in a linked list, the nodes are adjusted as necessary. Let’s take an example where we have a linked list with three nodes and we want to add a new element after the first node.

To achieve this, we would create a new node with the desired value (let’s say 15). Then, the reference of the previous node would be updated to point to the new node. Additionally, the new node would be set to point to the node that was originally after the first node.

As a result, adding or removing an element in a linked list does not require reallocation or shifting of all the elements, as it would in a fixed-size array. Instead, the references of the surrounding nodes are adjusted to include or exclude the new node or the removed node. This dynamic adjustment of references allows for efficient insertion and removal operations in a linked list.

Remember that the index of the first element in a linked list is 0, the second element is 1, and so on. Make sure to provide a valid index to avoid IndexOutOfBoundsException.

Characteristics

• Dynamic Size: Linked lists can dynamically adjust their size to accommodate the addition or removal of elements. This makes them suitable for scenarios where the number of elements may change frequently.
• Flexible Structure: Linked lists can be easily modified and reorganized by rearranging the references between nodes. This flexibility allows for efficient operations like splitting or merging lists.
• No Contiguous Memory: Unlike array-based lists, linked lists do not require contiguous memory locations. Nodes can be scattered in different memory locations, connected through their references.
• Dynamic Sorting: Linked lists can be sorted dynamically by rearranging the order of nodes based on specific criteria. This allows for efficient sorting algorithms that take advantage of the linking structure.

Performance considerations

• 🚀 Sequential Access: Linked lists excel at sequential access, allowing easy iteration through each element by following the references from one node to the next.
• 🚀 Efficient Insertion and Removal: Adding or removing an element in a linked list involves adjusting the references of neighboring nodes, rather than shifting all elements like in an array-based list. This makes insertion and removal operations efficient, especially for large lists or frequent modifications.
• 🔻 Limited Random Access: Linked lists require sequential traversal to access an item, which can be less efficient compared to array-based lists. The time it takes to access an item in a linked list is proportional to the size of the list (O(n)), where “n” is the number of elements. Due to the traversal required, linked lists perform worse than arrays for random access.
• 🔻 Slower for Middle Insertion/Removal: Linked lists excel at adding and removing elements at the beginning or end of the list. These operations only require updating adjacent nodes, making them efficient and fast. However, if you need to insert or remove an element in the middle of the list, the linked list requires traversing the list to locate the specific item before performing the operation. This additional traversal can be time-consuming, especially for large lists, and may result in slower performance.
• 🔻 Memory Usage: Linked lists use memory to store the nodes and their references, resulting in slightly higher memory usage compared to array-based lists. Each node requires additional memory overhead for storing the references.

In addition to the basic singly-linked list that we’ve discussed so far, there are other variations of linked lists that offer different functionality and features. Let’s explore two common variations:

• Doubly Linked List: This is an extended version of the singly linked list. In addition to the reference to the next node, each node also holds a reference to the previous node. This allows for more convenient traversal in both directions, making it easier to iterate through the list in reverse or insert/remove nodes at any position. However, it requires slightly more memory due to the extra reference.
• Circular Linked List: In a circular linked list, the last node connects back to the first node, forming a circular structure. This allows for seamless traversal from the last node to the first node and vice versa. It can be useful in scenarios where cyclic behavior is desired, like implementing circular buffers or circular data structures.

Usage in Kotlin

Now that we have a solid understanding of these data structures, let’s explore their practical application in Kotlin. In Kotlin, there is a hierarchy of interfaces that define various aspects of lists. These interfaces provide different functionalities and behaviors, allowing us to work with lists in a flexible and efficient manner.

Let’s analyze the hierarchy represented in the image below.

• Collection Interface: Highest-level hierarchy that defines common basic operations for all collections. It includes operations such as adding, removing, and accessing elements.
• List Interface: A interface List extends the interface Collection. It includes specific operations for lists, such as accessing elements by index and obtaining the size of the list. To create a list based on this interface, you can use listOf() to create an immutable list.

// Creates an immutable List with the specified elements ("apple", "banana", "orange")
val fruits = listOf("apple", "banana", "orange")

• MutableList Interface: The MutableList interface extends the List interface. It allows modification of the elements in the list by adding operations for adding, removing, and modifying elements. To create an mutable list, you can use the mutableListOf() function.

// Creates a mutable list with the specified elements ("red", "green", "blue")
val colors = mutableListOf("red", "green", "blue")

• Specific List Implementations: Finally, ArrayList and LinkedList are specific implementations of the MutableList interface and List, respectively. These classes are used to create the data structures we’ve discussed in this article. ArrayList provides array-based list functionality, while LinkedList utilizes a linked list structure. In Kotlin, there isn’t a specialized class to use the LinkedList structure, but we can use Java’s LinkedList from the collections library due to interoperability.

ArrayList

To implement an array-based list in Kotlin, you can use the ArrayList class. Although it is provided by Kotlin, the ArrayList class is actually a typealias for the Java ArrayList class. Kotlin aliases the Java ArrayList class to provide a seamless integration and make it easier for Kotlin developers to use this specific implementation of a list. This allows you to utilize the array-based list functionality provided by the Java ArrayList class directly in your Kotlin code.

To create an ArrayList, you can use the arrayListOf() function. Let’s take a look at an example:

// Creates an ArrayList and adds the specified elements (1, 2, 3, 4, 5) to it
val numbers = arrayListOf(1, 2, 3, 4, 5)

When comparing mutableListOf() and arrayListOf(), both create an instance of ArrayList. However, the difference lies in their return types: arrayListOf() directly returns an ArrayList, while mutableListOf() returns a MutableList implemented by ArrayList. As a result, arrayListOf()offers additional methods like trimToSize()and ensureCapacity()that are not available in the MutableList interface.

In practice, it is generally recommended to use mutableListOf() if you only need to work with the common behavior defined by the MutableList interface. This approach allows for flexibility and follows the principle of programming against interfaces. On the other hand, if you have a specific requirement to manipulate the underlying structure of the list or need access to the additional methods provided by ArrayList, you can use arrayListOf().

LinkedList

In Kotlin, we can use the LinkedList class provided by the Java library to represent a linked list. The LinkedList implementation in Java is a doubly-linked list, meaning that each node in the list has references to both the previous and next nodes.

Let’s see an example:

fun main() {
    // Create a LinkedList
    val linkedList = LinkedList<Int>()

    // Add elements to the LinkedList
    linkedList.add(10)
    linkedList.add(20)
    linkedList.add(30)

    // Get the size of the LinkedList
    val size = linkedList.size
    println(size) // Output: 3

    // Accessing elements by index
    val firstElement = linkedList[0]
    println("$firstElement") // Output: 10

    // Modify an element at a specific index
    linkedList[2] = 35
    println("$linkedList") // [10, 20, 35]

    // Remove an element at a specific index
    val removedElement = linkedList.removeAt(1)
    println("$removedElement") // Output: 20

    // Add an element at the beginning of the LinkedList
    linkedList.addFirst(5)
    println("$linkedList") // Output: [5, 10, 35]

    // Add an element at the end of the LinkedList
    linkedList.addLast(40)
    println("$linkedList") // Output: [5, 10, 35, 40]

    // Check if the LinkedList contains a specific element
    val containsElement = linkedList.contains(35)
    println("$containsElement") // Output: true

    // Iterate over the elements of the LinkedList
    for (element in linkedList) {
        println(element)
    } //Output: 5, 10, 35, 40
}

In conclusion, the choice of data structure will always depend on the specific objectives and requirements of your project. Selecting the right data structure is crucial for achieving optimal performance and efficiency. Whether you opt for an array-based list like ArrayList or a linked list like LinkedList, understanding their characteristics and trade-offs will help you make informed decisions and design more efficient algorithms.

Next articles

In Part 3 of our data structure series, we dive into Maps. Discover how to efficiently organize and retrieve data using key-value pairs. Stay tuned for Part 3 of our data structure series, coming soon!

References

Skiena, Steven S. The Algorithm Design Manual. 2nd ed., Springer, 2008.

LinkedList | Android Developers

Difference between Singly linked list and Doubly linked list - GeeksforGeeks

2 Array-Based Lists

kotlin.collections - Kotlin Programming Language