Data Structures and Algorithms in Kotlin

Let's dive into Time Complexity, Space Complexity, Big O Notation, Data Structures, Algorithms in kotlin language. Knowing these can make any developer a better one.

Time Complexity

Is a measure of the time required to run an algorithm as the input size increases.

Space Complexity

Is a measure of the resource required for the algorithm to manipulate the input data.

Big O Notation

Is used to represent the general form of time and space complexity.

Time & Space Complexity are high-level measure of scalability. They don't measure the actual speed of the algorithm itself.

For small data sets, Time Complexity is usually irrelevant.

As you can see in above picture we have some types of Big O Notation:

• O(N!) means Factorial Time
• O(2^N) means Exponential Time
• O(N^2) means Quadratic Time
• O(N log N) means Quasilinear Time
• O(N) means Linear Time
• O(Log N) means Logarithmic Time
• O(1) means Constant Time

The Green color represent that the algorithm speed is good when size of the data increasing

The Red color represent that the algorithm speed is ad when size of the data increasing

Remember this chart in your decisions

Data Structures

• LinkedList
• Array
• Stack
• Queue
• Tree
• Binary Tree
• Binary Search Tree
• AVL Tree
• Trie
• Heap
• Priority Queue
• Hashtable
• Set
• Graph

Algorithms

• Linear Search
• Binary Search
• Quicksort
• Mergesort
• Timsort
• Heapsort
• Bubbl sort
• Insertion sort
• Tree sort
• Selection sort
• Bucket sort
• Radix sort
• Counting sort
• Cubesort
• Shell sort

LinkedList

A collection of values arranged in a linear, unidirectional sequence which has several advantages over contiguous storage options such as Array & ArrayList:

• constant time insertion and removal from the front of the list
• reliable performance characteristics

LinkedList consists of Nodes and each node has two responsibility

• Hold a value
• Hold the reference to the next node, the null marks the end of the list.

Pros:

• LinkedList has O(1) time complexity for head first insertion but Array & ArrayList has O(n) time complexity for it.
• Dynamic data structure
• No memory wastage

Cons:

• As soon as you move from one node to another, you can't go back cause there is only has reference to the next node.
• In LinkedList the elements aren't in contiguous blocks of memory. This could lead to more cache misses, which increase the access time.

Stack

Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out).

The main goal of building a stack is to enforce how you access your data.

Stack has only two operation:

• Push: Adding an element to the top of the stack
• Pop: Removing the top element of the stack.

Real world examples:

• Android using stack for managing the fragments.
• A maze app will use a stack to do the contiguous operation.
• Memory allocation uses stacks at the architectural level.

Queue

A Queue is a linear structure which follows a particular order in which the operations are performed. The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.

The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

The core operation of Queue:

• enqueue: Inserts an element at the back of the queue and returns true if the operation is successful.
• dequeue: Removes the element at the front of the queue and returns it.
• isEmpty: Checks if the queue is empty using the count property.
• peek: Returns the element at the front of the queue without remove or manipulating it.

Tree

It's a data structure of profound importance. It's used to tackle many recurring challenges in software development.

such as:

• Representing hierarchical relationships
• Managing sorted data
• Facilitating fast lookup operations

Just like LinkedList the trees consists Node but the Node contains two child nodes.

The topmost node in the tree is called the root of the tree. this node is the only node that has no parent.

A node that has no child is called as Leaf.

Sponsor

If you like and use it, please tap the Star(⭐️) button at the above.

This source code is free for all; hence, it's not profitable. You can make me happy by donating me :)

License

Copyright 2021 Mehdi Janbarari

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

   http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.