Unit -1 Introduction To Data Structure

What is data structure?

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.
A data structure is not only used for organizing the data. It is also used for processing, retrieving, and storing
data. There are different basic and advanced types of data structures that are used in almost every program or
software system that has been developed. So we must have good knowledge about data structures.

Classification of Data Structure:

Classification of Data Structure

1. Linear Data Structure : Data structure in which data elements are arranged sequentially or linearly, where each
element is attached to its previous and next adjacent elements, is called a linear data structure.
Example: Array, Stack, Queue, Linked List, etc.

2. Static Data Structure: Static data structure has a fixed memory size. It is easier to access the elements in a
static data structure.
Example: array.

3. Dynamic Data Structure: In dynamic data structure, the size is not fixed. It can be randomly updated during
the runtime which may be considered efficient concerning the memory (space) complexity of the code.
Example: Queue, Stack, etc.

4. Non-Linear Data Structure: Data structures where data elements are not placed sequentially or linearly are
called non-linear data structures. In a non-linear data structure, we can’t traverse all the elements in a single
run only.
Examples: Trees and Graphs

What is an Algorithm?

The word Algorithm means “a process or set of rules to be followed in calculations or other problem-solving
operations”. Therefore Algorithm refers to a set of rules/instructions that step-by-step define how a work is to be
executed in order to get the expected results. Let’s take a look at an example for a better understanding. As a
programmer, we are all aware of the Linear Search program.
Basics Analysis Of Algorithm?

Algorithm analysis is the process of evaluating the performance of an algorithm, usually in terms of its time and
space complexity. There are several ways to analyze the performance of an algorithm, including asymptotic
analysis, which analyzes the behavior of an algorithm as the size of the input grows indefinitely.

What is a Flowchart?

A flowchart is a graphical representation of an algorithm. Programmers often use it as a program-planning tool to

solve a problem. It makes use of symbols that are connected among them to indicate the flow of information and
processing. The process of drawing a flowchart for an algorithm is known as “flowcharting”. Example: Draw a
flowchart to input two numbers from the user and display the largest of two numbers

Difference between algorithm and flow chart:

S.
No Algorithm Flowchart
An algorithm is a step-by-step procedure to A flowchart is a diagram created with different shapes to
1. solve a problem. show the flow of data.

2. The algorithm is complex to understand. A flowchart is easy to understand.

3. In the algorithm, plain text is used. In the flowchart, symbols/shapes are used.
4. The algorithm is easy to debug. A flowchart is hard to debug.
5. The algorithm is difficult to construct. A flowchart is simple to construct.

6. The algorithm does not follow any rules. The flowchart follows rules to be constructed.
The algorithm is the pseudo-code for the A flowchart is just a graphical representation of that
7. program. logic.

What Is 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.

What Is 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.

Array:
 An array is a collection of data items stored at contiguous memory locations. The idea is to store multiple items of
the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a
base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

Static Memory Allocation: Static Memory is allocated for declared variables by the compiler. The address can
be found using the address of operator and can be assigned to a pointer. The memory is allocated during compile
time.

Dynamic Memory Allocation: Memory allocation done at the time of execution(run time) is known as dynamic
memory allocation. Functions calloc() and malloc() support allocating dynamic memory. In the Dynamic
allocation of memory space is allocated by using these functions when the value is returned by functions and
assigned to pointer variables.

What is Recursion?
The process in which a function calls itself directly or indirectly is called recursion and the corresponding
function is called a recursive function. Using a recursive algorithm, certain problems can be solved quite easily.

What is function?

The corresponding function is called a recursive function. Using a recursive algorithm, certain problems can be
solved quite easily.

Array:

An array is a collection of data items stored at contiguous memory locations. The idea is to store multiple items of
the same type together. This makes it easier to calculate the position of each element by simply adding an offset to a
base value, i.e., the memory location of the first element of the array (generally denoted by the name of the array).

Types of Array

There are two main types of arrays:

 One-dimensional arrays: These arrays store a single row of elements.
 Multidimensional arrays: These arrays store multiple rows of elements.

1-dimensional array :
A One-Dimensional Array is the simplest form of an Array in which the elements are stored linearly and can be
accessed individually by specifying the index value of each element stored in the array.

What is a multidimensional array with example?

A multi-dimensional array is an array with more than one level or dimension. For example, a 2D array, or two-
dimensional array, is an array of arrays, meaning it is a matrix of rows and columns (think of a table). A 3D array adds
another dimension, turning it into an array of arrays of arrays.

What is a 2 dimensional array in data structure?

A two-dimensional array, also known as a 2D array, is a collection of data elements arranged in a grid-like structure
with rows and columns. Each element in the array is referred to as a cell and can be accessed by its row and column
indices/indexes.
Two-Dimensional Arrays

A 2D array is also known as a matrix (a table of rows and columns).

To create a 2D array of integers, take a look at the following example:

int matrix[2][3] = { {1, 4, 2}, {3, 6, 8} };

The first dimension represents the number of rows [2], while the second dimension represents the number of
columns [3]. The values are placed in row-or*9der, and can be visualized like this:

Access the Elements of a 2D Array

To access an element of a two-dimensional array, you must specify the index number of both the row and column.

This statement accesses the value of the element in the first row (0) and third column (2) of the matrix array.

Example
int matrix[2][3] = { {1, 4, 2}, {3, 6, 8} };

printf("%d", matrix[0][2]); // Outputs 2

Change Elements in a 2D Array

To change the value of an element, refer to the index number of the element in each of the dimensions:

The following example will change the value of the element in the first row (0) and first column (0):
Example
int matrix[2][3] = { {1, 4, 2}, {3, 6, 8} };
matrix[0][0] = 9;

printf("%d", matrix[0][0]); // Now outputs 9 instead of 1

Pointer
Pointer is used to points the address of the value stored anywhere in the computer memory. To obtain
the value stored at the location is known as dereferencing the pointer.

pointer to structure

A structure pointer is defined as the pointer which points to the address of the memory
block that stores a structure known as the structure pointer. Complex data structures like
Linked lists, trees, graphs, etc. are created with the help of structure pointers.
What is pointer to pointer in data structure?
The pointer to a pointer in C is used when we want to store the address of another pointer. The first pointer is used to
store the address of the variable. And the second pointer is used to store the address of the first pointer. That is why
they are also known as double-pointers.

String in Data Structure

In data structures, a string is a sequence of characters used to represent text. Strings are
commonly used for storing and manipulating textual data in computer programs. They can be
manipulated using various operations like concatenation, substring extraction, and
comparison.