Data Structures: Introduction
An instance of data which can either be defined by the user or native to the used language is called data type. A particular kind of systematic organization and a composition of data types are called data structures.
It is the sum of the organized data and the allowed operations on it. The complex data structures use the simple forms of data structure and take them as building blocks. There are four types of data structures, and they are the following-
1. Linear and Non-linear-
The linear data structure which stores the data in the sequence is called the linear data structure. The other counterpart has got the name, non-linear. An array is the example of the linear data structure, whereas, the tree is the instance of the non-linear data structure.
2. Homogenous and non-homogeneous data structure-
The type of data structure which uses only one type of data is called the homogeneous data structure, and the name of the data structure which has different data types in it is called non-homogenous data structure. An array stores its data in contiguous memory and is an ordered form of homogenous elements. Whereas, if we look into the record or a structure, then it comes under the category of the non-homogenous data structure.
3. Static and Dynamic-
The distinction of the data structure from the allocation of memory falls under this category.
4. Direct access as well as Sequential access-
In the direct access, the user and the data type has the ability of directly accessing the required item without access to any other item. Whereas, in the sequential access, the user needs to go through several numbers of items before actually reaching to the specific item. Or in the other and simple words, in this type of access, there is no direct access to any available item. If we have a look at the arrays, they provide direct access to any element in the array. It is done using indexing which means direct access. In the sequential access, the linked lists are the example as we need to traverse through the list for locating the specific node.
Data Structures and their selection and the sorting is an interesting topic to read. You can read it for getting a clear and comprehensive approach.
It is a type of linear data structure and is the simplest form. Here, a finite number of similar elements of data are referenced by the consecutive set of numbers. These are the numbers beginning at 1 and taken to the finite number say, n.
It is an array list of 5 elements which can be stored in the array of size 5.
The data structure in which all the components of the same data type, as well as they, have the dynamic height is called a stack. The other name of the stacks is LIFO system. It is the last in first out and works as the insertion and deletion of the specific component take place at the top of the stack. Here, the words top denotes the end of the stack. Yes, it is an example of the sequential access. The item which can be accessed at any given time lies on the top of the stack. We can see the example of a stack in real life. The dish or a coin stacker can be counted as the best and easy examples. The push and the pop are the terms which make the understanding of the system easy. Dishes are popped off the top, and they are pushed onto the top.
These are also the examples of the linear data structure and have a dynamic height. They also contain the single type of data. Therefore, it falls into the category of the homogeneous data structure. The other name of the queues is called a FIFO system. These are the system in which the working is as the principle of the first in first out. The rear end is the name through which the insertion takes place. It happens only through one end. The other end of the component through the deletion of the nodes takes place called the front end of the queue.
You can relate the word, queue in your real life as well. The line at the counter for a movie ticket or at the restaurant can be linked to comprehend the topic easily. The customers get the service in the order of their arrival.
Like the other two formats, like the array and the queue, it is also a form of a linear data structure, and it too has the dynamic height. The components of the same data type of the list are stored in nodes. It is also the homogenous structure of the data. For locating a specific node on the list, there is a sequential traversing of the data through the list. Yes, it does not have the direct access to the required nodes. The moment the item is added to the linked list; a memory space is allocated to each item. For the linkage part in the list, each item gets a link within the next item. The two elements in the nodes in the list are as follows-
1. The list of the items which are stored
2. It points to the next item in the linked list
In every list, the last node in the list has a NULL pointer. It is used for indicating the end of the list. It is also called the tail of the list. There is a dynamic allocation of the memory node as the items are added to the linked list. There is a limited number of items which can be added to the lists. It is done as per the amount of available memory.
Two types of linked lists:
1. Circular Linked Lists
2. Doubly Linked Lists
The non-empty and the finite set of edges, vertices in which there is the satisfaction of certain criterion are called trees.
Vertex- A node which contains the name and the other information associated with it is called vertex.
Edge- The connection set between the two vertices is called an edge.
Root- The one vertex designated especially are called the roots. The rest of the vertices are then partitioned to collect them in various sub-sets. Every vertex is then also called a tree.
A particular node which emerges from another particular node is called the children of that node in the tree. The node from which the nodes get emerged is called its parent. It is not necessary that every parent node must have children nodes. The line which takes the parent node to the child node is called an edge.
The non-empty set of edges and vertices which are connected to each other are called the graphs. The element in the set can have its association with the unordered pair. A tree is a graph, but it is not true that the graph would be the tree for all the time.