Summary
In order to use it effectively, Data Structure is a structured way to organize data. The founding terms of a data structure are the following terms.
Interface − There is an interface for each data structure. The interface describes a series of operations assisted by a data structure. The interface only includes a list of the operations supported, the type of parameters that can be accepted and the type of operations that can be returned.
Implementation − The internal representation of a data structure is given by the implementation. Implementation also gives the description of the algorithms used in the data structure operations.
Characteristics of a Data Structure
- Correctness − Data structure implementation should implement its interface correctly.
- Time Complexity − Running time or the execution time of operations of data structure must be as small as possible.
- Space Complexity − Memory usage of a data structure operation should be as little as possible.
Need for Data Structure
There are three common problems that applications face now-a-days as applications are becoming complicated and data rich.
- Data Search − Consider an inventory of 1 million(106) items of a store. If the application is to search an item, it has to search an item in 1 million(106) items every time slowing down the search. As data grows, search will become slower.
- Processor speed − Processor speed although being very high, falls limited if the data grows to billion records.
- Multiple requests − As thousands of users can search data simultaneously on a web server, even the fast server fails while searching the data.
Data structures come to the rescue to solve the problems described above. In a data system , data can be structured in such a way that it might not be necessary to scan all objects, and the appropriate data can be searched almost instantly.
Execution Time Cases
There are three instances that are typically used in a comparative way to compare the execution time of different data structures.
- Worst Case − This is the case in which it takes the maximum time for a specific data structure process. If the worst case time of an operation is f(n), then this operation does not take longer than f(n) when f(n) represents n function.
- Average Case − This is a scenario that represents the average execution time of a data structure process. If an operation takes f(n) time in execution, f(n) time would take operations.
- Best Case − This is the situation that demonstrates the least possible execution time of a data structure process. If an operation takes f(n) time to perform, so it may take time for the actual operation to be the random number that will be maximum as f(n).
Basic Terminology
- Data − Data are values or set of values.
- Data Item − Data item refers to single unit of values.
- Group Items − Data items that are divided into sub items are called as Group Items.
- Elementary Items − Data items that cannot be divided are called as Elementary Items.
- Attribute and Entity − An entity is that which contains certain attributes or properties, which may be assigned values.
- Entity Set − Entities of similar attributes form an entity set.
- Field − Field is a single elementary unit of information representing an attribute of an entity.
- Record − Record is a collection of field values of a given entity.
- File − File is a collection of records of the entities in a given entity set.