Data Structure
Data and structure forms Data Structure. we are arranging data inside the memory logically. this is not a real data structure we implement in physical memory. but we logically arrange data inside memory using various structures which are usefull to do operations on the data. data Structure allows us to perform various operations like inserting, deleting, traversing, searching etc.
we can perform number of operations.data structure helps to build scalable applications. world's top companies making use of data structure and making billions. worlds biggest search engine like Google focuses more on data structure , algorithm skillset.facebook uses graph data structure to manage your and your friends post. data Structure gives us flexibility to handle big data easily. in simple words arranging information/data in specific structure. we have different types of structures like Array,linkedlist,stack, queue,graph,tree. many times we have questions like why we have to use data structure, why not we do using general programming? The answer is ,when you have big data like millions of people Using your application then you have millions and billion rows of data and multiple operations people perform using your application that time general programming doesn't work. so, we need data structure to make our application more accessible, flexible and productive.
Take a help of following menu to move step by step.
Data object
Data Object represents a container for data values.It is a place where data values may be stored and retrieved. Data Object has a unique location in computers memory that contains value. Data Objects can be:- Variables, Constants, Arrays etc.
A data object is a memory location that stores information used by the program. It is a location in memory with an assigned name. A variable is a name used in the program to refer to a data object. A data object is a region of storage that contains a value or group of values. Each value can be accessed using its identifier. Data Object Memory Location referred with name x Variable named x. Data object binded with Type,name, location, Value and components.
Data type
Data types are templates for Data Objects Data types defines the way the values of the types can be stored. It also defines the operations that can be done on the data. In case of data type the value of data is not stored as it only represents the type of data that can be get stored. For example:- int rollno; int is data type which tells the type of rollno attribute.
As data type already represents the type of value that can be stored so values can directly be assigned to the data type variables. Difference Between Data Object and Data Type A data object is a unique location Data types are templates
Data structure
Data Structure means organizing data in the Memory Location. There are various ways to organize data. Remember we have seen Arrays in C In Arrays the data is arranged sequentially or contiguously.
Types of Data Structures:-
Primitive Data Structure :- int, float, char, double. (Already studied in C)
Non Primitive Data Structure:- It is divided into two types:-
Linear Data Structure:- All data is arranged in Sequential manner
For example:- Arrays, Lists, Stacks and Queues
Non Linear Data Structure:- Data is arranged in Random manner For example:- Trees and Graphs
Difference Between Data Type and Data Structure
Data Type & Data StructureData Type is the kind or form of a variable which is being used throughout the program. It defines that the particular variable will assign the values of the given data type only Data Structure is the collection of different kinds of data. That entire data can be represented using an object and can be used throughout the entire program. Can hold values and not data, so it is data less Can hold different kind and types of data within one single object Examples: int, float, double Examples: stacks, queues, tree.
Primitive Data Structure
It is a predefined data structure. We cannot change or alter this. These data types can be used directly in the program for a specific task. For Example:- int, float char etc.
Non Primitive Data Structure
These are called as User Defined Data Structure.These are done using Primitive Data Structures. These are derived from primitive data type. For Example:- Arrays, Structures.
Common Operations done on Data Structure
- Creation
- Searching
- Sorting
- Insertion
- Deletion
- Updation
Abstract data types (ADT)
ADT are entities which have definition of Data and Operations but do not have implementation details. For Example:- Consider an Array. Abstract View Implementation View Array is Collection of similar data type elements int a[4]; It is stored in Sequential/ Contiguous Memory.
Advantages of ADT
- Encapsulation
- Information hiding
- Implementation details hiding
The ADT is a useful guideline to implement and a useful tool to programmers who wish to use the data type correctly.
Data structure Defination
A data structure describes the set of data objects and describes the set of operations which can be performed on elements of the data objects.
Definition - A data structure is a set of domains D, a designated domain € D a set of function F and a set of axioms A. The triple (D,F,A) denotes the Data Structure d and it will be usually written as d=(D,F,A), where- Domain (D):- denotes the data objects Function(F):- denotes the set of operation that can be carried out on the data objects. Axioms(A):- Denotes the properties and rules of the operations. i.e. semantics of the operations.
Advantages of data structure
- To manipulate and access the information
- Various operations can be performed on Data Structure.
- To improve the program efficiency.
- To improve the memory utilization or storage.
- Related data can be stored together and in the required format.
Why to analyze Algorithm
An algorithm is a stepwise procedure to solve a particular problem. A problem may have many algorithms which provides us the required solution.
As we have many alternatives for solving a particular algorithm we need to have a method of finding best possible algorithm. For this we need to compare the algorithm on the basis of time. We need faster algorithms which need less amount of time and less amount of memory space.While analyzing we need to find Time and space Complexity of an algorithm.
Space complexity
Space complexity is the amount of memory used by the algorithm (including the input values to the algorithm) to execute and produce the result. It is written as S(P)= C + S(P) where C is Fixed part and S(P) is variable part.
Fixed part is the space required to store data and variables independent of size of the problem. Variable part is the space required by variables depending on size of the problem.
Time complexity
It is the amount of time taken by the algorithm to execute.
It depends upon number of times a statement executes, which is Frequency of the statement. To find it there is one method called as Step count.
In this method , we count number of times one instruction is executed. To express Time and Space Complexity we use Asymptotic notations.
Asymptotic analysis
In Asymptotic Analysis, we evaluate the performance of an algorithm in terms of input size (we don’t measure the actual running time). We calculate, how the time (or space) taken by an algorithm increases with the input size.
We have three cases to analyze an algorithm:
- 1) Best Case
- 2) Average Case
- 3) Worst Case
Simple Example of Understanding Best, Worst and Average Case
Suppose we want to search an element from the array given below. Assume that array is int a[4]={10,20,30,40}; Assume you need to search an element 10 from the array.
This is the best case of the problem. How many Comparisons have we done here? Only 1 Comparison and the element is searched. Why it is the best case of the problem? Because you need to compare the element only once.
Suppose you are asked to search element 50 in the array. You need to compare the element 50 with all elements in the array from beginning. But even after the comparison you are not able to find the same. This is the worst case of the algorithm.
How many Comparisons have we done here? 4 Comparisions i.e.: in general if we have n elements in the array we need to do n comparisions. Why this is called as Worst Case of the Algorithm? It is called as Worst Case because we are doing maximum number of Comparisions here.ie: in general if we have n elements we need to do n comparisions.
Suppose we are asked to find element 20 from the array. We need to compare this element with the array two times. Total Comparisons needed are two. This is Average Case of the algorithm.
How many comparisions are needed? 2 Comparisions i.e.: In general if there are n elements we require n/2 comparisions. Why it is called as Average Case of the Algorithm? It is Average Case because we need to do 2 Comparisions ie:- half of the total no of elements. In general if we have n elements total number of comparisions needed are n/2.
Asymptotic notations
Asymptotic notations are mathematical tools to represent time complexity of algorithms for asymptotic analysis. The following 3 asymptotic notations are mostly used to represent time complexity of algorithms.
Big Oh(O)
: Big-Oh (O) notation gives an upper bound for a function f(n) to within a constant factor. It calculates the Worst Case Complexity of an Algorithm.
Omega (Ω)
:Omega (Ω) notation gives a lower bound for a function f(n) to within a constant factor. It calculates the Best Case Complexity of an Algorithm.
Theta (Θ)
:Big-Theta(Θ) notation gives bound for a function f(n) to within a constant factor. It calculates the Average Case Complexity of an Algorithm.
Big o notations
It is a notation used to find out the efficiency of an algorithm. It gives the algorithm complexity in terms of input size n We can find it out using basic computer steps(Algorithm used) It is machine independent.
Big – O notation focuses on Worst Case Complexity of the Algorithm. It defines upper bound of an algorithm. Definition:- The function f(n)= O (g(n)) [read as f of n is Big-O of g of n] if and only if there exist positive constants C and no such that f(n)<=C*g(n) where C>0 and n>=no and no >=1.
Example of big o notations
General Rule is:- For any polynomial of degree n p(x)= anxn + an-1xn-1 +……a0 p(x) is O(xn ) For Example:- 4 x3+7x2+12 is O(x3 ) f(n)< =C*g(n) where C>0 and n>=no and no >=1.
Omega notation
It is a notation used to find out the efficiency of an algorithm. It indicates the minimum time required for any algorithm for all input values Omega notation focuses on Best Case Complexity of the Algorithm.
It defines lower bound of an algorithm. In simple words, when we represent a time complexity for any algorithm in the form of big-Ω, we mean that the algorithm will take atleast this much time to complete it's execution. It can definitely take more time than this too.
Definition
:- The function f(n)= Ω(g(n)) [read as f of n is Ω of g of n] if and only if there exist positive constants C and no such that f(n)> =C*g(n) where C>0 and n>=no and no >=1.
Theta Notations
It is a notation used to find out the efficiency of an algorithm. It represents the Average Case Time Complexity. It is also called as tight bound of an algorithm.
It shows upper and lower bound of the algorithm. Definition :- The function f(n)= Θ(g(n)) [read as f of n is Θ of g of n] if and only if there exist positive constants C and no such that C1*g(n) <= f(n) < =C2 *g(n) where C1 and C2 constants are>0 and n>=no and no >=1.
Did you know worlds biggest companies like facebook, Google, Amazon, bitcoin uses data structures like graph, linkedlist,Arrays etc. If you want hike in your salary study data structure in deep.
we would love to hear from you about this article. please add comments and plus improve this article by giving your own opinions on these points. we are waiting your response.thanks for reading till end of the post
Comments
Post a Comment
Please give us feedback through comments