Data Structures

Batch_16 _4 semester

th

CS + IT+ IS Departments




Lecture 1: Introduction to Data Structures

By: Hind Ali

 data structure
A data structure is a way of organizing and storing
data in a computer so that it can be accessed
and used efficiently.
It is also used for processing, retrieving data.
It defines the relationship between the data and the
operations that can be performed on the data.
Key Points:
 Data structures are essential for building efficient
software and solving problems.
 They provide the foundation for implementing
algorithms and designing systems.
Types of Data Structures

There are two types of data structures:

1. Primitive data structure
2. Non-primitive data structure
Primitive Data structure
• Primitive data structures are the basic building
blocks provided directly by the programming
language.
• The primitive data structures are primitive data
types. The int, char, f loat, double, and pointer are the
primitive data structures that can hold a single value.
Non-Primitive Data structure
• Non-primitive data structures are more complex and
allow storing multiple values.
• The non-primitive data structure is divided into two
types:
– Data is organized in a sequential order.:Linear data
structure
(array, linked list , queue , stack).
– Data is organized in a hierarchical or interconnected
manner.:Non-linear data structure
(graph , tree).
Types of Data Structures
Why are Data Structures Important?


Data structures are essential for the following reasons:
• Efficient Data Management:

Enable fast storage, retrieval, and processing of data, improving overall
performance.
• Data Organization:

Organize data logically, making it easier to understand, access, and
manipulate.
• Data Abstraction:

Hide low-level implementation details, allowing developers to focus on
solving problems rather than how data is stored.
• Algorithm Optimization:

The right data structure can significantly improve the efficiency of
algorithms.
• Improved Program Performance:

Better speed and memory usage result from choosing the appropriate
data structure.
• Simplifying Complex Problems:

Help represent and solve complex real-world problems in a manageable
way.
Applications of Data Structures


• Data structures are widely used in many fields, including:
• Database Management Systems (DBMS):

Used to store, retrieve, and manage large amounts of
structured data efficiently.
• Operating Systems:

Used in managing memory allocation, process scheduling,
and file systems.
• Compiler Design:

Help in representing syntax trees, symbol tables, and
intermediate code during program translation.
• Artificial Intelligence (AI):

Used to represent knowledge, support reasoning, and
implement learning algorithms.
• Graphics and Multimedia:

Used to handle and manipulate images, videos, and audio
data efficiently
Major Operations
The common operations performed on data structures
include:
– Searching: Finding the location of a specific
element within the data structure.
– Sorting: Arranging elements in a specific order
(e.g., ascending or descending).
– Insertion: Adding a new element to the data
structure.
– Updating: Modifying an existing element by
replacing it with a new value.
– Deletion: Removing an element from the data
structure
Data Structure Philosophy

 Each data structure has costs and

benefits.
 Rarely is one data structure better than
another in all situations.
 A data structure requires:
– space for each data item it stores,
– time to perform each basic operation,
– programming effort.
 Efficiency

 A solution is said to be efficient if it solves the

problem within its resource constraints.
 Space
 Time

 The cost of a solution is the amount of resources

that the solution consumes.
 Array
• An array is an elementary data structure that exists as a
built-in feature in most programming languages.
• It is a linear data structure that stores a collection of
elements of the same data type in contiguous memory
locations.
• Each element in an array has a unique index, and indexing
starts from 0,(i.e., the first element is at index 0, the second
at index 1, and so on.)
• Accessing elements is done using the index.
• Example: arr[2] accesses the third element.
• Once declared, the size of the array is f ixed and cannot be
changed during the execution of the program.
• Arrays can be multi-dimensional, such as 2D arrays
(matrices), 3D arrays, etc.
• The number of elements in an array can be calculated
using the sizeof operator in languages like C/C++.
• Example: sizeof(arr) / sizeof(arr[0]).
Array Declaration in C++

• In C++, we can declare an array by simply specifying the

data type first and then the name of an array with its size.

data_type array_name[Size_of_array];
• Example
int arr[5];
int: It is the type of data to be stored in the array. We can
also use other data types such as char, float, and double.
arr: It is the name of the array.
5: It is the size of the array which means only 5 elements
can be stored in the array.


Initialization of Array in C++
We can initialize an array in many ways but we will discuss
some most common ways to initialize an array. We can
initialize an array at the time of declaration or after declaration.
1. Initialize Array with Values
We have initialized the array with values. The values enclosed in
curly braces ‘{}’ are assigned to the array. Here, 1 is stored in
arr[0], 2 in arr[1], and so on. Here the size of the array is 5.
int arr[5] = {1, 2, 3, 4, 5};
2. Initialize Array with Values and without Size
We have initialized the array with values but we have not declared
the length of the array, therefore, the length of an array is equal
to the number of elements inside curly braces.
int arr[] = {1, 2, 3, 4, 5};
Characteristics of an Array:
 An array has various characteristics which are as
follows:
 Arrays use an index-based data structure which
helps to identify each of the elements in an array
easily using the index.
 If a user wants to store multiple values of the
same data type, then the array can be utilized
efficiently.
 An array can also handle complex data structures
by storing data in a two-dimensional array.
 An array is also used to implement other data
structures like Stacks, Queues, Heaps, Hash
tables, etc.
 The search process in an array can be done very
easily.
Types of Arrays
Arrays can be classified in two ways:
– On the basis of Size.
– On the basis of Dimensions.
Types of Arrays:
There are basically two types of arrays:
• Static Array: In this type of array, memory is allocated at compile
time having a fixed size of it. We cannot alter or update the size of
this array.
• Dynamic Array: In this type of array, memory is allocated at run time
but not having a fixed size. Suppose, a user wants to declare any
random size of an array, then we will not use a static array, instead
of that a dynamic array is used in hand. It is used to specify the size
of it during the run time of any program.
Example:
• Let us take an example, int a[5] creates an array of size 5 which
means that we can insert only 5 elements; we will not be able to
add 6th element because the size of the array is fixed above.
Types of Arrays on the basis of Dimensions

1. One-dimensional Array(1-D Array): You

can imagine a 1d array as a row, where
elements are stored one after another.
2. Multi-dimensional Array: A multi-dimensional array is an
array with more than one dimension. We can use
multidimensional array to store complex data in the form
of tables, etc. We can have 2-D arrays, 3-D arrays, 4-D arrays
and so on.
Two-Dimensional Array(2-D Array or Matrix):
2-D Multidimensional arrays can be considered as an array
of arrays or as a matrix consisting of rows and columns.
• A two-dimensional array is a grouping of elements
arrange d in ro ws and c o lumns. E ac h e le me nt is
accessed using two indices: one for the row and one for
the column, which makes it easy to visualize as a table
or grid.
• Syntax of 2D array
data_Type array_name[n][m];Where,
• n: Number of rows.
• m: Number of columns
Three-Dimensional Array(3-D Array):
A 3-D Multidimensional array contains three
dimensions, so it can be considered an array of two-
dimensional arrays.
Accessing an Element of an Array

• Elements of an array can be accessed by specifying

the name of the array, then the index of the element
enclosed in the array subscript operator []. For example,
arr[i].
Example 1: The C++ Program to Illustrate How to Access Array Elements
// C++ Program to Illustrate How to Access Array Elements
#include <iostream.h>
main()
{
int arr[3];
// Inserting elements in an array
arr[0] = 10;
arr[1] = 20;
arr[2] = 30;
 // Accessing and printing elements of the array
cout << "arr[0]: " << arr[0] << endl;
cout << "arr[1]: " << arr[1] << endl;
cout << "arr[2]: " << arr[2] << endl;
return 0;
}
Output
arr[0]: 10
arr[1]: 20
arr[2]: 30
Traverse an Array

• We can traverse over the array with the help of a loop using
indexing in C++. First, we have initialized an array ‘Arr’ with a
multiple of 2. After that, we run a for loop from 0 to 9 because
in an array indexing starts from zero. Therefore, using the
indices we print all values stored in an array.
• Example 2: The C++ Program to Illustrate How to
Traverse an Array
// C++ Program to Illustrate How to Traverse an Array
#include <iostream>

int main()
{
// Initialize the array
int Arr[10] = { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };

// Traverse the array using for loop

for (int i = 0; i < 10; i++) {
// Print the array elements using indexing
cout << Arr [i] << " ";
}
}
Search, Insert, and Delete in an Array | Array Operations




Search Operation:
• In an unsorted array, the search operation
can be performed by linear traversal from
the first element to the last element.
// C++ program to implement search in unsorted array
#include <iostream>
using namespace std;
// Function to implement search operation
int FindElement(int arr[], int n, int key)
{
for (int i = 0; i < n; i++)
if (arr[i] == key)
return i;
// If the key is not found
return -1;
}
// Driver's Code
int main()
{
int arr[] = { 5, 1, 3, 4, 2, 6};
int n = sizeof(arr) / sizeof(arr[0]);

// Using a last element as search element

int key = 3;

// Function call
int position = findElement(arr, n, key);

if (position == -1)
cout << "Element not found";
else
cout << "Element Found at Position: "
<< position + 1;

return 0;
}
Insert Operation:

#include <iostream>
using namespace std;
// Inserts a key in arr[] of the given capacity.
// n is the current size of arr[]. This
// function returns n + 1 if insertion
// is successful, else n.
int insertEnd(int arr[], int n, int key, int capacity)
{
// Cannot insert more elements if n is already more than or
equal to capacity
if (n >= capacity)
return n;
// insert arr[n] = key;
return (n + 1);
}
int main()
{
int arr[] = { 5, 1, 4, 2, 6};
int capacity = sizeof(arr) / sizeof(arr[0]);
int n = 6;
int i, key = 3;

cout << "Before Insertion: ";

for (i = 0; i < n; i++)
cout << arr[i] << " ";
// Inserting key
n = insertEnd(arr, n, key, capacity);
cout << "\nAfter Insertion: ";
for (i = 0; i < n; i++)
cout << arr[i] << " ";

return 0;
}
Applications of Arrays as a Data Structure

• Arrays serve as a foundation for various

c ompu tati on al tas ks an d are a c ore
element of many data structures and
al gor i th ms . H ere are s ome s pec i f ic
applications of arrays as a data structure:
– Data Storage and Representation
– Building Blocks for Other Data Structures
– Searching and Sorting Algorithms
– Matrix Representation and Operations
– Representation of Graphs
Advantages of Arrays as a Data Structure
• Random Access: Constant-time access using an
index.
• Ef fic i e nc y: S i m p l i f ie s i m p l e m e ntati on of
algorithms like sorting and searching.
• Compact Memory Usage: Elements stored in
contiguous memory locations.
 pointers
C++ pointers are a fundamental feature that allows direct memory access and
manipulation, enabling dynamic memory allocation, ef ficient array handling,
and the implementation of complex data structures. Understanding pointers
is crucial for leveraging C++'s full potential in creating ef ficient and powerful
applications.
Syntax
Pointers in C++ are declared using the following syntax:
datatype *pointer_name; // or
datatype* pointer_name; // or

We use the asterisk (*) symbol to designate a variable as a pointer in

The asterisk symbol can be placed anywhere before the pointer name and
after the datatype.
If we have to declare two (or more) pointers together in the same line, we will
need to use the asterisk symbol before each variable name. For example:
Int * var1, *var2; // Both var1 and var2 are pointers
int* var1, var2; // var1 is a pointer, var2 is an integer variable
#include <iostream>
int main()
{
int var = 23;
int *ptr;
ptr = &var;
cout << "Initial value of var is: " << var << endl;
cout << "Initial value of *ptr is: " << *ptr << endl
}
 Relation between Arrays and Pointers

In C++, arrays and pointers are closely related to each

other. The array name is treated as a pointer that stored
the memory address of the f irst element of the array. In
array elements are stored at contiguous memory locations
that’s why we can access all the elements of an array
using the array name.
Example : Illustrating the Relationship between Array and Pointers
// C++ Program to Illustrate that Array Name is a Pointer
// that Points to First Element of the Array
#include <iostream>

int main()
{
// Defining an array
int arr[] = { 1, 2, 3, 4 };

// Define a pointer
int* ptr = arr;
// Printing address of the arrary using array name
cout << "Memory address of arr: " << &arr << endl;
// Printing address of the array using ptr
cout << "Memory address of arr: " << ptr << endl;
return 0;
}
Output :
Memory address of arr: 0x7fff2f2cabb0
Memory address of arr: 0x7fff2f2cabb0
• In the above code, we f ir st def in e an array “arr” and then
declare a pointer “ptr” and assign the array “arr” to it. We are
able to assign arr to ptr because arr is also a pointer. After that,
we print the memory address of arr using reference operator
(&) and also print the address stored in pointer ptr and we can
see arr and ptr, both stores the same memory address.
 Exercise
Write a C++ program that performs the following tasks:
Ask the user to input the number of students n.
Dynamically create an array to store the grades of n students.
Write three separate functions to:
Calculate the average grade.
Find the maximum grade.
Find the minimum grade.
These functions must accept pointers (i.e., use pointer notation only –
do not use array indexing [] inside the functions).
Display the calculated results.
Properly deallocate the dynamic memory used.