Hands-On Data Structures and Algorithms with Kotlin

Level up your programming skills by understanding how Kotlin's data structure works

Chandra Sekhar Nayak, Rivu Chakraborty

• Publisher: Packt Publishing
• Year: 2019
• Print ISBN: 9781788994019
• eBook ISBN: 9781788998819
• Edition: 1
• Topic: Computer Science
• Subtopic: Programming in Java
• Index: Computer Science

Understand and solve complex computational problems and write efficient code with Kotlin

Key Features

• Learn about important data structures such as lists, arrays, queues, and stacks
• Design custom algorithms for real-life implementations
• Identify suitable tools for different scenarios and deliver immediate results

Book Description

Data structures and algorithms are more than just theoretical concepts. They help you become familiar with computational methods for solving problems and writing logical code. Equipped with this knowledge, you can write efficient programs that run faster and use less memory.

Hands-On Data Structures and Algorithms with Kotlin book starts with the basics of algorithms and data structures, helping you get to grips with the fundamentals and measure complexity. You'll then move on to exploring the basics of functional programming while getting used to thinking recursively. Packed with plenty of examples along the way, this book will help you grasp each concept easily. In addition to this, you'll get a clear understanding of how the data structures in Kotlin's collection framework work internally.

By the end of this book, you will be able to apply the theory of data structures and algorithms to work out real-world problems.

What you will learn

• Understand the basic principles of algorithms and data structures
• Explore general-purpose data structures with arrays and linked lists
• Get to grips with the basics of stacks, queues, and double-ended queues
• Understand functional programming and related data structures
• Use performant searching and efficient sorting
• Uncover how Kotlin's collection framework functions
• Become adept at implementing different types of maps

Who this book is for

If you're a Kotlin developer who wants to learn the intricacies of implementing data structures and algorithms for scalable application development, this book is for you.

Section 1: Getting Started with Data Structures

This section will walk you through the basics of data structures and will answer your query about why we need to learn data structures and algorithms. You will also learn about the efficiencies of algorithms and how to measure them. Yes, you read that right: Algorithms also have efficiencies, given that they are based on time complexities (execution time needed) and space complexities (memory footprints).

The following chapters will be covered in this section:

• Chapter 1, A Walk-through – Data Structures and Algorithms
• Chapter 2, Arrays – The First Step to Grouping Data

A Walk Through - Data Structures and Algorithms

This book is written with the objective of making you understand what an algorithm is and the importance of it in computer science. Since an algorithm becomes more powerful when used with proper data structures, we'll also walk you through various commonly used data structures in programming.

In this chapter, we're going to focus on theoretical definitions of algorithms and data structures. As we move forward, we'll learn about this in detail.

As this book's title says, we're going to use the Kotlin programming language in all of the examples provided here. You may be asking why Kotlin? Why not any other programming language? The answer would be that it's just a language preference. But as far as algorithms are concerned, they can be understood and practiced with any programming language.

This chapter will help us to understand the following topics:

• Algorithms and their importance
• The efficiency of an algorithm
• Data structures
• Complexity and notations, including Big O notation

Technical requirements

To practice the algorithms and data structures we'll learn from this book, we need the Kotlin compiler to be installed on our PC. There are many ways to set your PC up for this. Let's look into that. Here is the GitHub link of this book:

The GitHub URL for the chapter is here:

https://github.com/PacktPublishing/Hands-On-Data-Structures-and-Algorithms-with-Kotlin/tree/master/Chapter01

Working with the command-line compiler

The Kotlin binary is released over GitHub. So you need to find the latest release and download the ZIP file if you want to install the Kotlin compiler manually. Currently, the latest release is 1.2.40, which can be found at this GitHub URL: https://github.com/JetBrains/kotlin/releases/tag/v1.2.40. After the Kotlin compiler has downloaded, unzip the downloaded ZIP file into a directory and add the bin directory to your system path. This is the directory that contains all of the scripts to compile and run your code.

If you want to install the compiler via SDKMAN, Homebrew, or similar tools, then you can follow the official instruction mentioned here:

https://kotlinlang.org/docs/tutorials/command-line.html.

To write Kotlin code, you can use any of your favorite editors and start writing. Once the code is written, you can save the file as <filename>.kt and it's ready for compilation. Please note that Kotlin files are represented with the .kt extension.

For compiling the Kotlin code, you need to use the following command:

kotlinc <filename>.kt -include-runtime -d <filename>.jar

To run it, use the following command:

java -jar <filename>.jar

Working with IntelliJ IDEA

If you're comfortable with IDEs and want to use an IDE instead of a simple text editor, then you can choose IntelliJ IDEA as it works seamlessly with Kotlin. The steps for using Kotlin with IntelliJ IDEA are explained in the official documentation here: https://kotlinlang.org/docs/tutorials/getting-started.html.

Working with Eclipse

If you're more familiar with Eclipse than IntelliJ IDEA, then follow the official documentation at https://kotlinlang.org/docs/tutorials/getting-started-eclipse.html and set it up.

Learning about algorithms

In computer programming, the sole purpose of building any software is to solve a problem existing in the real world and make the world a better place to live in. When we talk about a solution to a problem, it's obvious that we're talking about the procedure to be followed to solve the problem.

Let's consider a case where your teacher comes to you and gives you a bunch of candy, asking you to distribute it equally among your classmates. If you consider this as a problem and try to achieve it with ease, then you might do it as follows:

1. Count the number of candies you have.
2. Count the number of students present in your class.
3. Calculate how many candies should be given to each student.
4. Ask all of the students form a queue so that no student can take the required candies twice.
5. Start distributing the candies to each student.
6. Maintain a separate group for students who already took candies.

As you can see, I've created six steps to solve the task. You might solve it in a different way. These steps are what we call algorithms in computer science.

So, in a nutshell, we can define algorithms as something that takes a value or a set of values as input, processes it, and returns a value or a set of values as output. In other words, we can say that algorithms are a solution to a well-defined computational problem.

In this book, we'll cover the most commonly used basic algorithms, for example, sorting algorithms, searching algorithms, hashing algorithms, and so on.

A few examples of algorithms

Let's look at some examples to understand algorithms. Consider the following code:

private fun add(x: Int, y: Int) = x + y

Please be sure that you have a basic understanding of Kotlin and its syntax.

In the preceding code snippet, the code accepts two arguments as input and returns their sum as output. It satisfies the definition of the algorithm by taking some input, processing the input, and returning the result. Now, consider the following code:

val hourInMillis = 24 * 60 * 60 * 1000

In the preceding example, we can still argue that this is an algorithm. Here, the compiler takes 24, 60, 60, and 1000 as input and multiplies all of them to get the single output and finally assigns the output back to the property named hoursInMillis. Even though this type of code has nothing to do with the runtime, we can define this as a compile-time algorithm.

So, in conclusion, we can say that programs that solve complex computation problems aren't the only programs that can be called algorithms. Instead, any program (whether simple or complex), if that consumes some input to calculate and gives some output can be called as an algorithm. For example, sorting and searching aren't the only processes that can be called algorithms; even a simple assignment can also be treated as an algorithm.

This is the beauty of computer science theory. There's no single definition available for algorithms. We just have a few rules to categorize something as an algorithm. As long as your program satisfies those, we can argue that it's an algorithm.

Introduction to data structures

We solved the previous example by taking a few steps, such as asking all students to stand in a queue and, once a student got candy, we moved them to a separate group. We could have also done the same task without asking them to maintain a queue or separating them into a separate group once they got the candy. But we did that to make the task go smoother. Of course, we could have done the task without these two sub-tasks, but that would have created a lot of confusion and made it tedious to finish the task on time.

If we consider that example, we can treat candies and students as data. And to solve the problem given by the teacher, we first structured the data and solved it with ease. This is what we call data structures in computer science.

In this book, we'll cover the most commonly used data structures such as an array, string, list, linked list, stack, queue, tree, graph, and so on. The order isn't the same though. If we talk about data structures in front of others, people generally think about the earlier mentioned data structures. But this doesn't mean that these are the only data structures available. We've a lot more data structures available and ones that are commonly used. In addition to these commonly used data structures, we can also define our own data structures based on our business needs. We might customize data structures in two ways:

• Extend existing data structures
• Customize data structures

If we've a problem, that can be achieved with the help of list but with a slight modification, then we'll try to extend the existing List class present in Kotlin's collection framework instead of creating a completely new data structure. For example, the problem statement says to have a list of names, only in uppercase. Of course, there's no existing data structure that can do this out of the box. So you need to extend the List and modify it a bit as per our need. So that all existing functionality of List gets inherited and works the same as earlier, except with the modified one. Let's see the code:

class UpperCasedList : ArrayList<S...

Table of contents

• Title Page
• Copyright and Credits
• Packt Upsell
• Contributors
• Preface
• Section 1: Getting Started with Data Structures
• A Walk Through - Data Structures and Algorithms
• Arrays - First Step to Grouping Data
• Section 2: Efficient Grouping of Data with Various Data Structures
• Introducing Linked Lists
• Understanding Stacks and Queues
• Maps - Working with Key-Value Pairs
• Section 3: Algorithms and Efficiency
• Deep-Dive into Searching Algorithms
• Understanding Sorting Algorithms
• Section 4: Modern and Advanced Data Structures
• Collections and Data Operations in Kotlin
• Introduction to Functional Programming
• Other Books You May Enjoy
• Assessments