Data Structure and Algorithms
Data structure and algorithm are important when it comes to write the efficient solution to a problem. Any problem can be solved by many different ways. But, which solution is efficient is measured using some techniques. These techniques of measurement and the things which will aid us in writing the efficient solution that we will learn in data structure and algorithm.
There are different ways of organizing the data as like there are different ways of organizing anything for example vehicles in parking lot. Each structure has some advantage and disadvantages. Depending upon the situation we have to choose the right structure to organize the data.
We discussed about the data structure, its time to discus about algorithms. Algorithms are the steps for solving any problem as like if you are cooking then recipe is algorithm. An algorithm is a set of steps to solve a problem.
There are different type of data structure available like Arrays, Linked List, Stack/Queue, Trees, Graph, Hash Table, etc and also there are different algorithms are available to solve any problem like for searching — Binary/Linear search and for sorting — Selection/Merge/Quick sort.
To identify which solution is best, we have to consider two factors Time and Space.Time Complexity and Space Complexity are parameter are used for comparing the multiple solutions to a problem.
Time Complexity
The time taken by solution on different system will be different. It depends on how powerful hardware you are using. So, It’s difficult to measure the solution based on time, because of this Big O notation is used to calculate the time complexity of the solution.
Big O notation
Big O notation measures the solution based on the number of statement that will be executed to solve any problem or number of comparisons in the solution.
Lets consider the problem of swapping two numbers, there are two solution to this problem, using temporary variable and without using third variable.
First solution,
var a=10,b=20;
var temp = a;
a = b;
b = temp;
Second Solution,
Var a =10, b = 20;
a = a+b;
b = a-b;
a = a -b;
for both solutions, three statements are required but addition/subtraction operation internally translated into more than one steps. The first solution will take less time compared to second but first solution requires more space than second. In today’s generation space doesn't matter much. Today, system comes with 32GB, 64GB RAM unlike in the beginning, RAM used to be 16KB or 32 KB only.
Big O(n) is used for the solution which follows linear pattern. If you increase the input then the number of steps to solve the problem will be increased. Lets take an example of finding the sum of elements in an array.
var arr = [1,2,3,4];
var sum = 0;
for(int i=0;i<arr.length;i++){
sum=sum + i;
}
console.log(“Sum=”,sum);
In the given example if we increase the size of the input i. e. array, the number of operation is going to increase. It follows the linear patterns.
Big O(1)
Big O(1) notation is used when the number of operation that we need to perform for the solution is constant on varying the input. Lets take an example of printing the first element in an array. It’s going to be constant for any list with different sizes.
How to calculate the complexity of summation problem?
Lets consider the below code for calculation
var arr = [ 1,3,4,5,5,6];
var sum=0;
for(int i = 0; i< arr.length;i++){
sum=sum+arr[i];
}
console.log(“sum=”,sum)
The first statement in the program takes O(1) as it’s constant. It doesn’t depend upon the size of input, same with the second statement. The number of times the third statement will execute is depends upon the input, so it will be O(n). The last statement is constant. so the complexity will be
O(1) + O(1) + O(n) +O(1) = O(3+n);
The rule of Big O computation states that remove all the constant, so if we remove 3 then the complexity becomes O(n). In this way complexity is calculated using Big O notation.
Big O(n²)
The Big O(n2) is a notation used to define the complexity of the problem where the number of operation to solve the problem increases quadratically upon increase in input. Let’s consider the below problem of printing elements in two dimensional array.
var arr = [[1,2,3],[4,5,6],[7,8,9]];
for(int i=0; i< arr.length;i++){
for(int j=0;j<arr[i].length;j++{
console.log(‘arr[’,i,j’]=’,arr[i][j]);
}
}
So here the statement 4 will run 9 times which is square of 3, which is nothing but the size of input. If you increase the size of input to 4 then the statement 4 will run for 16 times that’s why the complexity of such kind of problem where nested loop is there is O(n²).
Big O(n!)
The Big O(n!) complexity is used when the number of comparison required to solve any problem grows factorially. The solution with O(n!) is considered as the worst performance.
Space complexity
space complexity is calculated as amount extra space that program takes in order to solve the problem. Let’s take an example of sum of all the elements in an array.
var arr = [ 1,3,4,5,5,6];
var sum=0;
for(int i = 0; i< arr.length;i++){
sum=sum+arr[i];
}
console.log(“sum=”,sum);
So extra space required to solve the problem is variable sum and i.
Space Complexity = O(1) + O(1) = 0(2) → O(1)
The above example has Big 0(1) space complexity.
Let’s take an another example of finding out the square root of each element in an array.
var arr = [ 1,3,4,5,5,6];
var result = [];
for(int i = 0; i< arr.length;i++){
result[i] = arr[i] * arr[i];
}
console.log(“result=”,result);
In the above example amount of extra space required is equal to size of input array. It has Big O(n) space complexity.
Arrays
Its time to discuss each data structure one by one. Let’s start with an array.
Array is collection of the values or set of values of similar type. Why it is a collection of similar type and not different types, you will get to know very soon. In some language like JavaScript you can create the array of different type of elements as well.
Suppose you created an array, marks=[50,55,60,80], in memory array elements are stored at consecutive memory location. If you are creating the array of an integer then each element is going to take the 4 byte i.e. 32 bit.
So after every 32 bit next element of an array will be stored so let’s say the first element which is 50 will be store at memory location OX11 which is hexadecimal representation of memory address, next element will be stored after 4 position, as at every address 1 byte of data will be stored.
There are 6 major operations that are performed on any data structure. These operations are insert, update, delete, search,sort and traverse/Access each element in data structure.
Insert element into an array:
To insert element into an array, array element from the insertion index need to be shifted. In worst case scenario, if element to be inserted at index 0 then all the elements need to be shifted. The complexity of insert operation on an array is 0(n)
Update element at given position in an array:
To update the element at a given position in an array. Only one operation is required. Hence, the complexity of this operation is O(1).
Deleting element at given position in an array:
To delete an element at given position requires more than operation in worst case scenario. Suppose you want to delete first element in an array, all the element except first element needs shifting by one position. Hence, the complexity of this operation is O(n).
Searching element in an array:
To search any element in an array, worst case scenario is that the element it self is not present in an array. In this case comparison is required with each element in an array. Hence, the complexity of this operation is O(n).
Sort element in an array:
To sort an array, there are different type of solution available like bubble sort, merge sort, selection sort, quick sort, etc. Each solution has different complexity that we will discuss more detail in upcoming.
Traverse/Access each each element in an array:
The complexity of traversing each element in an array is O(n) as n operations needed to traverse through an array.
Linked List
Linked List is the linear data structure which element in linked list holds the data as well as address of the next element. This data consist of collection of nodes. In the below linked list each node has two values, data and address of the next element.
The first element in the linked list is called as Head/Start and last element is called as Tail/End of linked list.
There are two type of linked list singly linked list and doubly linked list. The example saw earlier is a singly linked list and has only one pointer which points to next element. In doubly linked list there will be two pointers one points to the previous element and other points to the next element as showed below.
Circular linked list
The circular linked list is the type of linked list where there is no head and tail after tail element again head is pointed, so it is going to be a circular as shown below.
Linked list complexities
We discuss the linked list complexities when performing the various operations on the linked list. We will discuss the complexities of access, insert, delete and search operation.
Access.
To access any element from the linked list. in worst case scenario we need to traverse through all the elements in the linked list. Hence, the complexity of this operation is 0(n)
Insert
To insert an element at given position in linked list we just have to perform following steps
i) Create a node with data and next equal to next of the position of element in the linked list.
ii) Next of the element already present at the position is equal to the address of the new node we are inserting.
There are two steps in inserting a element in linked list if we want to add at specific position and this will be constant for any size of linked list. Hence the complexity of this operation is 0(1).
Delete
To delete an element at given position in linked list we just have to perform following steps
i) Delete a nod
ii) Specify the next of deleting node to next of previous element.
There are two steps in deleting a element in linked list if we want to delete at specific position and this will be constant for any size of linked list. Hence, the complexity of this operation is 0(1).
Search
In order to search any element in the lined list , we have to traverse through all the elements in the list, in worst case scenario if the element is placed at tail of the linked list. Hence the complexity of this operation is 0(n).
Stack
The stack is the simple data structure which works on the principle of last in first out. A good real-life example of a stack is the pile of dinner plates that you encounter when you eat at the local cafeteria: When you remove a plate from the pile, you take the plate on the top of the pile. The plate you kept first that will be removed last.
Operations on the stack
There are three operation that we can perform on the stack pop,push,peek. Lets see the operation one by one.
Pop
This operation removes the element from the top of the stack and returns removed element.
Push
This operation inserts the element at the top of the stack.
Peek
This operation returns the element at top of the stack without removing it.
The stack can be implemented using Arrays or Linked list. The complexity of the operation pop and push of stack implemented using the linked list is better than the stack implemented using the arrays. As discussed earlier the complexities of insert and delete operation on array is 0(n), complexities of same operation on linked list is 0(1).
Queue
The queue is data structure which works on the principle of first in first out. A real time example for queue is people waiting for a bus on bus stand. first passenger in the long standing queue enters the first into bus.
When you add element in to the queue then it will be added at first position in queue and when you remove it, it will be removed from the tail or last position of the list.
Operations on queue
The operations that we perform on the queue are dequeue, enqueue, peek,
Dequeue
The operation of removing the element from the queue is called as dequeue. This removes the element from tail of the queue and returns deleted element.
Enqueue
The operation of inserting the elements in the queue is called and enqueue. This operation inserts the element at the head of queue.
Peek
This operation return the element at the tail of the queue without removing the element in the queue.
The queue can be implemented using Arrays or Linked list. The complexity of the operation pop and push of stack implemented using the linked list is better than the queue implemented using the arrays. As discussed earlier the complexities of insert and delete operation on array is 0(n), complexities of same operation on linked list is 0(1).
Hash Table
The hash table is data structure where elements are stored in key value pair. There is a hashing function that returns the index value using the key and value will be stored at generated index. Lets take an example of color and their hex value representation.
RED →#FF0000
GREEN →#00FF00
BLUE →#0000FF
YELLOW →#FFFF00
Like this there are hex value for each color. If we sore this color data in array/linked list to get the hex value from the color name requires O(n) complexity. If we store this information in HashTable then the complexity of the insert, delete and search is going to be 0(1).
When any value that you want to store in to the HashTable first hash value is calculated with the help of hash function. The hash value decides position of the element to store. If we store RED into the HashTable then first the hash value is calculated. Suppose the hash function for calculating the hash value is as below
i. Calculate the ASCII value for each character.
ii. Add all those value
iii. Calculate the modulus of 4 of the value, this will be the index to store the value.
For RED key the hash value will be 82+69+68 = 219%4 = 3
The hex value of color RED will be stored at 3rd position in an HashTable.
Hash Collision
There will be situation where two key will generate same hash value. This situation is called as the hash collision. This situation can be resolved by using different techniques
Chaining : The elements that generates same hash values are chained using the linked list. If the size of chain increases then the complexity of searching is going to be 0(n).
Linear Probing: In this technique if the collision happens then value will be stored at next available slot.The probe interval for this technique is 1.This technique is good for caching the position. But failed clustering as it will be difficult to find the next free slot.
Quadratic probing:
In this technique the quadratic function is used to calculate the probe interval. This method balances clustering and caching.
Double hashing:
In this technique second hash function will be used to calculate the probe interval, this technique is worst for caching and doe not have any clustering issue.
Coalesced hashing:
This technique is combination of both chaining and open addressing, when the collision happens then element will be stored at next free slot but linked to calculated hash value.
Tree
It is the type of data structure in which elements are linked in hierarchical structure. Following are the important concept in Tree data structure.
Root:- It is the parent node of all the node in the tree.
Parent:- The parent is the node from which other nodes are connected.
Child:- It is the node which is connected from parent.
Edge:- Nodes in the tree are connected by using the edges.
Sibling: Sibling are the nodes which has same parent node.
Leaf Node: The node which does not have any child node is called as leaf node.
