Introduction

Introduction to Data Structure

Data is a integral part of our application or programs.
- Program is a set of instruction which performs operations on data to get some results.
We should know about these terms:
1. Data structure
2. Database
3. Data warehouse
4. Big Data

Data structure

It can be defined as arrangement of collection of data items so that they can be utilized efficiently and operations on that data can be done efficiently.
The arrangement and operation on data take place inside the main memory and during the execution of a program.
During the execution of the program, how the program will manage data inside the main memory and perform the operations that is data structure.

How the program utilizes data and how they put the data in inside the main memory? ↓ ↓ ↓

Database

When data is larger in size or commercial data (used in businesses like banks, retail stores, etc.) they will have lot of data and they will have some organized data in the form of database table or relational data.

Data warehouse

We have talked about commercial data that is data used in businesses, so they will have huge amount of data and it will grow day by day.
The large size data may not be used daily like many year old data.
Commercial data can be categorized into two parts:
1. Operational data → used daily.
2. Legacy data (old/historical data) → data kept in storage and if required we can fetch the data and use it.
So, that historical data is kept on array of disk as it is historical data of any commercial firm, this storage is data warehouse.
For commerical firm this data warehouse are helpful for analyzing the business.
The algorithm written for analyzing the warehouse data are known as data mining algorithms.

Big data

The data avialable in internet like data about things, people and places, by analyzing this data, decisions are taken that is for management, governance, businesses analysis.
Study related to storing and utilizing that large size data is big data.

Short summary:
1. Data structure: arrangement of data in main memory.
2. Database: arrangement of data in disk.
3. Data warehouse: array of disk.
4. Big data: large data used in internet.

Static vs Dynamic Memory Allocation

Here we will discuss the following:

About main memory
How a program use memory
Static allocation
Dynamaic allocation

Main memory

How program uses Main memory?

Now we will discuss that if there are sequence of function calls then how the memory is allocated for these functions inside the stack?

How heap memory is utilized by a program?

Heap means piling things up.
Heap is used in two cases:
1. If the things are properly organized like a tower.
2. If the things are not organized.
Heap term can be used for both organized things and not organized things.
In main memory, heap is an unorganized memory.
Stack memory is organized.
Heap memory should be treated as a resource, means when required it should be utilized and when we don't require it we should release the memory.
Program cannot directly access heap memory so they use pointer to access heap memory.

Physical vs Logical Data Structures

Introduction to various data structures.
Mainly categorized into two:
1. Physical Data structures
2. Logical Data structures

Physical Data Structures

The two physical data structures are:
1. Array
2. Linked list
By combining array and linked list we can create various physical data structure.
The reason we call these physical data structure is because they defines how the memory is organized, how the memory is allocated.

These two DS are physical because they define how the memory should organized for storing the elements or data. So, these are more related to memory.

Logical Data Stuctures

List of logical DS:
1. Stack
2. Queues
3. Trees
4. Graph
5. Hash table

Difference between Physical and Logical DS ↓

Stack: It works on a discipline called LIFO.
Queue: It works on a discipline called FIFO.
Trees and graph: These have hierarichal type structure.
Logical DS are actually used in applications.
To implement logical DS we either use either array or linkedlist.

Abstract Datatype

First we will know about data type:
- A data type is defined into two terms:
  1- Representation of Data
  
  2- Operation on Data
  - Arithmetic operations like +, -, *, /, %
  - Relational operations like <,>, <=,>=, !=
  - Increment and decrement operations
Abstract means hiding internal details.
- For performing operations on int datatype do we need to know, how they are performed in the binary form inside the main memory.
- We are concerning about declaring a variable and peforming various operations without knowing the internal details.
- So, these internal details are hidden from us so we can call it abstract.
- We have taken a primitive data type and understood the concept of abstract datatype.
Abstract datatype is related to object oriented programming language.
Using classes in object oriented programming we can define our own data types that are abstract.

Let us take an example of list that is collection of elements.

Operations on a list:
1. add(element) → adding an element to the end of the list. It is also called append(element).
2. add(index, ele) → adding an element at a given index. Here we have to shift element to insert the element. A.K.A 0 Insert(index, ele).
3. remove(index) → removing element by shifting element in its space.
4. set(index, ele) → changing an element at a given index. It is also called as replace(index, ele).
5. get(index) → getting the element at a given index.
6. search(key) → searching an element in a list. The result of search is that it returns an index. It is also known as contains(key).
7. sort() → arraning list element in some order.

Time complexity

Time complexity basically depends upon the procedure that you are adopting.
Now using example we will see what procedure will take what amount of time.

Working with array and list.

In a list if we have 'n' elements and we are going through it just once then the time is 'n'. This 'n' is represented as a degree, O(n). [order of n]

Either from procedure or program code we can find time complexity.

                           
                           
                            for(i = 0; i < n; i++)
                            {
                                // searching 
                                // adding
                            }
                            // here 'i' goes from 0 to 'n' so it is O(n).

For each element in a list if there is again a comparision that means there are two for loop, one inside another with O(n²) time complexity.

                            
                            
                             for(i = 0; i < n; i++)
                             {
                                for(j = 0; j < n; j++)
                                {
                                    // processing
                                }
                             }

                            
                            
                             for(i = 0; i < n; i++)
                             {
                                for(j = i+1; j < n; j++)
                                {
                                    // processing
                                }
                             }
                             // O(n^2)

When a list is successively divide in two half until it reaches 1 that is represented as log₂ n

                            
                            
                             for(i = n; i > 1; i = 1/2)
                             {
                                 // processing
                             }
                             // O(log n)

Matrix

When we are processing upon a matrix of dimension nxn then it will require n² amount of time (if you are processing all the elements).
If you are processing single row or column then it take O(n) time complexity.

                           
                           
                            // matrix processing code

                            for(i = 0; i < n; i++)
                            {
                                for(j = 0; j < n; j++)
                                {
                                    // processing
                                }
                            }

Space complexity

If we want to know how much space is consumed in main memory during the execution of the program.
For array with 'n' elements its O(n). Space is depended upon 'n'.
For matrix O(n²).

Finding time complexity from program code.

We assume that every simple statement in a program takes one unit of time.

                   
                   
                    void swap(x, y)
                    {
                        int t;
                        t = x; // 1
                        x = y; // 1
                        y = t;// 1, each statement take 1 unit of time as it is simple assignment. 
                    }
                    time f(n) = 1 + 1 + 1
                              = 3 (constant)
                              = O(1)

                   
                   
                    int sum(int A[], int n)
                    {
                        int s, i;
                        s = 0; // 1 unit
                        for( i = 0; i < n; i++) // condition will be checked for n + 1 time and increment will be n time so total = n + 1 + n + 1 = 2(n + 1)
                        { // i = 0 assignment = 1 time
                            s = s + A[i]; // n 
                        }
                        return s; // 1
                    }
                    /* total = 1 + 2(n+1) + n + 1 
                             = 1 + 2n + 1 + n + 1
                             = 3n + 3
                             = O(n) as the degree of n is 1 */

                   
                   
                   void Add(int n)
                   int i, j;
                    for(i = 0; i < n; i++)
                    {
                        for(j = 0; j < n; j++)
                        {
                            C[i][j] = A[i][j] + B[i][j];
                        }
                    }
                    // O(n^2)

                   
                   
                    fun1()
                    {
                        fun2();
                    }

                    fun2()
                    {
                        for(i = 0; i < n; i++)
                        {
                            // processing
                        }
                    }
                    // O(n)