Data structure - a software unit that allows you to save and process a lot of the same or logically related information in computing devices. If you want to add, find, modify or delete information, the structure will provide a specific package of options, which makes up its interface.
What does the concept of data structure include?
This term may have several close, but still distinctive meanings. It:
- abstract type;
- implementation of the abstract form of information;
- an instance of a data type, for example, a specific list.
If we talk about the data structure in the context of functional programming, then this is a special unit that is preserved during changes. One can informally speak of it as a single structure, despite the fact that there may be different versions.
What forms a structure?
The data structure is formed using types of information, links and operations on them in a particular programming language. It is worth saying that different types of structures are suitable for implementing different applications, some, for example, have a completely narrow specialization and are suitable only for the production of established tasks.
If you take B-trees, then they are usually suitable for creating databases and only for them. At the same time, hash plates are still used everywhere in practice to create various dictionaries, for example, to demonstrate domain names in the Internet addresses of a PC, and not just to create databases.
During the development of a particular software, the complexity of the implementation and the quality of the functionality of the programs directly depend on the correct application of data structures. Such an understanding of things gave impetus to the development of formal development methods and programming languages, where structures, rather than algorithms, are put in the lead in the architecture of the program.
It is worth noting that many programming languages have an established type of modularity, which allows data structures to be used safely in various applications. Vivid examples are Java, C # and C ++. Now the classical structure of the data used is presented in standard libraries of programming languages or it is directly integrated into the language itself. For example, this hash table structure is built into Lua, Python, Perl, Ruby, Tcl, and others. The standard template library in C ++ is widely used.
Compare structure in functional and imperative programming
It should immediately be noted that designing structures for functional languages is more difficult than for imperative ones, at least there are two reasons for this:
- In fact, all structures often apply assignment in practice, which is not used in a purely functional style.
- Functional structures are flexible systems. In imperative programming, old versions are simply replaced with new ones, while in functional everything works as it worked. In other words, in imperative programming, structures are ephemeral, while in functional they are constant.
What does the structure include?
Often the data that programs work with is stored in arrays built-in to the programming language used, constant or in variable lengths. An array is the simplest structure with information, however, to solve some problems, greater efficiency of some operations is required, therefore other structures are used (more complicated).
The simplest array is suitable for frequent access to installed components by indexes and their changes, and the removal of elements from the middle functions according to the O (N) O (N) principle. If you need to remove elements in order to solve certain tasks, you will have to use a different structure. For example, the binary tree (std :: set) allows you to do this by O (logN) O (logN), however it does not support working with indexes, only elements are alternately traversed and searched by value. Thus, we can say that the structure is distinguished by operations, what it is able to perform, as well as the speed of their completion. For example, it is worth considering the simplest structures, which do not provide benefits in efficiency, but have a well-established set of supported operations.
Stack
This is one of the types of data structures presented in the form of a limited elementary array. The classic stack supports only three options:
- Push an item onto the stack (Difficulty: O (1) O (1)).
- Removing an item from the stack (Difficulty: O (1) O (1)).
- Check if the stack is empty or not (Difficulty: O (1) O (1)).
To clarify how the stack works, you can put into practice the analogy of a cookie jar. Imagine that at the bottom of the bowl there are several cookies. Upstairs you can put a couple more pieces or you can, on the contrary, take one cookie on top. The remaining cookies will be closed top, and you will not know anything about them. This is the case with the stack. To describe the concept, the abbreviation LIFO (Last In, First Out) is used, which emphasizes that the component that was the last to enter the stack will be the first and removed from it.
Turn
This is another type of data structure that supports the same set of options as the stack, but it has the opposite semantics. To describe the queue, the abbreviation FIFO (First In, First Out) is used, because at the beginning the element that was added before all is extracted. The name of the structure speaks for itself - the principle of operation completely coincides with the queues, which can be seen in the store, supermarket.
Dec
This is another kind of data structure, also called a double-ended queue. The option supports the following set of operations:
- Add an element to the beginning (Difficulty: O (1) O (1)).
- Extract component from start (Difficulty: O (1) O (1)).
- Putting an element at the end (Difficulty: O (1) O (1)).
- Extract an element from the end (Difficulty: O (1) O (1)).
- Checking if the deck is empty (Difficulty: O (1) O (1)).
Lists
This data structure defines a sequence of linearly connected components for which the operations of adding components to any place in the list and deleting it are allowed. A linear list is specified by a pointer to the beginning of the list. Typical operations on lists: crawling, searching for a specific component, inserting an element, deleting a component, combining two lists into a single whole, splitting a list into a couple, and so on. It should be noted that in the linear list, in addition to the first, there is a previous component for each element, not including the last. This means that the components of the list are in an ordered state. Yes, processing such a list is not always convenient, because there is no way to move in the opposite direction - from the end of the list to the beginning. However, in the linear list you can step by step go through all the components.
There are still ring lists. This is the same structure as a linear list, but it has an additional relationship between the first and last components. In other words, the next component is the first component.
In this list, items are peers. The selection of the first and last is a convention.
Trees
This is a set of components that are called nodes, in which there is a main (one) component in the form of a root, and all the others are divided into many disjoint elements. Each set is a tree, and the root of each tree is a descendant of the root of the tree. In other words, all components are interconnected by parent-child relationships. As a result, you can observe the hierarchical structure of nodes. If the nodes do not have a descendant, then they are called leaves. The following operations are defined above the tree: adding a component and removing it, crawling, searching for a component. A special role in computer science is played by binary trees. What it is? This is a special case of a tree, where each node can have no more than a pair of descendants, which are the roots of the left and right subtree. If, in addition, for the tree nodes, the condition is fulfilled that all the values of the components of the left subtree are less than the values of the root, and the values of the components of the right subtree are larger than the root, then such a tree is called a binary search tree, and it is intended for finding elements quickly. How does the search algorithm work in this case? The desired value is compared with the root value, and depending on the result, the search either ends or continues, but exclusively in the left or right subtree. The total number of comparison operations will not exceed the height of the tree (this is the largest number of components on the way from the root to one of the leaves).
Counts
Graphs are a set of components that are called vertices together with a complex of relations between these vertices, which are called edges. A graphical interpretation of this structure is represented as a set of points that are responsible for the vertices, and some pairs are connected by lines or arrows, which corresponds to edges. The latter case suggests that the graph should be called oriented.
Graphs can describe objects of any structure, they are the main means for describing complex structures and the functioning of all systems.
More about abstract structure
To build an algorithm, it is necessary to formalize the data or, in other words, it is necessary to bring the data to a specific information model that has already been investigated and written. Once the model is found, it can be argued that an abstract structure is established.
This is the main data structure that demonstrates features, qualities of the object, the relationship between the components of the object and the operation that can be performed on it. The main task is to search and display forms of presentation of information that are comfortable for computer adjustment. It is worth mentioning right away that computer science as an exact science acts with formal objects.
Analysis of data structures is performed by the following objects:
- Integers and real numbers.
- Boolean values.
- Symbols
To process all the elements on a computer, there are corresponding algorithms and data structures. Typical objects can be combined into complex structures. You can add operations on them, rules to certain components of this structure.
The data organization structure includes:
- Vectors.
- Dynamic structures.
- Tables.
- Multidimensional arrays.
- Counts.
If all the elements are selected successfully, then this will be the key to the formation of effective algorithms and data structures. If you apply in practice the analogy of structures and real objects, then you can effectively solve existing problems.
It is worth noting that all data organization structures exist separately in programming. Worked on them a lot back in the eighteenth and nineteenth centuries, when there was still no mention of a computer.
It is possible to develop an algorithm in terms of an abstract structure, however, to implement the algorithm in a particular programming language, you will need to find a methodology for representing it in data types, operators, which are supported by a specific programming language. To create structures, such as a vector, a plate, a string, a sequence, many programming languages have classical data types: a one-dimensional or two-dimensional array, a string, a file.
What are the guidelines for working with structures?
We figured out the characteristics of data structures, now we should pay more attention to understanding the concept of structure. When solving absolutely any task, it is required to work with some data in order to perform operations on information. Each task has its own set of operations, but a certain set is used in practice more often to solve a variety of tasks. In this case, it is useful to come up with a certain way of organizing information that will allow you to perform these operations as efficiently as possible. As soon as such a method appeared, we can assume that you have a “black box” in which data of a certain kind will be saved and which will perform certain operations with the data. This will allow you to escape from the details and completely concentrate on the characteristic features of the task. This "black box" can be implemented in any way, while it is necessary to strive for the most productive implementation.
Who needs to know this?
Beginning programmers who want to find their place in this area, but don’t know where to go, should get acquainted with the information. These are the basics in every programming language, therefore it will not be superfluous to learn immediately about data structures, and then work with them on specific examples and with a specific language. We should not forget that each structure can be characterized by logical and physical representations, as well as the totality of operations on these representations.
Do not forget: if you are talking about a particular structure, then keep in mind its logical representation, because the physical representation is completely hidden from the “external observer”.
In addition, keep in mind that the logical representation is completely independent of the programming language and the computer, while the physical, on the contrary, depends on translators and computer technology. For example, a two-dimensional array in Fortran and Pascal can be represented in the same way, and the physical representation in the same computer in these languages will be different.
Do not rush to start learning specific structures, it is best to understand their classification, get acquainted with everything in theory and preferably in practice. It is worth remembering that variability is an important feature of the structure, and it indicates a static, dynamic or semi-static position. Learn the basics before embarking on more global things, this will help you in further development.