Hands-On Data Structures and Algorithms with Kotlin

Hands-On Data Structures and Algorithms with Kotlin

by Chandra Sekhar Nayak, Rivu Chakraborty
Released February 2019
Publisher(s): Packt Publishing
ISBN: 9781788994019

Read it now on the O’Reilly learning platform with a 10-day free trial.

O’Reilly members get unlimited access to books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.

Start your free trial

Book description

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.

Table of contents

  1. Title Page
  2. Copyright and Credits
    1. Hands-On Data Structures and Algorithms with Kotlin
  3. Packt Upsell
    1. Why subscribe?
    2. Packt.com
  4. Contributors
    1. About the authors
    2. About the reviewer
    3. Packt is searching for authors like you
  5. Preface
    1. Who this book is for
    2. What this book covers
    3. To get the most out of this book
      1. Download the example code files
      2. Download the color images
      3. Conventions used
    4. Get in touch
      1. Reviews
  6. Section 1: Getting Started with Data Structures
  7. A Walk Through - Data Structures and Algorithms
    1. Technical requirements
      1. Working with the command-line compiler
      2. Working with IntelliJ IDEA
      3. Working with Eclipse
    2. Learning about algorithms
      1. A few examples of algorithms
    3. Introduction to data structures
    4. Complexity analysis
      1. Analyzing with time complexity
      2. Analyzing with space complexity
      3. Time complexity versus space complexity
    5. Learning about notations
      1. Counting instructions
      2. Asymptotic behavior
      3. Examples of complexity analysis
    6. Summary
    7. Further reading
  8. Arrays - First Step to Grouping Data
    1. Technical requirements
    2. Introduction to arrays
    3. Operations with arrays
      1. Creating an array
        1. Creating an array using library functions
        2. Creating an array using the constructor
      2. Accessing elements from an array
        1. Accessing an element using the Array Access Operator []
        2. Accessing an element using the get function
        3. Accessing an element using the extension functions
      3. Iterating over an array
      4. Updating elements in an array
    4. Vectors (dynamic arrays)
      1. Adding an element to a Vector class
      2. Updating and fetching an element
      3. Removing an element from Vector
    5. The beauty of immutable arrays
    6. Multidimensional array
      1. Operations in multidimensional arrays
        1. Accessing an element
        2. Updating an element
        3. Iterating over the array
      2. Working with a matrix
        1. Adding two matrices
        2. Multiplying two matrices
    7. A short introduction to strings
    8. Summary
    9. Questions
  9. Section 2: Efficient Grouping of Data with Various Data Structures
  10. Introducing Linked Lists
    1. Technical requirements
    2. Getting started with LinkedList
    3. Understanding a Singly Linked List
      1. Operations on a Singly Linked List
        1. Inserting a node in a Singly Linked List
          1. Inserting a node at the 0th index
          2. Inserting a node at the last index
          3. Inserting a node at a given index
        2. Fetching a node value from a Singly Linked List
          1. Fetching a value from the first or last node
          2. Fetching the value of a node at a given index
        3. Updating a node from a  Singly Linked List
        4. Deleting a node from a Singly Linked List
          1. Removing the first and last node of a LinkedList
          2. Removing the node based on its value
          3. Removing the node at a particular index
          4. Clearing the LinkedList
        5. Searching for an element in a Singly Linked List
    4. Understanding the Doubly Linked List
      1. Adding a node
      2. Deleting a node
      3. Fetching a node
    5. Understanding a Circular Linked List
    6. Summary
    7. Questions
  11. Understanding Stacks and Queues
    1. Technical requirements
    2. Understanding stacks
    3. Operations on a stack
    4. Implementing stacks
      1. Stacks with a fixed size
      2. Stacks with a dynamic size
      3. Stack implementation using a LinkedList
        1. Pushing an element into the stack
        2. Popping an element from the stack
    5. Understanding a queue
    6. Operations on queues
    7. Implementing a queue
      1. Queues with a fixed size
      2. Queues with a dynamic size
      3. Queue implementation using LinkedList
      4. Performance of a queue
    8. Introducing circular queues
      1. Primary operations in a circular queue
      2. Secondary operations in a circular queue
    9. Understanding deque – double-ended queue
      1. Primary operations – deque
    10. Summary
    11. Questions
    12. Further reading
    13. Questions
  12. Maps - Working with Key-Value Pairs
    1. Technical requirements
    2. Introducing Map
    3. Operations in Map
    4. Introducing hashing
      1. Benefits of hashing
      2. The hash function
      3. Hash collision
        1. Fixing collisions with chaining
    5. Implementing HashMap
      1. A template of the HashMap class
      2. The Node class of HashMap
      3. The hash function of HashMap
      4. Operations on HashMap
        1. Determining the bucket from the key
        2. Putting a key-value pair into the HashMap
        3. Getting a value from HashMap
        4. Removing a key-value pair from HashMap
    6. Implementing ArrayMap
      1. Internal data structure of ArrayMap
      2. A template of the ArrayMap class
      3. Operations on ArrayMap
        1. Putting a key-value pair into ArrayMap
        2. Getting a value from ArrayMap
        3. Removing a key-value pair from ArrayMap
    7. Summary
    8. Questions
  13. Section 3: Algorithms and Efficiency
  14. Deep-Dive into Searching Algorithms
    1. Technical requirements
    2. Understanding the searching algorithm
    3. Linear search
      1. Linear search in an unordered collection
      2. Linear search in an ordered collection
    4. Binary search
      1. Working with binary search
    5. Jump search
      1. Choosing indexes to be skipped
    6. Exponential search
    7. Pattern search
      1. Naive pattern search
        1. How Naive pattern search works
      2. The Rabin-Karp algorithm
        1. Hash functions for Rabin-Karp
        2. Rolled-hash functions for Rabin-Karp
        3. Searching using hash values
        4. Performance
      3. The Knuth-Morris-Pratt algorithm
        1. The prefix function
        2. Searching using a prefix array
    8. Summary
    9. Questions
  15. Understanding Sorting Algorithms
    1. Technical requirements
    2. Understanding the bubble sort algorithm
      1. How the bubble sort algorithm works
      2. Implementing bubble sort
    3. Understanding selection sort
      1. How the selection sort algorithm works
      2. Implementing selection sort
    4. Understanding insertion sort
      1. How the insertion sort algorithm works
      2. Implementing insertion sort
    5. Understanding merge sort
      1. How the merge sort algorithm works
      2. Implementing merge sort
    6. Understanding quick sort
      1. How the quick sort algorithm works
        1. Choosing the pivot element
        2. Example based on quick sort
      2. Implementing quick sort
    7. Understanding heap sort
      1. A basic introduction to heap
        1. Binary heap
      2. How the heap sort algorithm works
      3. Implementing heap sort
    8. Summary
    9. Questions
  16. Section 4: Modern and Advanced Data Structures
  17. Collections and Data Operations in Kotlin
    1. Technical requirements
    2. Introduction to collections
      1. Benefits of a collections framework
      2. The collection framework hierarchy
    3. Understanding a group of ordered elements – List, MutableList
      1. Various operations (sorting, searching) on List
        1. Sorting a list with custom class / data types
        2. Searching collections
      2. Mutable lists
    4. Group of unique elements – Set, MutableSet
    5. Maps – working with key-value pairs
    6. Understanding data operations in collections
      1. The map function
      2. The filter function
      3. The flatMap function
      4. The drop functions
      5. The take functions
      6. The zip function
    7. Summary
    8. Questions
  18. Introduction to Functional Programming
    1. Introducing functional programming
    2. Immutability
      1. Implementing immutability in Kotlin
      2. Immutable collections
    3. Exploring pure functions
    4. Lambda and higher-order functions
      1. Higher-order functions
    5. Functional data structures
    6. Understanding the Arrow framework and typed FP
      1. The Option type constructor
      2. The Either type constructor
    7. Introducing category theory
      1. Functors
      2. Applicatives
      3. Monads
    8. Summary
    9. Further reading
  19. Other Books You May Enjoy
    1. Leave a review - let other readers know what you think
  20. Assessments

Product information

  • Title: Hands-On Data Structures and Algorithms with Kotlin
  • Author(s): Chandra Sekhar Nayak, Rivu Chakraborty
  • Release date: February 2019
  • Publisher(s): Packt Publishing
  • ISBN: 9781788994019