The Audio blog for this is in here
Data Structures:
Data Structures are used in computers to store and retrieve data data. Data structures are used to organize data so that they will meet the requirements of the applications. Data type and Data Structures are similar. Data type refers a well defined format of storing data and applying operations over the data. Data Structures are implementations of abstract data types.
Some examples of data structures are Stack, Queue, Hash, Trees etc., By abstract data type we mean that , Stack is an abstract data type and it can have operations such as push(x), pop(x), is_empty(). But the implementation is programmer defined.
Class Stack {
Data_type data;
Date_type pop()
{ }
void push(Data_type x)
{}
bool Isempty()
{}
}
The above mentioned stack is just an abstract class and the implementation can use either an array or linked list. For example ,
Class array_stack : public Stack{
Stack()
{a = new (size of Data_type * N);,i=0;}
Data_type pop()
{
return a[i--];
}
void push(Data_type x)
{
a[++i] = x;
}
bool Isempty()
{if (i>=0) return false; else return true;}
}
Time and Space Complexity:
Time complexity is a measure of the time taken for a particular code to execute. It is usually represented using a 'O' notation. Here we will use the term n- no of inputs. Generally the time taken for order of execution in ascending order is 1, log n, n, nlog n, n^2,.... The space complexity is represented in the same manner. It is the space required for computing the given problem.
Uses of data Structures :
Data structures are used based on the particular application.
When you want to retrieve the max of the elements you are storing you can go for max heap the inverse applies for min heap. Queues can be used when there is a particular resource and many entities need the same resource. Then the queue can be used to order the entities based on the time of arrival.
Array is a simple method of storing data where you can access the data easily if you know the index where it is stored. The uses of data structures are very large and it is not easy to list them all within the space.
Which data structure is better ?
No two data structures can be compared. Each one is best suitable for the particular. Comparing two data structure is like comparing a world class piano artist with a world heavy weight champion. Sounds dumb right.!! If you wanna hear good music you can watch the artist performance. To watch a gr8 fight go for the boxer.
So the point i am trying to make hear is that the data structures which you choose should best choose your application. If you want retrieval of data instantly go for hash. If you want to get the extremes of the data go for heaps.
How to arrive at a particular data structure ?
Having a good data structure for a problem depends on the ability to map a data structure to the given problem. Or else you need to check each data structure until you come up with the best one.
Consider the given problem, if there is a string containing braces '{' and '}'. A string is valid if '{' contains a '}' pair following it later in the string. You need to find valid if the string is valid or not.
So what data structure you will use..????
A array is fine but it requires an extra storage and the execution time will be O(n^2). A hash map can be used by mapping the open braces to a list containing their position. So when a closed brace comes check for a preceding open brace in the list and delete it from the hash map. Stop the process until the string ends or you get a unmatched close brace.
A stack will be the good choice as it doesn't require extra memory and the execution time is O(n). So the best possible solution here is a stack.
Sometimes a single data structure cannot give a solution and more than one DS need to be coupled to get the output efficiently.
List:
List are dynamic data structures where you can allocate memory and remove the memory of the list members during the runtime of the program. Each list has a self referential pointer and you need the pointer to move through the list. The list is not a preferable DS if you need to access elements faster. And the pointer manipulations are somewhat tricky so the implementation requires caution.
Lists are categorized as singly linked list, Doubly linked list, circular linked list based on the link structure.
Sorting :
Sorting is to arrange the elements present in a ordered way. Programmers have developed a number of sorting methods. The best sorting methods offer a running time complexity of O(nlog n ). They are merge and quick sorts.
Both these sorts come under divide and conquer methods. By divide and conquer we divide the bigger problem, solve those subproblems and recursively you will end up in solving the problem.
For example, If you need to make 500 students in height order. Split the student into groups of 20, order them and then joining the ordered groups. It will be better than picking the next taller student each time from the group of 500.
Searching :
Searching is searching for a particular data in the Data Structure. Hash offers a better search having a time complexity of O( 1 ). DFS(Depth First Search) is a method of searching the data. The algorithm for the DFS is,
Get the Root
Push root into the Stack
While (The Stack is not empty)
Pop stack top into temp
if (Temp contains the data)
return the data
push the children of the temp into the stack
This can be done using recursion also. But it is better to present it this way as recursion may lead to stack overflow.
For Sorted data in a array you can apply binary search.
Data Structures:
Data Structures are used in computers to store and retrieve data data. Data structures are used to organize data so that they will meet the requirements of the applications. Data type and Data Structures are similar. Data type refers a well defined format of storing data and applying operations over the data. Data Structures are implementations of abstract data types.
Some examples of data structures are Stack, Queue, Hash, Trees etc., By abstract data type we mean that , Stack is an abstract data type and it can have operations such as push(x), pop(x), is_empty(). But the implementation is programmer defined.
Class Stack {
Data_type data;
Date_type pop()
{ }
void push(Data_type x)
{}
bool Isempty()
{}
}
The above mentioned stack is just an abstract class and the implementation can use either an array or linked list. For example ,
Class array_stack : public Stack{
Stack()
{a = new (size of Data_type * N);,i=0;}
Data_type pop()
{
return a[i--];
}
void push(Data_type x)
{
a[++i] = x;
}
bool Isempty()
{if (i>=0) return false; else return true;}
}
Time and Space Complexity:
Time complexity is a measure of the time taken for a particular code to execute. It is usually represented using a 'O' notation. Here we will use the term n- no of inputs. Generally the time taken for order of execution in ascending order is 1, log n, n, nlog n, n^2,.... The space complexity is represented in the same manner. It is the space required for computing the given problem.
Uses of data Structures :
Data structures are used based on the particular application.
When you want to retrieve the max of the elements you are storing you can go for max heap the inverse applies for min heap. Queues can be used when there is a particular resource and many entities need the same resource. Then the queue can be used to order the entities based on the time of arrival.
Array is a simple method of storing data where you can access the data easily if you know the index where it is stored. The uses of data structures are very large and it is not easy to list them all within the space.
Which data structure is better ?
No two data structures can be compared. Each one is best suitable for the particular. Comparing two data structure is like comparing a world class piano artist with a world heavy weight champion. Sounds dumb right.!! If you wanna hear good music you can watch the artist performance. To watch a gr8 fight go for the boxer.
So the point i am trying to make hear is that the data structures which you choose should best choose your application. If you want retrieval of data instantly go for hash. If you want to get the extremes of the data go for heaps.
How to arrive at a particular data structure ?
Having a good data structure for a problem depends on the ability to map a data structure to the given problem. Or else you need to check each data structure until you come up with the best one.
Consider the given problem, if there is a string containing braces '{' and '}'. A string is valid if '{' contains a '}' pair following it later in the string. You need to find valid if the string is valid or not.
So what data structure you will use..????
A array is fine but it requires an extra storage and the execution time will be O(n^2). A hash map can be used by mapping the open braces to a list containing their position. So when a closed brace comes check for a preceding open brace in the list and delete it from the hash map. Stop the process until the string ends or you get a unmatched close brace.
A stack will be the good choice as it doesn't require extra memory and the execution time is O(n). So the best possible solution here is a stack.
Sometimes a single data structure cannot give a solution and more than one DS need to be coupled to get the output efficiently.
List:
List are dynamic data structures where you can allocate memory and remove the memory of the list members during the runtime of the program. Each list has a self referential pointer and you need the pointer to move through the list. The list is not a preferable DS if you need to access elements faster. And the pointer manipulations are somewhat tricky so the implementation requires caution.
Lists are categorized as singly linked list, Doubly linked list, circular linked list based on the link structure.
Sorting :
Sorting is to arrange the elements present in a ordered way. Programmers have developed a number of sorting methods. The best sorting methods offer a running time complexity of O(nlog n ). They are merge and quick sorts.
Both these sorts come under divide and conquer methods. By divide and conquer we divide the bigger problem, solve those subproblems and recursively you will end up in solving the problem.
For example, If you need to make 500 students in height order. Split the student into groups of 20, order them and then joining the ordered groups. It will be better than picking the next taller student each time from the group of 500.
Searching :
Searching is searching for a particular data in the Data Structure. Hash offers a better search having a time complexity of O( 1 ). DFS(Depth First Search) is a method of searching the data. The algorithm for the DFS is,
Get the Root
Push root into the Stack
While (The Stack is not empty)
Pop stack top into temp
if (Temp contains the data)
return the data
push the children of the temp into the stack
This can be done using recursion also. But it is better to present it this way as recursion may lead to stack overflow.
For Sorted data in a array you can apply binary search.
No comments:
Post a Comment