Data structure tutorial

Data Structure

The data structure is a particular way of organizing and storing data in a computer so that it can be accessed and modified efficiently. It is a collection of data values, the relationships among them, and the functions or operations that can be applied to the data.

Arrays, Linked List, Stack, Queue, etc., are some examples of Data Structures that are universally used in almost every realm of Computer Science i.e. Operating systems, Compiler Design, Artificial intelligence, Graphics, and a lot more. To handle the data in an efficient way, Data Structures are used as the main part of many computer science algorithms. To enhance the performance of the software or a program as the main function of the software to store and retrieve the user’s data as fast as possible, the Data Structures are important.

Important terms used in Data Structure:

Data: Elementary value or the collection of values. Example: Name and ID of the employee are the data about the employee.
Group Items: Data items with subordinate data items. Example: The name of the employee can have the first name and the last name.
Record: The collection of various data items. Example: Name, address, and experience of the employee can be grouped together to form the record for the employee.
File: Collection of various records of one type of entity.
Attribute and Entity: An entity can be defined as the class of certain objects, containing various attributes, where each attribute represents the particular property of that entity.
Field: A single elementary unit of information representing the attribute of an entity.

Why we need Data Structures:

Complexed applications and an increase in the amount of data can result in below:

Processor speed: High-speed processing is a must to handle a large amount of data. Still, the processor may fail to deal with such a large amount of data, because the data is increasing day by day to the billions of files per entity.
Data Search: An inventory can have hundreds of items in a store, which simply means that an application needs to traverse hundreds of items every time to search for a particular item. This results in slowing down the search process.
Multiple requests: Even a very large server can fail if thousands of users are searching the data simultaneously on a web server. The data structures are used to solve any such problems. Thus, all the items are not required to be searched and the required data can be searched instantly if the data is organized to form a data structure in such a way.

Data Structures Advantages:

Efficiency: The choice of data structures decides the efficiency of a program. Example: Using an array may not be a very good choice if we have some data and we need to perform the search for a particular record. Organizing the data in an array means that we will have to search sequentially element by element. To make the search process efficient, we can use other data structures like an ordered array, binary search tree, or hash tables.
Reusability: After the implementation of a particular data structure, we can use it at any other place. Thus, the data structures are reusable. Compiling the implementation of data structures into libraries that can be used by different clients, serves this purpose.
Abstraction: The ADT provides a level of abstraction. The data structure is specified by ADT. The client program does not get into the implementation details and uses the data structure through the interface only.

Data Structures Types:

Linear Data Structures:

If all the elements of a data structure are arranged in linear order, it is called a linear data structure. The elements in linear data structures are stored in a non-hierarchical way. Here, each element has successors and predecessors except the first and last elements.

Types of Linear Data Structures:

Arrays: A collection of similar types of data items is called an array. It can be one-dimensional, two-dimensional, or multi-dimensional. Each data item in an array is called an element of the array. We can use any valid data type like char, int, float, or double as the data type of the element. The same variable name is shared by the elements of the array. However, each element carries a different index number known as a subscript.
Linked List: To maintain a list in the memory a linear data structure is used, also known as a linked list. We can also define it as a collection of nodes stored at non-contiguous memory locations, where each node of the list contains a pointer to its adjacent node.
Stack: A linear list in which insertion and deletions are allowed only at one end, i.e., top, is called a stack. It is an abstract data type (ADT), which is named as a stack because it behaves like a real-world stack. It can be implemented in most programming languages.
Queue: A linear list in which elements can be inserted only at one end called the rear and deleted only at the other end called the front is called a queue. It is also an abstract data structure, which is opened at both ends and thus follows the First-In-First-Out (FIFO) methodology for storing the data items.

Non-Linear Data Structures:

In a non-linear arrangement, the data elements are not arranged in a sequential structure, i.e., this data structure does not form a sequence and each item or element is connected with two or more other items.

Types of Non-Linear Data Structures:

Trees: A multilevel data structure with a hierarchical relationship among its elements is called a tree. The elements of a tree are known as nodes. In a hierarchy, the bottommost nodes are called the leaf node, and the topmost node is called the root node. To point the adjacent nodes, each node contains pointers. Based on the parent-child relationship among the nodes, each node in the tree can have more than one child except the leaf nodes whereas each node can have at most one parent except the root node.
Graphs: The pictorial representation of the set of elements (represented by vertices) connected by the links known as edges is called a graph. A graph can have a cycle while a tree can not have one and is thus different from a tree.

Commonly used data structure operations:

Traversing: A set of data elements is included in every data structure. Visiting each element of the data structure in order to perform some specific operation like searching or sorting, is called traversing the data structure.
Insertion: The process of adding the elements to the data structure at any location is defined as insertion. We can insert n-1 data elements into a data structure if the size of the data structure is n.
Deletion: Deletion is the process of removing an element from the data structure. An element can be deleted from the data structure at any random location. Underflow occurs if we try to delete an element from an empty data structure.
Searching: Searching is the process of finding the location of an element within the data structure. To perform searching, Linear Search and Binary Search are the two algorithms.
Sorting: Sorting is the process of arranging the data structure in a specific order. To perform sorting, there are many algorithms that can be used, including, insertion sort, selection sort, bubble sort, etc.
● Merging: Merging is the process where the two lists List A and List B of size M and N respectively, of similar types of elements, are clubbed or joined to produce the third list, List C of size (M+N).