Question

Please give a detailed examples of data structures and how we could analyze it

Answer 1

Data Structure(Overview)

A Data structure is a special format for organizing and storing data using. General data structure types include arrays, files, linked lists, stacks, queues, trees, graphs and so on. For example, we have some data which has, an employee's name is "Arjun" and employee id of 2001. Here "Arjun" is of String data type and employee id is of the integer data type.
We can organize this data as a record like an Employee record, which will have both employee's name and id in it. Now we can collect and store player's records in a file or database as a data structure. For example "Madhav" 2002, "Mahesh" 2003.
Data Structures help to store ordered data using any programming language or method so that various operations can be performed on it easily.

Basic types of Data Structures

Depending on the organization of the elements, data structures are classified into two types:

1. Linear data structures: Elements are accessed in sequential order but it is not compulsory to store all elements sequentially. Examples: Linked Lists, Stacks and Queues.
2. Non – linear data structures: Elements of this data structure are stored/accessed in a non-linear order. Examples: Trees and graphs.:

The data structures can also be classified on the basis of the following characteristics:

Characteristic	Description
Linear	In Linear data structures, the data items are arranged in a linear sequence. Example: Array
Non-Linear	In Non-Linear data structures, the data items are not in sequence. Example: Tree, Graph
Homogeneous	In homogeneous data structures, all the elements are of the same type. Example: Array
Non-Homogeneous	In a Non-Homogeneous data structure, the elements may or may not be of the same type. Example: Structures
Static	Static data structures are those whose sizes and structures associated memory locations are fixed, at compile time. Example: Array
Dynamic	Dynamic structures are those which expand or shrinks depending upon the program's need and its execution. Also, their associated memory locations changes. Example: Linked List created using pointers

There is no specific way to analyze any data structure but as data structures can be programmed, it all depends on the way it is programmed. To be specific it depends on the efficiency of the algorithm used for programming the data structure.

So the goal of the analysis of algorithms is to compare algorithms (or solutions) mainly in terms of running time but also in terms of other factors (e.g., memory, developer effort, etc.).

The types of analysis are:-

1. Time Complexity
2. Space Complexity

Space Complexity

Its the amount of memory space required by the algorithm, during the course of its execution. Space complexity must be taken seriously for multi-user systems and in situations where limited memory is available.

An algorithm generally requires space for the following components :

• Instruction Space: Its the space required to store the executable version of the program. This space is fixed but varies depending upon the number of lines of code in the program.
• Data Space: Its the space required to store all the constants and variables(including temporary variables) value.
• Environment Space: Its the space required to store the environment information needed to resume the suspended function.

Time Complexity

Time Complexity is a way to represent the amount of time required by the program to run until its completion. It's generally a good practice to try to keep the time required minimum so that our algorithm completes its execution in the minimum time possible.