# Programming and Data Structures Study Notes on GATE CS Exam

By Mukesh Kumar|Updated : December 4th, 2021

Programming and Data Structures Study Notes on GATE CS Exam: Introduction to Data Structures and AlgorithmsA data structure is important to perform operations on data in an efficient way by collecting and organizing these data. Data Structures is concerning rendering knowledge components in terms of some relationship for higher organization and storage. For instance, we've got some knowledge: player's name "Virat" and age twenty-six. Here "Virat" is of String knowledge sort, and twenty-six is of whole number knowledge sort.

This data can be arranged in the form of a record where we want to save the player record, which will contain both the player's name and age. Now we can also store player's records in a file or database as a data structure. For example: "Sachin" 50, "Virat" 31, "MSD" 33

If you are aware of Object-Oriented programming concepts, then a class also does the same thing; it collects the different types of data under one single entity. The only way data structure is a different being, and they provide techniques to access and manipulate data efficiently.

In other words, Data Structures are structures programmed to store ordered data so that various operations can be performed on it effectively. It represents the information of data to be arranged in memory. This should be designed and implemented in such a manner that it reduces complexity and increases efficiency.

Basic types of Data Structures

Anything that can store data is called a data structure, so we can say Integer, Float, Boolean, Char etc., all are data structures as well. They are known as Primitive Data Structures.

Some complex Data Structures can be used to store large and connected kinds of data. An example of Abstract Data Structure is as follows :

• Tree
• Stack
• Queue
• Graph, etc.

With these data structures, different operations can be performed on data. We can select these data structures according to the operation's requirements.

## Data Structure

A data structure is a specialized way for organizing and storing data in memory to perform operations on it.

The data structure is all about:

• How to represent data element(s)?
• What relationship do data elements have among themselves?
• How to access data elements, i.e., access methods

## Need of Data Structures

As applications are getting complexed and the amount of data is increasing day by day, there may arise the following problems:

Processor speed: To handle a large amount of data, high-speed processing is required, but as the data is growing these days rapidly to the billions of files per entity, the processor may not handle a large amount of data.

Data Search: Let us consider an inventory of size 106 items; if we need to search for a particular item, then we have to traverse 106 items every time; this will slow down the search process.

Multiple requests: If thousands of search request for the data occurs simultaneously on a web server, then there are high chances that a very large server could be failed during that process, so data structures are used to solve such problems. Data is arranged to form a data structure so that all items are not required to be traversed, and required data can be searched instantly.

Efficiency: The efficiency of the program depends upon the selection of data structures. For example, let us suppose we have some data, and we need to find a particular record. In such a case, if we organize our data in an array, we will have to search elements sequentially by element. Hence, using an array may not be very efficient here. Better data structures can make the search process efficient, like an ordered array, hash tables, or binary search tree.

Reusability: Data structures are reusable; once a particular data structure is implemented, it can be used again at another place. Data structures implementation can be compiled into libraries that different clients can use.

Abstraction: Data structures specified by the ADT(Abstract Data Types), which provides the level of abstraction. The client program uses the data structure via graphical interface only, without getting into the details of implementation.

## Types of Data Structure

The data structures can be classified according to the following characteristics:

Linear: In Linear data structures, all data items are organized in a linear sequence. e.g. Array

Non-Linear: In Non-Linear data structures, all data items are not arranged in sequence. Example: Tree, Graph

Homogeneous: In the homogeneous data structures, all the elements are of the same type. Example: Array

Non-Homogeneous: In a Non-Homogeneous data structure, the elements may or may not be of the same data type. For example Structure

Static: Static data structures are those data structures whose size and structures with associated memory locations are fixed at the compile time. For example Array

Dynamic: Dynamic structures are those data structure which expands or shrinks depending upon the program need and its execution. Also, their associated memory locations changes. Example: Linked List created using pointers

Linear Data Structures: A data structure is linear if all of its elements are arranged in linear order. In the linear data structure, all elements are stored in a non-hierarchical manner where each element has predecessors and successors except the first and last data element.

Linear Data Structures are as follows:

Arrays: It is defined as a collection of similar data items, and each data item is called an element of the Array. The element's data type may be any valid data type like char, int, float or double.

The array elements share the same variable name, but each carries a different index number known as a subscript. The Array can be 1D (one dimensional), 2D (two dimensional) or multidimensional.

The individual data elements of the array age are as follows:

age[0], age[1], age[2], age[3],......... age[88], age[89].

Linked List: It is a linear data structure that maintains a list. It is the collection of nodes that are stored at non-contiguous memory locations, and each node of the list have a pointer to its adjacent nodes.

Stack: Stack is described as a linear list in which insertion and deletions are allowed only at one end, i.e. top.

A stack is ADT and can be implemented in most programming languages. It is named a stack because it acts the same as a real-world stack, such as - a deck of cards or piles of plates etc.

Queue: A linear list in which data elements can be inserted from one end only known as rear and deleted only at the other end called the front.

It is also an ADT, similar to a stack. The queue is opened at both ends. Therefore it follows First-In-First-Out (FIFO) approach for storing the data items.

Non-Linear Data Structures: This data structure does not have a sequence which means each data item is connected with two or more other data items in a non-linear fashion.

Non-Linear Data Structures are of the following types:

Trees: Trees are hierarchical multilevel data structures with the relationship between elements known as nodes. The bottommost or last nodes in the hierarchy are called leaf nodes, while the topmost node is the root node. Each node has pointers to point to the adjacent nodes.

The tree data structure has the parent-child relationship between the nodes. Except for the leaf nodes, each node in the tree can have more than one child, whereas each node will have one parent node except the root node.

Graphs: Graphs are the pictorial representation of the set of data elements (represented by vertices) connected by the links known as edges. A graph is different from a tree because a graph can have a cycle while the tree can not have one.

Operations on Data Structures: The operations involved in the data structure are as follows-

1) Traversing: Every data structure has a set of data elements. Traversing the data structure means visiting every element to perform specific operations like Searching, Sorting, etc.

Example: If we want to calculate the average of the marks obtained by a student in 6 different subjects, we have to traverse the complete Array of marks and then calculate the total sum; after this, we will divide that sum by the number of subjects, i.e. 6, to determine the average.

2) Insertion: Insertion is defined as the process of adding elements to the data structure at any location.

If the size of the data structure is n, then we can insert n-1 data elements only.

3) Deletion: Deletion is defined as the process of removing an element from the data structure. We can delete a data element of the data structure from any random location.

Underflow is a situation that occurs when we try to delete an element from an empty data structure.

4) Searching: The process of identifying the location of an element within the data structure is called Searching. We have two algorithms to perform Searching, i.e. Linear Search and Binary Search.

5) Sorting: Sorting is the process of arranging and organizing the data structure in a specific order. Many algorithms are there to perform sorting, like, insertion sort, bubble sort, quick sort, etc.

6) Merging: When two lists, List X and List Y of size P and Q, respectively, of similar elements, are joined to produce the third list, List Z of size (P+Q), then this process is called merging

In this Data Structure, we provide the following topics and examples and assignment problems.

• Arrays, stacks, queues, linked lists, trees, binary search trees, binary heaps, and graphs.

Thanks

#DreamStriveSucceed