vii. Introduction

Data structures and algorithms are two essential topics in Computer Science. The study of data structures is one of efficiency. Given a particular type and amount of data, what’s the best way to store it to achieve a specific goal? How do you structure it to meet your needs?

As a programmer, you regularly use a variety of collection types, such as arrays, lists, maps and sets. Even if you aren’t aware of it, the libraries and frameworks that you use are using them. These are data structures that hold a collection of data, and each structure has its own performance characteristics in terms of memory space and the speed of basic operations.

As an example, consider the difference between an array and a set. Both are meant to hold a collection of elements, but searching for an element in an array takes far longer than searching for an element in a set. On the other hand, you can order the elements of an array, but you can’t order the elements of a set. You win some; you lose some.

Data structures are a well-studied discipline, and the concepts are language agnostic. A data structure from C is functionally and conceptually identical to the same data structure in any other language, including Kotlin. The way it’s implemented might differ from language to language — for instance, you can’t use pointers in Kotlin as you do in C — but the result will be the same. At the same time, Kotlin is a concise, high-level expressive language, and that makes it an ideal choice for learning these core concepts without sacrificing too much performance.

Who is this book for?

If you have a basic understanding of data structures and you want to see them in Kotlin, you already have a good reason to jump in. However, if you’re new to data structures and algorithms, you might wonder why you should take the time to learn them.

Interviews

When you interview for a software engineering position, chances are, the employer will test you on data structures and algorithms. Having a strong foundation in data structures and algorithms is the bar, so to speak, for many software engineering positions. The knowledge in this area is usually tested with the famous whiteboard interviews, the same ones that strike terror into aspiring software engineers. Know your algorithms, and you’ll have nothing to fear. So, go ahead, grab that red marker and impress everyone! :]

Career

Using an appropriate data structure is crucial when working with lots of data. Using the right algorithm plays a significant role in the performance and scalability of your software. Your mobile apps will be more responsive and have better battery life. Your server apps will be able to handle more concurrent requests. Algorithms often include proofs of correctness that you can leverage to build better software.

One can argue that these things are already implemented and you don’t need to reinvent the wheel. That’s true. But understanding how, when and why to use them is what makes the difference between a good developer and a great developer. You might already know that in the software industry, the answer to all of your questions is: “It depends”. However, if you know the basics, you’ll know what it depends on, which is key to getting to the bottom of all of the problems.

Self-Improvement

Knowing the strategies used by algorithms to solve tricky problems gives you ideas for improvements that you can make to your own code. The Kotlin standard library has a small set of general-purpose collection types; they don’t cover every case. And, yet, as you’ll see, you can use these data structures as a starting point for building more complex and special-purpose constructs. It’s like having LEGO pieces: The more types of pieces you have, the more complex things you can build.

The goal of this book

This book is meant to be both a reference and an exercise book. While it does not cover all of the data structures and algorithms ever invented, it has all of the most important and most used ones. It’s a great book to start preparing for whiteboard interviews and an excellent reference to come back to when you need to optimize some code.

If you’re familiar with other books from raywenderlich.com, you’ll feel right at home. In some cases, a starter project is provided; in other cases, you’ll start from scratch. Each chapter also ends with one or more challenges for you to solve. You can find solutions to these challenges at the end of the book. Do yourself a favor and make a serious attempt at solving each challenge before peeking at the solution.

This book is divided into five sections, each covering a specific theme:

1. Introduction
2. Elementary data structures
3. Trees
4. Sorting algorithms
5. Graphs

This book is best read in chronological order. However, it also works well as a reference if you want to skip around.