UNIT - I

INTRODUCTION:
 C++ is a middle level language developed by Bjarne Stroustrup in 1979 at Bell Labs.
 C++ is a middle-level language because it supports both high-level and low-level language features.
 C++ runs on a variety of platforms such as windows, mac OS and various version of UNIX.
 C++ is a statically typed, compiled, general-purpose, case sensitive, free-form programming language.
 C++ supports Procedural, Object-Oriented and generic programming.
 C++ was originally named as C-language with Classes but later in 1983 it was renamed as C++.
 C++ is a superset of C, hence all C-programs are legal C++ programs.
OBJECT-ORIENTED PROGRAMMING DESIGN:
 As the name suggests this design uses objects in programming. Object-oriented programming aims to
implement real-world entities using OOP concepts like inheritance, hiding, polymorphism, etc in
programming.
 The main aim of OOP is to bind the data and the functions (that operate on data together) together.
 The main advantage of binding the data is, no other part of the code can access this data except that
function.
 C++ fully supports Object-oriented programming, including the four pillars of object-oriented
development.

 Class:
o The basic building block of C++ that leads to Object Oriented programming is a Class.
o It is a user defined data type, which holds its own data members and member functions.
o Class can be accessed and used by creating an instance of that class.
o A class is like a blueprint for an object.
o Class in C++ is a blu-print representing a group of objects which shares some common properties
and behaviors.
 Object:
o An Object is an identifiable entity with some characteristics and behavior.
o An Object is an instance of a Class.
o When a class is defined, no memory is allocated but when it is instantiated (i.e. an object is created)
memory is allocated.
o Object take up space in memory and have an associated address like structure or union in C.
o When a program is executed the objects interact by sending messages to one another.
 Encapsulation:
o Encapsulation is defined as wrapping up of data and information under a single unit.
o Encapsulation is a process of combining data members and functions in a single unit. Example:
Class.
o Encapsulation also leads to data abstraction or hiding. As using encapsulation also hides the data.
o This is to prevent the access to the data directly, the access to them is provided through the
functions of the class.
 Data hiding (Abstraction):
o Data abstraction is one of the most essential and important features of object-oriented programming
in C++.
o Data abstraction refers to providing only essential information about the data to the outside world,
hiding the background details or implementation.
o Data hiding is hiding the details of internal data members of an object.
o Data hiding is also known as Information hiding.
o Data hiding hide the details of the class from outside of the class.

 Inheritance
o The reusability mechanism is achieved through inheritance.
o Inheritance in C++ takes place between classes.
o The capability of a class to derive properties and characteristics from another class is called
Inheritance.
o The class being inherited from is called the parent class, base class, or superclass, and the class
doing the inheriting is called the child class, derived class, or subclass.
o A child class inherits both behaviors (member functions) and properties (member variables) from
the parent class.
  Polymorphism
o The word polymorphism means having many forms.
o Polymorphism can be defined as the ability of a message to be displayed in more than one form.
o Example: A person at the same time can have different characteristic. Like a man at the same time
is a father, a husband, an employee. So the same person possess different behavior in different
situations. This is called polymorphism.
o Polymorphism occurs when there is a hierarchy of classes and they are related by inheritance.
o In C++ polymorphism means that a call to a member function will cause a different function to be
executed depending on the type of object that invokes the function.
C++ supports operator overloading and function overloading.
 Operator Overloading: The process of making an operator to exhibit different behaviors in
different instances is known as operator overloading.
 Function Overloading: Function overloading is using a single function name to perform
different types of tasks.

 Dynamic Binding:
o In dynamic binding, the code to be executed in response to function call is decided at runtime.
o C++ has virtual functions to support this.

 Message Passing:
o Objects communicate with one another by sending and receiving information to each other.
o A message for an object is a request for execution of a function in the receiving object that
generates the desired results.
o Message passing involves specifying the name of the object, the name of the function and the
information to be sent.
STANDARD LIBRARIES:
Standard C++ consists of thee important parts –
 The core language gives all the building blocks (also known as programming constructs) like variables,
datatypes and literals, etc.
 The C++ Standard Library gives a rich set of functions, which are helpful in manipulating files, strings, etc.
 The Standard Template Library (STL) gives a rich set of methods helpful in manipulating data structures,
etc.
USE OF C++:
 C++ is used by many programmers in essentially every application domain.
 C++ is widely used in teaching the basics of programming language and in research field.
 The user interfaces of Apple Macintosh and Windows are written in C++.

BASIC SYNTAX:
 A C++ program can be defined as a collection of objects that communicate via invoking each other's
methods.
 A C++ program may consists of a class, object, methods, and instant variables.
o Object - An object is an instance of a class. Objects have states and behaviors.
 Example: A dog has states - color, name, breed as well as behaviors - wagging, barking, and
eating.
o Class - A class can be defined as a template/blueprint that describes the behaviors/states of its type
object support.
o Methods - A method is basically a behavior. A class can contain many methods. It is in methods
where the logics are written, data is manipulated and all the actions are executed.
O Instant Variables - Each object has its unique set of instant variables. An object's state is created
by the values assigned to these instant variables.

C++ PROGRAM STRUCTURE:

 The following simple code will print the words Hello World.
Example:
#include <iostream>
using namespace std;
// main() is where program execution begins.
int main()
{
cout << "Hello World";
return 0;
}
Output:
Hello World

COMMENTS IN C++
 Comments are explanatory statements that can be included in the C++ code.
 These comments help anyone reading the source code. Every programming language allow the use of
comments.
 C++ supports single-line and multi-line comments.
 All characters available inside any comment are ignored by C++ compiler.
o Single-Line Comments: Single line comment starts with //, ends with end of the line.
Example: // this is Hello World program.
o Multi-line comments: To span our comment for multiple lines the start token /* and end with */.
Anything between /* and */ will be ignored by the compiler.
Example: /* this is
Hello world
Program. */
Nesting of Comments:
 Comments can be nested in C++. Doing so does not make any sense, but as part of programming one has to
know what happens if we nest the comments.
 There are four possibilities in which comments can be nested.
1. Nesting Single Line Comments within Single Line Comment: Doing so will not arise any
compile time errors as the nested single line comment token will be ignored by the compiler as it is
a part of outer single line comment.

No compile time errors.

2. Nesting Single Line Comments within Multi Line Comment: Doing so will not arise any
compile time errors, because the nested single line comment token will be ignored by the compiler
as it is a part of the multi-line comment.
Example:

No compile time errors.

3. Nesting Multi Line Comment within Multi Line Comment: Doing so will arise compile time
error, because the end token of nested multi line comment will be considered as the end token of
outer multi line comment. And the start token of nested multi line comment will be ignored as a
part of outer multi line comment. The extra content after the end token of nested multi line
comment will arise compile time errors.

Raises Compile time errors.

4. Nesting Multi Line Comment within Single Line Comment: Doing so will arise compile time
error, because the start token of nested multi line comment will be ignored as a part of outer single
line comment. And end of line will be considered as end of outer single line comment. The extra
content after the end of line comment will arise compile time errors.
BASIC INPUT / OUTPUT IN C++
 C++ comes with libraries which provides ways for performing input and output.
 In C++ input and output is performed in the form of sequence of bytes or more commonly known as
streams.
 Input Stream: If the direction of flow of bytes is from device (for example: Keyboard) to the main
memory then this process is called input. And the flow of data is called as input stream.
 Output Stream: If the direction of flow of bytes is opposite, i.e. from main memory to device (display
screen) then this process is called output. And the flow of data is called as output stream.
Header files available in C++ for Input – Output operation are:
 iostream: iostream stands for standard input output stream. This header file contains definitions to objects
like cin, cout, cerr etc.
 fstream: This header file mainly describes the file stream. This header file is used to handle the data being
read from a file as input or data being written into the file as output.
cin, cout & cerr:
o cout and cin are used for taking inputs and printing outputs.
o These two are the most basic methods of taking input and output in C++.
o For using cin and cout we must include the header file iostream in our program.
o cerr is the standard error stream which is used to output the errors.
o cin, cout & cerr are objects defined in the header file iostream.
Standard output stream (cout):
o The standard output device is the display screen.
o cout is the instance of the ostream class.
o cout is used to produce output on the standard output device display screen.
o The data needed to be displayed on the screen is inserted in the standard output stream (cout) using the
insertion operator (<<).
Example Programs:
#include <iostream>
using namespace std;
int main( ) {
char sample[] = "ISL Engineering College\n";
cout <<sample<<"Compueter Science & Engineering Department" << endl;
cout << "Well come to" << "\n";
cout << "Data Structures Lab";
return 0;
}
 Output:
ISL Engineering College
Compueter Science & Engineering Department
Well come to
Data Structures Lab

Setting field width in output stream Cout using setw() function:

o setw() is library function in C++.
o setw() is declared inside #include<iomanip>
o setw() will set field width.
o setw() sets the number of characters to be used as the field width for the next insertion operation

#include <iostream>
#include <iomanip>
using namespace std;
int main ()
{
cout << setw (10);
cout << “C++" << endl;
return 0;
}
Output:
C++

Standard input stream (cin):

o The standard input device is the keyboard.
o cin is the instance of the class istream and is used to read input from the standard input device keyboard.
o The extraction operator (>>) is used along with the object cin for reading inputs.
o The extraction operator extracts the data from the object cin which is entered using the keyboard.
Example Programs:
#include<iostream>
using namespace std;

int main()
{
int age,a,b;

cout << "Enter your age:";

cin >> age;
cout << "\nYour age is: "<<age;
cout << "\nEnter a,b values:";
cin >> a >> b;
cout <<"Sum=" << a+b;
return 0;
}
Output:
Enter your age: 18
Your age is: 18
Enter a,b values: 3 2
Sum=5
Un-buffered standard error stream (cerr):
o cerr is the standard error stream which is used to output the errors.
o This is also an instance of the ostream class.
o As cerr is un-buffered, it is used to display the error message immediately.
o It does not have any buffer to store the error message and display later.
Example Programs:
#include <iostream>
using namespace std;
int main( )
{
cerr << "An error occured";
return 0;
}
Output:
An error occured

Buffered standard error stream (clog):

o This is also an instance of ostream class and used to display errors.
o Unlike cerr the error is first inserted into a buffer and is stored in the buffer until it is not fully filled.
o The error message will be displayed on the screen too.
Example Programs:
#include <iostream>

using namespace std;

int main( )
{
clog << "An error occured";

return 0;
}
Output:
An error occured
DIFFERENCES BETWEEN C & C++
C Vs C++

S.No. C C++

1) C follows the procedural style C++ is multi-paradigm. It supports

programming. both procedural and object oriented.

2) Data is less secured in C. In C++, you can use modifiers for class
members to make it inaccessible for outside
users.

3) C follows the top-down approach. C++ follows the bottom-up approach.

4) C does not support function overloading. C++ supports function overloading.

5) In C, you can't use functions in structure. In C++, you can use functions in structure.

6) C does not support reference variables. C++ supports reference variables.

7) In C, scanf() and printf() are mainly used C++ mainly uses stream cin and cout to
for input/output. perform input and output operations.

8) Operator overloading is not possible in C. Operator overloading is possible in C++.

9) C programs are divided into procedures C++ programs are divided into functions and
and modules classes.

10) C does not provide the feature of C++ supports the feature of namespace.
namespace.

11) Exception handling is not easy in C. It C++ provides exception handling using Try
has to perform using other functions. and Catch block.
C++ FEATURES:

C++ is object oriented programming language. It provides a lot of features that are given below.

1. Simple
2. Machine Independent or Portable
3. Mid-level programming language
4. Structured programming language
5. Rich Library
6. Memory Management
7. Fast Speed
8. Pointers
9. Recursion
10. Extensible
11. Object Oriented
12. Compiler based
1) Simple
C++ is a simple language in the sense that it provides structured approach (to break the problem into parts),
rich set of library functions, data types etc.
2) Machine Independent or Portable
Unlike assembly language, c programs can be executed in many machines with little bit or no change. But
it is not platform-independent.
3) Mid-level programming language
C++ is also used to do low level programming. It is used to develop system applications such as kernel,
driver etc. It also supports the feature of high level language. That is why it is known as mid-level
language.
4) Structured programming language
C++ is a structured programming language in the sense that we can break the program into parts using
functions. So, it is easy to understand and modify.
5) Rich Library
C++ provides a lot of inbuilt functions that makes the development fast.
6) Memory Management
It supports the feature of dynamic memory allocation. In C++ language, we can free the allocated memory
at any time by calling the free() function.
7) Speed
The compilation and execution time of C++ language is fast.
8) Pointer
C++ provides the feature of pointers. We can directly interact with the memory by using the pointers. We
can use pointers for memory, structures, functions, array etc.
9) Recursion
In C++, we can call the function within the function. It provides code reusability for every function.
10) Extensible
C++ language is extensible because it can easily adopt new features.
11) Object Oriented
C++ is object oriented programming language. OOPs makes development and maintenance easier where as
in Procedure-oriented programming language it is not easy to manage if code grows as project size grows.
12) Compiler based
C++ is a compiler based programming language, it means without compilation no C++ program can be
executed. First we need to compile our program using compiler and then we can execute our program.
C++ FUNCTIONS
 The function in C++ language is also known as procedure or subroutine in other programming languages.
 To perform any task, we can create function. A function can be called many times. It provides modularity
and code reusability.
Advantage of functions in C
There are many advantages of functions.
1) Modularity
Using functions big complex problems are broken into small understandable modules. The complete
problem analysis can be done easily with the help of functions. The concept of breaking the problem into
small understandable units is known as modularity.
2) Code Reusability
By creating functions in C++, you can call it many times. So we don't need to write the same code again
and again. Reusability is a concept with which repetition of code can be avoided.
3) Code optimization
If there is no repetition of code in programming, it automatically makes the code optimized, we don't need
to write much code.

Types of Functions
There are two types of functions in C programming:
1. Library Functions (or) Pre-defined Functions: are the functions which are declared in the C++ header files
such as ceil(x), cos(x), exp(x), etc.
2. User-defined functions: are the functions which are created by the C++ programmer, so that we can use it
many times. It reduces complexity of a big program and optimizes the code.
Like every other object in programming a function should be defined before it can be used. Function definition
should come before it can be used.
Defining functions in C++
The syntax of creating function in C++ language is
return_type function_name(data_type parameter...)
{
//code to be executed
}

C++ Function Example

#include <iostream>
using namespace std;
void func(void) {
static int i=0; //static variable
int j=0; //local variable
i++;
j++;
 cout<<"i=" << i<<" and j=" <<j<<endl;
}
int main(void)
{
func();
func();
func();
}
Output
i= 1 and j= 1
i= 2 and j= 1
i= 3 and j= 1

PARAMETER PASSING TECHNIQUES IN C++

Parameters to the functions can be passed using the following mechanisms:
1. Call-by-Value
2. Call-by-Address (In C language, this mechanism is called call-by-reference)
3. Call-by-Reference (Aliasing)
Call-by-Value:
o In this method of parameter passing the values of the actual parameters in the calling function will be
copied to the corresponding formal parameters of the called function.
o Changes made to values of the formal parameters does not affect the values of actual parameters.
// function definition to swap the values.
void swap(int x, int y) {
int temp;

temp = x;
x = y;
y = temp;
}

#include <iostream>
using namespace std;

// function declaration
void swap(int, int);

int main (void) {

// local variable declaration:
int a = 100;
int b = 200;

cout << "Before swap, value of a :" << a << endl;

cout << "Before swap, value of b :" << b << endl;

// calling a function to swap the values.

swap(a, b);

cout << "After swap, value of a :" << a << endl;

 cout << "After swap, value of b :" << b << endl;

return 0;
}
Output:
Before swap, value of a :100
Before swap, value of b :200
After swap, value of a :100
After swap, value of b :200

Call-by-address:
o In this method the addresses of actual arguments in the calling function are copied into formal arguments
of the called function.
o At called function we provide pointer variable as arguments (formal parameters) to receive the address of
actual parameters.
o Using these addresses we can access actual arguments and hence we can able to manipulate them.
o In this case the changes made to the formal parameters do effect the actual parameters.
#include <iostream>
using namespace std;

// function declaration
void swap(int*, int*);

int main (void) {

// local variable declaration:
int a = 100;
int b = 200;

cout << "Before swap, value of a :" << a << endl;

cout << "Before swap, value of b :" << b << endl;

/* calling a function to swap the values.*/

swap(&a, &b);

cout << "After swap, value of a :" << a << endl;

cout << "After swap, value of b :" << b << endl;

return 0;
}

// function definition to swap the values.

void swap(int *x, int *y) {
int temp;
temp = *x;
*x = *y;
*y = temp;
}
Output:
Before swap, value of a :100
 Before swap, value of b :200
After swap, value of a :200
After swap, value of b :100

Aliasing:
o Aliasing means alternative name for an existing variable name (memory location).
o In C++, aliasing can be done by using ‘&’ operator.
#include<iostream>
using namespace std;
int main(void)
{
int a=100;
int& b=a; // making b as aliasing of a
a=a+100; //now alternative name of a is b
cout<<endl<<”a value is “<<a;
b=b+100;
cout<<endl<<”b value is “<<b;
}
Output:
a value is200
b value is300

o In the above program int &b=a; means, making b as alias of a. Now a and b refers to the same memory
location. So b is alternative name of a (b is also called reference variable).
Call-by-Reference (Aliasing):
 In this method the reference of an argument is copied into the formal parameter.
 Inside the function, the reference is used to access the actual argument used in the call. This means that
changes made to the formal parameter affect the actual argument.
 To pass the value by reference, argument reference is passed to the functions just like any other value. So
accordingly you need to declare the function parameters as reference types as in the following function
swap(), which exchanges the values of the two integer variables pointed to by its arguments.
#include <iostream>
using namespace std;
// function declaration
void swap(int&, int&);
int main (void) {
// local variable declaration:
int a = 100;
int b = 200;
cout << "Before swap, value of a :" << a << endl;
cout << "Before swap, value of b :" << b << endl;
/* calling a function to swap the values using variable reference.*/
swap(a, b);
cout << "After swap, value of a :" << a << endl;
cout << "After swap, value of b :" << b << endl;

return 0;
}
// function definition to swap the values.
void swap(int &x, int &y) {
int temp;
temp = x;
x = y;
y = temp;
}
Output:
Before swap, value of a :100
Before swap, value of b :200
After swap, value of a :200
After swap, value of b :100

C++ RECURSION

 When a function is called within the same function, it is known as recursion in C++.
 The function which calls the same function, is known as recursive function.

Syntax:
recursionfunction(){
recursionfunction(); //calling self-function
}
Example:
#include<iostream>
using namespace std;
int factorial(int);
int main(void)
{
int fact,value;
cout<<"Enter any number: ";
cin>>value;
fact=factorial(value);
cout<<"Factorial of a number is: "<<fact<<endl;
return 0;
}
int factorial(int n)
{
if(n<0)
return(-1); /*Wrong value*/
if(n==0)
return(1); /*Terminating condition*/
else
{
return(n*factorial(n-1));
}
}
Output:
Enter any number: 5
Factorial of a number is: 120
CLASSES AND OBJECTS:

 The main purpose of C++ programming is to add object orientation to the C programming language and
classes are the central feature of C++ that supports object-oriented programming.
 A class is a user defined type used to specify the form of an object.
 It combines data representation and methods for manipulating that data into one single unit.
 A class is a blueprint for an object. This doesn't actually define any data but it describes what an object
of the class will consist of and what operations can be performed on such an object.
 A class definition starts with the keyword class followed by the class name; and the class body,
enclosed by a pair of curly braces. A class definition must be followed either by a semicolon or a list of
declarations.

Example:
class Box {
public:
double length; // Length of a box
double breadth; // Breadth of a box
double height; // Height of a box
double getVolume(void); // Returns box volume
};

 Member functions can be defined within the class definition or separately using scope resolution
operator (::).
 The keyword public determines the access attributes of the members of the class that follows it. A
public member can be accessed from outside the class anywhere within the scope of the class object.

Example: Defining Member Function Inside the Class Definition

class Box {
public:
double length; // Length of a box
double breadth; // Breadth of a box
double height; // Height of a box

double getVolume(void) {
return length * breadth * height;
}
};
Example: Defining Member Function Outside the Class Definition Using Scope Resolution
Operator (::).
double Box::getVolume(void) {
return length * breadth * height;
}

Define C++ Objects

 A class provides the blueprints for objects, so basically an object is created from a class.

Syntax:
Box b1; // Declare Box1 of type Box
Box b2; // Declare Box2 of type Box
Accessing the Data Members & Member Functions

 The public data members of objects of a class can be accessed using the direct member access operator
(.).

Example: Demonstrate Class & Object

#include <iostream>

using namespace std;

class Box {
public:
double length; // Length of a box
double breadth; // Breadth of a box
double height; // Height of a box

// Member functions declaration

double getVolume(void);
void setLength( double);
void setBreadth( double);
void setHeight( double);
};

// Member functions definitions

double Box::getVolume(void) {
return length * breadth * height;
}

void Box::setLength( double len ) {

length = len;
}
void Box::setBreadth( double bre ) {
breadth = bre;
}
void Box::setHeight( double hei ) {
height = hei;
}

// Main function for the program

int main(void) {
Box b1; // Declare Box1 of type Box
Box b2; // Declare Box2 of type Box
double volume = 0.0; // Store the volume of a box here

// box 1 specification
b1.setLength(6.0);
b1.setBreadth(7.0);
b1.setHeight(5.0);

// box 2 specification
b2.setLength(12.0);
b2.setBreadth(13.0);
b2.setHeight(10.0);
 // volume of box 1
volume = b1.getVolume();
cout << "Volume of Box1 : " << volume <<endl;

// volume of box 2
volume = b2.getVolume();
cout << "Volume of Box2 : " << volume <<endl;
return 0;
}
Output:
Volume of Box1 : 210
Volume of Box2 : 1560

C++ Class Access Modifiers:

 Data hiding is one of the important features of Object Oriented Programming which allows preventing
the functions of a program to access directly the internal representation of a class type.
 The access restriction to the class members is specified by the keywords public, private, and protected
within the class body. The keywords public, private, and protected are called as access specifiers or
access modifiers.
 A class can have multiple public, protected, or private labeled sections. Each section remains in effect
until either another section label or the closing right brace of the class body is seen.
 The default access for members and classes is private.

Syntax:
class Base {
public:
// public members go here
protected:

// protected members go here

private:
// private members go here

};

The public Members

 A public member is accessible from anywhere outside the class but within a program.
 They can be accessed without any member function as shown in the following example.

#include <iostream>

using namespace std;

class Line {
public:
double length;
void setLength( double );
double getLength( void );
};
// Member functions definitions
double Line::getLength(void) {
return length ;
}

void Line::setLength( double len) {

length = len;
}

// Main function for the program

int main(void) {
Line line;

// set line length

line.setLength(6.0);
cout << "Length of line : " << line.getLength() <<endl;

// set line length without member function

line.length = 10.0; // OK: because length is public
cout << "Length of line : " << line.length <<endl; // OK: because length is public

return 0;
}
Output:
Length of line : 6
Length of line : 10

The private Members

 A private member variable or function cannot be accessed, or even viewed from outside the class.
 Only the class and friend functions can access private members.
 By default all the members of a class would be private.

Example:
#include <iostream>

using namespace std;

class Box {
private:
double width;

public:
double length;
void setWidth( double );
double getWidth( void );
};

// Member functions definitions

double Box::getWidth(void) {
return width ;
}
 void Box::setWidth( double wid ) {
width = wid;
}

// Main function for the program

int main(void) {
Box b1;

// set box length without member function

b1.length = 10.0; // OK: because length is public
cout << "Length of box : " << b1.length <<endl;

// set box width without member function

// b1.width = 10.0; // Error: because width is private
b1.setWidth(10.0); // Use public member function to set private data member.
cout << "Width of box : " << b1.getWidth() <<endl; // Use public member function to get private data member.

return 0;
}
Output:
Length of box : 10
Width of box : 10

The protected Members

 A protected member variable or function is very similar to a private member but it provided one additional
benefit that they can be accessed in child classes which are called derived classes.

Example:
#include <iostream>
using namespace std;

class Box {
protected:
double width;
};

class SmallBox:Box { // SmallBox is the derived class.

public:
void setSmallWidth( double );
double getSmallWidth( void );
};

// Member functions of child class

double SmallBox::getSmallWidth(void) {
return width ;
}

void SmallBox::setSmallWidth( double wid ) {

width = wid;
}

// Main function for the program

 int main(void) {
SmallBox sb;

// set box width using member function

sb.setSmallWidth(5.0);
cout << "Width of box : "<< sb.getSmallWidth() << endl;

return 0;
}
Output:
Width of box : 5

The Class Constructor

 A class constructor is a special member function of a class that is executed whenever a new objects of that
class is created.
 A constructor will have exact same name as the class and it does not have any return type at all, not even
void. A default constructor does not have any parameter, but a parameterized constructor can have
parameters.
 Constructors can be very useful for setting initial values for data members.

#include <iostream>

using namespace std;

class Line {
private:
double length;
public:
void setLength( double );
double getLength( void );
Line(); // This is the constructor
};

// Member functions definitions including constructor

Line::Line(void) {
cout << "Object is being created" << endl;
}

void Line::setLength( double len ) {

length = len;
}

double Line::getLength( void ) {

return length;
}

// Main function for the program

int main(void) {
Line line;

// set line length

line.setLength(6.0);
 cout << "Length of line : " << line.getLength() <<endl;

return 0;
}
Output:
Object is being created
Length of line : 6

Parameterized Constructor
 A constructor can have parameters, such constructor will be called as parameterized constructor.
 This helps to assign initial value to an object at the time of its creation as shown in the following
example.
Example:
#include <iostream>
using namespace std;
class Line {
private:
double length;
public:
void setLength( double );
double getLength( void );
Line(double); // This is the constructor
};
// Member functions definitions including constructor
Line::Line( double len) {
cout << "Object is being created, length = " << len << endl;
length = len;
}
void Line::setLength( double len ) {
length = len;
}
double Line::getLength( void ) {
return length;
}
// Main function for the program
int main(void) {
Line line(10.0);
// get initially set length.
cout << "Length of line : " << line.getLength() <<endl;
// set line length again
line.setLength(6.0);
cout << "Length of line : " << line.getLength() <<endl;
return 0;
}
Output:
Object is being created, length = 10
Length of line : 10
Length of line : 6
Using Initialization Lists to Initialize Fields

 In case of parameterized constructor, the following syntax can be used to initialize the fields of class.

Syntax:
C::C( double a, double b, double c): X(a), Y(b), Z(c) {
....
}
Example:
Line::Line( double len): length(len) {
cout << "Object is being created, length = " << len << endl;
}
The above example is same as:
Line::Line( double len) {
cout << "Object is being created, length = " << len << endl;
length = len;
}

The Class Destructor

 A destructor is a special member function of a class that is executed whenever an object of it's class
goes out of scope or whenever the delete expression is applied to a pointer to the object of that class.
 A destructor will have exact same name as the class prefixed with a tilde (~) and it can neither return a
value nor can it take any parameters.
 Destructor can be very useful for releasing resources before coming out of the program like closing
files, releasing memories etc.

#include <iostream>

using namespace std;

class Line {
private:
double length;

public:
void setLength( double );
double getLength( void );
Line(); // This is the constructor declaration
~Line(); // This is the destructor: declaration
};

// Member functions definitions including constructor

Line::Line(void) {
cout << "Object is being created" << endl;
}
Line::~Line(void) {
cout << "Object is being deleted" << endl;
}
void Line::setLength( double len ) {
length = len;
}
double Line::getLength( void ) {
return length;
 }

// Main function for the program

int main(void) {
Line line;

// set line length

line.setLength(6.0);
cout << "Length of line : " << line.getLength() <<endl;

return 0;
}
Output:
Object is being created
Length of line : 6
Object is being deleted

Copy Constructor

 The copy constructor is a special constructor which creates an object by initializing it with an object of the
same class, which has been created previously.
 The copy constructor is used to:
o Initialize one object from another of the same type.
o Copy an object to pass it as an argument to a function.
o Copy an object to return it from a function.
 The most common form of copy constructor is shown here –

classname (const class_name& object_name) {

// body of constructor
}

Example:
#include <iostream>
using namespace std;
class Line {
private:
int *ptr;

public:
int getLength( void );
Line( int ); // simple constructor
Line( const Line&); // copy constructor
~Line(); // destructor
};

// Member functions definitions including constructor

Line::Line(int len) {
cout << "Normal constructor allocating ptr" << endl;
// allocate memory for the pointer;
ptr = new int;
 *ptr = len;
}

Line::Line(const Line& obj) {

cout << "Copy constructor allocating ptr." << endl;
ptr = new int;
*ptr = *obj.ptr; // copy the value
}

Line::~Line(void) {
cout << "Freeing memory!" << endl;
delete ptr;
}

int Line::getLength( void ) {

return *ptr;
}

void display(Line obj) {

cout << "Length of line : " << obj.getLength() <<endl;
}

// Main function for the program

int main(void) {
Line line(10);

display(line);

return 0;
}
Output:
Object is being created
Length of line : 6
Object is being deleted

FRIEND FUNCTIONS:

 A friend function of a class is defined outside that class' scope but it has the right to access all private and
protected members of the class.
 The declaration of a friend functions appear in the class definition, but friend functions are not member
functions.
 Generally to access data members of multiple classes friend functions are helpful.
 While defining a friend function it does not require a class name, as the scope is not limited to any class. It
can be defined like a regular function but not like a member function of a class.
 While invoking the friend function it does not require any caller object, as the scope is not limited to any
class.
 To declare a function as a friend of a class, precede the function declaration in the class definition with
keyword friend as follows:
Example1: Friend Function
#include<iostream>
#include<conio.h>
using namespace std;
class Box2;
class Box1 {
double width;

public:
friend double addWidLen( Box1,Box2 );
void setWidth( double );
};

void Box1::setWidth(double wid)

{
width = wid;
}

class Box2 {
double length;

public:
friend double addWidLen( Box1, Box2 );
void setLength( double );
};

void Box2::setLength(double len)

{
length = len;
}

double addWidLen(Box1 b1,Box2 b2)

{
return b1.width + b2.length;
}

int main(void)
{
Box1 b1;
Box2 b2;
b1.setWidth(10);
b2.setLength(20);
cout << "Sum of Width+Length=" << addWidLen(b1,b2);
return 0;
}
Output:
Sum of Width+Length=30
Example2:
#include<iostream>
using namespace std;
class B;
class A
{
 private:
int a;
public:
int b;
A(int,int);
~A();
friend void display(A,B);
};

class B
{
private:
int x;
public:
int y;
B(int,int);
~B();
friend void display(A,B);
};

A::A(int t1, int t2):a(t1),b(t2)

{
cout << "Initializing A's Object..." << endl;
}

B::B(int t1, int t2):x(t1),y(t2)

{
cout << "Initializing B's Object..." << endl;
}

A::~A()
{
cout << "A's Object is being destroyed..." << endl;
}

B::~B()
{
cout << "B's Object is being destroyed..." << endl;
}

void display(A tobj1,B tobj2)

{
cout << "Data Members of A:" << tobj1.a <<" "<< tobj1.b <<endl;
cout << "Data Members of B:" << tobj2.x <<" "<< tobj2.y <<endl;
}

int main(void)
{
A obj1(10,20);
B obj2(40,50);
display(obj1,obj2);
}
Output:
Initializing A's Object...
Initializing B's Object...
Data Members of A:10 20
Data Members of B:40 50
A's Object is being destroyed...
B's Object is being destroyed...
B's Object is being destroyed...
A's Object is being destroyed...

C++ INHERITANCE:

 Inheritance allows us to define a class in terms of another class, which makes it easier to create and
maintain an application.
 Inheritance provides an opportunity to reuse the code functionality and fast implementation time.
 When creating a class, instead of writing completely new data members and member functions, the
programmer can designate that the new class should inherit the members of an existing class. This existing
class is called the base class, and the new class is referred to as the derived class.
 A class can be derived from more than one classes, which means it can inherit data and functions from
multiple base classes.
 To define a derived class, we use a class derivation list to specify the base class(es). A class derivation list
names one or more base classes and has the following form:

class derived-class: access-specifier base-class

Example: Consider a base class Shape and its derived class Rectangle as follows
#include <iostream>
using namespace std;
// Base class
class Shape {
protected:
int width;
int height;

public:
void setWidth(int w) {
width = w;
}
void setHeight(int h) {
height = h;
}
};

// Derived class
class Rectangle: public Shape {
public:
int getArea() {
return (width * height);
}
};
 int main(void) {
Rectangle Rect;

Rect.setWidth(5);
Rect.setHeight(7);

// Print the area of the object.

cout << "Total area: " << Rect.getArea() << endl;

return 0;
}
Output:
Total area: 35

Access Control and Inheritance:

 A derived class can access all the non-private members of its base class.
 Thus base-class members that should not be accessible to the member functions of derived classes
should be declared private in the base class.

Access public protected private

Same class yes yes yes

Derived classes yes yes no

Outside classes yes no no

 A derived class inherits all base class functions except −

o Constructors, destructors and copy constructors of the base class.
o Overloaded operators of the base class.
o The friend functions of the base class.

Modes of Inheritance:

When deriving a class from a base class, the base class may be inherited through public, protected or private
inheritance. While using different type of access specifiers in deriving the derived class from base class, following
rules are applied –

o Public Mode: When deriving a class from a public base class, public members of the base class
become public members of the derived class and protected members of the base class become
protected members of the derived class. A base class's private members are never accessible directly
from a derived class, but can be accessed through calls to the public and protected member functions
of the base class.
 o Protected Mode: When deriving from a protected base class, public and protected members of the
base class become protected members of the derived class.
o Private Mode: When deriving from a private base class, public and protected members of the base
class become private members of the derived class.

C++ Inheritance Types: C++ supports five types of inheritance as follows:

1. Single Inheritance
2. Multilevel Inheritance
3. Multiple Inheritance
4. Hierarchical Inheritance
5. Hybrid Inheritance

1) Single Inheritance: A derived class with only one base class is called single inheritance.

Example: Single Inheritance

#include<iostream>
using namespace std;
class A
{
public:
int a;
protected:
int b;
};

class B:public A
{
public:
int x;
void setBValue(int);
void display(void);
};

void B::setBValue(int temp)

{
b=temp;
}

void B::display(void)
{
cout <<"a,b and x values:"<< a <<" "<< b <<" "<< x;
}

int main(void)
{
B objB;
objB.a=10;
//objB.b=20; /*Protected variable out of scope*/
objB.setBValue(20);
objB.x=30;
objB.display();
return 0;
}
Output:
a,b and x values: 10 20 30

2) Multilevel Inheritance: A derived class with one base class which is in-turn a derived class of
another base class, such scenario is called multilevel inheritance.

Example:
#include<iostream>
using namespace std;
class A
{
public:
int a;
protected:
int b;
};

class B:public A
{
public:
int x;
protected:
int y;
};

class C:public B
{
public:
int p;
void setBYValues(int,int);
void display(void);
};
void C::setBYValues(int temp1,int temp2)
{
b=temp1;
y=temp2;
}

void C::display(void)
{
cout <<"a,b,x,y and p values:"<< a <<" "<< b <<" "<< x <<" "<< y <<" "<< p;
}

int main(void)
{
C objC;
objC.a=10;
//objC.b=20; /*Protected variable out of scope*/
objC.setBYValues(20,40);
objC.x=30;
objC.p=50;
objC.display();
return 0;
}
Output:
a,b,x,y and p values: 10 20 30 40 50

3) Multiple Inheritance: A derived class with multiple base class is called multiple inheritance.

4) Hierarchical Inheritance: Multiple derived classes with same base class is called hierarchical
inheritance.

5) Hybrid Inheritance: Hybrid Inheritance is implemented by combining more than one type of
inheritance. For example: Combining Hierarchical inheritance and Multiple Inheritance.
POINTERS TO OBJECTS:

 In C++ it is possible to create pointers of class type.

 A class type pointer can point the address of an object. It is called pointer to object.

Syntax:
class_name* optr;
class_name obj;
optr = &obj;

To access the data members or member functions of a class using pointer to object, the indirect access
operator (->) is used.
Example:
#include <iostream>
using namespace std;

class A {
public:
int p;

void display(void)
{
cout<<"Data Member:" << p <<endl;
}
};

int main(void) {
A* ptra;
A obja;
ptra = &obja;
cout << "Accessing class members using Object:" << endl;
obja.p = 20;
obja.display();
cout << "Accessing class members using Pointer to Object:" << endl;
ptra->p = 30;
ptra->display();
}
 Output:
Accessing class members using Object:
Data Member:20
Accessing class members using Pointer to Object:
Data Member:30

Pointers to Objects in Inheritance:

 A pointer of type base class is capable of pointing not only base class object, but also the derived class
object.
 When it is pointing to the base class object, it can access all public members of base class using indirect
selection operator (->).
 Even when it is pointing to the derived class object, in that case also it can access only the inherited
members (of base class) from derived class using indirect selection operator (->). It does not have any
access to the derived class members directly.
Example:
#include<iostream>
using namespace std;
class A
{
public:
int p;
void display(void);
};

void A::display(void)
{
cout<<"Base class Data member p:"<<p<<endl;
}

class B:public A
{
public:
int q;
void print(void);
};

void B::print(void)
{
cout<<"Derivedd class Data members p,q:"<<p<<","<<q<<endl;
}

int main(void)
{
A aobj;
A* ptraobj;
B bobj;
aobj.p=20;
aobj.display();
ptraobj = &aobj;
ptraobj->p=40;
ptraobj->display();
bobj.p=60;
bobj.q=80;
 bobj.print();
ptraobj = &bobj;
ptraobj->p = 90;
ptraobj->display();
// ptraobj->q = 100; //Error compiletime No access to derived class members
// ptraobj->print(); //Error compiletime No access to derived class members
}
Output:
Base class Data member p:20
Base class Data member p:40
Derivedd class Data members p,q:60,80
Base class Data member p:60

Constructor call in Inheritance:

 Base class constructors are always called in the derived class constructors.
 Whenever a derived class object is created, first the base class default constructor is executed and then the
derived class's constructor finishes execution.
 Whether derived class's default or parameterized constructor is called, base class's default constructor is
always called inside them.
 To call base class's parameterized constructor inside derived class's parameterized constructor, must
mention it explicitly while declaring derived class's parameterized constructor.

Example:
#include<iostream>
using namespace std;
class Base
{
int x;
public:
// parameterized constructor
Base(int i)
{
x = i;
cout << "Base Parameterized Constructor:"<<x<<endl;
}
};

class Derived : public Base

{
int y;
public:
// parameterized constructor
Derived(int j, int k):Base(k)
{
y = j;
cout << "Derived Parameterized Constructor:"<<y;
}
};

int main()
{
Derived d(10,20) ;
 }
Output:
Base Parameterized Constructor:20
Derived Parameterized Constructor:10

POLYMORPHISM IN C++:
 The word polymorphism means having many forms.
 Polymorphism occurs when there is a hierarchy of classes and they are related by inheritance.
 C++ polymorphism means that a call to a member function will cause a different function to be executed
depending on the type of object that invokes the function.
 Consider the following example where a base class has been derived by other two classes:
Example:
#include <iostream>
using namespace std;

class Shape {
protected:
int width, height;

public:
Shape( int a, int b){
width = a;
height = b;
}
int area() {
cout << "Parent class area :" <<endl;
return 0;
}
};
class Rectangle: public Shape {
public:
Rectangle( int a, int b):Shape(a, b) { }

int area () {
cout << "Rectangle class area :";
return (width * height);
}
};

class Triangle: public Shape {

public:
Triangle( int a, int b):Shape(a, b) { }

int area () {
cout << "Triangle class area :";
return (width * height / 2);
}
};

// Main function for the program

int main() {
Shape *shape;
 Rectangle rec(10,7);
Triangle tri(10,5);
int res;

// store the address of Rectangle

shape = &rec;

// call rectangle area.

res=shape->area();
cout << res << endl;
// store the address of Triangle
shape = &tri;

// call triangle area.

res=shape->area();
cout << res << endl;
return 0;
}
Output:
Parent class area :
0
Parent class area :
0
Example2:
#include<iostream>
using namespace std;
class A
{
public:
int p;
void display(void);
};

void A::display(void)
{
cout<<"Class A Data member p:"<<p<<endl;
}

class B:public A
{
public:
int q;
void display(void);
};

void B::display(void)
{
cout<<"Class B Data members p,q:"<<p<<","<<q<<endl;
}

int main(void)
{
A* ptraobj;
 B bobj;
bobj.p = 20;
bobj.q = 30;
ptraobj = &bobj;
ptraobj->display();
}
Output:
Class A Data member p:20

 The reason for the incorrect output is that the call of the function area() is being set by the compiler at
compile time, that is before the program is executed . This is called static resolution of the function call, or
static linkage.
 This is also sometimes called early binding because the area() function is set during the compilation of the
program.
 This above problem can be resolved by using the concept known as dynamic binding or runtime
polymorphism.

Virtual function:

 A virtual function is a function in a base class that is declared using the keyword virtual.
 Defining a virtual function in base class, with another version in a derived class, signals the compiler that,
static linkage of the same is not to be done.
 The selection of the function to be called at any given point in the program need to be done at runtime base
on the object reference. This is referred to as dynamic linkage, or late binding.

Example:
#include <iostream>
using namespace std;

class Shape {
protected:
int width, height;

public:
Shape( int a, int b){
width = a;
height = b;
}
virtual int area() {
cout << "Parent class area :" <<endl;
return 0;
}
};
class Rectangle: public Shape {
public:
Rectangle( int a, int b):Shape(a, b) { }

int area () {
cout << "Rectangle class area :";
return (width * height);
}
};
class Triangle: public Shape {
public:
Triangle( int a, int b):Shape(a, b) { }

int area () {
cout << "Triangle class area :";
return (width * height / 2);
}
};

// Main function for the program

int main() {
Shape *shape;
Rectangle rec(10,7);
Triangle tri(10,5);
int res;

// store the address of Rectangle

shape = &rec;

// call rectangle area.

res=shape->area();
cout << res << endl;
// store the address of Triangle
shape = &tri;

// call triangle area.

res=shape->area();
cout << res << endl;
return 0;
}
Output:
Rectangle class area :70
Triangle class area :25
Example2:
#include<iostream>
using namespace std;
class A
{
public:
int p;
virtual void display(void);
};

void A::display(void)
{
cout<<"Class A Data member p:"<<p<<endl;
}

class B:public A
{
public:
 int q;
void display(void);
};

void B::display(void)
{
cout<<"Class B Data members p,q:"<<p<<","<<q<<endl;
}

int main(void)
{
A* ptraobj;
A aobj;
aobj.p = 10;
ptraobj = &aobj;
ptraobj->display();
B bobj;
bobj.p = 20;
bobj.q = 30;
ptraobj = &bobj;
ptraobj->display();
}
Output:
Class A Data member p:10
Class B Data members p,q:20,30

Pure Virtual function:

 If there is no meaningful definition we have to include in the base class. Simply initialize the function
signature with zero (=0).
 The = 0 tells the compiler that the function has no body and such virtual function will be called as pure
virtual function.

Example:
#include <iostream>
using namespace std;

class Shape {
protected:
int width, height;

public:
Shape( int a, int b){
width = a;
height = b;
}
virtual int area() = 0;
};
class Rectangle: public Shape {
public:
Rectangle( int a, int b):Shape(a, b) { }

virtual int area () {

 cout << "Rectangle class area :";
return (width * height);
}
};

class Triangle: public Shape {

public:
Triangle( int a, int b):Shape(a, b) { }

int area () {
cout << "Triangle class area :";
return (width * height / 2);
}
};

// Main function for the program

int main() {
Shape *shape;
Rectangle rec(10,7);
Triangle tri(10,5);
int res;

// store the address of Rectangle

shape = &rec;

// call rectangle area.

res=shape->area();
cout << res << endl;
// store the address of Triangle
shape = &tri;

// call triangle area.

res=shape->area();
cout << res << endl;
return 0;
}
Output:
Rectangle class area :70
Triangle class area :25

C++ OVERLOADING (OPERATOR AND FUNCTION)

 C++ allows to specify more than one definition for a function name or an operator in the same scope,
which is called function overloading and operator overloading respectively.
 An overloaded declaration is that which is declared with the same name as a previously declared
declaration in the same scope, except that both declarations have different arguments and obviously
different definition (implementation).
 When an overloaded function or operator called, the compiler determines the most appropriate
definition to use, by comparing the argument types in the function call or operator with the parameter
types specified in the definitions. The process of selecting the most appropriate overloaded function or
operator is called overload resolution.
Function Overloading in C++

 In function overloading multiple definitions for the same function name can be used in the same scope.
 The definitions of the function must differ from each other by the types and/or the number of arguments in
the argument list.
 Function declarations that differ only by return type cannot be overloaded.
Example:
#include <iostream>
using namespace std;

class printData {
public:
void print(int i) {
cout << "Printing int: " << i << endl;
}
void print(double d) {
cout << "Printing double: " << d << endl;
}
void print(char* c) {
cout << "Printing string: " << c << endl;
}
};

int main(void) {
printData pd;

// Call print to print integer

pd.print(5);

// Call print to print float

pd.print(500.263);

// Call print to print character

pd.print("Hello C++");

return 0;
}
Output:
Printing int: 5
Printing float: 500.263
Printing character: Hello C++

Operator Overloading in C++:

 An operator is a symbol that tells the compiler to perform specific task.
 Every operator have their own functionality to work with built-in data types.
 Class is user-defined data type and compiler doesn't understand, how to use operators with user-defined
data types. To use operators with user-defined data types, they need to be overload according to a
programmer's requirement.
 Operator overloading is a way of providing new implementation of existing operators to work with user-
defined data types.
 An operator can be overloaded by defining a function to it. The function for operator is declared by using
the operator keyword followed by the operator.
Example: Binary Operator + Overloading
#include<iostream>
#include<conio.h>
using namespace std;
class Rectangle
{
int len,bre;

public:
Rectangle() //Default Constructor
{
len = 0;
bre = 0;
}

Rectangle(int x,int y) //Parameterize Constructor

{
len = x;
bre = y;
}

Rectangle operator+(Rectangle Rec) //Binary operator overloading func.

{
Rectangle R;
R.len = len + Rec.len;
R.bre = bre + Rec.bre;
return R;
}

void Display()
{
cout<<"\n\tLength : "<<len;
cout<<"\n\tBreadth : "<<bre;
}

};

int main()
{
Rectangle R1(2,5),R2(3,4),R3; //Creating Objects

cout<<"\n\tRectangle 1 : ";
R1.Display();

cout<<"\n\n\tRectangle 2 : ";
R2.Display();

R3 = R1 + R2; // R1.+(R2);
cout<<"\n\n\tRectangle 3 : ";
R3.Display();
return 0;
}
Output:
Rectangle 1 :
Length : 2
Breadth : 5

Rectangle 2 :
Length : 3
Breadth : 4

Rectangle 3 :
Length : 5
Breadth : 9
DYNAMIC MEMORY ALLOCATION:

 Understanding of how dynamic memory really works in C++ is essential to becoming a good C++
programmer. Memory in your C++ program is divided into two parts −

 The stack − All variables declared inside the function will take up memory from the stack.

 The heap − This is unused memory of the program and can be used to allocate the memory
dynamically when program runs.

 Sometimes, it is not known in advance that how much memory it will be need to store particular
information in a defined variable and it can be determined at run time.
 In C++ Memory allocation at run time can be done using a special operator new.
 new operator allocates the memory from heap, for the variable of a given type, and returns the address of
the space allocated.
 If the dynamically allocated memory does not required anymore, it can be deleted using delete operator,
which de-allocates memory that was previously allocated by new operator.

new and delete Operators

 The following generic syntax is used for new operator to allocate memory dynamically for any data-type.

Syntax:
Pointer_variable = new data_type;

 Here, data-type could be any built-in data type including an array or any user defined data types include
class or structure.
 For example to allocate memory of type double dynamically at runtime, a pointer to type double can be
used with new operator and then request that the memory be allocated at execution time.

double* pvalue = NULL; // Pointer initialized with null

pvalue = new double; // Request memory for the variable

 Sometimes the memory may not be allocated successfully, if the free store had been used up. So it is a
good practice to check if new operator is returning NULL pointer and take appropriate action as below –

double* pvalue = NULL;

if( !(pvalue = new double )) {
cout << "Error: out of memory." <<endl;
exit(1);
}

 At any point, when a variable that has been dynamically allocated is not anymore required, it can be freed
up with the ‘delete’ operator as follows –

delete pvalue; // Release memory pointed to by pvalue

 Example:
#include <iostream>
using namespace std;

int main () {
double* pvalue = NULL; // Pointer initialized with null
pvalue = new double; // Request memory for the variable

*pvalue = 29494.99; // Store value at allocated address

cout << "Value of pvalue : " << *pvalue << endl;

delete pvalue; // free up the memory.

return 0;
}
Output:
Value of pvalue : 29494.99

Dynamic Memory Allocation for Objects

 new operator can be used to allocate memory for array of objects.
Example:
#include <iostream>
using namespace std;

class Box {
public:
Box() {
cout << "Constructor called!" <<endl;
}
~Box() {
cout << "Destructor called!" <<endl;
}
};
int main() {
Box* myBoxArray = new Box[4];
delete [] myBoxArray; // Delete array

return 0;
}
Output:
Constructor called!
Constructor called!
Constructor called!
Constructor called!
Destructor called!
Destructor called!
Destructor called!
Destructor called!
NAMESPACES:
 Consider a situation, if there are two persons with the same name, in the same class. To differentiate them
definitely, we need some additional information along with their name, like either the area where they live,
mother’s or father’s name, etc.
 Same situation can arise in your C++ applications. For example, the code that has a function called xyz()
and there is another library available which is also having same function xyz(). Now the compiler has no
way of knowing which version of xyz() function to refer within the code.
 A namespace is designed to overcome this difficulty and is used as additional information to differentiate
similar functions, classes, variables etc. with the same name in different libraries.
 Using namespace, the context can be defined, in which names are defined. In simple terms, a namespace
defines a scope.

Defining Namespaces:
 A namespace definition begins with the keyword namespace followed by the namespace name as follows –

namespace namespace_name {
// code declarations
}

 To call the namespace-enabled version of either function or variable, prepend scope resolution (::) with the
namespace name as follows –
name::code; // code could be variable or function.
 The following example demonstrates, how namespace scope the entities including variable and functions –
Example:
#include <iostream>
using namespace std;

// first name space

namespace first_space {
void func() {
cout << "Inside first_space" << endl;
}
}

// second name space

namespace second_space {
void func() {
cout << "Inside second_space" << endl;
}
}

int main () {
// Calls function from first name space.
first_space::func();

// Calls function from second name space.

second_space::func();

return 0;
}
Output:
Inside first_space
Inside second_space
The using directive:
 To avoid prepending of namespaces, the using namespace directive can be used.
 This directive tells the compiler that the subsequent code is making use of names in the specified
namespace.
Example:
#include <iostream>
using namespace std;

// first name space

namespace first_space {
void func() {
cout << "Inside first_space" << endl;
}
}

// second name space

namespace second_space {
void func() {
cout << "Inside second_space" << endl;
}
}

using namespace first_space;

int main () {
// This calls function from first name space.
func();

return 0;
}
Output:
Inside first_space

 The ‘using’ directive can also be used to refer a particular item within a namespace. For example, to use
only cout from name space std, the following sample can be used.

Example:
#include <iostream>
using std::cout;

int main () {
cout << "std::endl is used with std!" << std::endl;

return 0;
}
Output:
std::endl is used with std!
C++ TEMPLATES
 Templates are the foundation of generic programming.
 Templates involves writing code in a way that is independent of any particular type.
 A template is a blueprint or formula for creating a generic class or a function.
 There is a single definition of each container, Example vector, and it can be used to define many different
kinds of vectors for example, vector <int> or vector <string>.
 Template is simple and yet very powerful tool in C++. The simple idea is to pass data type as a parameter
so that we don’t need to write same code for different data types.
 For example a software company may need add() for different data types. Rather than writing and
maintaining the multiple codes, we can write one generic add() and pass data type as a parameter.
 C++ uses two new keywords to support templates: ‘template’ and ‘typename’.
 Templates can be used to define functions as well as classes.

Function Template
 The general form of a template function definition is shown here –
Syntax:
template <typename type> ret-type func-name(parameter list) {
// body of function
}

 Here, type is a type name for a data type used by the function. This name can be used within the function
definition.
 The following is the example of a function template that returns the maximum of two values –
Example:
#include <iostream>
#include <string>
using namespace std;
template <typename T>
T myMax (T a, T b) {
return a < b ? b:a;
}
int main () {
int i = 39;
int j = 20;
cout << "Max(i, j): " << myMax<int>(i, j) << endl;
double f1 = 13.5;
double f2 = 20.7;
cout << "Max(f1, f2): " << myMax<double>(f1, f2) << endl;
string s1 = "Hello";
string s2 = "World";
cout << "Max(s1, s2): " << myMax<string>(s1, s2) << endl;
return 0;
}
Output:
Max(i, j): 39
Max(f1, f2): 20.7
Max(s1, s2): World
Class Template:
 Just as we can define function templates, we can also define class templates.
 The general form of a generic class declaration is shown here –
Syntax:
template <class type> class class-name {
.
.
.
}
template <class T>
class MyTemplate {
T element;
public:
MyTemplate (T arg) {element=arg;}
T divideBy2 () {return element/2;}
};

Example:
#include<iostream>
using namespace std;
template<class T, class U>
class A {
T x;
U y;
public:
A(T,U);
void show(void);
};
template<class T, class U>
A<T,U>::A(T t1,U t2)
{
cout<<"Constructor Called"<<endl;
x=t1;
y=t2;
}
template<class T, class U>
void A<T,U>::show(void)
{
cout <<"Data members of A:"<<x<<" "<<y<<endl;
}
int main() {
A<char, char> a('c','d');
A<int, double> b(24,3.786);
a.show();
b.show();
return 0;
}
Output:
Constructor Called
Constructor Called
Data members of A:c d
Data members of A:24 3.786
C++ EXCEPTION HANDLING

 An exception is a problem that arises during the execution of a program.

 A C++ exception is a response to an exceptional circumstance that arises while a program is running, such
as an attempt to divide by zero.
 Exceptions provide a way to transfer control from one part of a program to another.
 C++ exception handling is built upon three keywords: try, catch, and throw.

 throw − A program throws an exception when a problem shows up. This is done using a throw
keyword.
 catch − A program catches an exception with an exception handler at the place in a program where
you want to handle the problem. The catch keyword indicates the catching of an exception.
 try − A try block identifies a block of code for which particular exceptions will be activated. It's
followed by one or more catch blocks.

 Assuming a block will raise an exception, a method catches an exception using a combination of the try
and catch keywords.
 A try/catch block is placed around the code that might generate an exception. Code within a try/catch block
is referred to as protected code.
 The syntax for using try/catch as follows –

Syntax:
try {
// protected code
} catch( ExceptionName e1 ) {
// catch block
} catch( ExceptionName e2 ) {
// catch block
} catch( ExceptionName eN ) {
// catch block
}
 We can list down multiple catch statements to catch different type of exceptions in case your try
block raises more than one exception in different situations.

Why Exception Handling:

1) Separation of Error Handling code from Normal Code: In traditional error handling codes, there are
always if else conditions to handle errors. These conditions and the code to handle errors get mixed up
with the normal flow. This makes the code less readable and maintainable. With try catch blocks, the code
for error handling becomes separate from the normal flow.

2) Functions/Methods can handle any exceptions they choose: A function can throw many exceptions, but
may choose to handle some of them. The other exceptions which are thrown, but not caught can be
handled by caller. If the caller chooses not to catch them, then the exceptions are handled by caller of the
caller.
In C++, a function can specify the exceptions that it throws using the throw keyword. The caller of this
function must handle the exception in some way (either by specifying it again or catching it)

3) Grouping of Error Types: In C++, both basic types and objects can be thrown as exception. We can
create a hierarchy of exception objects, group exceptions in namespaces or classes, categorize them
according to types.
Throwing Exceptions
 Exceptions can be thrown anywhere within a code block using throw statement.
 Following is an example of throwing an exception when dividing by zero condition occurs –
Example:
double division(int a, int b) {
if( b == 0 ) {
throw "Division by zero condition!";
}
return (a/b);
}

Catching Exceptions
 The catch block following the try block catches any exception.
 You can specify what type of exception you want to catch and this is determined by the exception
declaration that appears in parentheses following the keyword catch.

Syntax:
try {
// protected code
} catch( ExceptionName e ) {
// code to handle ExceptionName exception
}
Above code will catch an exception of ExceptionName type.
To specify that a catch block should handle any type of exception that is thrown in a try block, just put
an ellipsis, ..., between the parentheses enclosing the exception declaration as follows −
try {
// protected code
} catch(...) {
// code to handle any exception
}

 The following is an example, which throws a division by zero exception and we catch it in catch
block.
Example:
#include<iostream>
using namespace std;
int main(void)
{
int a=20,b=10,c=10;
cout<<"Before Exception"<<endl;
try
{
if(b==0)
throw b;
c=a/b;
}
catch(...)
{
cout<<"Divide by Zero"<<endl;
}
cout<<"After Exception:"<<c;
 }
Output:
Before Exception
After Exception:2

C++ Standard Exceptions:

 C++ provides a list of standard exceptions defined in <exception> class, which we can use in our
programs.
 These are arranged in a parent-child class hierarchy shown below –

 Here is the small description of each exception mentioned in the above hierarchy –

Sr.No Exception & Description

1 std::exception
An exception and parent class of all the standard C++ exceptions.

2 std::bad_alloc
This can be thrown by new.

3 std::bad_cast
This can be thrown by dynamic_cast.
 4 std::bad_exception
This is useful device to handle unexpected exceptions in a C++ program.

5 std::bad_typeid
This can be thrown by typeid.

6 std::logic_error
An exception that theoretically can be detected by reading the code.

7 std::domain_error
This is an exception thrown when a mathematically invalid domain is used.

8 std::invalid_argument
This is thrown due to invalid arguments.

9 std::length_error
This is thrown when a too big std::string is created.

10 std::out_of_range
This can be thrown by the 'at' method, for example a std::vector and
std::bitset<>::operator[]().

11 std::runtime_error
An exception that theoretically cannot be detected by reading the code.

12 std::overflow_error
This is thrown if a mathematical overflow occurs.

13 std::range_error
This is occurred when you try to store a value which is out of range.

14 std::underflow_error
This is thrown if a mathematical underflow occurs.

Define New Exceptions:

 You can define your own exceptions by inheriting and overriding exception class functionality.
 Following is the example, which shows how you can use std::exception class to implement your own
exception in standard way –

Example:
#include <iostream>
#include <exception>
using namespace std;

struct MyException : public exception {

const char * what () const throw () {
 return "C++ Exception";
}
};

int main() {
try {
throw MyException();
} catch(MyException& e) {
std::cout << "MyException caught" << std::endl;
std::cout << e.what() << std::endl;
} catch(std::exception& e) {
//Other errors
}
}
Output:
MyException caught
C++ Exception

 Here, what() is a public method provided by exception class and it has been overridden by all the
child exception classes. This returns the cause of an exception.
ALGORITHMS:

INTRODUCTION:
 The concept of an algorithm is fundamental to computer science. Algorithms exist for many common
problems, and designing efficient algorithms plays a crucial role in developing large-scale computer
applications.
 Algorithm is a step-by-step procedure for solving a computational problem, which defines a set of
instructions to be executed in a certain order to get the desired output.
 A program is also a step by step procedure for solving a problem.
 At design time we write the steps for solving the given problem, this is not program but algorithm
(simple English like statements without using any syntax. This will not be written on a computer but on a
paper.)
 Algorithms are generally created independent of any language, to write algorithms, any natural language
can be used. Ex: English.
 An algorithm can be implemented in more than one programming language.

Algorithm Program
1. Written at Design Time. 1. Written at Implementation.
2. Any person who is having the domain 2. Programmers will write programs.
knowledge can write an algorithm. 3. Only programming languages has to
3. Any language can be used with be used. Ex: C, C++, JAVA.
optional mathematical notations. 4. Software & Hardware dependent. Ex:
4. Software & Hardware independent. Operating system and processor.
5. After writing the algorithm, it’ll be 5. After coding a program it’ll be tested.
analyzed for best results and measure
it according to time and space
complexities.

Characteristics / Specifications of Algorithms:

 Input: An algorithm has zero or more inputs, taken from a specified set of objects.
 Output: An algorithm has one or more outputs, which have a specified relation to the inputs.
 Definiteness: Each step must be precisely defined; Each instruction is clear and unambiguous.
 Finiteness: The algorithm must always terminate after a finite number of steps.
 Effectiveness: All operations to be performed must be sufficiently basic that they can be done exactly
and in finite length.

How to write an algorithm:

 While writing algorithm any intelligible or understandable statements can be used, as long as it is
understandable by the concerned parties.
 No need to follow any programming language syntax or notations specifically in the algorithms. There is
no fixed syntax for writing the algorithms.
 Any language can be used to write the algorithms with optional mathematical notations. Ex: English with
mathematical notations.
 An algorithm can be designed to get a solution of a given problem. A problem can be solved in more than
one ways. Hence, many solution algorithms can be derived for a given problem.

Example:
Problem − Design an algorithm to add two numbers and display the result.
Step 1 – START Step 1 – START
Step 2 − declare three integers a, b & c Step 2 − get values of a & b
 Step 3 − define values of a & b Step 3 − c ← a + b
Step 4 − add values of a & b Step 4 − display c
Step 5 − store output of step 4 to c Step 5 – STOP
Step 6 − print c
Step 7 − STOP

PERFORMANCE ANALYSIS:
 The most important attribute of a program is, its correctness.
 If a program does not perform the intended task, then it is of no use.
 However, a correct program may also be of little use if it takes more memory than the available memory in
a computer where it runs, as well as if it takes more time than the use is willing to wait.
 The word program performance is used to refer the memory and time requirements of a program.
 In straight approach, program performance mean the amount of computer memory and time needed to run a
program.
 There are two approaches to determine the performance of a program. One is analytical, where analytical
methods are used to analyze the performance. Second is experimental, where performance is measured by
conducting experiments.

Space Complexity:
 The space complexity of a program is the amount of memory needed to the program for completion.
 The following are the reasons for the importance of space complexity:
1. If the program is for multi user computer system, then the amount of memory needed for the
program must be specified.
2. It is always advantageous to know whether or not sufficient memory is available to run the
program.
3. A problem may have several solutions with different space requirements. The users will always
prefer the solution which consumes less space in the computer. The solution which consumes less
memory leaves the user with more memory for other tasks.

Components of Space Complexity:

The space required by the program has the following components:
Instruction Space: The space needed to store the compiled version of the program instructions.
 The amount of instruction space needed by the program depends on the following factors:
1. The compiler used to compile the program into machine code.
2. The compiler options in effect at the time of compilation.
3. The target computer.

Data Space: The space needed to store all constants and variable values.
 This has the following to components.
1. Space needed by constants and simple variables.
2. Space needed by dynamically allocated objects such as arrays and class objects.
 C++ language does not specify any space to be allocated for the various C++ datatypes. It is the
compiler which decides at compile time how much memory it has to allocate for a specific type.
 If it is a 16-bit compiler it allocates 2-bytes for int, and in a 32-bit compiler it allocates 4-bytes.
 To know the space requirement for an array multiply the array size and the space needed for a
single array element.
Example: int a[100];
In above example the array will consume 200-bytes in a 16-bit compiler and 400-bytes in a 32-bit
one.

Environment stack space: This is used to save information needed to stop and resume execution of
partially completed functions.
 Each time a function is invoked the following data are saved on environment stack:
1. The return address.
2. The values of all local variables and formal parameters in the function being invoked (in case of
recursive function).

Time complexity:
 The time complexity of a program is the amount of computer time it needs to run the program.
 The following are the reasons for the importance of space complexity:
1. Computer systems require the user to provide a valid time limit for the execution of a program, so
as to avoid the program from entering into infinite loops.
2. The program must need to provide a satisfactory real-time response.
For instance: A text editor that takes a minute to move the cursor for page down and page up
will not be acceptable.

Components of Time Complexity:

 The time complexity of a program depends on all the factors that the space complexity depends.
1. A program will run faster on a computer capable of executing 109 instructions per second than on a
computer 107 instructions per second.
2. A solution with less number of instructions always require less execution time. Small problem
solutions take less time compared to lagers problem solution.
3. Some compilers will take less time than others to generate the machine code.

 The time taken by a program P is the sum of the compile time and the runtime. As a compiled program can
be executed several times without recompilation. Only the runtime will be considered. This runtime is
denoted by tp.
 As the factors of tp are not known, when the program is created. The t p can only be estimated.
 tp can be determined as the sum of number of additions, subtractions, multiplications, divisions, compares,
loads, stores, and so on that the code for P performs.
tp(n) = caADD(n) + csSUB(n) + cmMUL(n) + cdDIV(n) + …

Where ca, cs, cm, and cd are the time needed for addition, subtraction, multiplication and division.
And ADD, SUB, MUL and DIV are functions whose value is the number of addition, subtraction,
multiplication and divisions performed in code P.
Two more approaches for estimating runtime are:
1. Operation Count: Identifying the key operations and determining the number of times these
operations are performed.
2. Step Count: Determining the total number of steps executed by the program.

Operation Counts: To estimate the time complexity of a program or a function, select one or more
operations such as add, multiply and compare and determine how many times these operations are
performed. The success of this method depends on the ability of the programmer in identifying the
operations that contributes to the time complexity. Operation count is a function of instance
characteristics (size of input and output, system performance).
Example: Consider the linear search example of the following.

Sample code for Linear search

template <class T>
void Lsearch(T *a, T item, int n)
{
int z=0;
for(int i=0;i<n;i++)
{
if(a[i]==item)
 {
cout<<”\n Item found at position:”<<i+1;
z=1;
return;
}
}
cout<<”\nItem not found…”;
}

Best, Worst and Average Operation Counts:

 In the above example to find the desired element in the list, a compare operation is performed
between the desired value and the elements in the list.
 Search process will begin at the start of the list and continue until it finds the desired element.
 The function returns the index value of element where it found the desired element.

Best Operation Count:

 Finding the element at the first location with n-elements in the list will lead in performing
only one compare operation.
 This will be considered as the best case scenario for our example. And also need only one
compare operation to lead to the success of the program.

Worst Operation Count:

 Finding the element at the last location with n-elements in the list, will lead in performing n-
comparisons within the list.
 This will be considered as the worst case scenario for our example. And also need n-
compares before finding the desired value.

Average Operation Count:

 Finding average operation count deals with performing the operation for some k-number of
times, adding the total number of compare operations resulted, dividing with k will give the
average case.
 The average operation count is often quite difficult to determine. As a result operation count
will deal with only best and worst cases and average case is ignored.

How to Analyze an Algorithm:

The criteria for analyzing an algorithm:
1. Time:
 The algorithm must be time efficient means it must be faster.
 In the analysis process the time taken by the algorithm is measured, whether the algorithm is lengthy
and time consuming or it is smaller and faster.
 The time consumed by the algorithm will be in the form of a function (Time function) and not in the
form of a watch/clock time.

2. Space:
 The algorithm will be converted into a program and going to be executed on a computer.
 One has to know how much memory space it is going to consume during its execution.

3. Network Consumption:
 The algorithm, if it is doing network transactions sending and receiving the data to and from the
network, then the consumption of Network resources need be considered as a criterion of analysis.
 4. Power Consumption:
 Now a day’s most of the programs are coded not only for desktop computers but also for mobile
phones, tablets and laptops, where the power consumption is an important issue.
 If the algorithm falls under this category then power consumption is also an important criterion of
analysis.

5. CPU registers:
 The CPU will also have memory known as registers.
 The amount of CPU register consumption by the algorithm need to be considered as a criterion while
designing the algorithm.

Measuring Time and Space Complexities:

Time Analysis:
 Every simple statement (not nested) in an algorithm will take one unit of time.
 If an algorithm is calling or using another algorithm in it, then the called algorithm must have to be
analyzed.
Space Analysis:
 Every simple variable in the algorithm will consume one word of memory.
 If it is a complex variable like an array then the total number of elements in that array need to
considered.

Examples:
Ex1:
Algorithm swap(a,b) Time Space
{ ---------------- --------------
temp <- a; ----------- 1 a -------------- 1
a <- b; ----------------- 1 b -------------- 1
b <- temp; ------------ 1 temp --------------- 1
} ---------------------- ------------------------
f(n) = 3 (a constant value) s(n) = 3 words
O(1) O(1)

Recursive Algorithms:
 A function is a set of instructions that perform a logical operation, perhaps a very complex and long
operation, can be grouped together as a function.
 Recursion is a process in which functions can call themselves (direct recursion) before they are done or
they may call other functions that again invoke the calling function (indirect recursion).
 A recursive algorithm is an algorithm which calls itself with "smaller (or simpler)" input values, and which
obtains the result for the current input by applying simple operations to the returned value for the smaller
(or simpler) input.
 In general, recursive computer programs require more memory and computation compared with iterative
algorithms, but they are simpler and for many cases a natural way of thinking about the problem.

Example:
Step 1: start factorial(n)
Step 2: read number n Step 1: if n==1 then return 1
Step 3: call factorial(n) Step 2: else
Step 4: print factorial f f=n*factorial(n-1)
Step 5: stop Step 3: return f
UNIT-II
ADT (ABSTRACT DATA TYPE):

 Abstract Data type (ADT) is a type (or class) for objects whose behavior is defined by a set of value and a
set of operations.
 The definition of ADT only mentions what operations are to be performed but not how these operations
will be implemented. It does not specify how data will be organized in memory and what algorithms will
be used for implementing the operations.
 It is called “abstract” because it gives an implementation-independent view. The process of providing only
the essentials and hiding the details is known as abstraction.
 The user of data type does not need to know how that data type is implemented, for example, we have been
using Primitive values like int, float, char data types only with the knowledge that these data type can
operate and be performed on without any idea of how they are implemented. So a user only needs to know
what a data type can do, but not how it will be implemented.
 Think of ADT as a black box which hides the inner structure and design of the data type.
 Consider the following examples of ADTs namely List ADT, Stack ADT, Queue ADT.

List ADT

 A list contains elements of the same type arranged in sequential order and following operations can
be performed on the list.
o get() – Return an element from the list at any given position.
o insert() – Insert an element at any position of the list.
o remove() – Remove the first occurrence of any element from a non-empty list.
o removeAt() – Remove the element at a specified location from a non-empty list.
o replace() – Replace an element at any position by another element.
o size() – Return the number of elements in the list.
o isEmpty() – Return true if the list is empty, otherwise return false.
o isFull() – Return true if the list is full, otherwise return false.

Stack ADT

 A Stack contains elements of the same type arranged in sequential order. All operations take place
at a single end that is top of the stack and following operations can be performed:
o push() – Insert an element at one end of the stack called top.
o pop() – Remove and return the element at the top of the stack, if it is not empty.
o peek() – Return the element at the top of the stack without removing it, if the stack is not
empty.
o size() – Return the number of elements in the stack.
o isEmpty() – Return true if the stack is empty, otherwise return false.
o isFull() – Return true if the stack is full, otherwise return false.

Queue ADT

 A Queue contains elements of the same type arranged in sequential order. Operations take place at
both ends, insertion is done at the end and deletion is done at the front. Following operations can be
performed:
o enqueue() – Insert an element at the end of the queue.
o dequeue() – Remove and return the first element of the queue, if the queue is not empty.
o peek() – Return the element of the queue without removing it, if the queue is not empty.
o size() – Return the number of elements in the queue.
 o isEmpty() – Return true if the queue is empty, otherwise return false.
o isFull() – Return true if the queue is full, otherwise return false.

 From these definitions, it is clear that the definitions do not specify how these ADTs will be
represented and how the operations will be carried out.
 There can be different ways to implement an ADT, for example, the List ADT can be implemented
using arrays, or singly linked list or doubly linked list.
 Similarly, stack ADT and Queue ADT can be implemented using arrays or linked lists.

STACK
 A stack is a linear data structure in which insertions (also called additions and pushes) and removals (also
called deletion and pops) take place at the same end. This end is called as the top of the stack.
 The other end is known as bottom of the stack.
 In a stack insertion and deletion of elements will be performed in LIFO fashion (Last In First Out).

Examples for stack:

1) Paper tray of the printer (or copy machine), where the sheets of papers are stacked in the tray. The next
sheet that gets used is always selected from top of the tray. Additional sheets will be added at the top. The
printer tray maintains a stack of papers and it works in a LIFO manner.
2) Plates in canteen are stacked for use. Students in food line picks up a plate from the top the stack. And new
plates to the stack will be added at the top of the stack. Here also the plates stacked work in LIFO manner.

Stack Errors:
Two things can go wrong with stacks:
 Underflow: An attempt was made to pop an empty stack. It doesn't make sense to remove something from
an empty collection. Stack underflow is a common error - calls to isEmpty should be used to guard against
it.
 Overflow: An attempt was made to push an item onto a full stack. Items can only be added to a collection
if there is enough available memory to store it into the collection.

Stack ADT
 A Stack contains elements of the same type arranged in sequential order. All operations take place at a
single end that is top of the stack and following operations can be performed:
o push() – Insert an element at one end of the stack called top, if it is not full.
o pop() – Remove and return the element at the top of the stack, if it is not empty.
o peek() – Return the element at the top of the stack without removing it, if the stack is not empty.
o size() – Return the number of elements in the stack.
o isEmpty() – Return true if the stack is empty, otherwise return false.
o isFull() – Return true if the stack is full, otherwise return false.
Array representation of Stack – using template
#include <iostream>
using namespace std;
// Class for stack
template <class T>
class StackDemo
{
T* arr;
int top;
int capacity;

public:
StackDemo(int); // constructor

void push(T);
T pop();
T peek();

int size();
bool isEmpty();
bool isFull();

// destructor
~ StackDemo(){
delete[] arr;
}
};

// Constructor to initialize stack

template <class T>
StackDemo<T>::StackDemo(int size)
{
arr = new T[size];
capacity = size;
top = -1;
}

// function to add an element t in the stack

template <class T>
void StackDemo<T>::push(T t)
{
if (isFull())
{
cout << "OverFlow\nProgram Terminated\n";
exit(1);
}

cout << "Inserting " << t << endl;

arr[++top] = t;
}

// function to pop top element from the stack

template <class T>
T StackDemo<T>::pop()
{
// check for stack underflow
if (isEmpty())
{
cout << "UnderFlow\nProgram Terminated\n";
exit(1);
}

cout << "Removing " << peek() << endl;

// decrease stack size by 1 and (optionally) return the popped element

return arr[top--];
}

// function to return top element in a stack

template <class T>
T StackDemo<T>::peek()
{
if (!isEmpty())
return arr[top];
else
exit(1);
}

// Utility function to return the size of the stack

template <class T>
int StackDemo<T>::size()
{
return top + 1;
}

// Utility function to check if the stack is empty or not

template <class T>
bool StackDemo<T>::isEmpty()
{
return top == -1; // or return size() == 0;
}

// Utility function to check if the stack is full or not

template <class T>
bool StackDemo<T>::isFull()
{
return top == capacity - 1; // or return size() == capacity;
}

// main function
int main()
{
StackDemo<string> st(2);

st.push("A");
st.push("B");
 st.pop();
st.pop();

st.push("C");

// Prints the top of the stack

cout << "Top element is: " << st.peek() << endl;

// Returns the number of elements present in the stack

cout << "Stack size is " << st.size() << endl;

st.pop();

// check if stack is empty or not

if (st.isEmpty())
cout << "Stack Is Empty\n";
else
cout << "Stack Is Not Empty\n";

return 0;
}
Output:
Inserting A
Inserting B
Removing B
Removing A
Inserting C
Top element is: C
Stack size is 1
Removing C
Stack Is Empty

APPLICATIONS OF STACK
1. Reversing a String.
2. Parsing - Balancing of Parenthesis.
3. Infix to Postfix /Prefix conversion.
4. Postfix expression evaluation.
5. Redo-undo features at many places like editors, Photoshop.
6. Forward and backward feature in web browsers.
7. Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem.
8. Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and Sudoku
solver.
9. In Graph Algorithms like Topological Sorting and Strongly Connected Components.

1. Expression Conversion (Infix to Postfix, Postfix to Prefix etc.,)

o While we use infix expressions in our day to day lives. Computers have trouble understanding this
format because they need to keep in mind rules of operator precedence and also brackets.
o Prefix and Postfix expressions are easier for a computer to understand and evaluate.
o Infix expression: The expression of the form a op b. When an operator is in-between every pair of
operands. This form of expressions are known as infix expressions.
 o Postfix expression: The expression of the form a b op. When an operator is followed for every pair of
operands. This form of expressions are known as postfix expressions.
o Prefix expression: The expression of the form op a b. When an operator is before every pair of
operands. This form of expressions are known as prefix expressions.

Infix to postfix conversion:

Why postfix representation of the expression?
o The compiler scans the expression either from left to right or from right to left.
o Consider the below expression: a + b * c + d
o The compiler first scans the expression to evaluate the expression b * c, then again scan the
expression to add a to it. The result is then added to d after another scan.
o The repeated scanning makes it very in-efficient. It is better to convert the expression to postfix (or
prefix) form before evaluation.
o The corresponding expression in postfix form is: abc*+d+. The postfix expressions can be evaluated
easily using a stack.

Algorithm:
1. Scan the infix expression from left to right.
2. If the scanned character is an operand, output it.
3. Else,
a. If the precedence of the scanned operator is greater than the precedence of the operator in the
stack (or the stack is empty or the stack contains a ‘(‘ ), push it.
b. Else, Pop all the operators from the stack which are greater than or equal to in precedence than
the scanned operator. (If you encounter parenthesis while popping then stop there and push the
scanned operator in the stack.)
c. After doing that Push the scanned operator to the stack.
4. If the scanned character is an ‘(‘, push it to the stack.
5. If the scanned character is an ‘)’, pop the stack and and output it until a ‘(‘ is encountered, and discard
both the parenthesis.
6. Repeat steps 2-6 until infix expression is scanned.
7. Pop and output from the stack until it is not empty.

/* C++ implementation to convert infix expression to postfix*/

#include <iostream>
#include <string.h>
using namespace std;

// Class for stack

template <class T>
class StackDemo
{
T* arr;
int top;
int capacity;

public:
StackDemo(int); // constructor

void push(T);
T pop();
T peek();

int size();
 bool isEmpty();
bool isFull();

// destructor
~ StackDemo(){
delete[] arr;
}
};

// Constructor to initialize stack

template <class T>
StackDemo<T>:: StackDemo(int size)
{
arr = new T[size];
capacity = size;
top = -1;
}

// function to add an element x in the stack

template <class T>
void StackDemo<T>::push(T t)
{
if (isFull())
{
cout << "OverFlow\nProgram Terminated\n";
exit(1);
}

cout << "Inserting " << t << endl;

arr[++top] = t;
}

// function to pop top element from the stack

template <class T>
T StackDemo<T>::pop()
{
// check for stack underflow
if (isEmpty())
{
cout << "UnderFlow\nProgram Terminated\n";
exit(1);
}

cout << "Removing " << peek() << endl;

// decrease stack size by 1 and (optionally) return the popped element

return arr[top--];
}

// function to return top element in a stack

template <class T>
T StackDemo<T>::peek()
{
 if (!isEmpty())
return arr[top];
else
exit(1);
}

// Utility function to return the size of the stack

template <class T>
int StackDemo<T>::size()
{
return top + 1;
}

// Utility function to check if the stack is empty or not

template <class T>
bool StackDemo<T>::isEmpty()
{
return top == -1; // or return size() == 0;
}

// Utility function to check if the stack is full or not

template <class T>
bool StackDemo<T>::isFull()
{
return top == capacity - 1; // or return size() == capacity;
}

//utility function to return operator precedence

int prec(char c)
{
if(c == '^')
return 3;
else if(c == '*' || c == '/')
return 2;
else if(c == '+' || c == '-')
return 1;
else
return -1;
}

// Utility function to convert infix expression to postfix expression

void infixToPostfix(char s[])
{
int len=strlen(s);
StackDemo<char> st(len);
st.push('N');
string ns;
for(int i = 0; i < len; i++)
{
// If the scanned character is an operand, add it to output string.
if((s[i] >= 'a' && s[i] <= 'z')||(s[i] >= 'A' && s[i] <= 'Z'))
ns+=s[i];
 // If the scanned character is an '(', push it to the stack.
else if(s[i] == '(')

st.push('(');

// If the scanned character is an ')', pop and to output string from the stack
// until an '(' is encountered.
else if(s[i] == ')')
{
while(st.peek() != 'N' && st.peek() != '(')
{
char c = st.peek();
st.pop();
ns += c;
}
if(st.peek() == '(')
{
char c = st.peek();
st.pop();
}
}

//If an operator is scanned

else{
while(st.peek() != 'N' && prec(s[i]) <= prec(st.peek()))
{
char c = st.peek();
st.pop();
ns += c;
}
st.push(s[i]);
}

}
//Pop all the remaining elements from the stack
while(st.peek() != 'N')
{
char c = st.peek();
st.pop();
ns += c;
}

cout << ns << endl;

// main function
int main()
{
char exp[] = "a+b*(c^d-e)^(f+g*h)-i";
infixToPostfix(exp);
return 0;
}
 Output:
Inserting N
Inserting +
Inserting *
Inserting (
Inserting ^
Removing ^
Inserting -
Removing -
Removing (
Inserting ^
Inserting (
Inserting +
Inserting *
Removing *
Removing +
Removing (
Removing ^
Removing *
Removing +
Inserting -
Removing -
abcd^e-fgh*+^*+i-

Infix to prefix conversion:

o Given two operands a and b and an operator +, the infix notation implies that operator + will be placed in
between a and b i.e a + b .
o When the operator + is placed after both operands i.e ab+, it is called postfix notation.
o And when the operator + is placed before the operands i.e + a b, the expression in prefix notation.

Examples:
Input : A * B + C / D
Output : + * A B/ C D
Input : (A - B/C) * (A/K-L)
Output : *-A/BC-/AKL
Algorithm:
Step-1: Reverse the infix expression i.e A+B*C will become C*B+A. Note while reversing each ‘(‘ will
become ‘)’ and each ‘)’ becomes ‘(‘.
Step-2: Obtain the postfix expression of the modified expression i.e CB*A+.
Step-3: Reverse the postfix expression. Hence in our example prefix is +A*BC.
// CPP program to convert infix to prefix
#include <iostream>
#include <string.h>
#include <bits/stdc++.h>
using namespace std;

bool isOperator(char c)
{
return (!isalpha(c) && !isdigit(c));
}
int getPriority(char C)
{
if (C == '-' || C == '+')
return 1;
else if (C == '*' || C == '/')
return 2;
else if (C == '^')
return 3;
return 0;
}

string infixToPostfix(string infix)

{
infix = '(' + infix + ')';
int l = infix.size();
stack<char> char_stack;
string output;

for (int i = 0; i < l; i++) {

// If the scanned character is an

// operand, add it to output.
if (isalpha(infix[i]) || isdigit(infix[i]))
output += infix[i];

// If the scanned character is an

// ‘(‘, push it to the stack.
else if (infix[i] == '(')
char_stack.push('(');

// If the scanned character is an

// ‘)’, pop and output from the stack
// until an ‘(‘ is encountered.
else if (infix[i] == ')') {

while (char_stack.top() != '(') {

output += char_stack.top();
char_stack.pop();
}

// Remove '(' from the stack

char_stack.pop();
}

// Operator found
else {

if (isOperator(char_stack.top())) {
while (getPriority(infix[i])
<= getPriority(char_stack.top())) {
output += char_stack.top();
char_stack.pop();
 }

// Push current Operator on stack

char_stack.push(infix[i]);
}
}
}
return output;
}

string infixToPrefix(string infix)

{
/* Reverse String
* Replace ( with ) and vice versa
* Get Postfix
* Reverse Postfix * */
int l = infix.size();

// Reverse infix
reverse(infix.begin(), infix.end());

// Replace ( with ) and vice versa

for (int i = 0; i < l; i++) {

if (infix[i] == '(') {
infix[i] = ')';
i++;
}
else if (infix[i] == ')') {
infix[i] = '(';
i++;
}
}

string prefix = infixToPostfix(infix);

// Reverse postfix
reverse(prefix.begin(), prefix.end());

return prefix;
}

// Driver code
int main()
{
string s = ("(a-b/c)*(a/k-l)");
cout << infixToPrefix(s) << std::endl;
return 0;
}
Output:
*-a/bc-/akl
The complexity is linear in time i.e O(n).
Evaluation of Postfix Expression
 The Postfix notation is used to represent algebraic expressions.
 The expressions written in postfix form are evaluated faster compared to infix notation as parenthesis are
not required in postfix, and the need of remembering operator precedence can be avoided.
 Following is algorithm for evaluation postfix expressions.

Algorithm:
1. Create a stack to store operands (or values).
2. Scan the given expression and do following for every scanned element.
…..a) If the element is a number, push it into the stack
…..b) If the element is a operator, pop operands for the operator from stack. Evaluate the operator and
push the result back to the stack
3. When the expression is ended, the number in the stack is the final answer
Example: Let the given expression be “2 3 1 * + 9 -“. We scan all elements one by one.

1. Scan ‘2’, it’s a number, so push it to stack. Stack contains ‘2’.

2. Scan ‘3’, again a number, push it to stack, stack now contains ‘2 3’ (from bottom to top).
3. Scan ‘1’, again a number, push it to stack, stack now contains ‘2 3 1’.
4. Scan ‘*’, it’s an operator, pop two operands from stack, apply the * operator on operands, we get 3*1
which results in 3. We push the result ‘3’ to stack. Stack now becomes ‘2 3’.
5. Scan ‘+’, it’s an operator, pop two operands from stack, apply the + operator on operands, we get 3 + 2
which results in 5. We push the result ‘5’ to stack. Stack now becomes ‘5’.
6. Scan ‘9’, it’s a number, we push it to the stack. Stack now becomes ‘5 9’.
7. Scan ‘-‘, it’s an operator, pop two operands from stack, apply the – operator on operands, we get 5 – 9
which results in -4. We push the result ‘-4’ to stack. Stack now becomes ‘-4’.
8. There are no more elements to scan, we return the top element from stack (which is the only element left
in stack).

Program: Postfix Expression evaluation

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;

class StackDemo
{
private:
int* arr;
int top, res, capacity;
public:
StackDemo(int);
void push(int);
int pop();
int peek();
int size();
bool isEmpty();
bool isFull();

void postEval(char[]);

// destructor
~ StackDemo(){
 delete[] arr;
}
};

// Constructor to initialize stack

StackDemo:: StackDemo(int size)
{
arr = new int[size];
capacity = size;
top = -1;
}

// function to add an element t in the stack

void StackDemo::push(int t)
{
if (isFull())
{
cout << "OverFlow\nProgram Terminated\n";
exit(1);
}

cout << "Inserting " << t << endl;

arr[++top] = t;
}

// function to pop top element from the stack

int StackDemo::pop()
{
// check for stack underflow
if (isEmpty())
{
cout << "UnderFlow\nProgram Terminated\n";
exit(1);
}

cout << "Removing " << peek() << endl;

// decrease stack size by 1 and (optionally) return the popped element

return arr[top--];
}

// function to return top element in a stack

int StackDemo::peek()
{
if (!isEmpty())
return arr[top];
else
exit(1);
}

// Utility function to return the size of the stack

int StackDemo::size()
{
return top + 1;
}

// Utility function to check if the stack is empty or not

bool StackDemo::isEmpty()
{
return top == -1;
}

// Utility function to check if the stack is full or not

bool StackDemo::isFull()
{
return top == capacity - 1;
}

void StackDemo::postEval(char texp[])

{
int op1, op2, op3;
while (*texp)
{
if ( *texp == ' ' || *texp == '\t' )
{
texp++;
continue;
}
if(*texp<='9' && *texp>='0')
{
res = *texp - '0' ;
push(res);
}
else
{
op1 = pop();
op2 = pop();
switch (*texp)
{
case '+':
op3 = op2 + op1 ;
break;
case '-':
op3 = op2 - op1 ;
break;
case '/':
op3 = op2 / op1 ;
break;
case '*':
op3 = op2 * op1 ;
break ;
case '%':
op3 = op2 % op1 ;
break;
case '^' :
 op3 = pow( op2 , op1 ) ;
break;
default :
cout << "Unknown Operator\n";
}
push(op3) ;
}
texp++ ;
}
res = pop();
cout << "Result is: " << res;
}

//Main function of the program

int main(void)
{
char exp[] = "647*+";
int len=strlen(exp);
StackDemo st(len);
st.postEval(exp);
return 0;
}
Output:
Inserting 6
Inserting 4
Inserting 7
Removing 7
Removing 4
Inserting 28
Removing 28
Removing 6
Inserting 34
Removing 34
Result is: 34
QUEUE ADT (Abstract Data Type):
 A Queue is a linear structure which follows a particular order in which the operations are performed. The
order is First In First Out (FIFO). The inserting operation (enQueue) can only be performed from one side
(called the rear) and the removing operation (deQueue) can only be performed from the other side (called
the front).
 A queue is an abstract data structure that contains a collection of elements.
 A good example of a queue is any queue of consumers for a resource where the consumer that came first is
served first.
 The difference between stacks and queues is in removing. In a stack we remove the item the most recently
added; in a queue, we remove the item the least recently added.
 The regular queue is also known as linear queue.

Queue EnQueue Operation:

Queue DeQueue Operation:

Applications of Queue:
 Queue is used when things don’t have to be processed immediately, but have to be processed in First In
First Out order like Breadth First Search.
 This property of Queue makes it also useful in following kind of scenarios.
1. When a resource is shared among multiple consumers. Examples include CPU scheduling, Disk
Scheduling.
2. When data is transferred asynchronously (data not necessarily received at same rate as sent)
between two processes. Examples include IO Buffers, pipes, file IO, etc.

Queue ADT
 A Queue contains elements of the same type arranged in sequential order. Operations take place at
both ends, insertion is done at the rear end and deletion is done at the front end.
 Following operations can be performed:
o enQueue() – Insert an element at the rear end of the queue, if the queue is not full.
o deQueue() – Remove and return the first element of the queue, if the queue is not empty.
o peekFront() – Return the front element of the queue without removing it, if the queue is not
empty.
o peekRear() – Return the rear element of the queue without removing it, if the queue is not
empty.
o size() – Return the number of elements in the queue.
o isEmpty() – Return true if the queue is empty, otherwise return false.
o isFull() – Return true if the queue is full, otherwise return false.

Array representation of Queue – using template

#include <iostream>
using namespace std;

template <class T>

class QueueDemo
{
T* queue;
int capacity;
int front;
int rear;
int count;

public:
QueueDemo(int);

void deQueue();
void enQueue(T);
T peekFront();
T peekRear();
int size();
bool isEmpty();
bool isFull();
};

template <class T>

QueueDemo<T>:: QueueDemo(int size)
{
queue = new T[size];
capacity = size;
 front = 0;
rear = -1;
count = 0;
}

template <class T>

void QueueDemo<T>::enQueue(T item)
{
if (isFull())
{
cout << "OverFlow\nProgram Terminated\n";
return;
}

cout << "Inserting: " << item << '\n';

queue[++rear] = item;
count++;
}

template <class T>

void QueueDemo<T>::deQueue()
{
if (isEmpty())
{
cout << "UnderFlow\nProgram Terminated\n";
return;
}

cout << "\nRemoving: " << queue[front++] << '\n';

count--;
}

template <class T>

T QueueDemo<T>::peekFront()
{
if (isEmpty())
{
cout << "UnderFlow\nProgram Terminated\n";
return 0;
}
return queue[front];
}

template <class T>

T QueueDemo<T>::peekRear()
{
if (isEmpty())
{
cout << "UnderFlow\nProgram Terminated\n";
return 0;
}
return queue[rear];
}

template <class T>

int QueueDemo<T>::size()
{
return count;
}

template <class T>

bool QueueDemo<T>::isEmpty()
{
return (count == 0);
}

template <class T>

bool QueueDemo<T>::isFull()
{
return (rear == capacity-1);
}

int main()
{
QueueDemo<string> que(4);

que.enQueue("a");
que.enQueue("b");
que.enQueue("c");

cout << "Front element is: " << que.peekFront() << endl;
cout << "Rear element is: " << que.peekRear() << endl;
que.deQueue();

que.enQueue("d");

cout << "Queue size is " << que.size() << endl;

que.deQueue();
que.deQueue();
que.deQueue();

if (que.isEmpty())
cout << "Queue Is Empty\n";
else
cout << "Queue Is Not Empty\n";

que.enQueue("e");
que.deQueue();
return 0;
}
Output:
Inserting a
Inserting b
Inserting c
 Front element is: a
Rear element is: c
Removing a
Inserting d
Queue size is 3
Removing b
Removing c
Removing d
Queue Is Empty
OverFlow
Program Terminated
UnderFlow
Program Terminated

CIRCULAR QUEUE:

 Circular Queue is a linear data structure in which the operations are performed based on FIFO (First In
First Out) principle and the last position is connected back to the first position to make a circle.
 It is also called ‘Ring Buffer’.

 In a normal Queue, we can insert elements until queue becomes full. But once queue becomes full, we
cannot insert the next element even if there is an empty space in front of the queue.
 The problem can be overcome with the help of a circular queue. In this the last position of the queue is
connected back to the first position to form the memory locations in a circular fashion.
 Here when the queue is full, and if there are empty locations before the front they can be reused to perform
more enQueue operations.
Applications of Circular Queue:
1. Traffic lights functioning is the best example for circular queues. The colors in a traffic light follow a
circular pattern.
2. In page replacement algorithm, a circular list of pages is maintained and when a page needs to be replaced,
the page in the front of the queue will be chosen.

Circular Queue ADT:

Operations on Circular Queue:
 enQueue(value) This function is used to insert an element into the circular queue. In a circular
queue, the new element is always inserted at Rear position.
 deQueue() This function is used to delete an element from the circular queue. In a circular
queue, the element is always deleted from front position.
 display() – Display all the elements form the circular queue.
 isFull() – Returns true if the circular queue is full, otherwise returns false.
 isEmpry() – Returns true if the circular queue is empty, otherwise returns false.
Array representation of Circular Queue using Template
#include<iostream>
#include<conio.h>
using namespace std;

// Creating a generic Queue class

template <class T>
class CQueueDemo
{
T* cqueue;
int front,rear,capacity;
public:
CQueueDemo(int);
void enQueue(T);
T deQueue();
void display();
bool isFull();
bool isEmpty();
};

template <class T>

CQueueDemo<T>:: CQueueDemo(int size)
{
cqueue=new T(size);
front=-1;
rear=0;
capacity=size;
}

// Enqueue function
template <class T>
void CQueueDemo<T>::enQueue(T item)
{
if (isFull())
{
cout << "Circular Queue is full\n";
exit(1);
 }
if(front==-1)
{
front=0;
rear=0;
}
else
rear=(rear+1)%capacity;
cqueue[rear] = item; //inserting the item in the circular queue
}

//Dequeue function
template <class T>
T CQueueDemo<T>::deQueue()
{
T val;
if(isEmpty())
{
cout << "Circular Queue is empty\n";
exit(1);
}
val= cqueue[front]; //item to be deleted
if(front==rear)
front=rear=-1;
else
front=(front+1)%capacity;
return val;
}

template <class T>

void CQueueDemo<T>::display()
{
int temp;
if(isEmpty())
{
cout<<"\n Circular Queue is Empty";
exit(1);
}
cout<<"Elements in the Circular Queue:" <<endl;
temp=front;
while(temp!=rear)
{
cout<<"\n "<<cqueue[temp];
temp=(temp+1)%capacity;
}
cout<<"\n "<<cqueue[temp];
cout<<"\n";
}

template <class T>

bool CQueueDemo<T>::isFull()
{
return (front==(rear+1)%capacity);
}

template <class T>

bool CQueueDemo<T>::isEmpty()
{
return ((front==-1)||(front==rear-1));
}

//The main function

int main(void)
{
CQueueDemo<char> cq(5);
cq.enQueue('p');
cq.enQueue('q');
cq.enQueue('r');
cq.enQueue('s');
cq.enQueue('t');
cq.display();
cq.deQueue();
cq.deQueue();
cq.display();
cq.enQueue('u');
cq.enQueue('v');
cq.display();
cq.deQueue();
cq.display();
}
Output:
Elements in the Circular Queue:
p
q
r
s
t
Elements in the Circular Queue:
r
s
t
Elements in the Circular Queue:
r
s
t
u
v
Elements in the Circular Queue:
s
t
u
v
UNIT – III, LINKED LISTS
Singly Linked Lists:
 A singly linked list is a way to store a collection of elements. Like an array these can be character or
integers. Each element in a singly linked list is stored in the form of a node.
 Like arrays, Singly Linked List is a linear data structure. Unlike arrays, singly linked list elements are not
stored at a contiguous location; the elements are linked using pointers.
 A node is a collection of two sub-elements or parts. A data part that stores the element and a next part that
stores the link to the next node.

 A singly linked list is formed when many such nodes are linked together to form a chain. Each node points
to the next node present in the order. The first node is always used as a reference to traverse the list and is
called HEAD. The last node points to NULL.

Why Singly Linked List?

Arrays can be used to store linear data of similar types, but arrays have the following limitations.

1. The size of the arrays is fixed: So we must know the upper limit on the number of elements in advance.
2. Inserting a new element in an array of elements is expensive because the room has to be created for the
new elements and to create room existing elements have to be shifted.
a. For example: in a system, if we maintain a sorted list of IDs in an array id[].
id[] = [1000, 1010, 1050, 2000, 2040].

And if we want to insert a new ID 1005, then to maintain the sorted order, we have to move all the
elements after 1000 (excluding 1000).
3. Deletion is also expensive with arrays until unless some special techniques are used. For example, to delete
1010 in id[], everything after 1010 has to be moved.

Advantages over arrays:

1) Dynamic size
2) Ease of insertion/deletion
Drawbacks:
1) Random access is not allowed. We have to access elements sequentially starting from the first node. So we
cannot do binary search with linked lists efficiently with its default implementation. Read about it here.
2) Extra memory space for a pointer is required with each element of the list.
3) Not cache friendly. Since array elements are contiguous locations, there is locality of reference which is not
there in case of linked lists.
Representation:
A singly linked list is represented by a pointer to the first node of the linked list. The first node is called the head.
If the singly linked list is empty, then the value of the head is NULL.
Each node in a list consists of at least two parts:
1) Data
2) Pointer (Or Reference) to the next node
In C++ Singly Linked List can be represented as a class Node, which contains a reference of Node class type.
class Node {
public:
int data;
Node* next;
};

Singly Linked List program to create a simple linked list with 3 nodes.
// A simple CPP program to introduce a singly linked list
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node* next;
};

// Program to create a simple singly linked list with 3 nodes

int main()
{
// allocate 3 nodes in the heap
Node* head = NULL;
Node* first = new Node();
Node* second = new Node();
Node* third = new Node();
head = first;
first->data = 1; // assign data in first node
first->next = second; // Link first node with the second node
second->data = 2; // assign data to second node
second->next = third; // Link second node with the third node
 third->data = 3; // assign data to third node
third->next = NULL; // make the third node link as null
return 0;
}

Singly Linked List Traversal

 Traversal is nothing but, it is a way of accessing all the elements from singly linked list. In Singly Linked
list traversal, all data elements of the singly linked list are accessed and same can be printed for reference.
 Let us traverse the created list and print the data of each node. For traversal, let us write a general-purpose
function printList() that prints any given list.

C++ program for traversal of a singly linked list

void printList(Node* temp)
{
if(temp==NULL)
{
cout << “Linked list is empty…”;
return;
}
while (temp != NULL)
{
cout << temp->data << “ “;
temp = temp->next;
}
}
Traversing a singly linked list operations involves visiting all nodes from head node till the last node. If there are
n nodes available in the singly linked list then a loop can be used to visit all the elements until the last node
pointer becomes NULL. Taking a loop involves visiting n elements to fetch their values, hence Time
Complexity will be O(n).

Inserting a Node into the singly linked list

A node into a singly linked list can be added in three ways
a) At the front of the singly linked list. (addAtFirst())
b) After a given node. (addAfter())
c) At the end of the singly linked list. (addAtEnd())

a) Add a node at the front: (A 4 steps process)

 In this case, the new node is added before the head of the given Singly Linked List. And newly added
node becomes the new head of the Singly Linked List.
 For example if the given Singly Linked List is 10->15->20->25 and after adding an item 5 at the
front, the Singly Linked List becomes 5->10->15->20->25.
  The function that adds an item at the front of the list is addAtFirst(). The addAtFirst() must receive a
pointer to the head, because addAtFirst() must change the head pointer to point to the new node (See
the following figure).

Algorithm and C++ code to perform addAtFirst() operation.

//Given a reference (pointer to pointer) to the head of a list and an int, inserts a new node on the front of the list.
void addAtFirst(int new_data)
{
// 1. Allocate node.
Node* new_node = new Node();

// 2. Put in the data.

new_node->data = new_data;

// 3. Make next of new node as head.

new_node->next = head;

// 4. Move the head to point to the new node.

head = new_node;
}
Time complexity of addAtFirst() is O(1) as it does constant amount of work.

b) Add a node after a given node: (6 steps process)

 In this case, the new node is added after a specified node location within the given Singly Linked List.
 For example if the given Singly Linked List is 10->15->20->25 and after adding an item 5 after node
15, the Singly Linked List becomes 10->15->5->20->25.
 The function that adds an item after a specified node in the list is addAfter(). The addAfter() must
receive a pointer to the head node, the number of nodes after which the new node needs to be inserted
and the data element to be inserted into the new node.(See the following figure).
Algorithm and C++ code to perform addAfter() operation.
/* Given a reference (pointer to pointer) to the head node and the number of nodes after which the new node is
added, insert a new node after the number of nodes*/
void addAfter(int num , int new_data)
{
/* 1. allocate new node */
Node* new_node = new Node();
Node *temp = head;

/* 2. put in the data */

new_node->data = new_data;

/* 3. If the Linked List is empty, then make the new_node as head */

if (head == NULL)
{
head = new_node;
new_node->next = NULL;
return;
}

/* 4. Else traverse till the number of nodes where the new_node has to be inserted*/
while (num>0)
{
temp = temp->next;
num--;
}

/* 5. Make next of new_node as next of next of current location (temp) */

new_node->next = temp->next;

/* 6. move the next of current location (temp) as new_node */

temp->next = new_node;
}
Time complexity of addAfter is O(n) where n is the number of nodes after which the new_node will be inserted.
Since there is a loop from head to the number of nodes after which the new_node will be inserted, the function
does O(n) work.

c) Add a node at the end: (6 steps process)

 In this case, the new node will be added after the last node of the given Singly Linked List.
 For example if the given Singly Linked List is 10->15->20->25 and we add an item 5 at the end, then
the Linked List becomes 10->15->20->25->5.
 Since a Singly Linked List is typically represented by the head of it, we have to traverse the list till end
and then change the next of last node to new node.
 The function that adds an item after at the end of the list is addAtEnd(). The addAtEnd() must receive
a pointer to the head node and the data element to be inserted into the new node.(See the following
figure).
 Algorithm and C++ code to perform addAtEnd() operation.
/* Given a reference (pointer to pointer) to the head of a list and an int, appends a new node at the end */
void addAtEnd(int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();
Node *temp = head; /* used in step 5*/
/* 2. put in the data */
new_node->data = new_data;

/* 3. This new node is going to be the last node, so make next of it as NULL*/
new_node->next = NULL;

/* 4. If the Linked List is empty, then make the new node as head */
if (head == NULL)
{
head = new_node;
return;
}

/* 5. Else traverse till the last node */

while (temp->next != NULL)
temp = temp->next;

/* 6. Change the next of last node */

temp->next = new_node;
return;
}
 Time complexity of addAtEnd is O(n) where n is the number of nodes in linked list. Since there is a loop
from head to end, the function does O(n) work.
 This method can also be optimized to work in O(1) by keeping an extra pointer to tail of singly linked
list.

Searching for an element into the singly linked list:

 Searching for an element is nothing but, searching for a value into the Singly Linked List.
 The function search() will searches a given key ‘x’ in a given singly linked list.
 The function returns true if x is present in singly linked list and false otherwise.
 The search() function will take head node and the key value to be searched as parameters and returns a
Boolean value.
 For example, if the key to be searched is 5 and linked list is 10->15->20->25, then function should return
false. If key to be searched is 15, then the function should return true.

Algorithm and C++ code for search operation on singly linked list.
1) Initialize a node pointer, temp = head.
2) Do following while temp is not NULL
a) temp->data is equal to the key being searched return true.
b) temp = temp->next
3) Return false
/* Checks whether the value x is present in linked list */
bool search(int x)
 {
Node* temp = head; // Initialize current
while (temp != NULL)
{
if (temp->data == x)
return true;
temp = temp->next;
}
return false;
}
 Time complexity of search() is O(n) where n is the number of nodes in linked list.

Delete operation on Singly Linked List

Delete operation on Singly Linked List can be performed in 3-different ways:
a) Deleting a Node with first occurrence of key value from Singly Linked List.
b) Deleting a Node at a given position from Singly Linked List.
c) Deleting the complete Singly Linked List.

a) Deleting a Node with first occurrence of key value from Singly Linked List.
 The deleteNodeKey() function will delete the first occurrence of node with the given key value in
singly linked list.
 The deleteNodeKey() function receives a pointer to the head node and the key value of the node to be
deleted.

Algorithm and C++ code for deleting a node with first occurrence of key value from singly linked list.
To delete a node from linked list, we need to do following steps.
1. Find previous node of the node to be deleted.
2. Change the next of previous node.
3. Free memory for the node to be deleted.
/* Given a reference (pointer to pointer) to the head of a list and a key, deletes the first occurrence of key in
linked list */
void deleteNodeKey(int key)
{
// Store head node
Node* temp = new Node();
temp = head;
Node* prev_node;

// If head node itself holds the key to be deleted

if (temp != NULL && temp->data == key)
{
 head = temp->next; // Changed head
free(temp); // free old head
return;
}

// Search for the key to be deleted, keep track of the previous node as we need to change 'prev->next'
while (temp != NULL && temp->data != key)
{
prev_node = temp;
temp = temp->next;
}

// If key was not present in linked list

if (temp == NULL)
{
cout <<endl<< "Key value does not exists in the list...!";
return;
}

// Unlink the node from linked list

prev_node->next = temp->next;

free(temp); // Free memory

}
 Time complexity of deleteNodeKey() is O(n).

b) Deleting a Node at a given position from Singly Linked List.

 The deleteNodePos() function will delete a node at a given position from the linked list.
 The function deleteNodePos() will take head node reference of the linked list and the position value
from where the node will be delete.
C++ code to delete a Node at a given position from singly linked list.
/* Given a reference (pointer to pointer) to the head of a list and a position, deletes the node at the given
position */
//Given a position value, deletes the node from that position
void deleteNodePos(int position)
{
// If linked list is empty
if (head == NULL)
{
cout << "Singly Linked List is Empty…";
return;
}

// Store head node into temp1

Node* temp = head;
Node* prev_node;

// If head needs to be removed

if (position == 0)
{
head = temp->next; // Change head
 free(temp); // free old head
return;
}

// Find previous node of the node to be deleted

while(position>0)
{
prev_node=temp;
temp=temp->next;
position--;
}
// If position is more than number of nodes
if (temp==NULL)
{
cout << "Position value is exceeded the number of nodes…";
return;
}

// Node temp1->next is the node to be deleted

// Store pointer to the temp2 of node to be deleted
prev_node->next = temp->next;

// Unlink the node from linked list

free(temp); // Free memory
}
Time complexity of deleteNodePos() function is O(n).

c) Deleting the complete Singly Linked List.

 To delete all nodes from the given singly linked list, simply traverse through the list node by node
and delete all nodes till the end point reached.
 Once the last node is reached (that is node -> next ==NULL) simply make the head node as NULL,
to indicate the list as empty.
Algorithm For C++:
 Iterate through the linked list and delete all the nodes one by one.
 Main point here is not to access next of the temp pointer if current pointer is deleted.
Program:
/* Function to delete the entire linked list */
void deleteList()
{
/* deref head_ref to get the real head */
Node* temp = head;
while (temp != NULL)
{
head = temp->next;
free(temp);
temp = head;
}
}
Time Complexity O(n).
IMPLEMENTATION OF A STACK USING SINGLY LINKED LIST

 Implementing a stack using single linked list concept is very easy.

 All the single linked list operations perform based on Stack operations LIFO(last in first out) and with the
help of that knowledge of single linked list.
 A stack can be easily implemented through the linked list.
 In stack Implementation, a stack contains a top pointer, which is “head” of the stack where pushing and
popping items will be performed.
 First node have null in link field and second node link have first node address in link field and so on and
last node address in “top” pointer.
 The main advantage of using linked list over an arrays is that it is possible to implements a stack that can
shrink or grow as much as needed.
 In using array will put a restriction to the maximum capacity of the array which can lead to stack overflow.
Here each new node will be dynamically allocate, so overflow is not possible.

Stack Operations:

 push() : Insert the element into linked list at the top node of the Stack.
 pop() : Return top element from the Stack and move the top pointer to the second node of the Stack.
 peek(): Return the top element.
 isEmpty(): Returns true, if stack is empty (top==NULL), otherwise returns false.
 display(): Print all element of Stack.

Implementation of Stack using Linked List

Program: Stack Implementation using Linked List

// C++ program to Implement a stack using singly linked list
#include <iostream>
using namespace std;

// Declare linked list node

class Node {
public:
int data;
Node* next;
};
Node* top=NULL;
// Utility function to add an element data in the stack
void push(int new_data)
{
// create new node new_node and allocate memory
Node* new_node = new Node();

// check if stack (heap) is full. Then inserting an element would lead to stack overflow
if (!new_node) {
cout << "\nHeap Overflow...";
exit(1);
}

// initialize data into new_node data field

new_node->data = new_data;

// put top pointer reference into new_node next

new_node->next = top;

// make new_node as top of Stack

top = new_node;
}

// Utility function to check if the stack is empty or not

int isEmpty()
{
return top == NULL;
}

// Utility function to return top element in a stack

int peek()
{
// check for empty stack
if (isEmpty())
{
cout << "\nStack is Empty...";
exit(1);
}
return top->data;
}

// Utility function to pop top element from the stack

void pop()
{
Node* temp;

// check for stack underflow

if (isEmpty())
{
cout << "\nStack Underflow..." << endl;
exit(1);
}
// top assign into temp
 temp = top;

// assign second node to top

top = top->next;

// destroy connection between first and second

temp->next = NULL;

// release memory of top node

delete temp;
}

// Function to print all the elements of the stack

void display()
{
Node* temp;

// check for stack underflow

if (isEmpty())
{
cout << "\nStack is Empty…";
exit(1);
}
temp = top;
cout<<endl<<"\nElements in Stack are:";
while (temp != NULL) {

// print node data

cout << temp->data <<" ";

// assign temp link to temp

temp = temp->next;
}
}

// Driver Code
int main()
{
// push the elements at top of the stack
push(11);
push(22);
push(33);
push(44);
// display stack elements
display();
// print top elementof stack
cout << "\nTop element is:" << peek();
// pop top elements of stack
pop();
pop();

// display stack elements

display();
 pop();
pop();
// print top elementof stack
cout << "\nTop element is:" << peek();
display();
return 0;
}
Output:
Elements in Stack are:44 33 22 11
Top element is:44
Elements in Stack are:22 11
Stack is Empty...

IMPLEMENTATION OF A QUEUE USING SINGLY LINKED LIST

• Implementing a linked list using single linked list concept is very easy.
• All the single linked list operations perform based on Queue operations FIFO(First in first out) and with the
help of the knowledge of single linked list.
• In Singly Linked List Implementation of Queue, a Queue contains two pointer front and rear, (which are
similar to the “head” of the linked list).
• enQueue of elements will be performed at the rear end of the queue and dequeue of elements will be
performed at the front end of the queue.
• Always last node address will be in “rear” pointer. Last node will have null in next field and last but one
node next have last node address in next field and so on and first node address will be in “front” pointer
and first node next will have null in its next field.
Queue Operations:
 enQueue(): Insert the element into linked list at the rear end of the Queue.
 deQueue(): Return front element from the Queue and move the front pointer to the second node of the
Stack.
 isEmpty(): Returns true, if Queue is empty (front==NULL), otherwise returns false.
 display(): Print all element of Queue.
Implementation of Queue using Linked List
Program: Queue Implementation using Linked List
// A CPP program to demonstrate linked list based implementation of queue
#include <iostream>
using namespace std;

// A linked list (LL) node to store a queue entry

class Node {
public:
int data;
Node* next;
};

// The queue, front stores the front node of LL and rear stores the last node of LL
Node* front=NULL;
Node* rear=NULL;

//The function to check queue is empty or not

bool isEmpty()
{
return (front==NULL||rear==NULL);
}

// The function to enQueue new_data into the queue

void enQueue(int new_data)
{
// Create a new LL node
Node* new_node = new Node();
if(!new_node)
{
cout <<"Heap Overflow...";
exit(1);
}
new_node->data = new_data;
new_node->next = NULL;
cout <<"\nenQueue:"<<new_data;
// If queue is empty, then new_node is front and rear both
if (isEmpty())
front = rear = new_node;
else
{
// Add the new_node at the end of queue and change rear
rear->next = new_node;
rear = new_node;
}
}

// Function to remove front element from queue

int deQueue()
{
int temp_data;
// If queue is empty
if (isEmpty())
{
cout << "\nQueue Underflow...";
 exit(1);
}
// Store previous front and move front one node ahead
Node* temp_node = front;
temp_data = front->data;
front = front->next;
delete(temp_node);
// If front becomes NULL, then change rear also as NULL
if (isEmpty())
rear = NULL;
return temp_data;
}

// Function to print all the elements of the Queue

void display()
{
Node* temp;

// check if the queue is empty or not

if (isEmpty())
{
cout << "\nQueue is Empty...";
return;
}
temp = front;
cout<<endl<<"\nElements in Queue are:";
while (temp != NULL) {

// print node data

cout << temp->data <<" ";

// assign temp link to temp

temp = temp->next;
}
}

// Driver code
int main()
{
enQueue(10);
enQueue(20);
display();
cout << "\nDequeued item is " << deQueue();
cout << "\nDequeued item is " << deQueue();
display();
enQueue(30);
enQueue(40);
enQueue(50);
display();
cout << "\nDequeued item is " << deQueue();
cout << "\nDequeued item is " << deQueue();
cout << "\nDequeued item is " << deQueue();
display();
cout << "\nDequeued item is " << deQueue();
 return 0;
}
Output:
enQueue:10
enQueue:20

Elements in Queue are:10 20

Dequeued item is 10
Dequeued item is 20
Queue is Empty...
enQueue:30
enQueue:40
enQueue:50

Elements in Queue are:30 40 50

Dequeued item is 30
Dequeued item is 40
Dequeued item is 50
Queue is Empty...
Queue Underflow...

DOUBLY LINKED LIST

 A doubly linked list is a way to store a collection of elements. Like an array these can be character or
integers. Each element in a doubly linked list is stored in the form of a node.
 Like arrays, Doubly Linked List is a linear data structure. Unlike arrays, doubly linked list elements are not
stored at a contiguous location; the elements are linked using pointers.
 A node in a doubly linked list is a collection of three sub-elements or parts. A prev part that stores the
address/link of the previous node, next part that stores the address/link of the next node and a data part that
stores the element data.

 A Doubly Linked List is formed when many such nodes are linked together to form a chain. Each node
points to the next node present in the order and also the previous node. The first node is always used as a
reference to traverse the list and is called HEAD. The first node prev pointer will be made to NULL as
there is no previous node to the first node and the last node next pointer points to NULL as there is no next
node to the last node.

Advantages over singly linked list:

1. A DLL can be traversed in both forward and backward direction.

2. The delete operation in DLL is more efficient, as there is no need to maintain a pointer to the previous node to
be deleted. (In singly linked list, to delete a node, pointer to the previous node is needed. To get this previous
node, sometimes the list is traversed. In DLL, we can get the previous node using previous pointer.)
3. It is also possible to insert a new node before a given position.
Disadvantages over singly linked list:
1. Every node of DLL Require extra space for a previous pointer.
2. All operations require an extra pointer previous to be maintained. For example, in insertion, we need to
modify previous pointers together with next pointers.

Representation:
 A doubly linked list is represented by a pointer to the first node of the linked list. The first node is called
the head. If the doubly linked list is empty, then the value of the head is NULL.
 Each node in a list consists of at three parts:
1) Data
2) Pointer (Or Reference) to the next node
3) Pointer (Or Reference) to the prev node
In C++ Doubly Linked List can be represented as a class Node, which contains two references of Node
class type and a data element.
class Node {
public:
int data;
Node* next;
Node* prev;
};

Doubly Linked List program to create a simple doubly linked list with 3 nodes.
// A simple CPP program to introduce a doubly linked list
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node* prev;
};
int main()
{
// allocate 3 nodes in the heap
 Node* head = NULL;
Node* first = new Node();
Node* second = new Node();
Node* third = new Node();
head = first;
first->prev = NULL; // make the first node prev as null
first->data = 1; // assign data in first node
first->next = second; // Link first node next with the second node
second->prev = first; // Link second node prev with the first node
second->data = 2; // assign data to second node
second->next = third; // Link second node with the third node
third->prev = second; // Link third node prev with the second node
third->data = 3; // assign data to third node
third->next = NULL; // make the third node link as null
return 0;
}

Doubly Linked List Traversal

 Traversal is nothing but, it is a way of accessing all the elements from doubly linked list. In doubly Linked
list traversal, all data elements of the linked list are accessed and same can be printed for reference.
 In doubly linked list as we have pointers pointing to both next as well as previous nodes, we can perform
the traversal in both forward and reverse directions.
 Let us traverse the created list and print the data of each node. For traversal, let us write a general-purpose
function printList() that prints any given list.

C++ program for traversal of a doubly linked list

// A simple C++ program for traversal of a doubly linked list
#include <iostream>
using namespace std;

class Node {
public:
int data;
Node* next;
Node* prev;
};

// This function prints contents of doubly linked list starting from the given node
void printList(Node* temp)
{
Node* last;
if(temp == NULL)
{
cout <<"List is empty..";
return;
}
cout<<"\nTraversal in forward direction: \n";
while (temp != NULL)
{
cout<<" "<< temp ->data<<" ";
last = temp;
temp = temp ->next;
}

cout<<"\nTraversal in reverse direction: \n";

while (last != NULL)
{
cout<<" "<<last->data<<" ";
last = last->prev;
}
}

int main()
{
Node* head = NULL;

// allocate 3 nodes in the heap

Node* first = new Node();
Node* second = new Node();
Node* third = new Node();

head=first;
first->prev = NULL; // make first node prev as NULL
first->data = 7; // assign data in first node
first->next = second; // Link first node with second

second->prev = first; // assign second node prev as first node

second->data = 2; // assign data to second node
second->next = third; // assign second node next as third node

third->prev = second; // assign third node prev as second node

third->data = 3; // assign data to third node
third->next = NULL; // assign third node next as NULL

cout<<"created Singly Linked List:";

printList(head);

return 0;
}

OUTPUT:
created Singly Linked List:
 Traversal in forward direction:
7 2 3
Traversal in reverse direction:
3 2 7
Traversing a doubly linked list operations involves visiting all nodes from head node till the last node. If there
are n nodes available in the doubly linked list then a loop can be used to visit all the elements until the last node
pointer becomes NULL. Taking a loop involves visiting n elements to fetch their values, hence Time
Complexity will be O(n).

Inserting a Node into the doubly linked list

A node into a doubly linked list can be added in four ways
a) At the front of the list (addAtFirst())
b) After a given node. (addAfter())
c) Before a given node. (addBefore())
d) At the end of the doubly linked list. (addAtEnd())

a) At the front of the doubly linked list (addAtFirst())

 The new node is added before the head of the given Linked List. And newly added node becomes the new
head of DLL.
 For example if the given Linked List is 10->15->20->25 and item 5 is added at the front, then the Linked
List becomes 5->10->15->20->25.
 Let us call the function that adds at the front of the list is addAtFront().
 The addAtFront () uses the head pointer, because addAtFront must change the head pointer to point to the
new node.

C++ Program code to add a node at the beginning of the doubly linked list.
/* Given a reference (pointer to pointer) to the head of a list
and an int, inserts a new node on the front of the list. */
void addAtFirst(int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();

/* 2. put in the data */

new_node->data = new_data;

/* 3. Make next of new node as head and previous as NULL */

new_node->next = head;
new_node->prev = NULL;
 /* 4. change prev of head node to new node */
if (head != NULL)
head->prev = new_node;

/* 5. move the head to point to the new node */

head = new_node;
}
Adding the node at the beginning of the linked list does not involve using loops in the functions.
Hence time complexity of this function is O(1).

b) After a given node. (addAfter())

 The function addAfter() uses the head node, and the position of the node after which the new node has to
be added, and the int data to be added into the node.

C++ Program code to add a node after the given position into the doubly linked list.
/* Given a node as prev_node, insert a new node after the given node */
void addAfter(int pos, int new_data)
{
/*1. Take the temp node to the head*/
Node* temp=head;

/* 2. allocate new_node */
Node* new_node = new Node();

/* 3. put in the data */

new_node->data = new_data;

/*check if DLL is empty, if so add the new_node as first node*/

if(head==NULL)
{
new_node->next=NULL;
new_node->prev=NULL;
head=new_node;
return;
}

// traverse till the position value

while(pos>0)
{
temp=temp->next;
pos--;
}
// if position value is morethan the no of DLL nodes
if(temp==NULL)
{
cout << "Position value exceeded the number of nodes";
return;
 }
/* 4. Make next of new node as next of prev_node */
new_node->next = temp->next;

/* 5. Make the next of prev_node as new_node */

temp->next = new_node;

/* 6. Make prev_node as previous of new_node */

new_node->prev = temp;

/* 7. Change previous of new_node's next node */

if (new_node->next != NULL)
new_node->next->prev = new_node;
}
Traversing till the node, after which the new node is inserted involves a loop consideration into the code. Hence
the time complexity will be O(n).

c) Before a given node. (addBefore())

 The function addBefore() uses the head node, and the position of the node before which the new node
has to be added, and the int data to be added into the node.

C++ Program code to add a node before the given position into the doubly linked list.
void addBefore(int pos, int new_data)
{
/*1. Take the temp node to the head*/
Node* temp=head;
/* 2. allocate new node */
Node* new_node = new Node();

/* 3. put in the data */

new_node->data = new_data;

/*check if DLL is empty, if so add the new_node as first node*/

if(head==NULL)
{
new_node->next=NULL;
new_node->prev=NULL;
head=new_node;
return;
}
// traverse till the position value
while(pos>0 && temp!=NULL)
{
temp=temp->next;
pos--;
}
// if position value is morethan the no of DLL nodes
if(temp==NULL)
{
cout << "Position value exceeded the number of nodes";
return;
}
 /* 4. Make prev of new node as prev of next_node */
new_node->prev = temp->prev;

/* 5. Make the prev of next_node as new_node */

temp->prev = new_node;

/* 6. Make next_node as next of new_node */

new_node->next = temp;

/* 7. Change next of new_node's previous node */

if (new_node->prev != NULL)
new_node->prev->next = new_node;
/* 8. If the prev of new_node is NULL, it will be the new head node */
else
head = new_node;
}
Traversing till the node, before which the new node is inserted involves a loop consideration into the code.
Hence the time complexity will be O(n).

d) At the end of the doubly linked list. (addAtEnd())

 The new node is added after the last node of the given Linked List.
 For example if the given DLL is 10->15->20->25 and we add an item 5 at the end, then the DLL becomes
10<->15<->20<->25<->5.
 Since a Linked List is typically represented by the head of it, we have to traverse the list till end and then
change the next of last node to new node, new node prev to last node and new node next as NULL.
 A typical function for adding a node at the end of the DLL will use the head pointer, and int data to be
added into the new node.

C++ Program code to add a node at the end of the doubly linked list.
/* Given a reference (pointer to pointer) to the head
of a DLL and an int, appends a new node at the end */
void addAtEnd(int new_data)
{
/* 1. allocate node */
Node* new_node = new Node();

Node* temp = head; /* used in step 5*/

/* 2. put in the data */

new_node->data = new_data;

/* 3. This new node is going to be the last node, so

make next of it as NULL*/
new_node->next = NULL;
 /* 4. If the Linked List is empty, then make the new
node as head */
if (head == NULL)
{
new_node->prev = NULL;
head = new_node;
return;
}

/* 5. Else traverse till the last node */

while (temp->next != NULL)
temp = temp->next;

/* 6. Change the next of last node */

temp->next = new_node;

/* 7. Make last node as previous of new node */

new_node->prev = temp;
}
Traversing till the last node, after which the new node is inserted involves a loop
consideration into the code. Hence the time complexity will be O(n).

Searching for an element into the doubly linked list:

 Searching for an element is nothing but, searching for a value into the doubly Linked List.
 The function search() will searches a given key ‘x’ in a given doubly linked list.
 The function returns true if x is present in doubly linked list and false otherwise.
 The search() function will take head node and the key value to be searched as parameters and returns a
Boolean value.
 For example, if the key to be searched is 5 and linked list is 1->9->7->8->6->4->NULL, then function
should return false. If key to be searched is 8, then the function should return true.

Algorithm and C++ code for search operation on doubly linked list.
1) Initialize a node pointer, temp = head.
2) Do following while temp is not NULL
a) temp->data is equal to the key being searched return true.
b) temp = temp->next
3) Return false
//The function will search for a given key value in the list
//If value present the function returns true else false
bool search(int x)
{
if(head==NULL
{
cout<<”\n DLL is Empty…”;
return 0;
}
Node* temp = head; // Initialize current
while (temp != NULL)
{
if (temp->data == x)
 return true;
temp = temp->next;
}
return false;
}
 Time complexity of search() is O(n) where n is the number of nodes in linked list.

Delete a node in a Doubly Linked List

 A node from the doubly linked list can be deleted in the following ways:
a) Deleting the Head Node from DLL
b) Deleting the Last Node from DLL
c) Deleting a Node with first occurrence of key value from doubly Linked List.
d) Deleting the complete doubly Linked List.

a) Deleting the Head Node from DLL

 The deleteFirst() function will delete the first node (Head Node) from doubly linked list.
 The deleteFirst() function receives a pointer to the head node deletes the first node.
Algorithm and C++ code for deleteFirst() fuction
void deleteFirst()
{
if(head==NULL)
{
cout<<"\nDLL is Empty...";
return;
}
/*1. Take temp to head*/
Node* temp = head;
/*2. Make head to point the second node*/
head = temp->next;
/*3. Make second node prev as NULL, as it will be the first node*/
head->prev = NULL;
/*4. Relese memory of first node*/
free(temp);
}
Time complexity – O(1)

b) Deleting the Last Node from DLL

 The deleteEnd() function will delete the last node (End Node) from doubly linked list.
 The deleteEnd() function receives a pointer to the head node deletes the last node.
Algorithm and C++ code for deleteEnd() fuction
void deleteEnd()
{
/*1. Take temp to head*/
Node* temp = head;
/*2. Run a loop until temp reaches the last node*/
while (temp->next != NULL)
temp = temp->next;
/*3. Make last but one node's next as NULL, as it will be the last node*/
temp->prev->next = NULL;
/*4. Release memory of the last node*/
free(temp);
}
Time complexity – O(n)

c) Deleting a Node with first occurrence of key value from doubly Linked List.
 Given an element value (key), the deleteNodeKey() function deletes a node with the first
occurrence of key.
 The deleteNodeKey() function uses the head pointer and key value of the node, and deletes a node
with the first occurrence of key.

/* Given a reference (pointer to pointer) to the head of a list and a key, deletes the first occurrence of key in
linked list */
void deleteNodeKey(int key)
{
// Store head node into temp
Node* temp = head;

// If head node itself holds the key to be deleted

if (temp != NULL && temp->data == key)
{
deleteFirst(); // free old head
return;
}

// Search for the key to be deleted, keep track of the previous node as we need to change 'prev->next'
while (temp != NULL && temp->data != key)
{
temp = temp->next;
}
// If key was not present in linked list
if (temp == NULL)
{
cout <<endl<< "Key value does not exists in the list...!";
return;
}
 if(temp->next!=NULL)
{
// Unlink the node from linked list
temp->next->prev = temp->prev;
temp->prev->next = temp->next;
free(temp); // Free memory
}
else
deleteEnd();

}
There is a need to traverse the list till we find the key in the list, or in the worst case we end up searching the
complete list without finding the key in the list. Hence Time Complexity O(n).

d) Deleting the complete doubly Linked List.

 To delete all nodes from the given doubly linked list, simply traverse through the list node by node
and delete all nodes till the end point reached.
 Once the last node is reached (that is node -> next ==NULL) simply make the head node as NULL,
to indicate the list as empty.
Algorithm For C++:
 Iterate through the linked list and delete all the nodes one by one.
 Main point here is not to access next of the temp pointer if current pointer is deleted.

Program:
void deleteList()
{
/* deref head_ref to get the real head */
Node* temp = head;
while (temp != NULL)
{
head = temp->next;
free(temp);
temp = head;
}
}
Time Complexity O(n).

Main Program to check the working of all above discussed functions.

int main()
{
// Insert 6. So DLL becomes 6->NULL
addAtEnd(6);

// Insert 7 at the beginning. So DLL becomes 7->6->NULL

addAtFirst(7);

// Insert 1 at the beginning. So DLL becomes 1->7->6->NULL

addAtFirst(1);
 // Insert 4 at the end. So DLL becomes 1->7->6->4->NULL
addAtEnd(4);

// Insert 8, after pos=1. so DLL becomes 1->7->8->6->4->NULL

addAfter(1, 8);

// Insert 9, before pos=1. so DLL becomes 1->9->7->8->6->4->NULL

addBefore(1, 9);

cout << "\nCreated DLL is: ";

printList(head);

//Searching for element 8 in the DLL

search(8)?cout<<"\nElement Found....":cout<<"\nElement not Found....";

//Delete first, So DLL becomes 9->7->8->6->4->NULL

deleteFirst();

cout << "\nCreated DLL is: ";

printList(head);

//Delete end, So DLL becomes 9->7->8->6->NULL

deleteEnd();

cout << "\nCreated DLL is: ";

printList(head);

//Delete Node with key value 8, So DLL becomes 9->7->6->NULL

deleteNodeKey(8);

cout << "\nCreated DLL is: ";

printList(head);

//Deleted the complete list, So head becomes NULL

deleteList();

cout << "\nCreated DLL is: ";

printList(head);
return 0;
}
Output:
Created DLL is:
Traversal in forward direction:
1 9 7 8 6 4
Traversal in reverse direction:
4 6 8 7 9 1
Element Found....
Created DLL is:
Traversal in forward direction:
9 7 8 6 4
Traversal in reverse direction:
4 6 8 7 9
Created DLL is:
 Traversal in forward direction:
9 7 8 6
Traversal in reverse direction:
6 8 7 9
Created DLL is:
Traversal in forward direction:
9 7 6
Traversal in reverse direction:
6 7 9
Created DLL is: DLL is Empty...
CIRCULAR LINKED LIST:
 Circular linked list is a linked list where all nodes are connected to each other so that a circle can be
formed. That is instead to make the last node as NULL, it will point the first node in the list.
 A circular linked list can be a singly circular linked list or doubly circular linked list.

Advantages of Circular Linked Lists:

1) Any node can be a starting point. We can traverse the whole list by starting from any point. We just need to
stop when the first visited node is visited again.
2) Useful for implementation of queue. Unlike singly linked list implementation, no need to maintain two
pointers for front and rear. A single pointer to the last inserted node is enough, and front can always be
obtained as next of last.
3) Circular lists are useful in applications to repeatedly go around the list. For example, when multiple
applications are running on a PC, it is common for the operating system to put the running applications on
a list and then to cycle through them, giving each of them a slice of time to execute, and then making them
wait while the CPU is given to another application. It is convenient for the operating system to use a
circular list so that when it reaches the end of the list it can cycle around to the front of the list.
4) Circular Doubly Linked Lists are used for implementation of advanced data structures like Fibonacci Heap.

CIRCULAR SINGLY LINKED LIST:

Problem in Singly Linked List:
 In a singly linked list, for accessing any node of linked list, always traversal will be performed from the
first node. If we are at any node in the middle of the list, then it is not possible to access nodes that precede
the given node.
 This problem can be solved by slightly altering the structure of singly linked list. That is with the help of
circular singly linked list.
 In a singly linked list, the next pointer of the last node will be made as NULL to indicate the end of the list.
If we make this next pointer as to point the first node, this will form a circular singly liken list.
 The structure thus formed is circular singly linked list look like this:
Traversal on Circular Singly Linked List:
 Traversal is nothing but, it is a way of accessing all the elements from circular singly linked list. In Circular
Singly Linked list traversal, all data elements of the linked list are accessed and same can be printed on
output.
 Let us traverse the created list and print the data of each node. For traversal, a general-purpose function
printList() is defined where a temp pointer visits all nodes in the list and prints their values.
 The function printList() uses the head reference to access the circular linked list elements.
Algorithm and C++ code to perform traversal on a Circular Linked List
/* Traversal Function to print node values in a given Circular linked list */
void printList(Node* head)
{
//1. Check whether the list is empty or not, if empty return
if(head == NULL)
{
cout << "CSLL is empty...";
return;
}
//2. Assign a temp pointer to head node
Node* temp = head;
//3. Visit all nodes until temp is not becoming head
do
{
cout << temp->data << " ";
temp = temp->next;
}while (temp != head);
}
Time Complexity of the above traversal function is O(n), as it requires visiting all the nodes.

Searching for a given key value in a Circular Singly List:

 Searching for an element is nothing but, searching for a value into the CSLL.
 The function search() will searches a given key in a given CSLL.
 The function returns true if key is present in CSLL and false otherwise.
 The search() function will uses head node and the key value to be searched as parameters and returns a
Boolean value.
 For example, if the key to be searched is 5 and linked list is 10->15->20->25, then function should return
false. If key to be searched is 15, then the function should return true.
 Algorithm and C++ code to perform search() operation on a Circular Linked List
/*Function will search for a key value into the CSLL*/
bool search(int key)
{
//1. Check whether CSLL is empty or not, if empty return
if(head==NULL)
{
cout<<"CSLL is Empty...";
return false;
}

//2. Assign a temp pointer to head node

Node* temp=head;

//3. Visit nodes one by one and search for the occurrence of key value
do
{
//If key value found return true,
if(temp->data==key)
return true;
temp=temp->next;
}while(temp!=head);
return false; //Key value not found, return false
}
Searching for an element requires visiting the nodes until the required key value found, in worst case the
operation will visits all the nodes, before confirming that the value is not there in the list. Hence the time
complexity here is O(n).

Inserting a Node into the Circular Singly Linked List

A node into a Circular Singly Linked List can be added in three ways
a) Add a node at the front of the CSLL. (addAtFirst())
b) Add a node after a given node position. (addAfter())
c) Add a node at the end of the CSLL. (addAtEnd())

a) Add a node at the front of the CSLL (addAtFirst())

 In this case, the new node is added before the head node of the given CSLL. And newly added node
becomes the new head of the CSLL.
 For example if the given CSLL is 10->15->20->25 and after adding an item 5 at the front, the CSLL
becomes 5->10->15->20->25.
 The function that adds an item at the front of the list is addAtFirst(). The addAtFirst() uses a pointer to
the head, because addAtFirst() must change the head pointer to point to the new node (See the
following figure).

Algorithm and C++ code for performing addAtFirst()

/* Function to insert a node at the beginning of a Circular linked list */
void addAtFirst(int new_data)
{
//1. Create the new_node and assign the data to be added
Node* new_node = new Node();
new_node->data = new_data;
 /*2. Check if the list is empty or not that is head==NULL
if empty add new_node as the first node and return*/
if(head==NULL)
{
head = new_node;
new_node->next = head;
return;
}

//3. Take a temp Pointer and make it point the head node
Node* temp=head;

//4. Traverse the temp pointer to the last node

do
{
temp=temp->next;
}while(temp->next!=head);

//5. Assign new_node next pointer to head node

new_node->next = head;

//6. Assign last node head pointer to new_node

temp->next = new_node;

//7. Make head to point the new_node

head = new_node;
}
Time Complexity O(n)

b) Add a node after a given node position in CSLL

 In this case, the new node is added after a specified node location within the given CSLL.
 For example if the given CSLL is 10->15->20->25 and after adding an item 5 after node pos=1, the
CSLL becomes 10->15->5->20->25.
 The function that adds an item after a specified node in the list is addAfter(). The addAfter() uses the
head node, the number of nodes (pos) after which the new node needs to be inserted and the data
element to be inserted into the new node.(See the following figure).

Algorithm and C++ code for performing addAfter()

/* Function to insert a node after a given position in a Circular linked list */
void addAfter(int new_data, int pos)
{
//1. Check if the CSLL is empty or not
//if empty add the new_node as first node
if(head==NULL)
{
addAtFirst(new_data);
return;
}

//2. Create the new_node and assign the data to be added

Node* new_node = new Node();
 new_node->data = new_data;

//3. Take a temp Pointer and make it point the head node
Node* temp=head;

//4. Traverse the temp pointer to the desired node position

do
{
temp=temp->next;
pos--;
}while(pos>0 && temp!=head);

//if in traversal the temp is reaching head then pos is greater than the no. of nodes
if(temp==head)
{
cout<<"Position value exceeded the no. of Nodes...";
return;
}

//5. Assign new_node next pointer to temp node next pointer

new_node->next = temp->next;

//6. Make the temp node next pointer to point the new_node
temp->next = new_node;
}
Time Complexity O(n)

c) Add a node at the end of CSLL

 In this case, the new node will be added after the last node of the given CSLL.
 For example if the given CSLL is 10->15->20->25 and we add an item 5 at the end, then the CDLL
becomes10->15->20->25->5.
 Since a CSLL is typically represented by the head of it, we have to traverse the list till end and then
change the next of last node to new node, and new node will point head node.
 The function that adds an item after at the end of the list is addAtEnd(). The addAtEnd() uses a pointer
to the head node and the data element to be inserted into the new node.(See the following figure).
Algorithm and C++ code for performing addAtEnd()
/* Function to insert a node at the end of a Circular linked list */
void addAtEnd(int new_data)
{ //1. Check if the CSLL is empty or not
//if empty add the new_node as first node
if(head==NULL)
{
addAtFirst(new_data);
return;
}

//2. Create the new_node and assign the data to be added

Node* new_node = new Node();
new_node->data = new_data;

//3. Take a temp Pointer and make it point the head node
Node* temp=head;
 //4. Traverse the temp pointer to the last node
do
{
temp=temp->next;
}while(temp->next!=head);

//5. Make the new_node to point to the head

new_node->next = head;

//6.make last node to point to the new_node.

temp->next = new_node;
}
Time Complexity O(n)

Delete operation on Circular Singly Linked List

Delete operation on CSLL can be performed in 4-different ways:
a) Deleting the first node from the front of CSLL.
b) Deleting the last node from the end of CSLL.
c) Deleting a node with matching key value from the CSLL.
d) Deleting the complete CSLL.

a) Deleting the first node from the CSLL (deleteFirst()).

 The deleteFirst() function will delete the first node from CSLL.
 The deleteFirst () function uses a pointer to the head node and deletes the first node from the list.
Algorithm and C++ code for performing deleteFirst()
/* Function to delete a node from the begining of the Circular linked list */
void deleteFirst()
{
//1. Check, if list is empty or not, if empty return
if(head == NULL)
{
cout << "CSLL is Empty...";
return;
}

//2. Assign a temp pointer to head

Node* temp = head;

//3. Traverse the temp pointer to the last node

do
{
temp=temp->next;
}while(temp->next!=head);

//4. Move head one node ahead

head=head->next;

//5. Delete the node using last node next pointer temp->next
delete temp->next;
 //6. Make last node to point the first node
temp->next = head;
}
Time complexity O(n)

b) Deleting the last node from the CSLL (deleteEnd()).

 The deleteEnd() function will delete the first node from CSLL.
 The deleteEnd() function uses a pointer to the head node, a pointer to the last but one node and deletes
the last node from the list.
Algorithm and C++ code for performing deleteEnd()
/* Function to delete a node from the end of the Circular linked list */
void deleteEnd()
{
//1. Check, if list is empty or not, if empty return
if(head == NULL)
{
cout << "CSLL is Empty...";
return;
}

//2. Assign a temp pointer to head

Node* temp = head;

//3. Take another temp pointer last

Node* last;

//4. Traverse in such a way that last should point last but one node
// and temp should point last node
do
{
last = temp;
temp=temp->next;
}while(temp->next!=head);

//5. Make last but one node to point head node

last->next = head;

//6. Delete the last node

delete temp;
}
Time Complexity O(n).

c) Deleting a node with matching key value from the CSLL. (deleteNodeKey())
 The deleteNodeKey() function will delete a node with matching key value from the linked list.
  The function deleteNodePos() will use head node reference of the linked list and the key value to delete
a node from the CSLL.
Algorithm and C++ code for performing deleteNodeKey()
/* Function to delete a node with matching key from the Circular linked list */
void deleteNodeKey(int key)
{
//1. Check, if list is empty or not, if empty return
if(head == NULL)
{
cout << "CSLL is Empty...";
return;
}

//2. If head node (first node) itself holding the key, delete the first node and return
if(head->data==key)
{
deleteFirst();
return;
}

/*3. Assign a temp pointer to head

take two pointers one to point the position node
another to point the previous of position node*/
Node* temp = head;
Node* temp1;

/*4. Traverse two pointers, temp to position node

temp1 to previous node of position node*/
do
{
temp1 = temp;
temp=temp->next;
}while(temp->data!=key);

//5. Make previous node to point the next node of position node
temp1->next = temp->next;

//6. Delete the position node

delete temp;
}
Time Complexity O(n).

d) Deleting the complete CSLL. (deleteList())

 To delete all nodes from the given CSLL, simply traverse through the list node by node and delete
all nodes till the end point reached. (That is head==last)
 Once the last node is reached, simply make the head node as NULL, to indicate the list as empty
and delete the last node as well.
Algorithm and C++ code for performing deleteList()
/* Function to delete a node with matching key from the Circular linked list */
void deleteList()
{
//1. Check, if list is empty or not, if empty return
if(head == NULL)
{
cout << "CSLL is Empty...";
return;
}

//2. Assign a last pointer to head

// Traverse the last pointer to the last node in the list
Node* last = head;
do
{
last=last->next;
}while(last->next!=head);

//3. Assign the temp pointer to head and move the head ahead
//4. Make last node to point the head and delete the temp.
//5. repeat step 3, 4 until the head reaches the last node
Node* temp;
do
{
temp=head;
head=head->next;
last->next=head;
delete temp;
}while(head!=last);
//6. Make head as Null and delete the last
head = NULL;
delete last;
}
Time Complexity O(n).

Main Function (Driver Program)

int main(void)
{
cout << "\nElements in CSLL:";
printList(head);
addAtFirst(10); //CSLL 10
addAtFirst(20); //CSLL 20->10
addAtEnd(30); //CSLL 20->10->30
addAfter(40,1); //CSLL 20->10->40->30
addAfter(60,1); //CSLL 20->10->60->40->30
addAtFirst(80); //CSLL 80->20->10->60->40->30
cout << "\nElements in CSLL:";
 printList(head);
deleteFirst(); //CSLL 20->10->60->40->30
cout << "\nElements in CSLL:";
printList(head);
deleteEnd(); //CSLL 20->10->60->40
cout << "\nElements in CSLL:";
printList(head);
search(220)?cout<<"\nElement Found....":cout<<"\nElement not Found....";
deleteList(); //CSLL NULL
cout << "\nElements in CSLL:";
printList(head);
return 0;
}
Output:
Elements in CSLL: CSLL is empty...
Elements in CSLL: 80 20 10 60 40 30
Elements in CSLL: 20 10 60 40 30
Elements in CSLL: 20 10 60 40
Element not Found....
Elements in CSLL: CSLL is empty...

CIRCULAR DOUBLY LINKED LIST (CDLL)

 Circular Doubly Linked List has properties of both doubly linked list and circular linked list in which two
consecutive elements are linked or connected by previous and next pointer and the last node points to first
node by next pointer and also the first node points to last node by previous pointer.

Following is representation of a Circular doubly linked list node

C++ code for Node representation for CDLL
// Class of the node
class Node
{
Public:
 int data;
Node* next; // Pointer to next node
Node* prev; // Pointer to previous node
};

Advantages and disadvantages of circular doubly linked list (CDLL)

 Following are advantages and disadvantages of circular doubly linked list:
Advantages:
 List can be traversed from both the directions i.e. from head to tail, or from tail to head.
 Jumping from head to tail, or from tail to head is done in constant time O(1).
 Circular Doubly Linked Lists are used for implementation of advanced data structures like
Fibonacci Heap.
Disadvantages:
 It takes slightly extra memory in each node to accommodate previous pointer.
 Lots of pointers involved while implementing or doing operations on a list. So, pointers should be
handled carefully otherwise data of the list may get lost.

Applications of Circular doubly linked list (CDLL)

 Managing songs playlist in media player applications.
 Managing shopping cart in online shopping.

Representation of Circular Doubly Linked List (CDLL)

 Following is representation of a Circular doubly linked list node.
 Circular Doubly Linked List (CDLL) has properties of both doubly linked list and circular linked
list in which two consecutive elements are linked or connected by previous and next pointer and the
last node points to first node by next pointer and also the first node points to last node by previous
pointer.

C++ code for Node representation for CDLL

// Class of the node
class Node
{
Public:
int data;
Node* next; // Pointer to next node
Node* prev; // Pointer to previous node
};

Traversal on Circular Doubly Linked List:

  Traversal is nothing but, it is a way of accessing all the elements from circular doubly linked list.
 In Circular Doubly Linked list traversal, all data elements of the linked list are accessed and same can be
printed on output.
 Traversal in CDLL is possible in both forward and reverse directions. In forward traversal the element are
visited from head-node to tail-node. And in reverse traversal the elements are visited from tail node to
head node.
 Let us traverse the created list and print the data of each node. For traversal, a general-purpose function
printList() is defined where a temp pointer visits all nodes in the list in forward and reverse directions, and
prints their values.
 The function printList() uses the head reference to access the circular linked list elements.
Algorithm and C++ code for Traversal on CDLL
/*fundtion to perform traversal on CDLL*/
void printList(Node* head)
{
/*1. Check if the CDLL is empty or not, if empty return*/
if(head==NULL)
{
cout<<"CDLL is Empty...";
return;
}
// 2. Make temp pointer to head
Node* temp = head;
//forward traversal
cout<<"\nTraversal in forward direction:";
do
{
cout<<" "<<temp->data;
temp = temp->next;
}while (temp!= head);

//reverse traversal
cout<<"\nTraversal in reverse direction:";
do
{
temp = temp->prev;
cout<<" "<<temp->data;
}while (temp!=head);
}
Traversal involves visiting all the nodes in the CDLL. Hence, Time Complexity O(n).

Searching for a given key value in a Circular Doubly Linked List:

 Searching for an element is nothing but, searching for a value into the CDLL.
 The function search() will searches a given key in a given CDLL.
 The function returns true if key is present in CDLL and false otherwise.
 The search() function will uses head node and the key value to be searched as parameters and returns a
Boolean value.
  For example, if the key to be searched is 5 and linked list is 10->15->20->25, then function should return
false. If key to be searched is 15, then the function should return true.
Algorithm and C++ code for search operation on CDLL
/*Function will search for a key value into the CDLL*/
bool search(int key)
{
//1. Check whether CDLL is empty or not, if empty return
if(head==NULL)
{
cout<<"CDLL is Empty...";
return false;
}

//2. Assign a temp pointer to head node

Node* temp=head;

//3. Visit nodes one by one and search for the occurrence of key value
do
{
//If key value found return true,
if(temp->data==key)
return true;
temp=temp->next;
}while(temp!=head);
return false; //Key value not found, return false
}
Searching for an element requires visiting the nodes until the required key value found, in worst
case the operation will visits all the nodes, before it finds the value in the list. Hence the time
complexity here is O(n).

Inserting a Node into the Circular Doubly Linked List

A node into a Circular Doubly Linked List (CDLL) can be added in three ways:
a) Add a node at the front of the CDLL. (addAtFirst())
b) Add a node after a given node position in CDLL. (addAfter())
c) Add a node at the end of the CDLL. (addAtEnd())

a) Add a node at the front of the CDLL (addAtFirst())

 In this case, the new node is added before the head node of the given CDLL. And newly added node
becomes the new head of the CDLL.
 For example if the given CDLL is 5 1015 and after adding an item 20 at the front, the CDLL
becomes 205 1015.
 The function that adds an item at the front of the list is addAtFirst(). The addAtFirst() uses a pointer to
the head, because addAtFirst() must change the head pointer to point to the new node (See the
following figure).
 Algorithm and C++ code for addAtFirst() operation in CDLL
// Function to insert Node at the beginning of the CDLL
void addAtFirst(int new_data)
{
// 1. Pointer points to last Node
Node* last = head->prev;
// 2. Create a new_node
Node* new_node = new Node();
new_node->data = new_data; // Inserting the data

// 3. setting up previous and next of new_node

new_node->next = head;
new_node->prev = last;

// 4. Update next and previous pointers of head and last.

last->next = head->prev = new_node;

// 5. Update head pointer as new_node

head = new_node;
}
In circular doubly linked list adding a new node at the beginning doesn’t traversal. Hence time
complexity is O(1).

b) Adding a node after a given node position in CDLL. (addAfter())

 In this case, the new node is added after a specified node location within the given CDLL.
 For example if the given CDLL is 5 1015 and after adding an item 20 after node pos=1, the
CDLL becomes 5 102015.
 The function that adds an item after a specified node in the list is addAfter(). The addAfter() uses
the head node, the number of nodes (pos) after which the new node needs to be inserted and the
data element to be inserted into the new node.(See the following figure).
Algorithm and C++ code for addAfter() operation in CDLL.
// Function to add node after the given position value
void addAfter(int new_data, int pos)
{
//1. Check if the CDLL is empty or not
//if empty add the new_node as first node
if(head==NULL)
{
addAtFirst(new_data);
return;
}

//2. Create a new_node

Node* new_node = new Node();
new_node->data = new_data; // Inserting the data

//3. Find the node at given position value

Node* temp = head;
do
{
temp = temp->next;
pos--;
}while (pos>0 && temp!= head);

//4. If pos exceeds no. of nodes return with error message.

if(temp==head)
{
cout<<"Position value exceeded the no. of nodes in the list...";
return;
}

//5. Insert new_node after the node at position (pos).

new_node->next = temp->next;
new_node->prev = temp;
temp->next->prev = new_node;
temp->next = new_node;
}
Time Complexity O(n).
c) Adding a node at the end of the CDLL. (addAtEnd())
 In this case, the new node will be added after the last node of the given CDLL.
 For example: if the given CDLL is 5 1015 and we add an item 20 at the end, then the CDLL
becomes 5 101520.
 Since a CDLL is typically have both prev and next pointers in for every node in the list. No need to
perform any traversal and, hence we perform a constant set of operations, time complexity will be
O(1).
 The function that adds an item after at the end of the list is addAtEnd(). The addAtEnd() uses a
pointer to the head node and the data element to be inserted into the new node.(See the following
figure).

Algorithm and C++ code for addAtEnd() operation in CDLL.

// Function to insert at the end of CDLL
void addAtEnd(int new_data)
{
//1. If the list is empty, create a single node in circular doubly list
if (head == NULL)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = new_node->prev = new_node;
head = new_node;
return;
}

//2. If list is not empty

/* Find last node */
Node* last = head->prev;

//3. Create Node dynamically and assign the data

Node* new_node = new Node();
new_node->data = new_data;

//4. head is going to be next of new_node

new_node->next = head;

//5. Make new_node previous of head

head->prev = new_node;

//6. Make last as preivous of new_node

 new_node->prev = last;

//7. Make new_node as next of old last

last->next = new_node;
}
Time complexity O(1).

Delete operation on Circular doubly Linked List (CDLL)

Delete operation on CDLL can be performed in 4-different ways:
e) Deleting the first node from the front of CDLL. (deleteFirst())
f) Deleting the last node from the end of CDLL. (deleteEnd())
g) Deleting a node with matching key value from the CDLL. (deleteNodeKey())
h) Deleting the complete CDLL. (deleteList())

a) Deleting the first node from the front of CDLL. (deleteFirst())

 The deleteFirst() function will delete the first node from CDLL.
 The deleteFirst () function uses a pointer to the head node and deletes the first node from the list.

Algorithm and C++ code for deleteFirst() operation in CDLL.

/* Function to delete a node from the begining of the Circular linked list */
void deleteFirst()
{
//1. Check, if list is empty or not, if empty return
if(head == NULL)
{
cout << "\nCDLL is Empty...";
return;
}
 //2. Assign a temp pointer to head
Node* temp = head;

//3. make temp pointer to the last node

temp=head->prev;

//4. Move head one node ahead

head=head->next;

//5. Delete the first node using last node next pointer temp->next
delete temp->next;

//6. Make last node to point the first node

temp->next = head;
//7. Make the first node to point the last node
head->prev = temp;
}
Time complexity O(1).

b) Deleting the last node from the CDLL (deleteEnd()).

 The deleteEnd() function will delete the first node from CDLL.
 The deleteEnd() function uses a pointer to the head node, a pointer to the last but one node and deletes
the last node from the list.

Algorithm and C++ code for deleteEnd() operation in CDLL.

/* Function to delete a node from the end of the Circular linked list */
void deleteEnd()
{
//1. Check, if list is empty or not, if empty return
if(head == NULL)
 {
cout << "\nCDLL is Empty...";
return;
}

//2. Assign a temp pointer to head

Node* temp = head;

//3. Take another temp pointer last

Node* last;

//4. Make temp as last node and last as last but one node
temp = head->prev;
last = temp->prev;

//5. Make last but one node to point head node (first node).
last->next = head;

//6. Make the head node to point last but one node
head->prev = last;

//5. Delete the last node

delete temp;
}
Time complexity O(1).

d) Deleting a node with matching key value from the CDLL. (deleteNodeKey())
 The deleteNodeKey() function will delete a node with matching key value from the linked list.
 The function deleteNodePos() will use head node reference of the linked list and the key value to delete
a node from the CDLL.
Algorithm and C++ code for deleteNodeKey() operation in CDLL.
/* Function to delete a node with matchin key from the Circular linked list */
void deleteNodeKey(int key)
{
//1. Check, if list is empty or not, if empty return
if(head == NULL)
{
cout << "\nCDLL is Empty...";
return;
}

//2. If head node (first node) itself holding the key, delete the first node and return
if(head->data==key)
{
deleteFirst();
return;
}

//3. Assign a temp pointer to head

//take two pointers one to point the position node
 //another to point the previous of position node
Node* temp = head;
Node* temp1;

//4. Traverse two pointers, temp to position node

// temp1 to previous node of position node
do
{
temp1 = temp;
temp=temp->next;
}while(temp->data!=key);

//5. Make previous node of position node, to point the next node of position node
temp1->next = temp->next;

//6. Make next node of position node to point the prev node of position node
temp->next->prev = temp->prev;

//7. Delete the position node

delete temp;
}
Time complexity O(n).

e) Deleting the complete CDLL. (deleteList())

 To delete all nodes from the given CDLL, simply traverse through the list node by node and delete
all nodes till the end point reached.(That is head == last)
 Once the last node is reached, simply make the head node as NULL, to indicate the list as empty
and delete the last node as well.
Algorithm and C++ code for deleteList() operation in CDLL.
/* Function to delete the complete Circular doubly linked list */
void deleteList()
{
//1. Check, if list is empty or not, if empty return
if(head == NULL)
{
cout << "CDLL is Empty...";
return;
}

//2. Assign a last pointer to last node head->prev

Node* last = head->prev;

//3. Assign the temp pointer to head and move the head ahead
//4. Delete the temp pointer and make last node to point the head
//5. repeat step 3, 4 untill the head reaches the last node
Node* temp;
do
{
temp=head;
head=head->next;
 last->prev=head;
head->prev=last;
delete temp;
}while(head!=last);
//6. Make head as Null and delete the last
head = NULL;
delete last;
}
Time complexity O(n).

Main Function (Driver Program)

int main()
{
// Insert 5. So linked list becomes 5->NULL
addAtEnd(5);

// Insert 4 at the beginning. So linked

// list becomes 4->5
addAtFirst(4);

// Insert 7 at the end. So linked list

// becomes 4->5->7
addAtEnd(7);

// Insert 8 at the end. So linked list

// becomes 4->5->7->8
addAtEnd(8);

// Insert 6, after 5. So linked list

// becomes 4->5->6->7->8
addAfter(6,1);

printf("\nCreated circular doubly linked list is: ");

printList(head);
deleteFirst();
printf("\nCreated circular doubly linked list is: ");
printList(head);
deleteEnd();
printf("\nCreated circular doubly linked list is: ");
printList(head);

deleteNodeKey(6);
printf("\nCreated circular doubly linked list is: ");
printList(head);

deleteList();
printf("\nCreated circular doubly linked list is: ");
printList(head);

search(6)?cout<<"\nElement Found....":cout<<"\nElement not Found....";

return 0;
}
Output:
Created circular doubly linked list is:
Traversal in forward direction: 4 5 6 7 8
Traversal in reverse direction: 8 7 6 5 4
Created circular doubly linked list is:
Traversal in forward direction: 5 6 7 8
Traversal in reverse direction: 8 7 6 5
Created circular doubly linked list is:
Traversal in forward direction: 5 6 7
Traversal in reverse direction: 7 6 5
Created circular doubly linked list is:
Traversal in forward direction: 5 7
Traversal in reverse direction: 7 5
Created circular doubly linked list is:
CDLL is Empty...
CDLL is Empty...
Element not Found....
UNIT – IV
TREES
Tree – Definitions
 In linear data structure data is organized in sequential order and in non-linear data structure data is
organized in random order.
 A tree is a very popular non-linear data structure used in a wide range of applications.
 A tree data structure can be defined as a non-linear data structure which organizes data in hierarchical
structure and this is a recursive definition.
 A tree data structure can also be defined as a collection of data (Node) which is organized in hierarchical
structure recursively.
 A tree is a connected graph without any circuits.
 In tree data structure, every individual element is called as Node. Node in a tree data structure stores the
actual data of that particular element and link to next element in hierarchical structure.
 In a tree data structure, if we have N number of nodes then we can have a maximum of N-1 number of
links.
The important properties of tree data structure are-
 There is one and only one path between every pair of vertices in a tree.
 A tree with n vertices has exactly (n-1) edges.
 A graph is a tree if and only if it is minimally connected.
 Any connected graph with n vertices and (n-1) edges is a tree.

Example:

Trees – Basic Terminology:

The following terminology is used in trees concept.
1. Root
o In a tree data structure, the first node is called as Root Node.
o Every tree must have a root node, the root node is the origin of the tree data structure.
o In any tree, there must be one and only one root node. There cannot be multiple root nodes in a tree.
2. Edge
o In a tree data structure, the connecting link between any two nodes is called as EDGE.
o In a tree with 'N' number of nodes there will be a maximum of 'N-1' number of edges.

3. Parent
o In a tree data structure, the node which is a predecessor of any node is called as PARENT NODE.
o In simple words, the node which has a branch from it to any other node is called a parent node.
o Parent node can also be defined as "The node which has child / children".

4. Child
o In a tree data structure, the node which is descendant of any node is called as CHILD Node.
o In simple words, the node which has a link from its parent node is called as child node.
o In a tree, any parent node can have any number of child nodes.
o In a tree, all the nodes except root are child nodes.
5. Siblings
o In a tree data structure, nodes which belong to same Parent are called as SIBLINGS.
o In simple words, the nodes with the same parent are called Sibling nodes.

6. Leaf
o In a tree data structure, the node which does not have a child is called as LEAF Node.
o In simple words, a leaf is a node with no child.
o In a tree data structure, the leaf nodes are also called as External Nodes.
o External node is also a node with no child.
o In a tree, leaf node is also called as 'Terminal' node.

7. Internal Nodes
o In a tree data structure, the node which has at least one child is called as INTERNAL Node.
o In simple words, an internal node is a node with at least one child.
o In a tree data structure, nodes other than leaf nodes are called as Internal Nodes.
o The root node is also said to be Internal Node if the tree has more than one node.
o Internal nodes are also called as 'Non-Terminal' nodes.
8. Degree
o In a tree data structure, the total number of children of a node is called as DEGREE of that Node.
o In simple words, the Degree of a node is total number of children it has.
o The highest degree of a node among all the nodes in a tree is called as 'Degree of Tree'.

9. Level
o In a tree data structure, the root node is said to be at Level 0 and the children of root node are at
Level 1 and the children of the nodes which are at Level 1 will be at Level 2 and so on...
o In simple words, in a tree each step from top to bottom is called as a Level and the Level count starts
with '0' and incremented by one at each level (Step).

10. Height
o In a tree data structure, the total number of edges from leaf node to a particular node in the longest
path is called as HEIGHT of that Node.
o In a tree, height of the root node is said to be height of the tree.
o In a tree, height of all leaf nodes is '0'.
11. Depth
o In a tree data structure, the total number of edges from root node to a particular node is called as
DEPTH of that Node.
o In a tree, the total number of edges from root node to a leaf node in the longest path is said to be
Depth of the tree.
o In simple words, the highest depth of any leaf node in a tree is said to be depth of that tree.
o In a tree, depth of the root node is '0'.

12. Path
o In a tree data structure, the sequence of Nodes and Edges from one node to another node is called as
PATH between that two Nodes.
o Length of a Path is total number of nodes in that path.
o In below example the path A - B - E - J has length 4.

13. Sub Tree

o In a tree data structure, each child from a node forms a subtree recursively.
o Every child node will form a subtree on its parent node.
TREE REPRESENTATIONS
o A tree data structure can be represented in two methods.
o Those methods are as follows:
a) List Representation
b) Left Child - Right Sibling Representation
Consider the following tree:

a) List Representation
o In this representation, two types of nodes are used, one for representing the node with data called 'data
node' and another for representing only references called 'reference node'.
o We start with a 'data node' from the root node in the tree. Then it is linked to an internal node through a
'reference node' which is further linked to any other node directly. This process repeats for all the nodes in
the tree.
The above example tree can be represented using List representation as follows:

b) Left Child - Right Sibling Representation

o In this representation, we use a list with one type of node which consists of three fields namely Data field,
Left child reference field and Right sibling reference field.
o Data field stores the actual value of a node, left reference field stores the address of the left child and right
reference field stores the address of the right sibling node.
o Graphical representation of that node is as follows:
 o In this representation, every node's data field stores the actual value of that node. If that node has left a
child, then left reference field stores the address of that left child node otherwise stores NULL.
o If that node has the right sibling, then right reference field stores the address of right sibling node otherwise
stores NULL.
The above example tree can be represented using Left Child - Right Sibling representation as follows:

Why Trees?
1. One reason to use trees is, to store information that naturally forms a hierarchy. For example, the file
system on a computer which stores the files and directories in a tree fashion.
2. Trees provide moderate access/search (quicker than Linked List and slower than arrays).
3. Unlike Arrays, Trees don’t have an upper limit on number of nodes as nodes are linked using pointers.
Main applications of trees include:
1. Manipulate hierarchical data.
2. Make information easy to search.
3. Manipulate sorted lists of data.
4. Router algorithms.
5. Multi-stage decision-making.

Different Types of Trees:

1. Binary Tree
2. Threaded Binary Tree
3. Binary Search Tree
4. AVL Tree
BINARY TREE
 In a normal tree, every node can have any number of children.
 A binary tree is a special type of tree data structure in which every node can have a maximum of 2
children. A tree in which every node can have a maximum of two children is called Binary Tree.
 The child node left side is known as a left child and the right side child node is known as right child.
 In a binary tree, every node can have either 0 children or 1 child or 2 children but not more than 2 children.

Example

There are different types of binary trees and they are...

a) Strictly Binary Tree
b) Complete Binary Tree
c) Extended Binary Tree

a) Strictly Binary Tree:

o In a binary tree, every node can have a maximum of two children.
o But in strictly binary tree, every node should have exactly two children or none.
o That means every internal node must have exactly two children.
o A binary tree in which every node has either two or zero number of children is called Strictly
Binary Tree.
o Strictly binary tree is also called as Full Binary Tree or Proper Binary Tree or 2-Tree.
Example

b) Complete Binary Tree

o In complete binary tree all the nodes must have exactly two children and at every level of complete
binary tree there must be 2level number of nodes.
o For example at level 2 there must be 22 = 4 nodes and at level 3 there must be 23 = 8 nodes.
o A binary tree in which every internal node has exactly two children and all leaf nodes are at same
level is called Complete Binary Tree / Perfect Binary Tree.
 Example

c) Extended Binary Tree

o A binary tree can be converted into Full Binary tree by adding dummy nodes to existing nodes
wherever required.
o The full binary tree obtained by adding dummy nodes to a binary tree is called as Extended Binary
Tree.
Example

In above figure, a normal binary tree is converted into full binary tree by adding dummy nodes (In pink color).

Binary Tree Representations

A binary tree data structure is represented using two methods. Those methods are as follows...
I. Array Representation
II. Linked List Representation
Consider the following binary tree...

I. Array Representation of Binary Tree

 In array representation of a binary tree, we use one-dimensional array (1-D Array) to represent a binary tree.
 Consider the above example of a binary tree and it is represented as follows...
 To represent a binary tree of depth 'n' using array representation, we need one dimensional array with a
maximum size of 2n + 1.
II. Linked List Representation of Binary Tree
 We use a double linked list to represent a binary tree.
 In a double linked list, every node consists of three fields. First field for storing left child address, second
for storing actual data and third for storing right child address.
 In this linked list representation, a node has the following structure...

 The above example of the binary tree represented using Linked list representation is shown as follows...

Linked List Implementation of Binary Tree:

//Binary Tree Node Representation
Graphical Representation C++ Code
class Node
{
public:
int data;
Node* left;
Node* right;
};

//Recursive function to insert a new_node into the Binary Tree

 The insert() function will recursively tests for the empty slot to insert the new_node into the binary tree.
 If the tree is empty the new_node will become the root node.
 If the tree is not empty then the insert function will recursively traverse till it finds the empty slot either
as a left child or as a right child.
 After finding the empty slot, the function will simply inserts the new_node into the binary tree.
//utility function to perform the insert operation into the binary tree
Node* insert(Node* root,int value)
{
//1. Create the new_node
Node* new_node = new Node();

//2. Assign the data value

 new_node->data = value;

//3. If the tree is empty insert the new_node as root node

if(root == NULL)
{
new_node->left = new_node->right = NULL;
root = new_node;
count++;
}
//4. Else find the free slot either the left side or the right side recursively and insert the new_node
else if(count%2 != 0)
root->left = insert(root->left,value);
else
root->right = insert(root->right,value);

//5. After the insertion return the root node.

return root;
}
As the function recursively searches for an empty slot till it finds one. If there are n nodes in the tree, then the
function has to do n searching before it finds the empty slot. Hence the time complexity is O(n).

Binary Tree Traversals:

 In order to display a binary tree, there must be some order needs to be followed. The order in which all the
nodes of that binary tree must be displayed.
 In any binary tree, displaying order of nodes depends on the traversal method.
 Displaying (or) visiting order of nodes in a binary tree is called as Binary Tree Traversal.
 There are two broad types of binary tree traversals:

I. The Depth First Traversal is categorized into three categories:

A. In - Order Traversal
B. Pre - Order Traversal
C. Post - Order Traversal
To perform the traversals. Consider the following binary tree as an example:
A. In - Order Traversal (LEFTCHILD - root - RIGHTCHILD)
 In In-Order traversal, the root node is visited between the left child and right child.
 In this traversal, the left child node is visited first, then the root node is visited and later the right
child node.
 This in-order traversal is applicable for every root node of all subtrees in the tree. This is performed
recursively for all nodes in the tree.
Example:
 In the above example of a binary tree, first we try to visit left child of root node 'A', but A's left
child 'B' is a root node for left subtree.
 So we try to visit its (B's) left child 'D' and again D is a root for subtree with nodes D, I and J. So
we try to visit its left child 'I' and it is the leftmost child.
 So first we visit 'I' then go for its root node 'D' and later we visit D's right child 'J'.
 With this we have completed the left part of node B. Then visit 'B' and next B's right child 'F' is
visited.
 With this we have completed left part of node A. Then visit root node 'A'. With this we have
completed left and root parts of node A.
 Then we go for the right part of the node A. In right of A again there is a subtree with root C.
 So go for left child of C and again it is a subtree with root G. But G does not have left part so we
visit 'G' and then visit G's right child K. With this we have completed the left part of node C.
 Then visit root node 'C' and next visit C's right child 'H' which is the rightmost child in the tree.
 So we stop the process.
 Here we have visited in the order of I - D - J - B - F - A - G - K - C - H using In-Order Traversal.
In-Order Traversal for above example of binary tree is

I-D-J-B-F-A-G-K-C-H

//Recursive function to perform In-Order Traversal

// Following Utility function will display the tree by using In-order Traversal
void inOrder(Node *root)
{
if(root!=NULL)
{
inOrder(root->left);
cout<<"\t"<<root->data;
inOrder(root->right);
}
}
 Since the number of edges that can originate from a node is limited to 2 in the case of a
Binary Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the
total number of nodes.
 The complexity then becomes O(n + n-1), which is O(n).
 O(n) , because you traverse each node once.

B. Pre - Order Traversal (root - leftChild - rightChild)

 In Pre-Order traversal, the root node is visited before the left child and right child nodes.
 In this traversal, the root node is visited first, then its left child and later its right child.
 This pre-order traversal is applicable for every root node of all subtrees in the tree.
 Example:
 In the above example of binary tree, first we visit root node 'A' then visit its left child 'B' which is a
root for D and F.
 So we visit B's left child 'D' and again D is a root for I and J. So we visit D's left child 'I' which is
the leftmost child.
 So next we go for visiting D's right child 'J'. With this we have completed root, left and right parts
of node D and root, left parts of node B.
 Next visit B's right child 'F'. With this we have completed root and left parts of node A. So we go
for A's right child 'C' which is a root node for G and H.
 After visiting C, we go for its left child 'G' which is a root for node K. So next we visit left of G, but
it does not have left child so we go for G's right child 'K'.
 With this, we have completed node C's root and left parts. Next visit C's right child 'H' which is the
rightmost child in the tree. So we stop the process.
 That means here we have visited in the order of A-B-D-I-J-F-C-G-K-H using Pre-Order Traversal.

Pre-Order Traversal for above example binary tree is

A-B-D-I-J-F-C-G-K-H

//Recursive function to perform Pre-Order Traversal

// Following Utility function will display the tree by using Pre-order Traversal
void preOrder(Node *root)
{
if(root!=NULL)
{
cout<<"\t"<<root->data;
preOrder(root->left);
preOrder(root->right);
}
}
 Since the number of edges that can originate from a node is limited to 2 in the case of a
Binary Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the
total number of nodes.
 The complexity then becomes O(n + n-1), which is O(n).
 O(n) , because you traverse each node once.

C. Post - Order Traversal ( leftChild - rightChild - root )

 In Post-Order traversal, the root node is visited after left child and right child.
 In this traversal, left child node is visited first, then its right child and then its root node.
 This is recursively performed until the right most node is visited.
 Here we have visited in the order of I - J - D - F - B - K - G - H - C - A using Post-Order Traversal.
Post-Order Traversal for above example binary tree is

I-J-D-F-B-K-G-H-C-A

//Recursive function to perform Post-Order Traversal

// Following Utility function will display the tree by using Post-order Traversal
void postOrder(Node *root)
{
 if(root!=NULL)
{
postOrder(root->left);
postOrder(root->right);
cout<<"\t"<<root->data;
}
}
 Since the number of edges that can originate from a node is limited to 2 in the case of a
Binary Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the
total number of nodes.
 The complexity then becomes O(n + n-1), which is O(n).
 O(n) , because you traverse each node once.

II. Breadth First Traversal of a tree prints all the nodes of a tree level by level. Breadth First
Traversal is also called as Level Order Traversal.
In our example we have visited in the order of A - B - C - D - F - G - H - I - J - K using Depth First
Traversal.
Depth First Traversal for above example binary tree is

A-B-C-D-F-G-H-I-J-K

Delete Operation in Binary Tree:

 Given a binary tree, delete a node from it by making sure that tree shrinks from the bottom (i.e. the deleted
node is replaced by bottom most and rightmost node).
 Here we do not have any order among elements, so we replace with last element.
Algorithm for deleting a node from a Binary Tree
Step – 1: Starting at root, find the deepest and rightmost node in binary tree and node which we want to delete.
Step – 2: Replace the deepest rightmost node’s data with node to be deleted.
Step – 3: Then delete the deepest rightmost node.

C++ Code for Delete Operation

//Utility function to delete the complete Binary Tree
void deleteTree(Node* root)
{
if (root == NULL)
return;

/* first delete both subtrees */

deleteTree(root->left);
deleteTree(root->right);
 /* then delete the node */
cout << "\n Deleting node: " << root->data;
delete root;
}

2. Threaded Binary Trees

 A binary tree can be represented using array representation or linked list representation.
 When a binary tree is represented using linked list representation, the reference part of the node which
doesn't have a child is filled with a NULL pointer.
 In any binary tree linked list representation, there is a number of NULL pointers than actual pointers.
 Generally, in any binary tree linked list representation, if there are 2N number of reference fields, then N+1
number of reference fields are filled with NULL ( N+1 are NULL out of 2N ).
 This NULL pointer does not play any role except indicating that there is no link (no child).
 J. Perlis and C. Thornton have proposed new binary tree called "Threaded Binary Tree", which makes use
of NULL pointers to improve its traversal process.
 In a threaded binary tree, NULL pointers are replaced by references of other nodes in the tree. These extra
references are called as threads.

Threaded Binary Tree is also a binary tree in which all left child pointers that are NULL (in Linked list
representation) points to its in-order predecessor, and all right child pointers that are NULL (in
Linked list representation) points to its in-order successor.

 If there is no in-order predecessor or in-order successor, then it points to the root node.

Consider the following binary tree...

 To convert the above example binary tree into a threaded binary tree, first find the in-order traversal of that
tree...
In-order traversal of above binary tree...

H-D-I-B-E-A-F-J-C-G

 When the above binary tree is represented using linked list representation, nodes H, I, E, F, J and G left
child pointers are NULL.
 This NULL is replaced by address of its in-order predecessor respectively (I to D, E to B, F to A, J to F and
G to C), but here the node H does not have its in-order predecessor, so it points to the root node A.
 And nodes H, I, E, J and G right child pointers are NULL. These NULL pointers are replaced by address of
its in-order successor respectively (H to D, I to B, E to A, and J to C), but here the node G does not have its
in-order successor, so it points to the root node A.

Above example binary tree is converted into threaded binary tree as follows.

In the above figure, threads are indicated with dotted links.

3. BINARY SEARCH TREE

 In a binary tree, every node can have a maximum of two children but there is no need to maintain the order
of nodes basing on their values. In a binary tree, the elements are arranged in the order they arrive at the
tree from top to bottom and left to right.
 To enhance the performance of binary tree, a special type of binary tree known as Binary Search Tree is
used. Binary search tree mainly focuses on the search operation in a binary tree. Binary search tree can be
defined as follows...
Binary Search Tree is a binary tree in which every node contains only smaller values in its left subtree and only
larger values in its right subtree.

 In a binary search tree, all the nodes in the left subtree of any node contains smaller values and all the
nodes in the right subtree of any node contains larger values as shown in the following figure...

Example
The following tree is a Binary Search Tree. In this tree, left subtree of every node
contains nodes with smaller values and right subtree of every node contains larger
values.

Every binary search tree is a binary tree but every binary tree need not to be binary
search tree.
 The above properties of Binary Search Tree provide an ordering among keys so
that the operations like search, minimum and maximum can be done fast.
 If there is no ordering, then we may have to compare every node data to search a
given key.

 Binary Search Tree, is a node-based binary tree data structure which has the following properties:
I. The left subtree of a node contains only nodes with keys lesser than the node’s key.
II. The right subtree of a node contains only nodes with keys greater than the node’s key.
 III. The left and right subtree each must also be a binary search tree. There must be no duplicate nodes.

Why Binary Search Trees:

 The above properties of Binary Search Tree provide an ordering among keys so that the operations like
search, minimum and maximum can be done fast.
 If there is no ordering, then we may have to compare every key to search a given key.

Example
Construct a Binary Search Tree by inserting the following sequence of numbers...

10, 12, 5, 4, 20, 8, 7, 15 and 13

Above elements are inserted into a Binary Search Tree as follows...

Operations on a Binary Search Tree

The following operations are performed on a binary search tree...
1. Search
2. Insertion
3. Traversal
4. Deletion
1. Search Operation in BST:
 In a binary search tree, the search operation is nothing but searching for a node with a given key value.
 To search a given key in Binary Search Tree, we first compare it with root, if the key is present at root,
we return root. If key is greater than root’s key, we recursively search the right subtree of root node.
Otherwise we recursively search the left subtree.
 The search operation is performed as follows...

Algorithm for search operation in a Binary Search Tree:

Step – 1: Read the search element from the user.
Step – 2: Compare the search element with the value of root node in the tree.
Step – 3: If both are matched, then display "Given node is found!!!" and terminate the function
Step – 4: If both are not matched, then check whether search element is smaller or larger than that node
value.
Step – 5: If search element is smaller, then continue the search process in left subtree.
Step – 6: If search element is larger, then continue the search process in right subtree.
Step – 7: Repeat the same until we find the exact element or until the search element is compared with
the leaf node.
Step – 8: If we reach to the node having the value equal to the search value then display "Element is
found" and terminate the function.
Step – 9: If we reach to the leaf node and if it is also not matched with the search element, then display
"Element is not found" and terminate the function.
C++ Code to perform search operation in a Binary Search Tree
// Utility function to search a given key in a given BST
Node* search(Node* root, int key)
{
// Base Cases: root is null or key is present at root
if (root == NULL || root->data == key)
return root;

// Key is greater than root's key

if (root->data < key)
return search(root->right, key);

// Key is smaller than root's key

return search(root->left, key);
}
Time Complexity: The worst case time complexity of search and insert operations is O(h) where h is
height of Binary Search Tree. In worst case, we may have to travel from root to the deepest leaf node.
The height of a skewed tree may become n and the time complexity of search and insert operation may
become O(n).

2. Insertion of a new node into the BST

 A new data element is always inserted at leaf. We start searching a data value of the node from root till
we hit a leaf node. Once a leaf node is found, the new node is added as a child of the leaf node.
 The insertion operation is performed as follows...
 Algorithm for insert operation in a Binary Search Tree:
Step – 1: Create a new_node with given value and set its left and right to NULL.
Step – 2: Check whether tree is Empty.
Step – 3: If the tree is Empty, then set root to new_node.
Step – 4: If the tree is Not Empty, then check whether the value of new_node is smaller or larger than the
node (here it is root node).
Step – 5: If new_node is smaller than or equal to the node then move to its left child. If new_node is
larger than the node then move to its right child.
Step – 6: Repeat the above steps until we reach to the leaf node (i.e., reaches to NULL).
Step – 7: After reaching the leaf node, insert the new_node as left child if the new_node is smaller or
equal to that leaf node or else insert it as right child.
C++ Code to perform insert operation in a Binary Search Tree
/* A utility function to insert a new node with given key in BST */
Node* insert(Node* root, int new_data)
{
Node* new_node=new Node();
new_node->data=new_data;
new_node->left=new_node->right=NULL;

/* If the tree is empty, return a new node */

if (root == NULL)
return new_node;

/* Otherwise, recur down the tree */

if (new_data < root->data)
root->left = insert(root->left, new_data);
else if (new_data > root->data)
root->right = insert(root->right, new_data);

/* return the (unchanged) root pointer */

return root;
}
Time Complexity: The worst case time complexity of search and insert operations is O(h) where h is
height of Binary Search Tree. In worst case, we may have to travel from root to the deepest leaf node. The
height of a skewed tree may become n and the time complexity of search and insert operation may
become O(n).

3. Traversal Operation in BST:

 In order to display a binary search tree, there must be some order needs to be followed. The order in
which all the nodes of that binary search tree must be displayed.
 In any binary search tree, displaying order of nodes depends on the traversal method.
 Displaying (or) visiting order of nodes in a binary search tree is called as Binary serch Tree Traversal.
 The traversal methods are same like as in Binary tree: In-Order, Pre-Order and Post-Order.

In-Order Traversal: (Left Child – Root – Right Child)

 In In-Order traversal, the root node is visited between the left child and right child.
  In this traversal, the left child node is visited first, then the root node is visited and later the
right child node.
 This in-order traversal is applicable for every root node of all subtrees in the tree. This is
performed recursively for all nodes in the tree.

C++ Code for In-order Traversal on Binary Search Tree

void inOrder(Node* root)
{
if(root!=NULL)
{
inOrder(root->left);
cout<<" "<<root->data;
inOrder(root->right);
}
}
Pre-Order Traversal: (Root – Left Child – Right Child)
 In Pre-Order traversal, the root node is visited before the left child and right child nodes.
 In this traversal, the root node is visited first, then its left child and later its right child.
 This pre-order traversal is applicable for every root node of all subtrees in the tree.

C++ Code for Pre-order Traversal on Binary Search Tree

void preOrder(Node* root)
{
if(root!=NULL)
{
cout<<" "<<root->data;
preOrder(root->left);
preOrder(root->right);
}
}
Post-Order Traversal: (Left Child – Right Child – Root)
 In Post-Order traversal, the root node is visited after left child and right child.
 In this traversal, left child node is visited first, then its right child and then its root node.
 This is recursively performed until the right most node is visited.

C++ Code for Post-order Traversal on Binary Search Tree

void postOrder(Node* root)
{
if(root!=NULL)
{
postOrder(root->left);
postOrder(root->right);
cout<<" "<<root->data;
}
}
 Time Complexity:
 Since the number of edges that can originate from a node is limited to 2 in the case of a Binary
Tree, the maximum number of total edges in a Binary Tree is n-1, where n is the total number
of nodes.
 The complexity then becomes O(n + n-1), which is O(n).
 O(n) , because you traverse each node once.

4. Deletion Operation in BST:

 In a binary search tree, the deletion operation is performed with O(log n) time complexity.
 Deleting a node from Binary search tree includes following three cases...
 Case 1: Deleting a Leaf node (A node with no children)
 Case 2: Deleting a node with one child
 Case 3: Deleting a node with two children

Case – 1: Deleting a Leaf node (A node with no children)

The following steps are used to delete a leaf node from BST...
Step – 1: Find the node to be deleted using search operation
Step – 2: Delete the node using delete function (If it is a leaf) and terminate the function.

Case – 2: Deleting a node with one child

The following steps are used to delete a node with one child from BST...
Step – 1: Find the node to be deleted using search operation
Step – 2: If it has only one child then create a link between its parent node and child node.
Step – 3: Delete the node using free function and terminate the function.

Case – 3: Deleting a node with two children

The following steps are used to delete a node with two children from BST...
Step – 1: Find the node to be deleted using search operation
Step – 2: If it has two children, then find the largest node in its left subtree (OR) the smallest node in its
right subtree.
Step – 3: Swap both deleting node and node which is found in the above step.
Step – 4: Then check whether deleting node came to case 1 or case 2 or else goto step 2
Step – 5: If it comes to case 1, then delete using case 1 logic.
Step – 6: If it comes to case 2, then delete using case 2 logic.
Step – 7: Repeat the same process until the node is deleted from the tree.
C++ Code to perform delete operation in a Binary Search Tree
/* Given a binary search tree and a key, this function deletes the key and returns the new root */
Node* deleteNode(Node* root, int key)
{
// base case
if (root == NULL)
return root;

// If the key to be deleted is smaller than the root's key, then it lies in left subtree
if (key < root->data)
root->left = deleteNode(root->left, key);
 // If the key to be deleted is greater than the root's key, then it lies in right subtree
else if (key > root->data)
root->right = deleteNode(root->right, key);

// if key is same as root's key, then This is the node to be deleted

else
{
// node with only one child or no child
if (root->left == NULL)
{
Node* temp = root->right;
delete root;
return temp;
}
else if (root->right == NULL)
{
Node* temp = root->left;
delete root;
return temp;
}

// node with two children: Get the inorder successor (smallest in the right subtree)
Node* temp = root->right;
while (temp && temp->left != NULL)
temp = temp->left;

// Copy the inorder successor's content to this node

root->data = temp->data;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->data);
}
return root;
}
Time Complexity: The worst case time complexity of delete operation is O(h) where h is height of
Binary Search Tree. In worst case, we may have to travel from root to the deepest leaf node. The height of
a skewed tree may become n and the time complexity of delete operation may become O(n)
4. AVL TREE DATA STRUCTURE

 The AVL tree was introduced in the year 1962 by G.M. Adelson-Velsky and E.M. Landis.
 AVL tree is a height-balanced binary search tree. That means, an AVL tree is also a binary search tree but
it is a balanced tree.
 A binary tree is said to be balanced if, the difference between the heights of left and right subtrees of every
node in the tree is either -1, 0 or +1.
 In other words, a binary tree is said to be balanced if the height of left and right children of every node
differ by either -1, 0 or +1.
 In an AVL tree, every node maintains an extra information known as balance factor.
 An AVL tree is defined as follows...
An AVL tree is a balanced binary search tree. In an AVL tree, balance factor of every node is either -1, 0 or +1.

Balance Factor:
 Balance factor of a node is the difference between the heights of the left and right subtrees of that
node.
 The balance factor of a node is calculated either height of left subtree - height of right subtree (OR)
height of right subtree - height of left subtree.
 In the following explanation, we calculate as follows...

Balance factor = heightOfLeftSubtree - heightOfRightSubtree

Example of AVL Tree

The above tree is a binary search tree and every node is satisfying balance factor condition. So
this tree is said to be an AVL tree.
Every AVL Tree is a binary search tree but every Binary Search Tree need not be AVL tree.

Why AVL Trees?

 Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height
of the BST.
 The cost of these operations may become O(n) for a skewed Binary tree.
 If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can
guarantee an upper bound of O(Logn) for all these operations.
 The height of an AVL tree is always O(Logn) where n is the number of nodes in the tree.
AVL Tree Rotations

 In AVL tree, after performing operations like insertion and deletion we need to check the balance factor of
every node in the tree.
 If every node satisfies the balance factor condition then we conclude the operation otherwise we must make
it balanced.
 Whenever the tree becomes imbalanced due to any operation we use rotation operations to make the tree
balanced.
 Rotation operations are used to make the tree balanced.
Rotation is the process of moving nodes either to left or to right to make the tree balanced.

 There are four rotations and they are classified into two types.

Single Left Rotation (LL Rotation)

 AVL tree may become unbalanced, when a node is inserted into the right subtree of the right subtree,
then we perform a single left rotation −
 In LL Rotation, every node moves one position to left from the current position.
 To understand LL Rotation, let us consider the following insertion operation in AVL Tree...

C++ Code for Single Left Rotation

// A utility function to left rotate subtree rooted with root
Node* leftRotate(Node* root)
{
Node* temp1 = root->right;
Node* temp2 = temp1->left;

// Perform rotation
temp1->left = root;
root->right = temp2;
 // Update heights
root->height = max(height(root->left), height(root->right)) + 1;
temp1->height = max(height(temp1->left), height(temp1->right)) + 1;

// Return new root

return temp1;
}
Time Complexity: O(1), The rotation operations (left and right rotate) take constant time as only a few
pointers are being changed there.

Single Right Rotation (RR Rotation)

 AVL tree may become unbalanced, if a node is inserted in the left subtree of the left subtree. The tree
then needs a right rotation to make it balanced.
 In RR Rotation, every node moves one position to right from the current position.
 To understand RR Rotation, let us consider the following insertion operation in AVL Tree...

C++ Code for Single Right Rotation

// A utility function to right rotate subtree rooted with root
Node* rightRotate(Node* root)
{
Node* temp1 = root->left;
Node* temp2 = temp1->right;

// Perform rotation
temp1->right = root;
root->left = temp2;

// Update heights
root->height = max(height(root->left), height(root->right)) + 1;
temp1->height = max(height(temp1->left), height(temp1->right)) + 1;

// Return new root

return temp1;
}
 Time Complexity: O(1), The rotation operations (left and right rotate) take constant time as only a few
pointers are being changed there.

Left Right Rotation (LR Rotation)

 Double rotations are slightly complex versions of single rotations.

 The LR Rotation is a sequence of single left rotation followed by a single right rotation.
 In LR Rotation, at first, every node moves one position to the left and one position to right from the current
position.
 To understand LR Rotation, let us consider the following insertion operation in AVL Tree...

Right Left Rotation (RL Rotation)

 The RL Rotation is sequence of single right rotation followed by single left rotation.
 In RL Rotation, at first every node moves one position to right and one position to left from the current
position.
 To understand RL Rotation, let us consider the following insertion operation in AVL Tree...

Operations on an AVL Tree

 The following operations are performed on AVL tree...

1. Search
2. Insertion
3. Traversal
4. Deletion

1. Search Operation in AVL Tree:

 The search operation in AVL tree is same as what we have seen in Binary Search Tree.
 Refer the search function of Binary Search Tree.
2. Insertion Operation in AVL Tree:
 To make sure that the given tree remains AVL after every insertion, we must augment the standard
BST insert operation to perform some re-balancing.
 Following are two basic operations that can be performed to re-balance a BST without violating the
BST property (keys(left) < key(root) < keys(right)).
 In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, a
new node is always inserted as a leaf node. The insertion operation is performed as follows...
 In an AVL tree, the insertion operation is performed with O(log n) time complexity.

Algorithm for Insert Operation in an AVL Tree

Step – 1: Insert the new element into the tree using Binary Search Tree insertion logic.
Step – 2: After insertion, check the Balance Factor of every node.
Step – 3: If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.
Step – 4: If the Balance Factor of any node is other than 0 or 1 or -1 then that tree is said to be imbalanced.
In this case, perform suitable Rotation to make it balanced and go for next operation.
C++ Code for Insert Operation in an AVL Tree
// Recursive function to insert a key in the subtree rooted with node and returns the new root of the subtree.
Node* insert(Node* root, int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->left = new_node->right = NULL;
new_node->height = 1;

/* 1. Perform the normal BST insertion */

if(root == NULL)
return new_node;

if(new_data < root->data)

root->left = insert(root->left, new_data);
else if(new_data > root->data)
root->right = insert(root->right, new_data);
else // Equal keys are not allowed in BST
return root;

/* 2. Update height of this ancestor node */

root->height = 1 + max(height(root->left), height(root->right));

/* 3. Get the balance factor of this ancestor node to check whether this node became unbalanced */
int balance = getBalance(root);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case
if (balance > 1 && new_data < root->left->data)
return rightRotate(root);
 // Right Right Case
if (balance < -1 && new_data > root->right->data)
return leftRotate(root);

// Left Right Case

if (balance > 1 && new_data > root->left->data)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}

// Right Left Case

if (balance < -1 && new_data < root->right->data)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}

/* return the (unchanged) node pointer */

return root;
}
Time Complexity: The rotation operations (left and right rotate) take constant time as only a few pointers
are being changed there. Updating the height and getting the balance factor also takes constant time. So the
time complexity of AVL insert remains same as BST insert which is O(h) where h is the height of the tree.
Since AVL tree is balanced, the height is O(Logn). So time complexity of AVL insert is O(Logn).

3. Traversal On AVL Tree:

 The Traversal operation in AVL tree is same as what we have seen in Binary Search Tree.
 Refer the different traversal functions like In-Order, Pre-Order and Post-Order of Binary Search Tree.

4. Delete Operation in AVL Tree:

 The deletion operation in AVL Tree is similar to deletion operation in BST.
 But after every deletion operation, we need to check with the Balance Factor condition.
 If the tree is balanced after deletion go for next operation otherwise perform suitable rotation to make
the tree Balanced.

Algorithm for Delete Operation in an AVL Tree

Step – 1: Delete the key element from the tree using Binary Search Tree delete logic.
Step – 2: After delete, check the Balance Factor of every node.
Step – 3: If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.
Step – 4: If the Balance Factor of any node is other than 0 or 1 or -1 then that tree is said to be imbalanced.
In this case, perform suitable Rotation to make it balanced and go for next operation.
C++ Code for Delete Operation in an AVL Tree
Node* deleteNode(Node* root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;

// If the key to be deleted is smaller than the root's key, then it lies in left subtree
if( key < root->data )
root->left = deleteNode(root->left, key);

// If the key to be deleted is greater than the root's key, then it lies in right subtree
else if( key > root->data )
root->right = deleteNode(root->right, key);

// if key is same as root's key, then this is the node to be deleted

else
{
// node with only one child or no child
if( (root->left == NULL) || (root->right == NULL) )
{
Node *temp = root->left ? root->left : root->right;

// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of the non-empty child
delete temp;
}
else
{
// node with two children: Get the inorder successor (smallest in the right subtree)
Node* temp = root->right;
while (temp->left != NULL)
temp = temp->left;

// Copy the inorder successor's data to this node

root->data = temp->data;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->data);
}
}

// If the tree had only one node then return

if (root == NULL)
 return root;

// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE

root->height = 1 + max(height(root->left), height(root->right));

// STEP 3: GET THE BALANCE FACTOR OF THIS NODE

//(to check whether this node became unbalanced)
int balance = getBalance(root);

// If this node becomes unbalanced, then there are 4 cases

// Left Left Case
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);

// Left Right Case

if (balance > 1 && getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}

// Right Right Case

if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);

// Right Left Case

if (balance < -1 && getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}
Time Complexity: The rotation operations (left and right rotate) take constant time as only few pointers are
being changed there. Updating the height and getting the balance factor also take constant time. So the time
complexity of AVL delete remains same as BST delete which is O(h) where h is height of the tree. Since
AVL tree is balanced, the height is O(Logn). So time complexity of AVL delete is O(Log n).
Heap Data Structure

 Heap data structure is a specialized binary tree-based data structure. Heap is a binary tree with special
characteristics.
 In a heap data structure, nodes are arranged based on their values. A heap data structure sometimes also
called as Binary Heap.
 Generally, Heaps can be of two types:
1. Max-Heap: In a Max-Heap the key present at the root node must be greatest among the keys present
at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

2. Min-Heap: In a Min-Heap the key present at the root node must be minimum among the keys present
at all of it’s children. The same property must be recursively true for all sub-trees in that Binary Tree.

Applications of Heaps:
i. Heap Sort: Heap Sort uses Binary Heap to sort an array in O(nLogn) time.
ii. Priority Queue: Priority queues can be efficiently implemented using Binary Heap because it supports
insert(), delete() and extractmax(), decreaseKey() operations in O(logn) time. Binomoial Heap and
Fibonacci Heap are variations of Binary Heap. These variations perform union also efficiently.
iii. Graph Algorithms: The priority queues are especially used in Graph Algorithms like Dijkstra’s Shortest
Path and Prim’s Minimum Spanning Tree.

Operations on Max Heap

The following operations are performed on a Max heap data structure...

1. Finding Maximum
2. Insertion
3. Deletion

1. Finding Maximum Value Operation in Max Heap

 Finding the node which has maximum value in a max heap is very simple.
 In a max heap, the root node has the maximum value than all other nodes. So, directly we can display root
node value as the maximum value in max heap.
2. Insertion Operation in Max Heap
 Insertion Operation in max heap is performed as follows…
Algorithm to perform Insert in a Max Heap
Step – 1: Insert the new_node as last leaf from left to right.
Step – 2: Compare new_node value with its Parent node.
Step – 3: If new_node value is greater than its parent, then swap both of them.
Step – 4: Repeat step – 2 and step – 3 until new_node value is less than its parent node (or) new_node
reaches to root.
Example: Consider the above max heap. Insert a new_node with value 85.
Step – 1: Insert the new_node with value 85 as last
leaf from left to right. That means new_node is
added as a right child of node with value 75. After
adding max heap is as follows...

Step – 2: Compare new_node value (85) with its Step – 3: Here new_node value (85) is greater than
Parent node value (75). That means 85 > 75 its parent value (75), then swap both of them. After
swapping, max heap is as follows...

Step – 4: Now, again compare new_node value (85) Here, new_node value (85) is smaller than its parent node value
with its parent node value (89). (89). So, we stop insertion process. Finally, max heap after
insertion of a new node with value 85 is as follows...
3. Deletion Operation in Max Heap
 In a max heap, deleting the last node is very simple as it does not disturb max heap properties.
 Deleting root node from a max heap is little difficult as it disturbs the max heap properties.
 The following steps are used to delete the root node from a max heap...
Algorithm to delete the root node from a Max Heap
Step – 1: Swap the root node with last node in max heap
Step – 2: Delete last node.
Step – 3: Now, compare root value with its left child value.
Step – 4: If root value is smaller than its left child, then compare left child with its right sibling. Else
goto Step – 6.
Step – 5: If left child value is larger than its right sibling, then swap root with left child otherwise swap
root with its right child.
Step – 6: If root value is larger than its left child, then compare root value with its right child value.
Step – 7: If root value is smaller than its right child, then swap root with right child otherwise stop the
process.
Step – 8: Repeat the same until root node fixes at its exact position.
Example: Consider the max heap. Delete root node (90) from the max heap.
Step – 1: Swap the root node (90) with last node
75 in max heap. After swapping max heap is as
follows...

Step – 2: Delete last node. Here the last node is 90. Step – 3: Compare root node (75) with its left
After deleting node with value 90 from heap, max child (89).
heap is as follows...

Here, root value (75) is smaller than its left child Step – 4: Here, left child value (89) is larger than
value (89). So, compare left child (89) with its its right sibling (70), So, swap root (75) with left
right sibling (70). child (89).
Step – 5: Now, again compare 75 with its left child Here, node with value 75 is larger than its left
(36). child. So, we compare node 75 with its right child
85.

Step – 6: Here, node with value 75 is smaller than Step – 7: Now, compare node with value 75 with
its right child (85). So, we swap both of them. its left child (15).
After swapping max heap is as follows...

Here, node with value 75 is larger than its left child

(15) and it does not have right child. So we stop
the process.
Finally, max heap after deleting root node (90) is
as follows...
Unit – V
GRAPHS
Introduction to Graphs
 Graph is a non-linear data structure. It contains a set of points known as nodes (or vertices) and a set of
links known as edges (or Arcs). Here edges are used to connect the vertices.
 A graph is defined as follows...
Graph is a collection of vertices and arcs in which vertices are connected with arcs
Graph is a collection of nodes and edges in which nodes are connected with edges
 Generally, a graph G is represented as G = (V, E), where V is set of vertices and E is set of edges.
Example:
 The following is a graph with 5 vertices and 6 edges.
 This graph G can be defined as G = ( V , E )
 Where V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.

Graph Terminology
The following terms are used in graph data structure...
1) Vertex
 Individual data element of a graph is called as Vertex. Vertex is also known as node.
 In above example graph, A, B, C, D & E are known as vertices.

2) Edge
 An edge is a connecting link between two vertices.
 Edge is also known as Arc. An edge is represented as (startingVertex, endingVertex).
 For example, in above graph the link between vertices A and B is represented as (A,B).
 In above example graph, there are 7 edges (i.e., (A,B), (A,C), (A,D), (B,D), (B,E), (C,D), (D,E)).

Edges are three types:

i. Undirected Edge: An undirected edge is a bidirectional edge. If there is undirected edge between
vertices A and B then edge (A, B) is equal to edge (B, A).
ii. Directed Edge: A directed edge is a unidirectional edge. If there is directed edge between vertices
A and B then edge (A, B) is not equal to edge (B, A).
iii. Weighted Edge: A weighted edge is an edge with value (cost) on it.

3) Undirected Graph
 A graph with only undirected edges is said to be undirected graph.
4) Directed Graph
 A graph with only directed edges is said to be directed graph.

5) Mixed Graph
 A graph with both undirected and directed edges is said to be mixed graph.

6) End vertices or Endpoints

 The two vertices joined by edge are called end vertices (or endpoints) of that edge.

7) Origin
 If an edge is directed, its first endpoint is said to be the origin of it.

8) Destination
 If an edge is directed, its first endpoint is said to be the origin of it and the other endpoint is said to
be the destination of that edge.

9) Adjacent
 If there is an edge between vertices A and B then both A and B are said to be adjacent. In other
words, vertices A and B are said to be adjacent if there is an edge between them.

10) Incident
 Edge is said to be incident on a vertex if the vertex is one of the endpoints of that edge.

11) Outgoing Edge

 A directed edge is said to be outgoing edge on its origin vertex

12) Incoming Edge

 A directed edge is said to be incoming edge on its destination vertex.

13) Degree
 Total number of edges connected to a vertex is said to be degree of that vertex.

14) In-degree
 Total number of incoming edges connected to a vertex is said to be in-degree of that vertex.

15) Out-degree
 Total number of outgoing edges connected to a vertex is said to be out-degree of that vertex.

16) Parallel edges or Multiple edges

 If there are two undirected edges with same end vertices and two directed edges with same origin
and destination, such edges are called parallel edges or multiple edges.

17) Self-loop
 Edge (undirected or directed) is a self-loop if its two endpoints coincide with each other.

18) Simple Graph

 A graph is said to be simple if there are no parallel and self-loop edges.
 19) Path
 A path is a sequence of alternate vertices and edges that starts at a vertex and ends at other vertex
such that each edge is incident to its predecessor and successor vertex.

Graph Representations
 Graph data structure is represented using following representations...
1) Adjacency Matrix
2) Incidence Matrix
3) Adjacency List

1) Adjacency Matrix
 In this representation, the graph is represented using a matrix of size total number of vertices by a
total number of vertices.
 That means a graph with 4 vertices is represented using a matrix of size 4X4. In this matrix, both
rows and columns represent vertices.
 This matrix is filled with either 1 or 0.
 Here, 1 represents that there is an edge from row vertex to column vertex and 0 represents that there
is no edge from row vertex to column vertex.
For example, consider the following undirected graph representation...

Consider the following directed graph representation...

2) Incidence Matrix
 In this representation, the graph is represented using a matrix of size total number of vertices by a
total number of edges.
 That means graph with 4 vertices and 6 edges is represented using a matrix of size 4X6.
 In this matrix, rows represent vertices and columns represents edges.
  This matrix is filled with 0 or 1 or -1. Here, 0 represents that the row edge is not connected to
column vertex, 1 represents that the row edge is connected as the outgoing edge to column vertex
and -1 represents that the row edge is connected as the incoming edge to column vertex.

For example, consider the following directed graph representation...

3) Adjacency List
 In this representation, every vertex of a graph contains list of its adjacent vertices.

For example, consider the following directed graph representation implemented using linked list...

This representation can also be implemented using an array as follows…

GRAPH TRAVERSAL
 Graph traversal is a technique used for a searching vertex in a graph.
 The graph traversal is also used to decide the order of vertices is visited in the search process.
 A graph traversal finds the edges to be used in the search process without creating loops.
 That means using graph traversal we visit all the vertices of the graph without getting into looping path.
 There are two graph traversal techniques and they are as follows...
1) DFS (Depth First Search)
2) BFS (Breadth First Search)
1) DFS (Depth First Search)
 DFS traversal of a graph produces a spanning tree as final result.
 Spanning Tree is a graph without loops.
 Stack data structure is used with maximum size of total number of vertices in the graph to
implement DFS traversal.
The following steps are used to implement DFS traversal...
Step – 1: Define a Stack of size total number of vertices in the graph.
Step – 2: Select any vertex as starting point for traversal. Visit that vertex and push it on to the Stack.
Step – 3: Visit any one of the non-visited adjacent vertices of a vertex which is at the top of stack and
push it on to the stack.
Step – 4: Repeat step 3 until there is no new vertex to be visited from the vertex which is at the top of
the stack.
Step – 5: When there is no new vertex to visit then use back tracking and pop one vertex from the stack.
Step – 6: Repeat steps 3, 4 and 5 until stack becomes Empty.
Step – 7: When stack becomes Empty, then produce final spanning tree by removing unused edges from
the graph
Note: Back tracking is coming back to the vertex from which we reached the current vertex.

Example: Consider the following example graph to perform DFS traversal

2) BFS (Breadth First Search)
 BFS traversal of a graph produces a spanning tree as final result.
 Spanning Tree is a graph without loops.
 Queue data structure is used with maximum size of total number of vertices in the graph to
implement BFS traversal.
The following steps are used to implement BFS traversal...
Step – 1: Define a Queue of size total number of vertices in the graph.
Step – 2: Select any vertex as starting point for traversal. Visit that vertex and insert it into the
Queue.
Step – 3: Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue and
insert them into the Queue.
Step – 4: When there is no new vertex to be visited from the vertex which is at front of the Queue
then delete that vertex.
Step – 5: Repeat steps 3 and 4 until queue becomes empty.
Step – 6: When queue becomes empty, then produce final spanning tree by removing unused edges
from the graph
Example: Consider the following example graph to perform BFS traversal
SEARCHING
 Search is a process of finding a key value in a list of values.
 In other words, searching is the process of locating a given key value position in a list of values.
 Searching Algorithms are designed to check for an element or retrieve an element from any data structure
where it is stored.
 Based on the type of search operation, these algorithms are generally classified into two categories:

1) Sequential Search: In this, the list or array is traversed sequentially and every element is checked.
For example: Linear Search.

2) Interval Search: These algorithms are specifically designed for searching in sorted data-structures.
These type of searching algorithms are much more efficient than Linear Search as they repeatedly
target the center of the search structure and divide the search space in half.
For Example: Binary Search.
1. Linear Search Algorithm (Sequential Search Algorithm)
 Linear search algorithm finds a given element in a list of elements with O(n) time complexity where
n is total number of elements in the list.
 This search process starts comparing search element with the first element in the list.
 If both are matched then result is element found otherwise search element is compared with the next
element in the list.
 Repeat the same until search element is compared with the last element in the list, if that last
element also doesn't match, then the result is "Element not found in the list".
 That means, the search element is compared with element by element in the list.
Linear search is implemented using following steps...
Step – 1: Read the search element from the user.
Step – 2: Compare the search element with the first element in the list.
Step – 3: If both are matched, then display "Given element is found!!!" and terminate the function.
Step – 4: If both are not matched, then compare search element with the next element in the list.
Step – 5: Repeat steps 3 and 4 until search element is compared with last element in the list.
Step – 6: If last element in the list also doesn't match, then display "Element is not found!!!" and
terminate the function.
Time Complexity: Linear search algorithm finds a given element in a list of elements with O(n) time
complexity where n is total number of elements in the list.

Example: Consider the following list of elements and the element to be searched...
Implementation of Linear Search Algorithm using C++ Code:
#include<iostream>
using namespace std;

int main(void)
{
int list[20],size,i,sKey;
cout<<"Enter size of the list: ";
cin>>size;

cout<<"Enter any "<<size<<" integer values: ";

for(i = 0; i < size; i++)
cin>>list[i];

cout<<"Enter the element to be Search: ";

cin>>sKey;

// Linear Search Logic

for(i = 0; i < size; i++)
{
if(sKey == list[i])
{
cout<<"Element is found at "<<i<<" index";
break;
}
}
if(i == size)
cout<<"Given element is not found in the list!!!";
 return 0;
}
Output:
Enter size of the list: 5
Enter any 5 integer values: 10 24 72 35 56
Enter the element to be Search: 35
Element is found at 3 index

2. Binary Search Algorithm

 Binary search algorithm finds a given element in a list of elements with O(log n) time complexity
where n is total number of elements in the list.
 The binary search algorithm can be used with only a sorted list of elements.
 That means the binary search is used only with a list of elements that are already arranged in an
order.
 The binary search cannot be used for a list of elements arranged in random order.
 This search process starts comparing the search element with the middle element in the list. If both
are matched, then the result is "element found". Otherwise, we check whether the search element is
smaller or larger than the middle element in the list.
 If the search element is smaller, then we repeat the same process for the left sub-list of the middle
element.
 If the search element is larger, then we repeat the same process for the right sub-list of the middle
element.
 We repeat this process until we find the search element in the list or until we left with a sub-list of
only one element.
 And if that element also doesn't match with the search element, then the result is "Element not
found in the list".
Binary search is implemented using following steps...
Step – 1: Read the search element from the user.
Step – 2: Find the middle element in the sorted list.
Step – 3: Compare the search element with the middle element in the sorted list.
Step – 4: If both are matched, then display "Given element is found!!!" and terminate the function.
Step – 5: If both are not matched, then check whether the search element is smaller or larger than the
middle element.
Step – 6: If the search element is smaller than middle element, repeat steps 2, 3, 4 and 5 for the left
sub-list of the middle element.
Step – 7: If the search element is larger than middle element, repeat steps 2, 3, 4 and 5 for the right
sub-list of the middle element.
Step – 8: Repeat the same process until we find the search element in the list or until sub-list
contains only one element.
Step – 9: If that element also doesn't match with the search element, then display "Element is not
found in the list!!!" and terminate the function.
Time Complexity: Binary search algorithm finds a given element in a list of elements with O(log n)
time complexity where n is total number of elements in the list.

Example: Consider the following list of elements and the element to be searched...
Implementation of Binary Search Algorithm using C++ Code:
#include<iostream>
using namespace std;

int main(void)
{
int first, last, mid, size, i, sKey, list[100];
system("cls"); //clrscr();

cout<<"Enter the size of the list: ";

cin>>size;

cout<<"Enter "<<size<<" integer values in Assending order\n";

for (i = 0; i < size; i++)

cin>>list[i];

cout<<"Enter value to be search: ";

cin>>sKey;

first = 0;
last = size - 1;
mid = (first+last)/2;

while (first <= last)

{
if (list[mid] < sKey)
first = mid + 1;
else if (list[mid] == sKey)
{
cout<<"Element found at index: "<<mid;
break;
 }
else
last = mid - 1;

mid = (first + last)/2;

}
if (first > last)
cout<<"Element Not found in the list.";
return 0;
}
Output:
Enter the size of the list: 5
Enter 5 integer values in Ascending order
10 20 30 40 50
Enter value to be search: 40
Element found at index: 3

SORTING
 Sorting is the process of arranging a list of elements in a particular order (either Ascending or Descending).
 A Sorting Algorithm is used to rearrange a given array or list elements according to a comparison operator
on the elements.
 The comparison operator is used to decide the new order of element in the respective data structure.
 Different algorithms can be used to sort the elements in a list. They are:
1. Selection Sort
2. Bubble Sort
3. Insertion Sort
4. Quick Sort
5. Merge Sort
6. Heap Sort

1. Selection Sort Algorithm:

 Selection Sort algorithm is used to arrange a list of elements in a particular order (Ascending or
Descending).
 In selection sort, the first element in the list is selected and it is compared repeatedly with all the
remaining elements in the list.
 If any element is smaller than the selected element (for ascending order), then both are swapped so
that first position is filled with the smallest element in the sorted order.
 Next, we select the element at a second position in the list and it is compared with all the remaining
elements in the list.
 If any element is smaller than the selected element, then both are swapped.
 This procedure is repeated until the entire list is sorted.
The selection sort algorithm is performed using the following steps...
Step – 1: Select the first element of the list (i.e., Element at first position in the list).
Step – 2: Compare the selected element with all the other elements in the list.
Step – 3: In every comparison, if any element is found smaller than the selected element (for
Ascending order), then both are swapped.
Step – 4: Repeat the same procedure with element in the next position in the list till the entire list is
sorted.
C++ Code for Selection Sort Logic
//Selection sort logic

for(i=0; i<size; i++)

{
for(j=i+1; j<size; j++)
{
if(list[i] > list[j])
{
temp=list[i];
list[i]=list[j];
list[j]=temp;
}
}
}

Example: Consider the following unsorted list of elements

Complexity of the Selection Sort Algorithm
 To sort an unsorted list with 'n' number of elements, we need to make ((n-1)+(n-2)+(n-
3)+......+1) = (n (n-1))/2 number of comparisons in the worst case.
 If the list is already sorted then it requires 'n' number of comparisons.

Worst Case : O(n2)

Best Case : Ω(n2)
Average Case : Θ(n2)

Implementation of Selection Sort Algorithm using C++ Code

#include<iostream>
using namespace std;

int main(void)
{
int size,i,j,temp,list[100];
system("cls"); //clrscr();

cout<<"Enter the size of the List: ";

cin>>size;

cout<<"Enter "<<size<<" integer values: ";

for(i=0; i<size; i++)
cin>>list[i];

//Selection sort logic

for(i=0; i<size; i++)
 {
for(j=i+1; j<size; j++)
{
if(list[i] > list[j])
{
temp=list[i];
list[i]=list[j];
list[j]=temp;
}
}
}

cout<<"List after sorting is: ";

for(i=0; i<size; i++)
cout<<" "<<list[i];
return 0;
}
Output:
Enter the size of the List: 5
Enter 5 integer values: 3 5 1 2 6
List after sorting is: 1 2 3 5 6

2. Bubble Sort Algorithm:

 Bubble Sort is a simple algorithm which is used to sort a given set of n elements provided in form
of an array with n number of elements.
 Bubble Sort compares all the element one by one and sort them based on their values.
 If the given array has to be sorted in ascending order, then bubble sort will start by comparing the
first element of the array with the second element, if the first element is greater than the second
element, it will swap both the elements, and then move on to compare the second and the third
element, and so on.
 If we have total n elements, then we need to repeat this process for n-1 times.
 It is known as bubble sort, because with every complete iteration the largest element in the given
array, bubbles up towards the last place or the highest index, just like a water bubble rises up to the
water surface.
 Sorting takes place by stepping through all the elements one-by-one and comparing it with the
adjacent element and swapping them if required.
The Bubble sort algorithm is performed using the following steps...
Step – 1: Starting with the first element (index = 0), compare the current element with the next
element of the array.
Step – 2: If the current element is greater than the next element of the array, swap them.
Step – 3: If the current element is less than the next element, move to the next element.
Step – 4: Repeat the same procedure with element in the next position in the list till the entire list is
sorted.
C++ Code for Bubble Sort Logic
//Bubble sort logic

for(i = 0; i < size; i++)

{
for(j = 0; j < size-i-1; j++)
{
 if( list[j] > list[j+1])
{
// swap the elements
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}

Example: Consider the following unsorted list of elements

{5, 1, 6, 2, 4, 3}

1, 2, 4, 3, 5, 6 After second Iteration

1, 2, 3, 4, 5, 6 After Third Iteration
1, 2, 3, 4, 5, 6 After Fourth Iteration
1, 2, 3, 4, 5, 6 After Fifth Iteration
The Time complexity for the Bubble Sort algorithm:

Worst Case Time Complexity [ Big-O ]: O(n2)

Best Case Time Complexity [Big-omega]: O(n)
Average Time Complexity [Big-theta]: O(n2)

Implementation of Bubble Sort Algorithm using C++ Code

// A simple C++ program for Bubble Sort
#include <iostream>
using namespace std;
int main(void)
{
 int list[100], i,j, size, temp;

// ask user for number of elements to be sorted

cout<<"Enter the number of elements to be sorted: ";
cin>>size;

// input elements if the array

cout<<"Enter "<<size<<" integer values: ";
for(i = 0; i < size; i++)
cin>>list[i];

//Bubble sort logic

for(i = 0; i < size; i++)
{
for(j = 0; j < size-i-1; j++)
{
if( list[j] > list[j+1])
{
// swap the elements
temp = list[j];
list[j] = list[j+1];
list[j+1] = temp;
}
}
}

// print the sorted array

cout<<"Sorted Array: ";
for(i = 0; i < size; i++)
cout<<" "<<list[i];

return 0;
}
Output:
Enter the number of elements to be sorted: 5
Enter 5 integer values: 6 4 3 1 2
Sorted Array: 1 2 3 4 6

3. Insertion Sort Algorithm

 Insertion sort algorithm arranges a list of elements in a particular order.
 In insertion sort algorithm, every iteration moves an element from unsorted portion to sorted
portion until all the elements are sorted in the list.
 Consider you have 10 cards out of a deck of cards in your hand. And they are sorted, or arranged in
the ascending order of their numbers.
 If I give you another card, and ask you to insert the card in just the right position, so that the cards
in your hand are still sorted. What will you do?
 Well, you will have to go through each card from the starting or the back and find the right position
for the new card, comparing its value with each card. Once you find the right position, you will
insert the card there.
 Similarly, if more new cards are provided to you, you can easily repeat the same process and insert
the new cards and keep the cards sorted too.
 This is exactly how insertion sort works. It starts from the index 1(not 0), and each index starting
from index 1 is like a new card, that you have to place at the right position in the sorted subarray on
the left.

Important characteristics of Insertion Sort:

 It is efficient for smaller data sets, but very inefficient for larger lists.
 Insertion Sort is adaptive, that means it reduces its total number of steps if a partially sorted array is
provided as input, making it efficient.
 It is better than Selection Sort and Bubble Sort algorithms.
 Its space complexity is less. Like bubble Sort, insertion sort also requires a single additional
memory space.
 It is a stable sorting technique, as it does not change the relative order of elements which are equal.

The insertion sort algorithm is performed using the following steps...

Step – 1: Assume that first element in the list is in sorted portion and all the remaining elements
are in unsorted portion.
Step – 2: Take first element from the unsorted portion and insert that element into the sorted
portion in the order specified.
Step – 3: Repeat the above process until all the elements from the unsorted portion are moved
into the sorted portion.
C++ Code for Bubble Sort Logic
//Insertion sort logic
for(i = 1;i<=size-1;i++)
{
temp = list[i];
j = i-1;
while ((temp < list[j]) && (j > 0))
{
list[j] = list[j-1];
j = j - 1;
}
list[j] = temp;
}

Example: Consider the following unsorted list of elements.

Complexity of the Insertion Sort Algorithm
 To sort an unsorted list with 'n' number of elements, we need to make (1+2+3+......+n-1) =
(n (n-1))/2 number of comparisons in the worst case.
 If the list is already sorted then it requires 'n' number of comparisons.
 Worst Case : O(n2)
Best Case : Ω(n)
Average Case : Θ(n2)

Implementation of Insertion Sort Algorithm using C++ Code:

#include<iostream>
using namespace std;
int main(void)
{
int size, i, j, temp, list[100];
cout<<"Enter the size of the list: ";
cin>>size;

cout<<"Enter "<<size<<" integer values: ";

for (i = 0; i < size; i++)
cin>>list[i];

//Insertion sort logic

for (i = 1; i < size; i++)
{
temp = list[i];
j = i - 1;
while ((temp < list[j]) && (j >= 0))
{
list[j + 1] = list[j];
j = j - 1;
}
list[j + 1] = temp;
}

cout<<"List after Sorting is: ";

for (i = 0; i < size; i++)
cout<<" "<<list[i];
return 0;
}
Output:
Enter the size of the list: 5
Enter 5 integer values: 10 2 14 1 15
List after Sorting is: 1 2 10 14 15

4. Quicksort Algorithm
 Quick sort is a fast sorting algorithm used to sort a list of elements.
 Quick sort algorithm is invented by C. A. R. Hoare.
 The quick sort algorithm attempts to separate the list of elements into two parts and then sort each
part recursively. That means it use divide and conquer strategy.
 In quick sort, the partition of the list is performed based on the element called pivot. Here pivot
element is one of the elements in the list.
 The list is divided into two partitions such that "all elements to the left of pivot are smaller than the
pivot and all elements to the right of pivot are greater than or equal to the pivot".

In Quick sort algorithm, partitioning of the list is performed using following steps...
Step – 1: Consider the first element of the list as pivot (i.e., Element at first position in the list).
Step – 2: Define two variables i and j. Set i and j to first and last elements of the list respectively.
Step – 3: Increment i until list[i] > pivot then stop.
Step – 4: Decrement j until list[j] < pivot then stop.
Step – 5: If i < j then exchange list[i] and list[j].
Step – 6: Repeat steps 3, 4 & 5 until i > j.
Step – 7: Exchange the pivot element with list[j] element.
C++ Code for Quick Sort Logic
//Quick Sort Logic
void quickSort(int list[10],int first,int last)
{
int pivot,i,j,temp;
if(first < last)
{
pivot = first;
i = first;
j = last;

while(i < j)
{
while(list[i] <= list[pivot] && i < last)
i++;
while(list[j] && list[pivot])
j--;
if(i < j)
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
temp = list[pivot];
list[pivot] = list[j];
list[j] = temp;
quickSort(list,first,j-1);
quickSort(list,j+1,last);
}
}

Example: Consider the following unsorted list of elements.

Complexity of the Quick Sort Algorithm
 To sort an unsorted list with 'n' number of elements, we need to make ((n-1)+(n-2)+(n-
3)+......+1) = (n (n-1))/2 number of comparisions in the worst case.
 If the list is already sorted, then it requires 'n' number of comparisions.

Worst Case : O(n2)

Best Case : O (n log n)
Average Case : O (n log n)

Implementation of Quick Sort Algorithm using C++ Code

#include<iostream>
using namespace std;

void quickSort(int[],int,int);
int main(void)
{
int list[20],size,i;

cout<<"Enter size of the list: ";

cin>>size;

cout<<"Enter "<<size<<" integer values: ";

for(i = 0; i < size; i++)
cin>>list[i];

quickSort(list,0,size-1);

cout<<"List after sorting is: ";

for(i = 0; i < size; i++)
cout<<" "<<list[i];

return 0;
}

void quickSort(int list[],int first,int last)

{
int pivot,i,j,temp;

if(first < last)

{
pivot = first;
i = first;
j = last;

while(i < j)
{
 while(list[i] <= list[pivot] && i < last)
i++;
while(list[j] > list[pivot])
j--;
if(i <j)
{
temp = list[i];
list[i] = list[j];
list[j] = temp;
}
}
temp = list[pivot];
list[pivot] = list[j];
list[j] = temp;
quickSort(list,first,j-1);
quickSort(list,j+1,last);
}
}
Output:
Enter size of the list: 5
Enter 5 integer values: 12 3 42 2 1
List after sorting is: 1 2 3 12 42

5. Merge Sort Algorithm

 Merge Sort follows the rule of Divide and Conquer to sort a given set of numbers/elements,
recursively, hence consuming less time.
 Merge sort runs in O(n*log n) time in all the cases.

Divide and Conquer

 If we can break a single big problem into smaller sub-problems, solve the smaller sub-problems and
combine their solutions to find the solution for the original big problem, it becomes easier to solve
the whole problem.
 In Merge Sort, the given unsorted array with n elements, is divided into n subarrays, each having
one element, because a single element is always sorted in itself.
 Then, it repeatedly merges these subarrays, to produce new sorted subarrays, and in the end, one
complete sorted array is produced.
 The concept of Divide and Conquer involves three steps:
I. Divide the problem into multiple small problems.
II. Conquer the sub-problems by solving them. The idea is to break down the problem into
atomic sub-problems, where they are actually solved.
III. Combine the solutions of the sub-problems to find the solution of the actual problem.
In merge sort we follow the following steps:
Step – 1: Take a variable p and store the starting index of the list in this. And take another
variable r and store the last index of the list in it.
Step – 2: Then, find the middle of the list using the formula (p + r)/2 and mark the middle index
as q, and break the list into two sub-lists, from p to q and from q + 1 to r index.
Step – 3: Then, divide these 2 sub-lists again, just like the above divided main list and this
continues.
Step – 4: Once the complete main list is sub divided into sub-lists with single elements, then start
merging the sub-lists.
C++ Code for Merge Sort Logic
// merge sort function
void mergeSort(int a[], int p, int r)
{
int q;
if(p < r)
{
q = (p + r) / 2;
mergeSort(a, p, q);
mergeSort(a, q+1, r);
merge(a, p, q, r);
}
}

Example: Consider the following unsorted list of elements…

{14, 7, 3, 12, 9, 11, 6, 12}
The total time for merge-Sort function will become n(log n + 1), which gives us a time
complexity of O(n*log n).

Worst Case Time Complexity [ Big-O ]: O(n*log n)

Best Case Time Complexity [Big-omega]: O(n*log n)
Average Time Complexity [Big-theta]: O(n*log n)

Implementation of Heap Sort Algorithm using C++ Code

#include <iostream>
using namespace std;

// function to merge the subarrays

void merge(int list[], int p, int q, int r)
{
 int temp[5];
int i, j, k;
k = 0;
i = p;
j = q + 1;
while(i <= q && j <= r)
{
if(list[i] < list[j])
{
temp[k++] = list[i++];
}
else
{
temp[k++] = list[j++];
}
}

while(i <= q)
{
temp[k++] = list[i++];
}

while(j <= r)
{
temp[k++] = list[j++];
}

for(i=r; i >= p; i--)

{
list[i] = temp[--k];
}
}

void mergeSort(int list[], int p, int r)

{
int q;
if(p < r)
{
q = (p + r) / 2;
mergeSort(list, p, q);
mergeSort(list, q+1, r);
merge(list, p, q, r);
}
}

int main(void)
{
int list[20],size,i;

cout<<"Enter size of the list: ";

cin>>size;
 cout<<"Enter "<<size<<" integer values: ";
for(i = 0; i < size; i++)
cin>>list[i];

// calling merge sort

mergeSort(list, 0, size - 1);

printf("\nSorted array: \n");

for (i=0; i < size; i++)
cout<<" "<<list[i];
return 0;
}
Output:
Enter size of the list: 5
Enter 5 integer values: 12 3 1 9 8

Sorted array:
1 3 8 9 12

6. Heap Sort Algorithm

 Heap sort is one of the sorting algorithms used to arrange a list of elements in order.
 Heapsort algorithm uses one of the tree concepts called Heap Tree.
 In this sorting algorithm, we use Max Heap to arrange list of elements in Descending order and Min
Heap to arrange list elements in ascending order.

The Heap sort algorithm to arrange a list of elements in ascending order is performed using
following steps...
Step – 1: Construct a Binary Tree with given list of Elements.
Step – 2: Transform the Binary Tree into Min Heap.
Step – 3: Delete the root element from Min Heap using Heapify method.
Step – 4: Put the deleted element into the Sorted list.
Step – 5: Repeat the same until Min Heap becomes empty.
Step – 6: Display the sorted list.

Consider the following list of unsorted elements which are to be sorted using heap sort:
 Complexity of the Heap Sort Algorithm

To sort an unsorted list with 'n' number of elements, following are the complexities...

Worst Case : O(n log n)

Best Case : O(n log n)
Average Case : O(n log n)

HASHING:
 In all search techniques like linear search, binary search and search trees, the time required to search an
element depends on the total number of elements present in that data structure.
 In all these search techniques, as the number of elements increases the time required to search an element
also increases linearly.
 Hashing is another approach in which time required to search an element doesn't depend on the total
number of elements.
 Using hashing data structure, a given element is searched with constant time complexity.
 Hashing is an effective way to reduce the number of comparisons to search an element in a data structure.
 Hashing is defined as follows...
Hashing is the process of indexing and retrieving element (data) in a data structure to provide a faster
way of finding the element using a hash key.

 Here, the hash key is a value which provides the index value where the actual data is likely to be
stored in the data structure.
 In this data structure, we use a concept called Hash table to store data.
 All the data values are inserted into the hash table based on the hash key value.
 The hash key value is used to map the data with an index in the hash table. And the hash key is
generated for every data using a hash function.
  That means every entry in the hash table is based on the hash key value generated using the hash
function.
 Hash Table is defined as follows...

Hash table is just an array which maps a key (data) into the data structure with the help of hash
function such that insertion, deletion and search operations are performed with constant time
complexity (i.e. O(1)).
 Hash tables are used to perform insertion, deletion and search operations very quickly in a data
structure.
 Using hash table concept, insertion, deletion, and search operations are accomplished in constant time
complexity.
 Generally, every hash table makes use of a function called hash function to map the data into the hash
table.
 A hash function is defined as follows...

Hash function is a function which takes a piece of data (i.e. key) as input and produces an integer
(i.e. hash value) as output which maps the data to a particular index in the hash table.

 Basic concept of hashing and hash table is shown in the following figure...

Example:

Collision handling in hashing:

 Since a hash function gets us a small number for a big key, there is possibility that two keys result in same
value.
 The situation where a newly inserted key maps to an already occupied slot in hash table is called collision
and must be handled using some collision handling technique.
 Following are the ways to handle collisions:
(A) Chaining: The idea is to make each cell of hash table point to a linked list of records that have
same hash function value. Chaining is simple, but requires additional memory outside the table.
 (B) Open Addressing: In open addressing, all elements are stored in the hash table itself. Each table
entry contains either a record or NIL. When searching for an element, we one by one examine table
slots until the desired element is found or it is clear that the element is not in the table.

(A) Separate Chaining:

 The idea is to make each cell of hash table point to a linked list of records that have same hash function
value.

Let us consider a simple hash function as “key mod 7” and sequence of keys as 50, 700, 76, 85, 92, 73,
and 101.

Advantages:
1. Simple to implement.
2. Hash table never fills up, we can always add more elements to the chain.
3. Less sensitive to the hash function or load factors.
4. It is mostly used when it is unknown how many and how frequently keys may be inserted or deleted.
Disadvantages:
1. Cache performance of chaining is not good as keys are stored using a linked list. Open addressing provides
better cache performance as everything is stored in the same table.
2. Wastage of Space (Some Parts of hash table are never used)
 3. If the chain becomes long, then search time can become O(n) in the worst case.
4. Uses extra space for links.
Performance of Chaining:
 Performance of hashing can be evaluated under the assumption that each key is equally likely to be
hashed to any slot of table (simple uniform hashing).
m = Number of slots in hash table
n = Number of keys to be inserted in hash table

Load factor α = n/m

Expected time to search = O(1 + α)
Expected time to insert/delete = O(1 + α)
Time complexity of search insert and delete is O(1) if α is O(1)

(B) Open Addressing

 Like separate chaining, open addressing is a method for handling collisions.
 In Open Addressing, all elements are stored in the hash table itself.
 So at any point, size of the table must be greater than or equal to the total number of keys (Note that we can
increase table size by copying old data if needed).
 Insert(k): Keep probing until an empty slot is found. Once an empty slot is found, insert k.
 Search(k): Keep probing until slot’s key doesn’t become equal to k or an empty slot is reached.
 Delete(k): Delete operation is interesting. If we simply delete a key, then search may fail. So slots of
deleted keys are marked specially as “deleted”.
 Insert can insert an item in a deleted slot, but the search doesn’t stop at a deleted slot.

Open Addressing is done following ways:

a) Linear Probing: In linear probing, we linearly probe for next slot. For example, typical gap between two
probes is 1 as taken in below example also.
let hash(x) be the slot index computed using hash function and S be
the table size:
If slot hash(x) % S is full, then we try (hash(x) + 1) % S
If (hash(x) + 1) % S is also full, then we try (hash(x) + 2) % S
If (hash(x) + 2) % S is also full, then we try (hash(x) + 3) % S
..................................................
..................................................
 Let us consider a simple hash function as “key mod 7” and sequence of keys as 50, 700, 76, 85, 92, 73,
and 101.

b) Quadratic Probing We look for i2‘th slot in i’th iteration.

let hash(x) be the slot index computed using hash function.
If slot hash(x) % S is full, then we try (hash(x) + 1*1) % S
If (hash(x) + 1*1) % S is also full, then we try (hash(x) + 2*2) % S
If (hash(x) + 2*2) % S is also full, then we try (hash(x) + 3*3) % S
..................................................
..................................................

c) Double Hashing We use another hash function hash2(x) and look for i*hash2(x) slot in i’th rotation.

let hash(x) be the slot index computed using hash function.

If slot hash(x) % S is full, then we try (hash(x) + 1*hash2(x)) % S
If (hash(x) + 1*hash2(x)) % S is also full, then we try (hash(x) + 2*hash2(x)) % S
If (hash(x) + 2*hash2(x)) % S is also full, then we try (hash(x) + 3*hash2(x)) % S
..................................................
..................................................
Comparison of above three Open Addressing Techniques:
 Linear probing has the best cache performance but suffers from clustering. One more advantage of
linear probing is easy to compute.
 Quadratic probing lies between the two in terms of cache performance and clustering.
 Double hashing has poor cache performance but no clustering. Double hashing requires more
computation time as two hash functions need to be computed.
S. No. Separate Chaining Open Addressing

Open Addressing requires more

1. Chaining is Simpler to implement. computation.

In chaining, Hash table never fills up, we In open addressing, table may become
2. can always add more elements to chain. full.

Chaining is Less sensitive to the hash Open addressing requires extra care
3. function or load factors. for to avoid clustering and load factor.

Chaining is mostly used when it is Open addressing is used when the

unknown how many and how frequently frequency and number of keys is
4. keys may be inserted or deleted. known.

Open addressing provides better cache

Cache performance of chaining is not good performance as everything is stored in
5. as keys are stored using linked list. the same table.

Wastage of Space (Some Parts of hash In Open addressing, a slot can be used
6. table in chaining are never used). even if an input doesn’t map to it.

7. Chaining uses extra space for links. No links in Open addressing

Performance of Open Addressing:

 Like Chaining, the performance of hashing can be evaluated under the assumption that each key is
equally likely to be hashed to any slot of the table (simple uniform hashing)

m = Number of slots in the hash table

n = Number of keys to be inserted in the hash table
Load factor α = n/m ( < 1 )
Expected time to search/insert/delete < 1/(1 - α)
So Search, Insert and Delete take (1/(1 - α)) time