Data Structures in Kotlin: Array — [PartI]

Hey everyone! In this article series, we’ll be exploring data structures and their implementations in Kotlin. We’ll explore different types of data structures and how they can supercharge your programs. We’ll keep things simple, humble, and friendly as we unravel the concepts and techniques behind data structures.

So, let’s get started and learn how to leverage the power of data structures.

What is Data Structure?

A data structure, as the name suggests, is simply a way to structure or organize the storage of our data in a manner that makes it easy to access and manipulate. Think about how you organize your wardrobe. Do you group items by type or sort them by color? Now imagine you’re running late for work and need to grab the appropriate outfit. If everything is a mess, it will take you some time to find it (if you find it at all). But if you had organized your clothes by type, color, style, and preference, you would likely go straight to the desired item and take just seconds to grab it.

The idea behind structuring data is essentially the same: organizing stored data and optimizing access and manipulation to efficiently achieve our objectives.

When we use an appropriate data structure, we can store data in a way that makes it easy to find, insert, remove, or modify the information within that data. This structured organization of data allows operations to be performed more effectively, saving time and resources.

Therefore, by understanding the characteristics and performance of different data structures, it is possible to select the one that optimizes the operations that will be performed most frequently in the specific context of the problem.

Contiguous vs Linked Data Structures

Data structures can be classified into two main categories: contiguous and linked. Contiguous data structures, such as arrays, matrices, heaps, and hash tables, are composed of a single block of memory that stores all the elements in a consecutive manner. This means that the elements are placed next to each other in memory without any gaps between them.

On the other hand, linked data structures, such as lists, trees, and graph adjacency lists, are composed of separate memory chunks that are connected through pointers. Each chunk, or node, contains the data and a pointer that points to the next node in the structure.

To visualize this, imagine a contiguous structure as a long row of boxes placed one after another, where each box holds an element. In a linked structure, think of it as a collection of individual boxes scattered around, with each box having a label pointing to the next box in the sequence.

These two types of data structures have different characteristics and are suitable for different scenarios. Contiguous structures allow for efficient access to elements using indices, but their size is fixed once created. Linked structures, on the other hand, offer more flexibility in terms of size and dynamic element manipulation, but accessing elements may require traversing the structure sequentially.

Understanding the distinction between contiguous and linked data structures is essential for choosing the right structure for specific data manipulation needs.

Let's talk about the contiguously-allocated structure, Array.

What is an array?

An array is a fundamental contiguously-allocated data structure that allows you to store a collection of elements of the same type. It provides a way to organize and access these elements in a systematic manner.

Imagine you have a shelf where you want to organize different types of fruits. Each fruit represents an element in our data structure. To create this shelf representation, you can use an array.

Shelf Representation of Fruit Items

In an array, you can store elements of the same type, in this case, fruits. Each fruit occupies a specific position, or index, within the array, just like each compartment on the shelf holds a specific fruit. The index serves as a unique identifier for each fruit and allows us to locate and retrieve them individually.

For example, let’s consider an array named fruits that stores the names of different fruits:

val fruits: Array<String> = arrayOf("pear", "strawberry", "cherry", "apple", "banana")

In this array, each fruit, or string, is assigned a position based on its index. The first fruit, “pear”, is at index 0, the second fruit, “strawberry”, is at index 1, and so on.

Shelf Representation of Fruit Items with respective index

To access a specific fruit, or string, you can refer to its index. For instance, fruits[2] refers to the fruit at index 2, which is "cherry". By using the appropriate index, you can retrieve or modify individual fruits, or strings, in the array.

Accessing Elements

In an array, elements are stored in contiguous memory locations. This means that the elements are placed one after another in memory, without any gaps between them. Each element occupies a fixed amount of memory space, determined by its data type.

To access a specific element, Kotlin calculates the memory address by multiplying the index with the element’s size, resulting in an offset. This offset represents the number of memory spaces needed from the base address to reach the desired element.

By adding this offset to the base address, we obtain the precise memory address where the desired element is stored. This enables direct access to the element in memory, allowing us to retrieve its value or perform operations on it.

Let’s consider an example with the following array:

val numbers: Array<Int> = arrayOf(10, 20, 30, 40, 50, 60)

In this array, the first element, 10, is stored at the base memory address (201). The second element, 20, is stored at the next memory address (205), and so on.

Now let’s suppose we want to access the value of the array item at index 3.

1- Offset calculation: Since we’re using an array of Integers, each element occupies 4 bytes (assuming a 32-bit system).

• Index: 3
• Data type size: 4 bytes
• Calculation: 3 * 4 = 12 bytes (Offset for index 3)

2- Apply offset: We add the offset (12) to the base address, which is the memory location where the first element (10) is stored — in this case, 201.

• Base address: Memory location of the first element (10) = 201
• Calculation: Base address (201) + Offset (12) = Memory location (213)

This process allows for efficient and direct access to specific elements in the array.

It’s important to note that if the index is outside the valid bounds of the array, an IndexOutOfBoundsException will be thrown. Therefore, always ensure the index is within the valid range before accessing an element.

Understanding how the offset is calculated and its relation to the base address enables efficient element access in an array. This approach allows direct retrieval from memory without traversing the entire array.

Characteristics

• Same Type Elements: All elements in an array must be of the same data type. For example, if you have an array of integers, you can only put integers in it. This rule ensures that the array can efficiently allocate memory for the elements and perform operations on them.
• Fixed Size: Once an array is created, its size remains fixed and cannot be changed. You cannot add or remove items from the array unless you create a new array with a different size.
• Constant-Time Access Given the Index: Each element in the array has a unique index, starting from 0. This allows us to access any element directly by specifying its index, without having to search or iterate through the entire array. It’s like instantly finding the item you need by knowing its position in the box.

Performance considerations

• 🚀 Space Efficiency: Arrays are space-efficient because they consist purely of data. There is no extra space wasted on links or formatting information. It’s like having a compact box that efficiently utilizes all its available space for storing the elements.
• 🚀 Memory Locality: Arrays have good memory locality, which means that accessing consecutive elements in the array is faster. This is because the elements are stored in contiguous memory locations, allowing the computer’s cache memory to work more efficiently.
• 🚀 Efficient Iteration: Arrays provide efficient iteration over all elements using loops, such as for loops. The elements can be sequentially accessed and processed one by one.
• 🚀 O(1) Time Complexity for Access: Due to the random access nature of arrays, accessing an element by its index has a constant-time complexity of O(1). This means that regardless of the size of the array, the time it takes to access an element remains the same.
• 🔻 Memory Overhead: Arrays require memory space to store all the elements in contiguous locations. This can lead to memory overhead if the array is large or if it is not fully utilized.
• 🔻 Insertion and Deletion Overhead: Inserting or deleting an element in the middle of an array requires shifting the subsequent elements to accommodate the change. This can be time-consuming, especially for large arrays, as it may involve moving many elements, resulting in a time complexity proportional to the array size (O(n)).

Usage in Kotlin

In Kotlin, the data structure that represents an array is the Array class. The Array class is a generic class that can be used to declare arrays of any data type, whether primitive or object.

To declare an array using the Array class, you can use the arrayOf() function and specify the elements within the parentheses. For example:

val array: Array<Int> = arrayOf(1, 2, 3, 4, 5)

Kotlin also provides specialized classes for arrays of primitive data types, such as IntArray, DoubleArray, BooleanArray, and more. These specialized classes offer performance optimizations and additional functionalities specific to each data type. However, they have a slight additional memory overhead due to the object representation.

To declare an array of a primitive type, you can use the corresponding specialized class. For example:

val intArray: IntArray = intArrayOf(1, 2, 3, 4, 5)

Let's see an example in Kotlin that demonstrates various properties of an array:

fun main() {
    // Creating an array of integers
    val numbers = arrayOf(1, 2, 3, 4, 5)

    // Accessing elements by index
    val firstNumber = numbers.first()
    val secondNumber = numbers[1]
    val lastNumber = numbers.last()

    // Modifying an element at a specific index
    numbers[3] = 10

    // Length of the array
    val length = numbers.size

    // Checking if the array is empty
    val isEmpty = numbers.isEmpty()

    // Iterating over the elements
    for (number in numbers) {
        println(number)
    }

    // Finding the index of a specific element
    // Iterates through the array until the item is found
    val index = numbers.indexOf(4)

    // Checking if an element exists in the array
    // Iterates through the array until the item is found
    val containsElement = numbers.contains(3)

    // Adding an element to the array
    // Creates another array to reallocate the items
    val newArray = numbers.plus(6)

    // Removing an element from the array
    // Creates another array to reallocate the items
    val removedArray = numbers.dropLast(1)
    
    // Printing the array
    println(numbers.contentToString())
}

Dos and Don’ts

Do:

• Use arrays when you have a fixed-size collection of elements of the same type.
• Use arrays when you need direct and efficient access to elements using index-based retrieval.
• Use arrays when you want to store elements in a specific order.
• Use arrays when you need to process data efficiently in loops, as arrays provide fast access to elements.
• Use arrays when working with multidimensional structures, such as matrices or tables.

Don’t:

• Don’t use arrays when you have a large number of insertions or removals in the middle or beginning of the array.
• Don’t use arrays when you need dynamic resizing based on the number of elements.
• Don’t use arrays when you require complex search operations or automatic sorting.
• Don’t use arrays when memory usage is critical and the array size is unknown. Arrays allocate memory even if not all elements are used, resulting in potential waste.

Remember, the choice of data structure depends on your specific needs and problem requirements. Consider analyzing the characteristics of your problem before deciding to use an array or exploring alternative data structures.

That's it for now.

In the upcoming article, we will delve deeper into other data structures. I hope you find this series enjoyable and that it proves helpful to you in some way.

References

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

Know Thy Complexities!

Data Structures & Algorithms in Kotlin, Chapter 2: Complexity

2 Array-Based Lists

Arrays | Kotlin