5 Data handling with lists

Data structures are one of the most important concepts in programming, as well as in everyday life. The world as you see it is a huge data structure composed of simpler data structures, which are in turn composed of simpler structures. Each time you model something, be it objects or facts, you end up with data structures.

Data structures come in many types. In computing, data structures referring to the multiple occurrences of data of a given common type are generally represented as a whole by the term collections. A collection is a group of data items that have some relationship to each other. In its simplest form, this relationship is that they belong to the same group.

This chapter covers data structures and how to create your own implementation of the singly linked list. Kotlin has its own lists, both mutable and immutable. But the Kotlin immutable list isn’t really immutable, and it doesn’t implement data sharing, making operations such as adding and removing elements less efficient. The immutable list you’ll develop in this chapter is far more efficient for stack operations, and it’s immutable.

5.1 How to classify data collections

5.2 Different types of lists

5.3 Relative expected list performance

5.3.1 Trading time against memory space and complexity

5.3.2 Avoiding in-place mutation

Update in place

5.4 What kinds of lists are available in Kotlin?

5.4.1 Using persistent data structures

5.4.2 Implementing immutable, persistent, singly linked lists

5.5 Data sharing in list operations

5.6 More list operations

5.6.1 Benefiting from object notation

5.6.2 Concatenating lists

5.6.3 Dropping from the end of a list

5.6.4 Using recursion to fold lists with higher-order functions (HOFs)

5.6.5 Using variance

5.6.6 Creating a stack-safe recursive version of foldRight

5.6.7 Mapping and filtering lists

Summary