Introduction to Data Structure

What is a Data Structure?

A Data Structure is a way of collecting and organising data in such a way that we can perform various operations on it.

 Why Data Structure is Important?

Data Structures are important because they make it easier for computers to process large, complex sets of information. By logically organising data elements, data structure increases the efficiency of computer code .

Classification of Data Structure:-




There are two types of Data Structure :-

1. Primitive Data Structure :- The primitive data structures in c are those basic data structure that are already defined in the C language. These data structures are used to store a single value . Eg:- integer, Float, Char, Double, Long. etc.

2. Non-primitive Data Structure:- The non-primitive data structures are highly developed complex data structures. Basically , these are developed from primitive data structure. It is responsible  for organizing the group of homogeneous and heterogeneous data elements 

eg;- Array, List, Stack, Files etc. 

In Non-Primitive Data structure there are two types :-

1. Linear Data Structure :- 

• A linear data structure is one in which data items are ordered sequentially or linearly, with each member attached to its previous and next neighbouring elements. 

• As the elements are stored sequentially, so they can be traversed or accessed in a single run. 

• The implementation of linear data structures is easier as the elements are sequentially organized in memory.  

eg:- 

Array:- An array consists of data elements of a same data type. For example, if we want to store the roll numbers of 10 students, so instead of creating 10 integer type variables, we will create an array having size 10. Therefore, we can say that an array saves a lot of memory and reduces the length of the code. 


Stack: It is linear data structure that uses the LIFO (Last In-First Out) rule in which the data added last will be removed first. The addition of data element in a stack is known as a push operation, and the deletion of data element form the list is known as pop operation. 


Queue: It is a data structure that uses the FIFO rule (First In rule, the element which is added first will be removed first. There are two terms used in the queue front end and rear The insertion operation performed at the back end is known as enqueue, and the deletion operation performed at the front end is known as dequeue. 




2. Non-Linear Data Structure :- 

A non-linear data structure is another important type in which data elements are not arranged sequentially; mainly, data elements are arranged in random order without forming a linear structure. Data elements are present at the multilevel, for example, tree. 

eg:

Tree: It is a non-linear data structure that consists of various linked nodes. It has a hierarchical tree structure that forms a parent diagrammatic representation of a tree data structure is shown below: 


Graph: A graph is a non-linear data structure that has a finite number of vertices and edges, and these edges are used to connect the vertices. The vertices are used to store the data elements, while the edges represent the relationship between the vertices. 


Need of data structure: 

• Data Structures are necessary for designing efficient algorithms. 

• It provides reusability and abstraction. 

• Using appropriate data structures can help programmers save a good amount of time while performing operations such as storage, retrieval, or processing of data. 

• Manipulation of large amounts of data is easier.  

Advantages of Data Structure: 

• The data structure is a good solution for storing data on framework. 

• Data structures make it easier for us to handle data. 

• Data structures also aid us in efficiently storing data on circles so that we can recover the data. 

• Data structures are critical for planning computations. 

Basic terminologies: 

Data: Data are values or set of values. 

Database: A database is an organized collection of data.

Algorithm: Algorithm is a step-by-step procedure, which defines a set of instructions to be executed in a certain order to get the desired output. Algorithms are generally created independent of underlying languages, i.e. an algorithm can be implemented in more than one programming language. 

Group Item: Data item that are divided into sub items are called as group items. 

Elementary item: Data item that cannot be divided. 

Attribute or entity: An entity is that which contain certain attributes or properties, which may be assigned values.

Entity Set: Entities of similar attributes from an entity set. 

Field: Field is a single elementary unit of information representing an attribute of an entity. 

File: File is collection entities in a given entity set.

Operations on Data Structure: 

Primitive Data Structure: 

1. Creation: To create new data structure.

2. Destroy: To delete data structure. 

3. Selection: To access (select) data from the data structure. 

4. Updating: To edit or change the data within the data structure. 

Non-Primitive Data Structure:

1. Inserting: Adding a new data in the data structure is referred as insertion. 

2. Deleting: Removing a data from the data structure is referred as deletion. 

3. Sorting: Arranging the data in some logical order (ascending or descending, numerically...) 

4. Searching: Finding the location of data within the data structure which satistify the searching condition. 

5. Traversing: Accessing each data exactly once in the data structure so that each data item is traversed or visited. 

6. Merging: Combining the data of two different sorted files into a single sorted file. 

7. Copying: Copying the contents of one data structure to another. 

8. Concatenation: Combining the data from two or more data structure. 

Time complexity: 

• Time complexity is defined in terms of how many times it takes to run a given algorithm, based on the length of the input. 

• Time complexity is not a measurement of how much time it takes to execute a particular algorithm because such factors as programming language, operating system, and processing power are also considered. 

• Time complexity is a type of computational complexity that describes the time required to execute an algorithm.

 • The time complexity of an algorithm is the amount of time it takes for each statement to complete. 

• As a result, it is highly dependent on the size of the processed data. It also aids in defining an algorithm's effectiveness and evaluating its performance. 

• Categories of Time Complexity: 

1. Best Case

2. Worst Case

3. Average Case

Space Complexity:

• When an algorithm is run on a computer, it necessitates a certain amount of memory space. 

• The amount of memory used by a program to execute it is represented by its space complexity. 

• Because a program requires memory to store input data and temporal values while running, the space complexity is auxiliary and input space. 

Time-space trade off: 

A trade off is a situation where one thing increases and another thing decreases. It is a way to solve a problem in: • Either in less time and by using more space, or • In very little space by spending a long amount of time. 

Big O notation:

Big O Notation is a tool used to describe the time complexity of algorithms. It calculates the time taken to run an algorithm as the input grows. In other words, it calculates the worst-case time complexity of an algorithm. Big O Notation in Data Structure describes the upper bound of an algorithm's runtime.