Linked Lists in Kotlin: An educational approach (1)

Data structures are a challenge, for both teachers and students. It is common for students to have difficulties comprehending the data structure fundamentals as they need to understand the data structure’s purpose, besides having a piece of solid algorithm knowledge. Thus, the programming language can often be a hurdle in this process. We can highlight at least two issues about a programming language and data structure:

1. Language issues (because that language is new, sometimes).
2. Data structure’s concepts challenge.

Therefore, in this paper, we will talk about an educational approach to teaching an important data structure, aiming to reduce the friction between learning a new computing concept and a new programming language.

Linked List

What is a Linked List?

“A linked list is a data structure in which the objects are arranged in a linear order. Unlike an array, however, in which the linear order is determined by the array indices, the order in a linked list is determined by a pointer in each object. Linked lists provide a simple, flexible representation for dynamic sets.” (CORMEN et al., 2009).

A doubly linked list L (Source: CORMEN et al., 2009)

Often C language is used to teach data structure, because C is a general-purpose and procedural language that gives us a good introduction to algorithms and programming languages as well. By using C, when working with Liked List, we will need to introduce a struct to manipulate complex data types and the pointer to link the list. At this moment, we have two important things to explain in a classroom: what are complex data and a pointer? Considering that node is a data that has at least two pieces of information (value and pointer), therefore it is not a primitive data type and we need to talk about struct or aggregates.

“Structures — sometimes referred to as aggregates — are collections of related variables under one name. Structures may contain variables of many different data types — in contrast to arrays that contain only elements of the same data type. Structures are commonly used to define records to be stored in files” (DEITEL and DEITEL, 2010).

💡 Brazil students, Feofiloff (2022) brings a good introduction to Linked List.

So, probably students will work and learn about structs and pointers strictly in data structure and this is not good, because a specific feature of the language can lead the students to think that the data structure subject is conditioned to this. It is important to know that we can implement data structure in any programming language.

But how can we introduce students to the data structure without using a restricted feature of a programming language?

We can think about a more common or modern programming paradigm! Therefore, we increase the possibility that students learn about a language-specific feature in another context. In the case of struct, a class would be a good choice. So, this will also contribute to the introduction of OOP.

And about the pointer? Pointer is one of the most difficult concepts for students, it is a bit abstract to say that a variable stores a memory address. Using classes you can also contribute to this aspect, so we can just talk about reference variables.

☝️ It is important for computer students to know the concept of pointers, I am not saying it is not useful, but we can introduce these subjects more efficiently at a different moment, perhaps in programming language advanced topics or when students are more mature in programming.

So, let’s see a simple example of a Singly Linked List in an object-oriented programming approach, based on Galata and Suica (2019) implementations, using a powerful and at the same time concise language… Kotlin: A modern programming language that makes developers happier (https://kotlinlang.org/).

Why Kotlin?

“Just as C++ was initially intended to be “a better C,” Kotlin was initially oriented towards being “a better Java.” It has since evolved significantly beyond that goal. Kotlin pragmatically chooses only the most successful and helpful features from other programming languages — after those features have been field-tested and proven especially valuable.” (ECKEL and ISAKOVA, 2021)

Node

Firstly, we will create a simple node with a value of String data type. You can change this along with the evolution of teaching the concepts (applying generics, for example), but for now, this is sufficient to illustrate a Linked List.

A node using data class

Linked List

Let’s implement the Linked List class with our starting approach. Here we have three properties: head, tail, and size, the basic concepts of a Linked List.

Linked List: First implementation in Kotlin

Push

When we insert a value in front of the list we call this a push operation. Initially, we will implement this operation due to its simplicity.

Linked List: Push operation

When the push function is called with a passed value, the head object is changed by receiving a new reference with a specific String value. If the tail is null, now it is equal to the head.

Pop

Pop operation aims to remove the first value of the Linked List. It’s very simple like the push operation.

Linked List: Pop operation

These two operations are a good starting point! 👌 Besides serving as a reference when you talk about Stacks.

Right now you can discuss the actions of inserting and removing data in a Linked List, and you will not have a lot of difficulties explaining the concepts of a class, object, or property. Logic and arithmetic operations are also simple. Take a look at our first Linked List implementation:

First Linked List implementation in Kotlin

Inserting two values into the list, using push operation:

Inserting two values into the list

In the next paper we will see the append, insert, removeLast and removeAfter operations. These operations show us the efficiency of a Linked List in terms of time complexity.

The OOP paradigm approach to teaching data structure is a suggestion aiming to reduce the friction between learning a new computing concept and a new programming language.

___

References

Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C. Introduction to Algorithms. 3. ed. Cambridge: Mit Press, 2009. 1292 p.

Deitel, P.; Deitel, H. C: How to Program. 6. ed. New Jersey: Pearson, 2010. 966 p.

Eckel, B.; Isakova, S. Atomic Kotlin. Colorado: Mindview Llc, 2021. 636 p.

Feofiloff, P. Listas encadeadas. Disponível em: https://www.ime.usp.br/~pf/algoritmos/aulas/lista.html. Acesso em: 16 abr. 2022.

Galata, I.; Suica, M. Data Structures & Algorithms in Kotlin. Alexandria: Razeware, 2019. 403 p.