Data Structures.

#programming #algorithms #codenewbie #100daysofcode

Introduction

A data structure is a storage that is used to store and organize data. It is a way of arranging data on a computer so that it can be accessed and updated efficiently.

In case you are wondering why bother learning Data structures and algorithms this is why Applications are getting complex and data is getting rich, there are three common problems that applications face now-a-days.

Consider an inventory of 1 million. items of a store. If the application is to search an item, it has to search an item X in 1 million items every time slowing down the search. As data grows, search will become slower.

P Processor speed although being very high, falls limited if the data grows to billion records. As data grows , the processor slows down .

Consider a thousands users searching data simultaneously on a web server, even the fast server fails while searching the data. Right ??

Since Data can be organized in such a way that all items may not be required to be searched, and the required data can be retrieved instantly, then we need data structures.

To structure the data in memory, a number of algorithms were proposed, and all these algorithms are known as Abstract data types. These abstract data types are the set of rules that are followed in creating the data structures.

Classification of data structures

Data structures can also be :

Static data structure:

It is a type of data structure where the size is allocated at the compile time. Therefore, the maximum size is fixed.
Dynamic data structure:

It is a type of data structure where the size is allocated at the run time. Therefore, the maximum size is flexible.

Primitive Data structure

The primitive data structures are primitive data types. The int, char, float, double, and pointer are the primitive data structures that can hold a single value. Primitive data types are a set of basic data types from which all other data types are constructed.

Non-Primitive Data structure

The non-primitive data structure is divided into two types:

Linear data structure
Non-linear data structure

Linear data structures

Linear data structure is where the arrangement of the data follows a linear trend. The data elements are arranged linearly such that the element is directly linked to its previous and the next elements. As the elements are stored linearly, the structure supports single-level storage of data. And hence, traversal of the data is achieved through a single run only.

List of data structure in a linear type of data structure

Array An array is a static type of structure that stores homogeneous elements at memory locations which are contiguous. The same types of objects are stored sequentially in an array. The main idea of an array is that multiple data of the same type can be stored together. Before storing the data in an array, the size of the array has to be defined. Any element in the array can be accessed or modified and the elements stored are indexed to identify their locations. An array can be explained with the help of a simple example of storing the marks for all the students in a class. Suppose there are 20 students, then the size of the array has to be mentioned as 20. Marks of all the students can then be stored in the created array without the need for creating separate variables for marks for every student. Simple traversal of the array can lead to the access of the elements.
Linked list Linked list are dynamic type of linear data structures. The linked list is that type of data structure where separate objects are stored sequentially. Every object stored in the data structure will have the data and a reference to the next object. The last node of the linked list has a reference to null. The first element of the linked list is known as the head of the list. There are many differences between a linked list to the other types of data structures. These are in terms of memory allocation, the internal structure of the data structure, and the operations carried on the linked list. Getting to an element in a linked list is a slower process compared to the arrays as the indexing in an array helps in locating the element. However, in the case of a linked list, the process has to start from the head and traverse through the whole structure until the desired element is reached. In contrast to this, the advantage of using linked lists is that the addition or deletion of elements at the beginning can be done very quickly. Our learners also read: Free Python Course with Certification There are three types of linked lists: • Single Linked List: This type of structure has the address or the reference of the next node stored in the current node. Therefore, a node which at the last has the address and reference as a NULL. Example: A->B->C->D->E->NULL.

•A Double Linked List: As the name suggests, each node has two references associated with it. One reference directs to the previous node while the second reference points to the next node. Traversal is possible in both directions as reference is available for the previous nodes. Also, explicit access is not required for deletion. Example: NULL<-A<->B<->C<->D<->E->NULL.

•Linked List which is circular: The nodes in a circular linked list are connected in a way that a circle is formed. As the linked list is circular there is no end and hence no NULL. This type of linked list can follow the structure of both singly or doubly. There is no specific starting node and any node from the data can be the starting node. The reference of the last node points towards the first node. Example: A->B->C->D->E.

Properties of a linked list are:
•
o Access time: O(n)
o Searching time: O(n)
o Adding element: O(1)
• Deleting an Element : O(1)

3. Stack

The stack is another type of structure where the elements stored in the data structure follow the rule of LIFO (last in, first out) or FILO (First In Last Out). Two types of operations are associated with a stack i.e. push and pop. Push is used when an element has to be added to the collection and pop is used when the last element has to be removed from the collection. Extraction can be carried out for only the last added element.

Properties of a stack are:
• Adding element: O(1)
• deleting element: O(1)
• Accessing Time: O(n) [Worst Case]
• Only one end allows inserting and deleting an element.
Examples of the stack include the removal of recursion. In scenarios where a word has to be reversed, or while using editors when the word that was last typed will be removed first (using an undo operation), stacks are used.

*4. Queue *

A Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is open at both its ends. One end is always used to insert data (enqueue) and the other is used to remove data (dequeue). Queue follows First-In-First-Out methodology, i.e., the data item stored first will be accessed first.

**2. Nonlinear Data Structure

**
Data structures in which the data elements do not have to be arranged in a linear or sequential fashion are referred to as nonlinear data structures. All the data elements in non linear data structure can not be traversed in single run. In a nonlinear structure, only one level of data is not used. So, it is impossible to traverse the entire structure in one run. Nonlinear data structures can be straightforward to design and implement compared to linear data structures. They make use of computer memory effectively when compared to a linear structure. Examples of this are graphs and trees.

- Trees
A tree can be described as a nonlinear information system comprised of a variety of nodes. The nodes of the tree data structure are organized in order of hierarchy.

It is composed of a root node that corresponds to the different kids' nodes that are present at the next level. The tree is built from a level foundation, and root nodes are minimum kid nodes based on the tree's growing order. In the tree of binary, the position of the root has two nodes, which means it has the capacity to be able to have up to two kids per node and not more than that.

For Non-Linear Data Structure, the nonlinear system of data cannot be used directly, so it is implemented using the linear data structure, such as linked lists and arrays. The tree itself is a large info structure, and it is broken down into various kinds like Binary trees, Binary search trees, Heap, AVL trees max Heap, min-heap, and many more.

The types of trees mentioned above are different based on the properties they possess. The term "tree" refers to an acyclic, nonlinear connected graph. It's a nonlinear system of data like a tree. A node may be linked to one or more nodes. It's a collection of nodes linked by direct (or possibly indirectly) edges. It's comprised of a significant node called the 'root node.'

- Graphs
A graph can be described as a nonlinear information system with a restricted number of vertices and edges, and these edges are used to join the vertex pairs. The graph is classified by certain characteristics. When we talk about a large graph, it is composed of a set of vertex together with every vertex that is attached to the various vertex sets, gaining an advantage over the two. The vertices hold the data elements, whereas they are the tip of the link between the vertex sets.

The graph concept is essential in many fields. The network is represented with the help of the graph principle as well as its ideas within computer networks. In Maps, we consider each spot as a vertex, and the road between two locations is considered an edge. The main goal of graph representation is to determine the distance between two vertex points through an advantage mass that is minimal.

Conclusion
Data structures are essential for computer programs to be able to handle the increasing data volume. If data is not organized in a structured manner, it can make it difficult to achieve the desired results for projects. It is important to manage the data in order to make it easy and hassle-free. It's known as a linear system when data components are arranged in sequential order.

However, if data elements are arranged in nonlinear ways, it's known as a nonlinear structure. Machine learning languages, real-life problems, and other areas continue to have a wide range of data system