DATA STRUCTURE
Data Structure can be defined as the way of organizing and storing the data on the computer memory so that it can be used efficiently.
- The data structure is about rendering data elements in terms of some relationship, for better organization and storage.
- The data structure is classified into the following two categories
- Primitive Data Structure: They are basic structures and are directly operated by machine instructions.
- Non-Primitive Data Structure: These are more sophisticated and are derived from primitive data structures.
DIFFERENCE BETWEEN PRIMITIVE AND NON-PRIMITIVE DATA STRUCTURE
| Primitive | Non-Primitive |
|---|---|
| PrimitivePrimitive Data Structure are predefined in the programming language. | Non-PrimitiveNon-Primitive Data Structure are derived from Primitive Data Strucutre. |
| PrimitivePrimitive Data Structure never contain NULL value. | Non-PrimitiveNon-Primitive Data Strucutre may or maynot contain NULL value. |
| PrimitivePrimitive Data Structure have fixed size. | Non-PrimitiveNon-Primitive Data Structure have variable size. |
| PrimitivePrimitive Data Structure can be used to call functions to perform operation. | Non-PrimitiveNon-Primitive Data Structure cannot be used to call methods. |
| PrimitivePrimitive Data Structure stores data of only one type. | Non-PrimitiveNon-Primitive Data Structure can store data of more than one type. |
| PrimitivePrimitive Data Structure begins with lowercase character. | Non-PrimitiveNon-Primitive Data Structure begins with Uppercase character. |
| Primitivee.g int, float, char etc. | Non-Primitiveee.g Stack, Queue, Graph etc. |
NON-PRIMITIVE DATA STRUCUTRE
These non-primitive data structures can be further divided into two categories:
Linear Data Structure-: Data are stored linearly and sequentially.
Non-Linear Data Structure-: Data are not stored hierarchical manner.
OPERATIONS ON DATA STRUCTURE
Data Structure = Organized Data + Allowed Operations
Commonly used operations are Searching, Inserting, Deleting, Sorting, etc.
Following are the operations on a data structure.
- Traverse: Print all the array elements one by one.
- Insertion: Adds an element to the given index.
- Deletion: Deletes an element at the given index.
- Search: Searches an element using the given index or by the value.
- Update: Updates an element at the given index.
ABSTRACT DATA TYPE
ADT can be defined as the mathematical model that contains a set of values and functions which operate on those values without specifying the detail of the function. It does not specify how data will be organized in memory and what algorithms will be used for implementing the operations.
An ADT consists of two parts:
- Value Definition- It defines the collection of values for ADT. It consists of two parts.
- Definition Clause- All permissible data values are defined.
- Condition Clause- It is used to specify any conditions that may be on data values.
- Operator Definition- It describes all possible operators that can be implemented on values defined in the definition clause.
Each operator is also defined as a function with three parts:
- Header
- Pre-Condition
- Post-Condition
EXAMPLES OF ADT
 |
| ARRAY AS ADT |
DIFFERENCE BETWEEN DATA STRUCTURE AND ADT
| ADT | Data Structure |
|---|---|
| ADTLogical picture of data and operation that manipulate them. | Data StructurePhysical organization of data and operation on these values. |
| ADTIt is implementation independent. | Data StructureIt is implementation dependent. |
| ADTIt doesnot deal with space and time complexity. | Data StructureThe ADT converted additional operation algorithm is data structure. |
| ADTIt focuses on "What". | Data StructureIt answers "How". |
IMPORTANCE OF DATA STRUCTURE
- Compiler Design
- Database Management System
- Encapsulation
- Memory Management
ALGORITHM
An algorithm is a set of rules for carrying out calculations either by hand or machine. An algorithm is a sequence of computational steps that transform the input into the output. An algorithm is performed on data that have to be organized in the data structure. An algorithm is an abstraction of a program to execute on a physical machine.
Algorithm Design:
An algorithm design is a specific method to create a mathematical process for solving a problem.
Steps for developing algorithm:
1. Problem definition
2. Specification of algorithm
3. Design an algorithm
4. Checking the correctness of the algorithm
5. Analysis of algorithm
6. Implementation of algorithm
7. Problem Testing
8. Documentation
Algorithm Efficiency:
How fast is an algorithm?
How much money does it cost?