Monday, 12 June 2017

Data structure tutorial for beginners

1.     What is Data structure?

How effectively we are storing the data it’s called as data structure.

Data structure is particular way of storing and organizing data so that it can use efficiently.
Structuring the data which really help us to manage it properly.

Let’s take the example of Dictionary (defined into liner form), Cash book (defined in tabular form)

It is not a language it’s a set of algorithm or process which help to store data effectively.


Data structure à Algorithm à Abstract Data type à Set of rules
Algorithm à Array, Stack, Queue, linked list, tree, graphs

Algorithm (data structure) is divided into two types ::


·         Liner Data structure – Data are structure in sequential format one data connected to another. Like array, stack, queues, Linked list.

·         Non Liner Data structure - Non Liner format. One data connect to multiple data. example Trees and graph

2.     Abstract Data Type in Data structure

 Data structure is all about creating abstract data type.

Combination of data structure and their operation are known as Abstract Data Type.

Store the given number of element into any type of element. Read element by position or modify element by position is called as ADT.

Like: Arrays, Linked List, Stack, Queue, Tree, Graph etc.

2.1 Array:


Store the given number at given datatype, write & read element in position.
Int i[10];

·         It holds more than one element. Finite number of collections.
·         Homogenous data type.
·         Index based
·         Doesn’t follow any algorithm.
·         Derived datatype


How to initialize Array.

Int arr[5] = { 10, 20, 30,40, 50};
0
1
2
3
4
10
20
30
40
50
2046
2048
2050
2052
2054

Number of arr[n] is called  size of array.


Calculate the location of array value as (Base address + size of int * n)  e.g. a[3] :: 2046 + 2 *3 :: 2046 + 6 :: 2052

The process of one multiplication and one addition. This two operation take the constant time and  we can say that array access can performed in constant time.

Array Dimension 
A[n] : it is one Dimension  array
arr[3]

0
1
2
10
20
30
2046
2048
2050

A[n][m] : it is two Dimension  array
e.g : way of representing data Arr[2][3]


0
1
2
0
20
30
40
1
12
10
12
2
10
4
5
3
6
78
8



2.2 Dynamic Array :


Empty List has 0 size, insert, Remove, count, Read & modify element at the position.

When array is full create, create a new larger array, free the memory for the previous array. But it is very costly operation to insert the new element in the given position and shift the values.

Access – Read/write at an index.  Constant  time O(1)
Insert – O(n).
Remove – O(n)
Add – O(n)

2.3 Linked List


It is liner data structure , its collection of element. Element is called as Node, each element has value(data) and reference of Next node. Microsoft Provide strongly typed linked list LinkedList(T) in System.Collections.Generic namespace.

Linked List is mainly three types::

Singly Linked List:  It contains the value and reference of next node. Last node next reference will be null.

Benefits:   It is dynamic data structure, where length of array is predefined.


Doubly Linked List: It contains data and 2 references. One of the next reference and another for the previous reference.

Benefits:  Doubly linked list offers easy implementation of many operations, whereas singly linked list requires more info for the same operation. e.g. Deletion of singly linked list, we need a pointer to it for previous node.
It traverses in both forward and backward direction.


Circular Linked List :  Here last nodes reference will be head or first element.

2.4 Stack :


Stack is liner data structure, it  is ADT which is used in most of the programming language. It is follow the rule of FILO ( First In Last Out) or LIFO (Last in first out).

Mainly two basic operation perform in stack.

Push :  Add new items into stack. If the stack is full than it is said to be overflow condition.

POP : Remove the items from the stack.

We can check the status of stack as like:

Peek() : Get the top data element of the stack.

IsFull() : Check if the stack is full.

IsEmpty() : Check if the stack is empty.

2.5            Queue


Queue is liner data type like Stack; treat as an abstract datatype in Data structure. Unlike array it is open ended from both side.

One end is always use to insert data is called enqueue. Another is used to remove the data is called as Dequeue.

It follow the process of FIFO(First in first out). The data which store first will be accessed first.
Basic Operations in Queue:

Enqueue() : Add (store) an item into queue.

Dequeue() : Remove the items from the queue.

Peek() : Get the element at the front of the Queue.

Isfull() : Checks if the queue is full.

IsEmpty() :  Check if the queue is empty.

2.6. Trees        


Tree is non liner data type; it’s a ADT in data structure.  You can see the data in the tree as like Multiple nodes, where each node has some associated data and set of children. Nodes are in two parts, parent and children. 

 Node just beneath of the other node are called as children node. Node just above the node is called as parent node. There is Root in all the tree, for root node don’t have any parent.

e.g.  Organization structure of any company is in tree format.

There is special kind of tree where each parent node is having only two children which is called as Binary Tree.




Nodes which don’t have any children which is called as Leaf node. Nodes which have one or Two children are referred as internal nodes.

3.     Analysis of algorithm


Time & Space – less time and space is good algorithm
Calculate the good algorithm by Rate of Growth; the rate at which the running time increases as a function of input is called rate of growth.

 Analyzing of time complexity

Running time depends upon:

a.       Single or multiprocessor
b.      Read/write speed of memory
c.       32 bit or 64 bit
d.      Input [ we need to check this in our programming]
Rate of growth of input machine.

Before calculating the time you need a model computer. Let’s take an example and consider 1 unit time for arithmetical and logical and 1 unit for assignment and return.


Sum of number :
SumofNumber( a,b)
{
Return a+b; à 1 unit for sum and 1 Unit for return so total time for it is 2 Unit.
}
Let’s take another  sum of n numbers in array;



Lets see the calculation for simple, liner and  complex application.


4.     Type of analysis


To analysis the algorithm we need to know on what input algorithm is taking less time and what will take more time.

Worst case

Average case

Best case


Take an example of 10 number which you need to arrange in order, if the number is already in order than it is best case. Suppose it distorted like any thing than it can be the worst case and Average case is middle of it.

5.     Asymptotic Notation


For all three case we need to identify the Upper and Lower bounds.

Syntax representation of bounds are :

Big o notation – finding the upper bound it is denote by O(n)

Omega notation – finding the lower bound.

Theta notation – finding the upper and lower bound both

6.     Recursion of Data structure


1.       The function which will call itself is called as recursion.
2.       Recursive code is generally shorter and easier to write than iterative problem.
3.       It terminate when base case has reached.
4.       Each recursive call requires extra space in the stack memory. [In term of memory it is not good if more recursive]
5.       You need to have some point where you need to close the recursion.
e.g:


6.1. List of application for recursion.


a.       Fibonacci Series
b.      Factorial of number
c.       Greatest common divisible
d.      Tower of Hanoi
e.      Graph traverse (DFS & BFS)
f.        Tree traversal
g.       Merge sort and Quick Sort
h.      Back tracking algo

6.2. Fibonacci series:  

Sum the last two numbers.
It is as 0 1 1 2 3 5 8 13 21 34 55 89 …
To get the Fibonacci of Fib(5) you need to add fib(4) and fib(3)
Fib(5) = fib(4) + fib(3)
Fib(4) = fib(3) + fib(2)
Fib(3) = fib(2) + fib(1)
Fib(2) = 1
Fib(1) = 1

Print the Fibonacci number is Recursive function
class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Enter Number");
            int val = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine("Fibonacci series is :: ");
            for(int i = 1;i <= val;i++)
                Console.Write(Fib(i) + ", ");
        }

        public static int Fib(int n)
        {
            if (n == 1 || n == 2)
                return 1;
            return ( Fib(n -1)  + Fib(n - 2));

        }
    }

Program to check that number is Fibonacci or not
class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Enter Number");
            int val = Convert.ToInt32(Console.ReadLine());

            /// Print febonacci series
            //Console.WriteLine("Febonacci series is :: ");
            //for(int i = 1;i <= val;i++)
            //    Console.Write(Fib(i) + ", ");


            /// Is that fibonacci number
            Console.WriteLine("It is {0}  Fibonacci", IsFibnacci(val) == true ? " " : " not" );
        }

        public static int Fib(int n)
        {
            if (n == 1 || n == 2)
                return 1;
            return ( Fib(n -1)  + Fib(n - 2));

        }

        public static bool IsFibnacci(int n)
        {
            return IsperfectSquare(5 * n * n + 4) || IsperfectSquare(5 * n * n);
        }

        public static bool IsperfectSquare(int x)
        {
            int half = x/2;
           
            int i =1;
            bool isperfectsquare = false;
            while( i < x/2)
            {
                if(i * i == x)
                {
                    isperfectsquare = true;
                }

                i++;
            }

            return isperfectsquare;
        }
    }


6.3. Factorial Number

 Multiplication of values till number pass.
5! = 5 X 4 X 3 X 2 X 1
Fact(5)  = 5 X fact(4)
Fact(4) = 4 X fact(3)
Fact(3) = 3 X fact(2)
Fact(2) = 2 X fact(1)
static void Main(string[] args)
        {
            Console.WriteLine("Enter Number");
            int val = Convert.ToInt32(Console.ReadLine());

            /// Print Factorial number
            Console.WriteLine("Factorial series is :: {0}", fact(val));
           

        }

        public static long fact(int n)
        {
           if( n >0)
               return (n * fact(n -1));
           else
               return 1;
        }

6.4. Greatest common divisible


 Finding the greatest common divisible between the numbers.
E.g GCD of 4 and 6
4 = 4 2 1
6 = 6 3 2 1
So, 2 is greatest common divisible GCD(4,6)
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Enter 1st Number");
            int val1 = Convert.ToInt32(Console.ReadLine());

            Console.WriteLine("Enter 2nd Number");
            int val2 = Convert.ToInt32(Console.ReadLine());


            /// Get the gretest common division
            Console.WriteLine("GCD is :: {0}", GCD(val1, val2));
           

        }

        public static int GCD(int n,int m)
        {
            if (n == m)
                return n;
            if(n % m == 0)
                return m;
            if (m % n == 0)
                return n;
            if (m < n)
               return GCD(n % m, m);
            else
               return  GCD(m % n, n);
        }

    }


7.     Searching Techniques

In data structure we come across many ways to search the particular data in an array or list.

7.1. Liner Search

Liner search or sequential search are technique on which every item will check sequentially and match with the given item. If find the particular match than it will return that item.
Let’s see the algorithm for it.
Arr[6] = 12, 56, 18, 90, 38, 67, 72
Search value = 18
Step 1: Initialize i which work as count of array
Step2: Check condition if i <= arr.lenth -1
Step3: if value == arr[i] than break else Continue
Step 4 : increase count of i++. Goto step 2
Step 5 : Print : value found in ith position.
Step 6: Exit

The complexity of liner search algorithm in O(n).

No comments:

Post a Comment

Others

You will like to read it