DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

DATA STRUCTURE USING C++

BCAMJ23402 Unit 2

Unit 2 Syllabus
Introduction: Basic Terminology, Elementary Data Organization, Data Structure operations,
Algorithm Complexity and Time Space trade off. Arrays : Array Definition, Representation and
Analysis, Single and Multidimensional Arrays, address calculation, application of arrays, Character
String in C, Character string operation, Array as Parameters, Sparse Matrices, and Vectors, Arrays in
terms of pointers, Static and Dynamic Memory Management. Tower of Hanoi Problem.

A data structure is a particular way of storing and organizing data in a computer so

that it can be used efficiently different kinds of data structures are used to different kinds of
applications, and some are highly specialized to specific tasks Data structures provide a
means to manage large amounts of data efficiently, such as large databases.

BASIC TERMINOLOGY; ELEMENTARY DATA ORGANIZATION

Data are simply values or set of values

A data item is either the value of a variable or a constant. For example, a data item is a row in
a database table, which is described by a data type. A data item that does not have
subordinate data items is called an elementary item. A data item that is composed of one or
more subordinate data items is called a group item.

A record can be either an elementary item or a group item. For example, an employee’s name
may be divided into three sub items – first name, middle name and last name – but the
social_security_number would normally be treated as a single item.

An entity is something that has certain attributes or properties which may be assigned
values. The values themselves may be either numeric or nonnumeric. For example, an
employee of a given organization is entity.

Entities with similar attributes (E.g. all the employees in an organization) collectively form
an entity set. Each attributes of an entity set has a range of values. The set of all possible
values could be assigned to the particular attributes.

A field is a single elementary unit of information representing an attributes of an entity,

A record is the collection of field values of a given entity

A file is the collection of records of theentities in given entity set.

Each record in a file may contain many field items, but the value in a certain field may
uniquely determine the record in the file. Such a field K is called a Primary Key, and the
values K1, K2….in such field are called keys or key values.

The Information is a Processed Data. That will useful for Decision making.

1|Page
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

Data Structure is a Logical or mathematical description of the structure. The Choice of a

particular Data structure depends on the following Consideration:
 It Must be able to represent the relationship of data.
 It can be simple so that it can be process efficiently

The data structure includes :

 Logical description of Data structure.
 Implementation of Data structure.
 Quantitative analysis of the data structure, which includes determining the amount of
memory needed to store the structure and the time required to process the structure.

TYPE OF DATA STRUCTURE

The data Structure can be divided into two parts

Linear Data Structure

A data structure whose element form a sequence, and every element in the structure has a
unique predecessor and unique successor For ex. Array, linked List, Stack and Queue.

Non Linear Data Structure

A data structure whose element do not form a sequence, There is no unique predecessor and
unique successor. For ex. Tree and Graph.

DATA STRUCTURE OPERATION

The various operations that can be performed on different Data Structure are described
below:
(a) Traversal. Processing each element in the list.
(b) Search. Finding the location of the element with a given value or the record with a given
key.
(c) Insertion. Adding a new element to the list.
(d) Deletion. Removing an element from the list.
(e) Sorting. Arranging the elements in some type of order.
(f) Merging. Combining two lists into a single list.

ALGORITHM:
An algorithm is a set of instructions, sometimes called a procedure or a function that is used
to perform a certain task.
Every Algorithm must satisfy the following criteria : -
 Input : There are zero or more values which are extremely supplied.
 Output : At Least one value is produced
 Definiteness: Each step must be clear and ambiguous.
 Finiteness: If we trace the steps of algorithm, therefore all cases, the algorithm must
terminate after a finite no of steps.

ALGORITHM NOTATION:

Variable Name

2|Page
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

Variable Name will use capital letter Only ex. MAX, SUB.

Assignment Statement
Assignment Statements will use colon equal Notation ex. MAX:=DATA[1]

Input and Output

Data may be input and assigned to a variable by means of a Read Statement with the
following form ex. Read : VARIABLE NAME
Similarly message placed in quotation marks data in variable smay be output by means of
Write or Print statement ex. Write : Message or Variable Name.

Procedure
The term procedure will be used for an independent algorithm module which solves a
particular problem.

Comment
Each step may contain a comment in the Square Brackets which indicate the main purpose of
the steps.

CONTROL STRUCTURE:
Algorithms are contains three kinds control structure

Sequence Control
It Contains only the Sequence of statements.

Selection Control
It Contains the if structure
Ex. If [Condition] then:
[module]
[EndIf]

Iteration Control
Repeat for k=1 to n by 1
[module]
[end of the loop]

EXAMPLE : Write an Algorithm to find the largest between n numbers

Algorithm : Largest(A[ ],N,MAX,I)

STEP 1 : I := 1, LOC := 1, MAX := A[I]
STEP 2 : Repeat STEP 3 & 4 While(I<=N)
STEP 3 : IF MAX < A[I]
MAX:=A[I] & LOC:=I
STEP 4 : I:=I+1[Increment]
STEP 5 : PRINT MAX, LOC
STEP 6 : EXIT

3|Page
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

ANALYSIS/EFFICIENCY/COMPLEXITY OF AN ALGORITHM
The complexity of an algorithm is a function describing the efficiency of the algorithm in
terms of the amount of data the algorithm must process. Usually there are natural units for the
domain and range of this function. There are two main complexity measures of the efficiency
of an algorithm:

Space complexity is a function describing the amount of memory (space) an algorithm takes
in terms of the amount of input to the algorithm. The space needed by a program is consist of
following components

Instruction Space
The space needed to store executable version of the program.

Data Space
Space needed to store all constants, variables, and values.

Environmental Stack Space

Space needed to store the information needed to resume the suspended function.

Recursive Stack Space

The amount of space needed by recursive function is called recursive stack space

Time complexity is a function describing the amount of time an algorithm takes for
execution. To measure the time complexity we can count all the operation performed in an
algorithm. If we know the time for each one of the primitive operation performed on a given
computer we can easily compute the time taken by an algorithm to complete its execution.
This time will vary system to system.

Time Space Tradeoffs:

The best algorithm to solve a problem is one that require less space in memory and takes less
time to complete its execution but it is not always possible to achieve both of its objective.

There are more than one approach to solve the same problem one approach may require more
space but it takes less time to complete its execution while other approach require less space
but takes more time to complete its execution. So we can say that there exist a time space
trade of among algorithm.

Algorithm Efficiency:

The general format is f(n)=Efficiency

For Linear Loop

for(i=1;i<=1000;i++)
{}

f(n)=1000
the general form is f(n)=n

4|Page
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

for(i=1;i<=1000;i=i+2)
{}

f(n)=500
the general form is f(n)=n/2

Nested Loop:

Iteration=Inner loop * Outer loop

for(i=1;i<=10;i++)
{
for(j=1;j<=10;j++)
{
/*statements*/
}
}

the general form is f(n)=n2

Dependent Quadratic :

for(i=1;i<=10;i++)
{
for(j=1;j<=i;j++)
{
/*statements*/
}
}

1+2+3+4+5+6+7+8+9+10=55
Average=55/10=5.5
We can generalize as (n+1)/2
Multiply inner by outer loop f(n)=n((n+1)/2)

BIG O NOTATION
Big Oh is a characterization scheme that allows to measure the properties of algorithm such
as performance and memory requirement. Big oh Notation can be derived from f(n) using
following steps.
 In each term set the coefficient of the term to 1.
 Keep the largest term in the function and discard the other.
Ex f(n)=n((n+1)/2)
We first remove all coefficient tis gives us
f(n) = n2 + n
After removing the smallest factor
We have f(n) = n2
Which is big o Notation is stated as
5|Page
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

F(n) = O(n2)

Another ex.
F(n) = ajnk + aj-1nk-1 + - - - - - - - - - - - - - - - a2n2 + a1n + a0

F(n)=O(nk)

Standard Measure of Efficiency/Complexity if n=10000

EFFICIENCY BIG O ITERATION TIME

Logarithmic O(logn) 14 Microsecond
Linear O(n) 10000 Second
Linear Logarithmic O(nlogn) 140000 Minutes
Quadratic O(n2) (10000)2 Minutes
Polynomial O(nk) (10000)k Hours
Exponential O(en) e10000 Intact able
Factorial O(n!) (10000)! Intact able

ARRAY

ARRAY
An Array is a collection of homogeneous data element (elements of same type) described by
the same name. Each element of an array is referenced by subscripted variable.

Linear Array
 A Linear array is a list of a finite no n of homogeneous data element such that
 The element of an array are referenced by an index set.
 The element of an array are stored in consecutive memory location.
 Array name is actually a pointer to the first location of the memory block allocated to
the name of the array.
 An array either be a integer, character or floating data type.
 There is no bound checking concepts for array in C. It is up to programmer to check
upper bound of array.

Size of an Array
The general equation to find the length or the number of data elements of the array is,
Length = UB – LB + 1
where, UB is the largest index, called the upper bound, and LB is the smallest index,
called the lower bound of the array. Remember that length=UB when LB=1.
Also, remember that the elements of an array A may be denoted by the subscript notation,
A1, A2, A3……..An

REPRESENTATION OF LINEAR ARRAYS IN MEMORY

Consider LA be a linear array in the memory of the computer. As we know that the memory
of the computer is simply a sequence of addressed location as pictured in figure as given
below.

6|Page
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

int A[10];

1001 11 A[1]
1003 22 A[2]
1005 33 A[3]
1007 44 A[4]
1009 55 A[5]
1011 66 A[6]
1013 77 A[7]
1015 88 A[8]
1017 99 A[9]
1019 110 A[10]

Let we use the following notation when calculate the address of any element in linear arrays
in memory, LOC(LA[K]) = address of the element LA[K] of the array LA.
As previously noted, the elements LA are stored in successive memory cells. Accordingly,
the computer does not need to keep track of the address of ever element of LA, but needs to
keep track only of the address of the first element of LA, which is denoted by Base(LA)
and called the base address of LA. Using this address Base(LA), the computer calculates
the address of any element of LA by the following formula:
LOC(LA[K]) = Base(LA) + w (K- lower bound)
where w is the number of words per memory cell for the array LA.

For Example find the location k=5

LOC(LA[K]) = Base(LA) + w (K- lower bound)
= 1001 + 2 * (5 – 1)
= 1001 + 8
= 1009

TRAVERSING LINEAR ARRAYS

The following algorithm is used to traversing a linear array LA.

Algorithm : TRAVERSE(LA, LB, UB, K)
1. [Initialize counter] Set K:= LB.
2. Repeat Steps 3 and 4 while K<= UB
3. [Visit element] Apply PROCESS to LA[K]
4. [Increase counter] Set K:= K + 1
[End of Step 2 loop]
5. Exit.

We also state an alternative form of the algorithm which uses a repeat-for loop instead of the
repeat-while loop. This algorithm traverses a linear array LA with lower bound LB and upper
bound UB.
Algorithm : TRAVERSE(LA, LB, UB, K)
1. Repeat for K = LB to UB:
Apply PROCESS to LA[K].
[End of loop]
2. Exit.

INSERTING
7|Page
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

This algorithm inserts an element ITEM into the K th position in LA.

Algorithm : INSERT(LA, LB, UB, N, K, ITEM)
1. [Initialize counter] Set J := N
2. Repeat Steps 3 and 4 while J >= K.
3. [Move Jth element downward] Set LA[J+1] := LA[J]
4. [Decrease counter] Set J : = J-1
[End of Step 2 loop]
5. [Insert element] Set LA[K] := ITEM
6. [Reset N] Set n:= N+1
7. Exit

DELETING
This algorithm deletes the Kth element from LA.
Algorithm : DELETE(LA, LB, UB, N, K, ITEM)
1. Set ITEM:= LA[K]
2. Repeat for J = K to N-1
[Move J + 1st element upward] Set LA[J] := LA[J+1]
[End of loop]
3. [Reset the number N of elements in LA] Set N := N – 1.
4. Exit.

Two-Dimensional Arrays
A two-dimensional m x n array A is a collection of m . n data elements such that each element
is specified by a pair of integers (such as J, K), called subscripts.

Size of Two Dimensional Arrays:

Size = Row * column = m* n

Representation of two Arrays in Memory:

Two dimensional Array can be stored in two different ways.
 Row Major Order
 Column major Order

Row Major Order

In Row Major Order the elements are stored row by row n elements of first row are stored in
first n location, element of the second row are stored in next n Location and so on.

For ex. int A[3][3];

1001 11 A[1][1]
1003 22 A[1][2]
1005 33 A[1][3]
1007 44 A[2][1]
1009 55 A[2][2]
1011 66 A[2][3]
1013 77 A[3][1]
1015 88 A[3][2]
1017 99 A[3][3]

8|Page
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

Finding Location in row Major order :

The formula for row major order is,
LOC(A[I, J]) = Base(A) + w[N(I-LB1) + (J-LB2)]

Where Base(A) is a base Address, w is the size of each element of the array, m is the no of
rows, n is the no of column, LB1 is the lower bound of row, LB@ is the lower bound of
column.

For ex. Find the location of A[2][3]

LOC(A[I, J]) = Base(A) + w[N(I-LB1) + (J-LB2)]

LOC(A[2][3]) = 1001 + 2 * [3*(2-1) + (3-1)]
= 1001 + 2 * 5
LOC(A[2][3]) =1011

Column Major Order

In Column Major Order the elements are stored column by column m elements of first
column are stored in first m location, element of the second column are stored in next m
Location and so on.

For ex. int A[3][3];

1001 11 A[1][1]
1003 22 A[2][1]
1005 33 A[3][1]
1007 44 A[1][2]
1009 55 A[2][2]
1011 66 A[3][2]
1013 77 A[1][3]
1015 88 A[2][3]
1017 99 A[3][3]

Finding Location in Column Major order:

The formula for column major order is,
LOC(A[I, J]) = Base(A) + w[M(J-LB2) + (I-LB1)]

Where Base(A) is a base Address, w is the size of each element of the array, m is the no of
rows, n is the no of column, LB1 is the lower bound of row, LB2 is the lower bound of
column.

For ex. Find the location of A[2][3]

LOC(A[I, J]) = Base(A) + w[M(J-LB2) + (I-LB1)]

LOC(A[2][3]) = 1001 + 2 * [3*(3-1) + (2-1)]
= 1001 + 2 * 7
LOC(A[2][3]) =1015

Example : Write an algorithm for multiplication of two matrix.

Algorithm : MATMUL(A[], B[], C[], M, N, P, I, J, K)
9|Page
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

1. Repeat step 2 to 4 for I=1 to M

2. Repeat step 3 to 4 for J= 1 to N
3. [initialize] C[I][J] := 0
4. Repeat for K=1 to P
5. C[I][J] = C[I][J]+A[I][K]*B[K][J]
6. [End of inner loop}
7. [End of step 2 middle loop]
8. [End of step 1 Outer Loop]
9. Exit

Array as Parameters in C++

In C++, when you pass an array to a function, what actually gets passed is a pointer to the
first element of the array. This means that any changes make to the array inside the
function affect the original array, and the function doesn't know the size of the array
unless pass it as an additional parameter.

Key Points:
1. Decaying into a Pointer:
o When an array is passed as a parameter, it "decays" into a pointer to its first
element.
o For example, if you have an int arr[5], passing it to a function means the
function receives an int*.
2. Size Information:
o The function does not inherently know the size of the array.
o You usually need to pass the size as an extra parameter.
3. Modifying the Array:
o Since the function receives a pointer to the original array, modifications within
the function will change the actual array.
4. Syntax for Passing Arrays:
o You can declare the function parameter as int arr[] or int *arr—both are
equivalent in this context.

Example Code:

#include <iostream>
using namespace std;
// Function to print elements of an array
void printArray(int arr[], int size)
{
cout << "Array elements: ";
for (int i = 0; i < size; i++)
{
cout << arr[i] << " ";
}
cout << endl;
}

// Function to modify the array (e.g., double each element)

void doubleArray(int arr[], int size)
{
for (int i = 0; i < size; i++)
10 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

{
arr[i] *= 2; // Modifies the original array
}
}

int main()
{
int myArray[5] = {1, 2, 3, 4, 5};

// Pass the array and its size to the function

printArray(myArray, 5);

// Modify the array

doubleArray(myArray, 5);

// Print the modified array

printArray(myArray, 5);

return 0;
}

Explanation:
 Function printArray:
o Declaration:
void printArray(int arr[], int size)
Here, arr[] is equivalent to int *arr, and size is passed so the function knows how
many elements to process.
o Loop:
Iterates from 0 to size - 1 to print each element.
 Function doubleArray:
o Modification:
The function loops through the array, doubling each element. Since arr points
to the original array in main(), the modifications are reflected there.
 Main Function:
o An array myArray is defined and initialized.
o printArray is called to display the original array.
o doubleArray is then called to modify the array.
o printArray is called again to show the changes.

Sparse Matrix and its representations

A matrix is a two-dimensional data object made of m rows and n columns, therefore having
total m x n values. If most of the elements of the matrix have 0 value, then it is called a
sparse matrix.

In many applications (e.g., finite element methods) it is common to deal with very large
matrices where only a few coefficients are different from zero. In such cases, memory
consumption can be reduced and performance increased by using a specialized representation
storing only the nonzero coefficients. Such a matrix is called a sparse matrix.

11 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

1 0 0 1 
   
 5 6 0 5 6 
2 9 8  2 9 8
   

Matrix Sparse Matrix

Why to use Sparse Matrix instead of simple matrix ?

 Storage: There are lesser non-zero elements than zeros and thus lesser memory can
be used to store only those elements.
 Computing time: Computing time can be saved by logically designing a data
structure traversing only non-zero elements.

Example:

00304
00570
00000
02600

Representing a sparse matrix by a 2D array leads to wastage of lots of memory as zeroes in

the matrix are of no use in most of the cases. So, instead of storing zeroes with non-zero
elements, we only store non-zero elements. This means storing non-zero elements
with triples- (Row, Column, value).
Sparse Matrix Representations can be done in many ways following are two common
representations:
1. Array representation
2. Linked list representation

Method 1: Using Arrays:

2D array is used to represent a sparse matrix in which there are three rows named as
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index – (row,column)

#include <iostream>
using namespace std;

int main()
{
12 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

// Assume 4x5 sparse matrix

int sparseMatrix[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};

int size = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
size++;

// number of columns in compactMatrix (size) must be equal to number of non - zero

//elements in sparseMatrix
int compactMatrix[3][size];

// Making of new matrix

int k = 0;
for (int i = 0; i < 4; i++)
for (int j = 0; j < 5; j++)
if (sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}

for (int i=0; i<3; i++)

{
for (int j=0; j<size; j++)
cout <<" "<< compactMatrix[i][j];

cout <<"\n";
}
return 0;
}
Output
001133
242312
345726

Time Complexity: O(NM), where N is the number of rows in the sparse matrix, and M is
the number of columns in the sparse matrix.

Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined as:
13 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

 Row: Index of row, where non-zero element is located

 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index – (row,column)
 Next node: Address of the next node

Vector in C++
Vector is a dynamic array with the ability to resize itself automatically when an element
is inserted or deleted. It is the part Standard Template Library (STL) and provide various
useful functions for data manipulation.

Syntax of Vector
Vector is defined as the std::vector class template which contains its implementation and
some useful member functions. It is defined inside the <vector> header file.
vector<T> vec_name;
where,
 T: Type of elements in the vector.
 vec_name: Name assigned to the vector.
Declaration and Initialization
Declaration and initialization are the process of creating an instance of std::vector class and
assigning it some initial value. In C++, vectors can be declared and initialized in multiple
ways as shown below:
1. Default Initialization
An empty vector can be created using the below declaration. This vector can be filled later on
in the program.
vector<T> vec_name;
2. Initialization with Size and Default Value
A vector of a specific size can also be declared and initialized to the given value as default
value.
vector<T> vec_name(size, value);
3. Initialization Using Initializer List
Vector can also be initialized using a list of values enclosed in {} braces separated by
comma.
vector<T> vec_name = { v1, v2, v3….};
vector<T> vec_name ({ v1, v2, v3….});

Enable C++11 or Later in Dev-C++ for Vector

1. Open Dev-C++
2. Go to → Tools → Compiler Options
3. In the "Add the following commands when calling the compiler" box, add:
14 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

-std=c++11

Let’s take a look at an example that shows implements the above methods:
#include <bits/stdc++.h>// #include<vector>
using namespace std;

void printV(vector<int> v)
{
for (int i = 0; i < v.size(); i++)
{
cout << v[i] << " ";
}
cout << endl;
}

int main()
{
// Creating an empty vector
vector<int> v1;

// Creating a vector of 5 elements from

// initializer list
vector<int> v2 = {1, 4, 2, 3, 5};

// Creating a vector of 5 elements with

// default value
vector<int> v3(5, 9);

printV(v1);
printV(v2);
printV(v3);

return 0;
}

Output
14235
99999

Basic Vector Operations

The basic operations of vector are shown below:
1. Accessing Elements
Just like arrays, vector elements can be accessed using their index inside the [] subscript
operator. This method is fast but doesn’t check whether the given index exists in the vector
or not. So, there is another member method vector at() for safely accessing elements:
The below example illustrates how to access the vector elements:
#include <bits/stdc++.h>
using namespace std;

15 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

int main() {
vector<char> v = {'a', 'c', 'f', 'd', 'z'};

// Accessing and printing values using indexes

cout << v[3] << endl;
cout << v.at(2);

return 0;
}

Output
d
f
To know more about accessing vector elements, refer to the article – How to Access an
Element in a Vector in C++?
2. Updating Elements
Updating elements is very similar to the accessing except that we use an additional
assignment operator to assign a new value to a particular element. It uses the same methods:
[] subscript operator and vector at().
The below example illustrates how to update vector elements:
#include <bits/stdc++.h>
using namespace std;

int main() {
vector<char> v = {'a', 'c', 'f', 'd', 'z'};

// Updating values using indexes 3 and 2

v[3] = 'D';
v.at(2) = 'F';

cout << v[3] << endl;

cout << v.at(2);

return 0;
}

Output
D
F

3. Traversing Vector
Vector in C++ can be traversed using indexes in a loop. The indexes start from 0 and go up to
vector size – 1. To iterate through this range, we can use a loop and determine the size of the
vector using the vector size() method.
#include <bits/stdc++.h>
using namespace std;

int main() {
vector<char> v = {'a', 'c', 'f', 'd', 'z'};

16 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

// Traversing vector using vector size()

for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
return 0;
}

Output
acfdz
acfdz
More ways to traverse vectors are discussed in this article – How to Iterate Through a Vector
in C++?
4. Inserting Elements
An element can be inserted into a vector using vector insert() method which takes linear
time. But for the insertion at the end, the vector push_back() method can be used. It is much
faster, taking only constant time.
The below example illustrates how to insert elements in the vector:
#include <bits/stdc++.h>
using namespace std;

int main() {
vector<char> v = {'a', 'f', 'd'};

// Inserting 'z' at the back

v.push_back('z');

// Inserting 'c' at index 1

v.insert(v.begin() + 1, 'c');

for (int i = 0; i < v.size(); i++) {

cout << v[i] << " ";
}
return 0;
}

Output
acfdz
More ways to insert an element in the vector are discussed in this article – How to Add
Elements in a Vector in C++?
5. Deleting Elements
An element can be deleted from a vector using vector erase() but this method needs iterator
to the element to be deleted. If only the value of the element is known, then find() function is
used to find the position of this element.
For the deletion at the end, the vector pop_back() method can be used, and it is much faster,
taking only constant time.
The below example demonstrates how to delete an element from the vector:
#include <bits/stdc++.h>
using namespace std;

int main() {
17 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

vector<char> v = {'a', 'c', 'f', 'd', 'z'};

// Deleting last element 'z'

v.pop_back();
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
cout << endl;

// Deleting element 'f'

v.erase(find(v.begin(), v.end(), 'f'));
for (int i = 0; i < v.size(); i++) {
cout << v[i] << " ";
}
return 0;
}

Output
acfd
acd

What is Memory Management?

Memory management is a process of managing computer memory, assigning the memory
space to the programs to improve the overall system performance.

Why is memory management required?

As we know that arrays store the homogeneous data, so most of the time, memory is allocated
to the array at the declaration time. Sometimes the situation arises when the exact memory is
not determined until runtime. To avoid such a situation, we declare an array with a maximum
size, but some memory will be unused. To avoid the wastage of memory, we use the new
operator to allocate the memory dynamically at the run time.

Memory Management Operators

In C language, we use the malloc() or calloc() functions to allocate the memory dynamically
at run time, and free() function is used to deallocate the dynamically allocated
memory. C++ also supports these functions, but C++ also defines unary operators such
as new and delete to perform the same tasks, i.e., allocating and freeing the memory.

New operator
A new operator is used to create the object while a delete operator is used to delete the
object. When the object is created by using the new operator, then the object will exist until
we explicitly use the delete operator to delete the object. Therefore, we can say that the
lifetime of the object is not related to the block structure of the program.

Syntax
1. pointer_variable = new data-type
The above syntax is used to create the object using the new operator. In the above
syntax, 'pointer_variable' is the name of the pointer variable, 'new' is the operator,
and 'data-type' defines the type of the data.
18 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

Example 1:
1. int *p;
2. p = new int;
In the above example, 'p' is a pointer of type int.
Example 2:
1. float *q;
2. q = new float;
In the above example, 'q' is a pointer of type float.
In the above case, the declaration of pointers and their assignments are done separately. We
can also combine these two statements as follows:
1. int *p = new int;
2. float *q = new float;
Assigning a value to the newly created object
Two ways of assigning values to the newly created object:
o We can assign the value to the newly created object by simply using the assignment
operator. In the above case, we have created two pointers 'p' and 'q' of type int and
float, respectively. Now, we assign the values as follows:
1. *p = 45;
2. *q = 9.8;
We assign 45 to the newly created int object and 9.8 to the newly created float object.
o We can also assign the values by using new operator which can be done as follows:
1. pointer_variable = new data-type(value);
Let's look at some examples.
1. int *p = new int(45);
2. float *p = new float(9.8);
How to create a single dimensional array
As we know that new operator is used to create memory space for any data-type or even user-
defined data type such as an array, structures, unions, etc., so the syntax for creating a one-
dimensional array is given below:
1. pointer-variable = new data-type[size];
Examples:
1. int *a1 = new int[8];
In the above statement, we have created an array of type int having a size equal to 8 where
p[0] refers first element, p[1] refers the first element, and so on.
Delete operator
When memory is no longer required, then it needs to be deallocated so that the memory can
be used for another purpose. This can be achieved by using the delete operator, as shown
below:
1. delete pointer_variable;
In the above statement, 'delete' is the operator used to delete the existing object,
and 'pointer_variable' is the name of the pointer variable.
In the previous case, we have created two pointers 'p' and 'q' by using the new operator, and
can be deleted by using the following statements:
1. delete p;
2. delete q;
The dynamically allocated array can also be removed from the memory space by using the
following syntax:
1. delete [size] pointer_variable;

19 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

In the above statement, we need to specify the size that defines the number of elements that
are required to be freed. The drawback of this syntax is that we need to remember the size of
the array. But, in recent versions of C++, we do not need to mention the size as follows:
1. delete [ ] pointer_variable;
Let's understand through a simple example:
1. #include <iostream>
2. using namespace std
3. int main()
4. {
5. int size; // variable declaration
6. int *arr = new int[size]; // creating an array
7. cout<<"Enter the size of the array : ";
8. std::cin >> size; //
9. cout<<"\nEnter the element : ";
10. for(int i=0;i<size;i++) // for loop
11. {
12. cin>>arr[i];
13. }
14. cout<<"\nThe elements that you have entered are :";
15. for(int i=0;i<size;i++) // for loop
16. {
17. cout<<arr[i]<<",";
18. }
19. delete arr; // deleting an existing array.
20. return 0;
21. }

In the above code, we have created an array using the new operator. The above program will
take the user input for the size of an array at the run time. When the program completes all
the operations, then it deletes the object by using the statement delete arr.
Output

Advantages of the new operator

The following are the advantages of the new operator over malloc() function:
20 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

o It does not use the sizeof() operator as it automatically computes the size of the data
object.
o It automatically returns the correct data type pointer, so it does not need to use the
typecasting.
o Like other operators, the new and delete operator can also be overloaded.
o It also allows you to initialize the data object while creating the memory space for the
object.
Differences between the malloc() and new
o The new operator constructs an object, i.e., it calls the constructor to initialize an
object while malloc() function does not call the constructor. The new operator
invokes the constructor, and the delete operator invokes the destructor to destroy the
object. This is the biggest difference between the malloc() and new.
o The new is an operator, while malloc() is a predefined function in the stdlib header
file.
o The operator new can be overloaded while the malloc() function cannot be
overloaded.
o If the sufficient memory is not available in a heap, then the new operator will throw
an exception while the malloc() function returns a NULL pointer.
o In the new operator, we need to specify the number of objects to be allocated while in
malloc() function, we need to specify the number of bytes to be allocated.
o In the case of a new operator, we have to use the delete operator to deallocate the
memory. But in the case of malloc() function, we have to use the free() function to
deallocate the memory.
Differences between delete and free()
The following are the differences between delete and free() in C++ are:
o The delete is an operator that de-allocates the memory dynamically while the free() is
a function that destroys the memory at the runtime.
o The delete operator is used to delete the pointer, which is either allocated using new
operator or a NULL pointer, whereas the free() function is used to delete the pointer
that is either allocated using malloc(), calloc() or realloc() function or NULL pointer.
o When the delete operator destroys the allocated memory, then it calls the destructor of
the class in C++, whereas the free() function does not call the destructor; it only frees
the memory from the heap.
o The delete() operator is faster than the free() function.

Tower of Hanoi Algorithm

Tower of Hanoi is a mathematical puzzle where we have three rods (A, B, and C)
and N disks. Initially, all the disks are stacked in decreasing value of diameter i.e., the
smallest disk is placed on the top and they are on rod A. The objective of the puzzle is to
move the entire stack to another rod (here considered C), obeying the following simple rules:
 Only one disk can be moved at a time.
 Each move consists of taking the upper disk from one of the stacks and placing it on
top of another stack i.e. a disk can only be moved if it is the uppermost disk on a
stack.
 No disk may be placed on top of a smaller disk.

Tower of Hanoi using Recursion

21 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

The idea is to use the helper node to reach the destination using recursion. Below is the
pattern for this problem:
 Shift ‘N-1’ disks from ‘A’ to ‘B’, using C.
 Shift last disk from ‘A’ to ‘C’.
 Shift ‘N-1’ disks from ‘B’ to ‘C’, using A.

Image illustration for 3 disks

Follow the steps below to solve the problem:

 Create a function towerOfHanoi where pass the N (current number of
disk), from_rod, to_rod, aux_rod.
 Make a function call for N – 1 th disk.
 Then print the current the disk along with from_rod and to_rod
 Again make a function call for N – 1 th disk.
// C++ recursive function to
// solve tower of hanoi puzzle
#include <bits/stdc++.h>
using namespace std;

void towerOfHanoi(int n, char from_rod, char to_rod,

char aux_rod)
{
if (n == 0) {
return;
}
towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);
cout << "Move disk " << n << " from rod " << from_rod
<< " to rod " << to_rod << endl;
towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);
}

// Driver code
int main()

22 | P a g e
DATA STRUCTURE USING C++ BCAMJ23402 UNIT II

{
int N = 3;

// A, B and C are names of rods

towerOfHanoi(N, 'A', 'C', 'B');
return 0;
}

Output
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C

Time complexity: O(2N), There are two possibilities for every disk.
Therefore, 2 * 2 * 2 * . . . * 2(N times) is 2N

Sources:
1. Data Structures Tutorial - Tpoint Tech
2. C++ Strings
3. C++ Arrays
4. C Arrays - GeeksforGeeks

23 | P a g e