What is Data Structure?

Data structure is a way of storing, organized and systematic data organization so that data can be used effectively.

Here are two fundamental concepts that form a data structure:

Interface : Each data structure has an Interface. The interface represents a set of calculations that a data structure supports. An Interface provides only a list of supported calculations, the types of parameters they can accept and the return type of these operations.

Implementation (can be understood as implementation) : Provides internal representation of a data structure. Implementation also provides a definition of the algorithm used in data structure calculations.

Characteristics of a Data Structure

Exactly : The implementation of the Data Structure should implement its Interface correctly.

Time complexity (Time Complexity) : Runtime or execution time of data structure calculations must be as small as possible.

Memory complexity (Space Complexity) : The memory usage of each calculation of the data structure should be as small as possible.

Why is data structure necessary?

Today, applications are increasingly complex and the amount of data is growing with a variety of types. This presents three major problems that every developer faces:

Searching for data : Suppose there are 1 million goods stored in stock. And suppose there is an application needed to search for a goods. Every time I do a search, this app will have to search for 1 item in 1 million goods. As the data increases, the search will become more and more slow and expensive.

Processor speed : Although the processor has a very high speed, it is also limited and when the amount of data is up to billions of records, the processing speed will no longer be fast.

Multiple requirements : When thousands of users perform a search operation on a Web Server, no matter how fast the Web Server is, it is really difficult to handle thousands of calculations at once.

To handle the above problems, data structures are a great solution. Data can be organized in a data structure in such a way that when a search of an element is performed, the requested data is immediately found.

Implementation time complexity in data structures and algorithms

There are 3 cases that are often used to compare the execution time of different data structures:

Worst case (Worst Case) : is a situation where a calculation of certain data structures takes maximum time (the longest time). For example, with three numbers 1, 2, 3, if sorted in descending order, the execution time will be the longest (and this is the worst case); if sorted in ascending order, execution time will be the shortest (and this is the best case).

Average Case : describes the average execution time of a calculation of a data structure.

Best Case : A situation where the execution time of a calculation of a data structure is the least. Example as above.

Basic terminology in Data Structures

Data : Data are values ​​or a set of values.

Data element : Data element is a single unit of value.

Group elements : Data elements that are divided into sub-elements are called group elements.

Basic elements : Data elements that cannot be subdivided into child elements are called basic elements.

Attributes and Entities : An entity is something that contains certain attributes, and these attributes can be assigned values.

Entity aggregation : Entities that have similar attributes constitute an entity set.

Field : A field is a basic information unit representing an attribute of an entity.

Record : A record is a set of field values ​​of a given entity.

File : A collection of records of entities in a given entity set.

According to Tutorialspoint

Previous article: Web programming in C ++

Next lesson: Setting environment in Data structure