Back to Lesson 5

Implementing a list using an array

Part a: a simple list interface

For this exercise, we’ll write a class to implement the following list interface:

interface MyList {
    /* Add an element to the list */
    fun add(elt: Int)

    /* Look up an element by index */
    fun get(idx: Int): Int

    /* Remove an element (by index) from the list */
    fun remove(idx: Int)

    /* Get the number of elements */
    fun count(): Int
}

Copy this code and save it in a file FixedSizeList.kt.

Part b: arrays

Deep under the hood, all lists are actually built on the array data type. They’re tricky to work with, though, because they have a fixed size (so you can’t make it any bigger – instead, you have to copy all elements to a new, bigger array).

You can make a new array that holds 10 Ints, with all values initially null (signifying that you don’t have a valid value in those elements), using the arrayOfNulls function:

    val maxSize: Int = 10
    val myArr: Array<Int?> = arrayOfNulls<Int>(maxSize)

Once you have an array, you can access/modify elements using square brackets (e.g., myArr[2]) and get the number of elements (some of which may be null) with .count() (like myArr.count()).

Part c: using an array to build a list

Write a class FixedSizeList that implements a simple MyList interface using an Array<Int?> as its underlying data store.

For now, just define the blank class with methods that do nothing interesting (i.e., return -1 if they need to return an Int).

For example, this could be your count method at first:

    // Get the number of elements in the list
    override fun count(): Int {
        return -1 // this is a lie
    }

Here is a main function you should use to test your code:

fun main() {
    val mylist = FixedSizeList()
    mylist.add(2025)
    mylist.add(9)
    mylist.add(24)

    println("Elements present in the list: ")
    var numElts: Int = mylist.count()
    for (i in 0..<numElts) {
        val elt: Int = mylist.get(i)
        println(elt)
    }

    mylist.remove(1) // removes the 9 at index 1

    println("removed 9 from the list")

    println("Elements present in the list: ")
    numElts = mylist.count()
    for (i in 0..<numElts) {
        val elt: Int = mylist.get(i)
        println(elt)
    }
}

Before moving on, make sure it compiles! It should look like this when you use kotlinc and kotlin to run it (in the snippet below, % is my terminal prompt):

% kotlin FixedSizeListKt.class
Elements present in the list:
removed 9 from the list
Elements present in the list:

Part d: implementing part of the interface

Now, try to implement the add, get, and count methods of the MyList interface in your FixedList class. You can assume the list will never grow beyond a hard-coded maxSize value, and that the lookup will always succeed.

Note that the underlying array starts out with a bunch of null values; if you know the value stored at a given index is actually valid, you can use !! (like this: myArr[2]!!) to convince Kotlin to let you grab it as an Int rather than a nullable Int (e.g., Int?). We’ll see null safety more next week.

Once you have these three methods implemented, your output should look like this:

% kotlin FixedSizeListKt.class
Elements present in the list: 
2025
9
24
removed 9 from the list
Elements present in the list:
2025
9
24

Part e: finishing up

Finally, implement the remove function. How will this work to make sure you don’t have any rogue null values in the middle of your list?

Make sure you get this output after:

% kotlin FixedSizeListKt.class
Elements present in the list: 
2025
9
24
removed 9 from the list
Elements present in the list:
2025
24

Part f: extensions

Want to keep going? Try adding some new functionality to your interface (and thus class that implements it).

• Add an element at a given index
• Remove an element by value, rather than by index
• Error handling
• Create a new class called ArrayList that implements this same interface, but can grow beyond its initial maximum size; make sure to copy everything over when you have to grow the list on an add!

Back to Lesson 5