Computer Applications
Subject-
(Data File Structure)
Class notes-
(2022-2023)
, Content-
Serial No. Topics
Definition-Data file structure, Types, Basic operations.
1
2 Define Array & Its other concepts.
3 Linked list concept.
4 Definition of Stacks & concept.
5 Concept of Queues.
6 Tree structures.
7 Concept of Sorting and Searching.
,What is Data Structure?
Data Structure is a particular way of storing and organizing data in the memory of the computer
so that these data can easily be retrieved and efficiently utilized in the future when required.
Classification of Data Structures
We can classify Data Structures into two categories:
1. Primitive Data Structure
2. Non-Primitive Data Structure
The following figure shows the different classifications of Data Structures.
Primitive Data Structures
1. Primitive Data Structures are the data structures consisting of the numbers and the
characters that come in-built into programs.
2. These data structures can be manipulated or operated directly by machine-level
instructions.
3. Basic data types like Integer, Float, Character, and Boolean come under the
Primitive Data Structures.
4. These data types are also called Simple data types, as they contain characters that can't
be divided further.
,Non-Primitive Data Structures
1. Non-Primitive Data Structures are those data structures derived from Primitive Data
Structures.
2. These data structures can't be manipulated or operated directly by machine-level
instructions.
3. The focus of these data structures is on forming a set of data elements that is
either homogeneous (same data type) or heterogeneous (different data types).
4. Based on the structure and arrangement of data, we can divide these data structures into
two sub-categories -
a. Linear Data Structures
b. Non-Linear Data Structures
Linear Data Structures
A data structure that preserves a linear connection among its data elements is known as a Linear
Data Structure. The arrangement of the data is done linearly, where each element consists of
the successors and predecessors except the first and the last data element.
Based on memory allocation, the Linear Data Structures are further classified into two types:
1. Static Data Structures: The data structures having a fixed size are known as Static
Data Structures. The memory for these data structures is allocated at the compiler time,
and their size cannot be changed by the user after being compiled; however, the data
stored in them can be altered.
The Array is the best example of the Static Data Structure as they have a fixed size,
and its data can be modified later.
2. Dynamic Data Structures: The data structures having a dynamic size are known as
Dynamic Data Structures. The memory of these data structures is allocated at the run
time, and their size varies during the run time of the code. Moreover, the user can
change the size as well as the data elements stored in these data structures at the run
time of the code.
Linked Lists, Stacks, and Queues are common examples of dynamic data structures
Non-Linear Data Structures
Non-Linear Data Structures are data structures where the data elements are not arranged in
sequential order. Here, the insertion and removal of data are not feasible in a linear manner.
There exists a hierarchical relationship between the individual data items.
,Types of Non-Linear Data Structures
The following is the list of Non-Linear Data Structures that we generally use:
1. Trees
A Tree is a Non-Linear Data Structure and a hierarchy containing a collection of nodes such
that each node of the tree stores a value and a list of references to other nodes (the "children").
2. Graphs
A Graph is another example of a Non-Linear Data Structure comprising a finite number of
nodes or vertices and the edges connecting them. The Graphs are utilized to address problems
of the real world in which it denotes the problem area as a network such as social networks,
circuit networks, and telephone networks. For instance, the nodes or vertices of a Graph can
represent a single user in a telephone network, while the edges represent the link between them
via telephone.
Basic Operations of Data Structures
In the following section, we will discuss the different types of operations that we can perform
to manipulate data in every data structure:
1. Traversal: Traversing a data structure means accessing each data element exactly once
so it can be administered. For example, traversing is required while printing the names
of all the employees in a department.
2. Search: Search is another data structure operation which means to find the location of
one or more data elements that meet certain constraints. Such a data element may or
may not be present in the given set of data elements. For example, we can use the search
operation to find the names of all the employees who have the experience of more than
5 years.
3. Insertion: Insertion means inserting or adding new data elements to the collection. For
example, we can use the insertion operation to add the details of a new employee the
company has recently hired.
4. Deletion: Deletion means to remove or delete a specific data element from the given
list of data elements. For example, we can use the deleting operation to delete the name
of an employee who has left the job.
5. Sorting: Sorting means to arrange the data elements in either Ascending or Descending
order depending on the type of application. For example, we can use the sorting
operation to arrange the names of employees in a department in alphabetical order or
, estimate the top three performers of the month by arranging the performance of the
employees in descending order and extracting the details of the top three.
6. Merge: Merge means to combine data elements of two sorted lists in order to form a
single list of sorted data elements.
7. Create: Create is an operation used to reserve memory for the data elements of the
program.
8. Selection: Selection means selecting a particular data from the available data. We can
select any particular data by specifying conditions inside the loop.
9. Update: The Update operation allows us to update or modify the data in the data
structure. We can also update any particular data by specifying some conditions inside
the loop, like the Selection operation.
10. Splitting: The Splitting operation allows us to divide data into various subparts
decreasing the overall process completion time.
Complexities of an Algorithm
The complexity of an algorithm computes the amount of time and spaces required by an
algorithm for an input of size (n). The complexity of an algorithm can be divided into two
types. The time complexity and the space complexity
Time Complexity of an Algorithm
The time complexity is defined as the process of determining a formula for total time required
towards the execution of that algorithm.
Space Complexity of an Algorithm
Space complexity is defining as the process of defining a formula for prediction of how much
memory space is required for the successful execution of the algorithm.
What do you understand by time and space trade-off?
Time Space Trade Off:
It is a way of solving a problem or calculation in less time by using more storage space (or
memory), or by solving a problem in very little space by spending a long time.
It is a case where an algorithm or program trades increased space usage with decreased time.
Here, space refers to the data storage consumed in performing a given task (RAM, HDD, etc),
and time refers to the time consumed in performing a given task (computation time or response
time)
,Need of Time Space Tradeoff:
1.) Less time by using more memory)
2.) By solving a problem in very little space by spending a long time.
,Array
Arrays are defined as the collection of similar types of data items stored at contiguous
memory locations. It is one of the simplest data structures where each data element
can be randomly accessed by using its index number.
Representation of an array
We can represent an array in various ways:
As per the above illustration, there are some of the following important points -
o Index starts with 0.
o The array's length is 10, which means we can store 10 elements.
o Each element in the array can be accessed via its index.
How Do You Declare an Array?
How Do You Initialize an Array?
You can initialize an array in different ways:
o Method 1:
int a[6] = {2, 3, 5, 7, 11, 13};
o Method 2:
int arr[]= {2, 3, 5, 7, 11};
,What Are the Types of Arrays?
There are majorly two types of arrays, they are:
One-Dimensional Arrays:
You can imagine a 1d array as a row, where elements are stored one after another.
Multi-Dimensional Arrays:
These multi-dimensional arrays are again of two types. They are:
Two-Dimensional Arrays:
You can imagine it like a table where each cell contains elements.
Three-Dimensional Arrays:
You can imagine it like a cuboid made up of smaller cuboids where each cuboid can
contain an element.
, Memory allocation of an array
All the data elements of an array are stored at contiguous locations in the main
memory. The name of the array represents the base address or the address of the first
element in the main memory. Each element of the array is represented by proper
indexing.
We can define the indexing of an array in the below ways -
1. 0 (zero-based indexing): The first element of the array will be arr[0].
2. 1 (one-based indexing): The first element of the array will be arr[1].
3. n (n - based indexing): The first element of the array can reside at any random
index number.
In the above image, we have shown the memory allocation of an array arr of size 5.
The array follows a 0-based indexing approach. The base address of the array is 100
bytes. It is the address of arr[0]. Here, the size of the data type used is 4 bytes; therefore,
each element will take 4 bytes in the memory.
Subject-
(Data File Structure)
Class notes-
(2022-2023)
, Content-
Serial No. Topics
Definition-Data file structure, Types, Basic operations.
1
2 Define Array & Its other concepts.
3 Linked list concept.
4 Definition of Stacks & concept.
5 Concept of Queues.
6 Tree structures.
7 Concept of Sorting and Searching.
,What is Data Structure?
Data Structure is a particular way of storing and organizing data in the memory of the computer
so that these data can easily be retrieved and efficiently utilized in the future when required.
Classification of Data Structures
We can classify Data Structures into two categories:
1. Primitive Data Structure
2. Non-Primitive Data Structure
The following figure shows the different classifications of Data Structures.
Primitive Data Structures
1. Primitive Data Structures are the data structures consisting of the numbers and the
characters that come in-built into programs.
2. These data structures can be manipulated or operated directly by machine-level
instructions.
3. Basic data types like Integer, Float, Character, and Boolean come under the
Primitive Data Structures.
4. These data types are also called Simple data types, as they contain characters that can't
be divided further.
,Non-Primitive Data Structures
1. Non-Primitive Data Structures are those data structures derived from Primitive Data
Structures.
2. These data structures can't be manipulated or operated directly by machine-level
instructions.
3. The focus of these data structures is on forming a set of data elements that is
either homogeneous (same data type) or heterogeneous (different data types).
4. Based on the structure and arrangement of data, we can divide these data structures into
two sub-categories -
a. Linear Data Structures
b. Non-Linear Data Structures
Linear Data Structures
A data structure that preserves a linear connection among its data elements is known as a Linear
Data Structure. The arrangement of the data is done linearly, where each element consists of
the successors and predecessors except the first and the last data element.
Based on memory allocation, the Linear Data Structures are further classified into two types:
1. Static Data Structures: The data structures having a fixed size are known as Static
Data Structures. The memory for these data structures is allocated at the compiler time,
and their size cannot be changed by the user after being compiled; however, the data
stored in them can be altered.
The Array is the best example of the Static Data Structure as they have a fixed size,
and its data can be modified later.
2. Dynamic Data Structures: The data structures having a dynamic size are known as
Dynamic Data Structures. The memory of these data structures is allocated at the run
time, and their size varies during the run time of the code. Moreover, the user can
change the size as well as the data elements stored in these data structures at the run
time of the code.
Linked Lists, Stacks, and Queues are common examples of dynamic data structures
Non-Linear Data Structures
Non-Linear Data Structures are data structures where the data elements are not arranged in
sequential order. Here, the insertion and removal of data are not feasible in a linear manner.
There exists a hierarchical relationship between the individual data items.
,Types of Non-Linear Data Structures
The following is the list of Non-Linear Data Structures that we generally use:
1. Trees
A Tree is a Non-Linear Data Structure and a hierarchy containing a collection of nodes such
that each node of the tree stores a value and a list of references to other nodes (the "children").
2. Graphs
A Graph is another example of a Non-Linear Data Structure comprising a finite number of
nodes or vertices and the edges connecting them. The Graphs are utilized to address problems
of the real world in which it denotes the problem area as a network such as social networks,
circuit networks, and telephone networks. For instance, the nodes or vertices of a Graph can
represent a single user in a telephone network, while the edges represent the link between them
via telephone.
Basic Operations of Data Structures
In the following section, we will discuss the different types of operations that we can perform
to manipulate data in every data structure:
1. Traversal: Traversing a data structure means accessing each data element exactly once
so it can be administered. For example, traversing is required while printing the names
of all the employees in a department.
2. Search: Search is another data structure operation which means to find the location of
one or more data elements that meet certain constraints. Such a data element may or
may not be present in the given set of data elements. For example, we can use the search
operation to find the names of all the employees who have the experience of more than
5 years.
3. Insertion: Insertion means inserting or adding new data elements to the collection. For
example, we can use the insertion operation to add the details of a new employee the
company has recently hired.
4. Deletion: Deletion means to remove or delete a specific data element from the given
list of data elements. For example, we can use the deleting operation to delete the name
of an employee who has left the job.
5. Sorting: Sorting means to arrange the data elements in either Ascending or Descending
order depending on the type of application. For example, we can use the sorting
operation to arrange the names of employees in a department in alphabetical order or
, estimate the top three performers of the month by arranging the performance of the
employees in descending order and extracting the details of the top three.
6. Merge: Merge means to combine data elements of two sorted lists in order to form a
single list of sorted data elements.
7. Create: Create is an operation used to reserve memory for the data elements of the
program.
8. Selection: Selection means selecting a particular data from the available data. We can
select any particular data by specifying conditions inside the loop.
9. Update: The Update operation allows us to update or modify the data in the data
structure. We can also update any particular data by specifying some conditions inside
the loop, like the Selection operation.
10. Splitting: The Splitting operation allows us to divide data into various subparts
decreasing the overall process completion time.
Complexities of an Algorithm
The complexity of an algorithm computes the amount of time and spaces required by an
algorithm for an input of size (n). The complexity of an algorithm can be divided into two
types. The time complexity and the space complexity
Time Complexity of an Algorithm
The time complexity is defined as the process of determining a formula for total time required
towards the execution of that algorithm.
Space Complexity of an Algorithm
Space complexity is defining as the process of defining a formula for prediction of how much
memory space is required for the successful execution of the algorithm.
What do you understand by time and space trade-off?
Time Space Trade Off:
It is a way of solving a problem or calculation in less time by using more storage space (or
memory), or by solving a problem in very little space by spending a long time.
It is a case where an algorithm or program trades increased space usage with decreased time.
Here, space refers to the data storage consumed in performing a given task (RAM, HDD, etc),
and time refers to the time consumed in performing a given task (computation time or response
time)
,Need of Time Space Tradeoff:
1.) Less time by using more memory)
2.) By solving a problem in very little space by spending a long time.
,Array
Arrays are defined as the collection of similar types of data items stored at contiguous
memory locations. It is one of the simplest data structures where each data element
can be randomly accessed by using its index number.
Representation of an array
We can represent an array in various ways:
As per the above illustration, there are some of the following important points -
o Index starts with 0.
o The array's length is 10, which means we can store 10 elements.
o Each element in the array can be accessed via its index.
How Do You Declare an Array?
How Do You Initialize an Array?
You can initialize an array in different ways:
o Method 1:
int a[6] = {2, 3, 5, 7, 11, 13};
o Method 2:
int arr[]= {2, 3, 5, 7, 11};
,What Are the Types of Arrays?
There are majorly two types of arrays, they are:
One-Dimensional Arrays:
You can imagine a 1d array as a row, where elements are stored one after another.
Multi-Dimensional Arrays:
These multi-dimensional arrays are again of two types. They are:
Two-Dimensional Arrays:
You can imagine it like a table where each cell contains elements.
Three-Dimensional Arrays:
You can imagine it like a cuboid made up of smaller cuboids where each cuboid can
contain an element.
, Memory allocation of an array
All the data elements of an array are stored at contiguous locations in the main
memory. The name of the array represents the base address or the address of the first
element in the main memory. Each element of the array is represented by proper
indexing.
We can define the indexing of an array in the below ways -
1. 0 (zero-based indexing): The first element of the array will be arr[0].
2. 1 (one-based indexing): The first element of the array will be arr[1].
3. n (n - based indexing): The first element of the array can reside at any random
index number.
In the above image, we have shown the memory allocation of an array arr of size 5.
The array follows a 0-based indexing approach. The base address of the array is 100
bytes. It is the address of arr[0]. Here, the size of the data type used is 4 bytes; therefore,
each element will take 4 bytes in the memory.
