DATA STRUCTURES USING C

BCA IISEM
Unit:1 Basic Concepts

Algorithm
 What is an Algorithm?
An algorithm is a finite sequence of unambiguous instructions to solve a
particular problem.
Input. Zero or more quantities are externally supplied.
 Output. At least one quantity is produced.
 Definiteness. Each instruction is clear and unambiguous. It must be
perfectly clear what should be done.
 Finiteness. If we trace out the instruction of an algorithm, then for all
cases, the algorithm terminates after a finite number of steps.
 Effectiveness. Every instruction must be very basic so that it can be
carried out, in principle, by a person using only pencil and paper. It is
not enough that each operation be definite as in criterion c; it also
must be feasible.

 Algorithm Specification
An algorithm can be specified in
 Simple English
 Graphical representation like flow chart
 Programming language like c++/java
 Combination of above methods.

What is Performance Analysis of an algorithm?

✓ Suppose if we want to go from city "A" to city "B", there can be many ways of
doing this. We can go by flight, by bus, by train and also by bicycle. Depending
on the availability and convenience, we choose the one which suits us.
✓ Similarly, in computer science, there are multiple algorithms to solve a
problem. When we have more than one algorithm to solve a problem, we need
to select the best one. Performance analysis helps us to select the best
algorithm from multiple algorithms to solve a problem.
✓ When there are multiple alternative algorithms to solve a problem, we analyze
them and pick the one which is best suitable for our requirements.
Generally, the performance of an algorithm depends on the following elements...
➢ Whether that algorithm is providing the exact solution for the problem?
➢ Whether it is easy to understand?
➢ Whether it is easy to implement?
➢ How much space (memory) it requires to solve the problem?
➢ How much time it takes to solve the problem? Etc.,
Performance analysis of an algorithm is performed by using the following measures...
• Space required to complete the task of that algorithm (Space Complexity). It includes
program space and data space
▪ Time required to complete the task of that algorithm (Time Complexity)
What is Space complexity?
For any algorithm, memory is required for the following purposes...
[Link] store constant values.
[Link] store program instructions.
[Link] store variable values.
[Link] for few other things like function calls, jumping statements etc,.
Space complexity of an algorithm can be defined as follows...
Total amount of computer memory required by an algorithm to complete its execution is
called as space complexity of that algorithm.
Consider the following example
ntint square(int a)
{
return a * a;
}
It requires 2 bytes of memory to store variable 'a' and another 2 bytes of memory is
used for return value.
Totally it requires 4 bytes of memory to complete its execution. And this 4 bytes of
memory is fixed for any input value of 'a'.
This space complexity is said to be Constant
Space Complexity.
Consider the following example
int sum(int A[ ], int n)
{ int sum = 0, i;
for(i = 0; i < n; i++)
sum = sum + A[i];
return sum; }
'n*2' bytes of memory to store array variable 'a[ ]'
2 bytes of memory for integer parameter 'n'
4 bytes of memory for local integer variables 'sum' and 'i' (2 bytes each)
2 bytes of memory for return value. totally it requires '2n+8' bytes of memory to complete
its execution. Here, the total amount of memory required depends on the value of 'n'. As 'n'
value increases the space required also increases proportionately. This type of space
complexity is said to be Linear Space Complexity.
What is Time complexity?
The time complexity of an algorithm is the total amount of time required by an algorithm to
complete its execution.
• To calculate exact Time complexity of program is very difficult task.
• So a rough estimate can possible with help of Active operation in program.
• The total number of active operations is defined as its frequency count
• After calculating the frequency count the Time complexity is expressed using an
asymptotic notation.
Example
a=a=a+b; This statements executes 1 time thus its frequency count is =1
for(i=1;i<=n;i++)
a=a*b;
This statements executes n time thus its frequency count is =n
for(i=1;i<=m;++i)
for(j=1;j<=n;j++)
a=a*b
This statements executes m*n time thus its frequency count is m~n=n2

Asymptotic Notations
What is Asymptotic Notation?
Whenever we want to perform analysis of an algorithm, we need to calculate the
complexity of that algorithm. But when we calculate the complexity of an algorithm it does
not provide the exact amount of resource required. So instead of taking the exact amount of
resource, we represent that complexity in a general form (Notation) which produces the
basic nature of that algorithm. We use that general form (Notation) for analysis process.
Asymptotic notation of an algorithm is a mathematical representation of its complexity

There are mainly three asymptotic notations:

Big-O Notation (O-notation)

Omega Notation (Ω-notation)
Theta Notation (Θ-notation)

1. Theta Notation (Θ-Notation):

Theta notation encloses the function from above and below. Since it represents the upper
and the lower bound of the running time of an algorithm, it is used for analyzing the
average-case complexity of an algorithm.

.Theta (Average Case) You add the running times for each possible input combination
and take the average in the average case.

Let g and f be the function from the set of natural numbers to itself. The function f is said
to be Θ(g), if there are constants c1, c2 > 0 and a natural number n0 such that c1* g(n) ≤
f(n) ≤ c2 * g(n) for all n ≥ n0

Mathematical Representation of Theta notation:

Θ (g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 ≤ c1 * g(n) ≤ f(n)
≤ c2 * g(n) for all n ≥ n0}

Note: Θ(g) is a set

The above expression can be described as if f(n) is theta of g(n), then the value f(n) is
always between c1 * g(n) and c2 * g(n) for large values of n (n ≥ n0). The definition of
theta also requires that f(n) must be non-negative for values of n greater than n0.

The execution time serves as both a lower and upper bound on the algorithm's time
complexity.

It exist as both, most, and least boundaries for a given input value.

A simple way to get the Theta notation of an expression is to drop low-order terms and
ignore leading constants. For example, Consider the expression 3n3 + 6n2 + 6000 =
Θ(n3), the dropping lower order terms is always fine because there will always be a
number(n) after which Θ(n3) has higher values than Θ(n2) irrespective of the constants
involved. For a given function g(n), we denote Θ(g(n)) is following set of functions.

Examples :

{ 100 , log (2000) , 10^4 } belongs to Θ(1)

{ (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Θ(n)
{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Θ( n2)

Note: Θ provides exact bounds.

2. Big-O Notation (O-notation):

Big-O notation represents the upper bound of the running time of an algorithm.
Therefore, it gives the worst-case complexity of an algorithm.

.It is the most widely used notation for Asymptotic analysis.

.It specifies the upper bound of a function.
.The maximum time required by an algorithm or the worst-case time complexity.
.It returns the highest possible output value(big-O) for a given input.
.Big-O(Worst Case) It is defined as the condition that allows an algorithm to complete
statement execution in the longest amount of time possible.

If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive
constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0

It returns the highest possible output value (big-O)for a given input.

The execution time serves as an upper bound on the algorithm's time complexity.

Mathematical Representation of Big-O Notation:

O(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ f(n) ≤ cg(n) for all n
≥ n0 }

For example, Consider the case of Insertion Sort. It takes linear time in the best case and
quadratic time in the worst case. We can safely say that the time complexity of the
Insertion sort is O(n2).
Note: O(n2) also covers linear time.

If we use Θ notation to represent the time complexity of Insertion sort, we have to use
two statements for best and worst cases:

The worst-case time complexity of Insertion Sort is Θ(n2).

The best case time complexity of Insertion Sort is Θ(n).
The Big-O notation is useful when we only have an upper bound on the time complexity
of an algorithm. Many times we easily find an upper bound by simply looking at the
algorithm.

Examples :

{ 100 , log (2000) , 10^4 } belongs to O(1)

U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to O(n)
U { (n^2+n) , (2n^2) , (n^2+log(n))} belongs to O( n^2)

Note: Here, U represents union, we can write it in these manner because O provides exact
or upper bounds .

3. Omega Notation (Ω-Notation):

Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.

The execution time serves as a lower bound on the algorithm's time complexity.

It is defined as the condition that allows an algorithm to complete statement execution in

the shortest amount of time.
Let g and f be the function from the set of natural numbers to itself. The function f is said
to be Ω(g), if there is a constant c > 0 and a natural number n0 such that c*g(n) ≤ f(n) for
all n ≥ n0

Mathematical Representation of Omega notation :

Ω(g(n)) = { f(n): there exist positive constants c and n0 such that 0 ≤ cg(n) ≤ f(n) for all n
≥ n0 }

Let us consider the same Insertion sort example here. The time complexity of Insertion
Sort can be written as Ω(n), but it is not very useful information about insertion sort, as
we are generally interested in worst-case and sometimes in the average case.

Examples :

{ (n^2+n) , (2n^2) , (n^2+log(n))} belongs to Ω( n^2)

U { (n/4) , (2n+3) , (n/100 + log(n)) } belongs to Ω(n)
U { 100 , log (2000) , 10^4 } belongs to Ω(1)

Note: Here, U represents union, we can write it in these manner because Ω provides exact
or lower bounds.

Data Structure:

INTRODUCTION TO DATA STRUCTURES

A data structure is a special way of organizing and storing data in a computer so that it
can be used efficiently. Array, Linked List, Stack, Queue, Tree, Graph etc. are all data
structures that stores the data in a special way so that we can access and use the data
efficiently. We have two types of data structures:
Classification of Data Structure:

Data Structures are normally classified into two categories.

 Primitive Data Structure

 Non-primitive data Structure

 Primitive Data Structure:

Primitive data structures are basic structures and are directly operated upon by machine
instructions. Primitive data structures have different representations on different
computers. These data types are available in most programming languages as built in
type.
 Integer: It is a data type which allows all values without fraction part. We can use it
for whole numbers.
 Float: It is a data type which use for storing fractionalnumbers.
 Character: It is a data type which is used for charactervalues.
 Pointer: A variable that holds memory address of another variable are called pointer.
 Non Primitive Data Structure:
These are more sophisticated data structures. These are derived from primitive data
structures. The non-primitive data structures emphasize on structuring of a group of
homogeneous or heterogeneous data items.

A Non-primitive data type is further divided into Linear and Non-Linear data structure.

 Linear Data Structure:

If a data structure is organizing the data in sequential order, then that data structure is
called as Linear Data Structure.
 Array: An array is defined as the collection of similar type of data items stored at
contiguous memory locations.
 Stack: Stack is a Linear Data structure in which, insertion and deletion operations are
performed at one end only. Stack is also called as Last in First out (LIFO) data structure.
The insertion operation is referred to as ‘PUSH’ and deletion operation is referred to as
‘POP’ operation.
 Queue: The data structure which allow the insertion at one end and Deletion at
another end, known as Queue. End at which deletion is occurs is known as FRONT end
and another end at which insertion occurs is known as REAR end. Queue is also called as
First in First out (FIFO) data structure.
 Linked list: Linked List is a linear data structure. Unlike arrays, linked list elements
are not stored at a contiguous location the elements are linked using pointers.
 Non-Linear Data Structure:

Nonlinear data structures are those data structure in which data items are not arranged in
a sequence. Examples of Non-linear Data Structure are Tree and Graph.
 Tree: A tree can be defined as finite set of data items (nodes) in which data items are
arranged in branches and sub branches according to requirement.
 Graph: Graph is a collection of nodes (Information) and connecting edges (Logical
relation) between nodes.

Data types in C:

A Data type is a set of values along with a set of rules for allowed operations. ‘C’
supports several data types of data each of which is stored differently in the computer’s
memory mainly data types are divided into three types.

 Primitive Data type:

‘C’ supports mainly four primitive datatypes.
 Character Data Type
 Integer Data Type
 Float Data Type
 Double Data Type
 Void Data Type
 Character Data Type:

The character data type accepts single character only. Characters are either signed or
unsigned. But mostly characters are used an unsigned type. The size of the character data
type is 1 byte in the memory. The range of unsigned character is 0to 255. The range of
signed are character is – 128 to + 127. Char is the keyword of the character data type.

Syntax: char list of variables;

E.g. char ch1, ch2, ch3;

 Integer Data Type:

An integer type accepts integer values only. It does not contains any real or float values.
The range of an integer variable is -32, 768 to +327,67. int is the keyword for integer
data type. In generally 2 bytes of memory is required to store an integer value.

Syntax: int list of variables;

E. g: int a, b, c;

 Float Data Type:

The float data type accepts real values it can contains any floating point values. The range
of the floating variable is 3.4E – 38 to 3.4E + 38. Float is the keyword for floating Data
type. In generally 4 bytes of memory is required to store an float value with 6 digits of
precision.
Syntax: float list of variable;

E.g. float f1, f2, f3;

 Double Data Type :

The double data type accepts large floating value. The range of the double variable is1.7E
– 308 to 1.7E + 308. Double is the key word for double data type. In generally 8 bytes of
memory is required to store double value.

Syntax: double list of variables;

E.g. double d, e, f;

 Void Data type: Void is an empty data type that has no value. . The void keyword
specifies that the function does not return a value.
 DerivedData Types:

Derived data types are derived from the primary data types. The derived data types may
be used for representing a single or multiple values. These are called secondary data type.
The derived data types are arrays, pointers, functions, etc.
 Array: An array is defined as the collection of similar type of data items stored at
contiguous memory locations.
 Pointer: A pointer is a variable that stores the address of another variable.
 Function: A function is a group of statements that together perform a task. Every C
program has at least one function, which is main().

3. User Defined Data type:

C allows the feature called which allows programmers to define their identifier that
would represent an existing data type. There are three such types:
 Enum: Enumeration is a special data type that consists of integral constants, and each
of them is assigned with a specific name. "enum" keyword is used to define the
enumerated data type.
 Structure: It is a package of variables of different types under a single name. This is
done to handle data efficiently. "struct" keyword is used to define a structure.
 Union: These allow storing various data types in the same memory location.
Programmers can define a union with different members, but only a single member can
contain a value at a given time.

Linear Data Structure:

If a data structure is organizing the data in sequential order, then that data structure is
called as Linear Data Structure.
 Array: An array is defined as the collection of similar type of data items stored at
contiguous memory locations.
 Stack: Stack is a Linear Data structure in which, insertion and deletion operations are
performed at one end only. Stack is also called as Last in First out (LIFO) data structure.
The insertion operation is referred to as ‘PUSH’ and deletion operation is referred to as
‘POP’ operation.
 Queue: The data structure which allow the insertion at one end and Deletion at
another end, known as Queue. End at which deletion is occurs is known as FRONT end
and another end at which insertion occurs is known as REAR end. Queue is also called as
First in First out (FIFO) data structure.
 Linked list: Linked List is a linear data structure. Unlike arrays, linked list elements
are not stored at a contiguous location the elements are linked using pointers.

Non-Linear Data Structure:

Nonlinear data structures are those data structure in which data items are not arranged
in a sequence. Examples of Non-linear Data Structure are Tree and Graph.
 Tree: A tree can be defined as finite set of data items (nodes) in which data items are
arranged in branches and sub branches according to requirement.
 Graph: Graph is a collection of nodes (Information) and connecting edges (Logical
relation) between nodes.

Abstract Data Type:

Abstract Data type (ADT) is a type (or class) for objects whose behaviour 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, and 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. Now we’ll define three ADTs namely List ADT,
Stack ADT, Queue ADT.

Operations on ADT:

 Find (key): Return a record with the given key or null if no record with the given
key.

 Insert (key, data): Insert a new record with the given key and error if the dictionary
already contains a record with the given key.
 Remove (key): Removes the record with the given key and error if there is no record
with the given key.

C Programming Tips:
C is one of the most important and widely used of all programming languages. It is a
powerful language that can be used not only to build general-purpose applications but
also to write “low-level” programs that interact very closely with the computer hardware.
Experienced C programmers have all kinds of tricks to make the most of the C language.
Here is a list of the top 10 tips for both new and experienced C programmers.
 Function pointers
Sometimes it is useful to store a function in a variable. This isn’t a technique that is
normally used in day-to-day programming, but it can be used to increase the modularity
of a program by, for example, storing the function to be used in handling an event in the
event’s data (or control) structure.
 Variable-length argument lists
Normally you declare a function to take a fixed number of arguments. But it is also
possible to define functions capable of taking variable numbers of arguments. The
standard C function printf() is a function of this sort.
 Testing and setting individual bits
Manipulating the individual bits of items such as integers is sometimes considered to be a
dark 6 art used by advanced programmers. It’s true that setting individual bit values can
seem a rather obscure procedure. But it can be useful, and it is a technique that is well
worth knowing.
 Short circuit operators
C’s logical operators, && (“and”) and || (“or”), let you chain together conditions when
you want to take some action only when all of a set of conditions are true (&&) or when
any one set of conditions is true (||). But C also provides the & and | operators.
 Ternary operators
A ternary operation is one that takes three arguments. In C the ternary operator (? can be
used as a shorthand way of performing if else tests.
 Stacks – pushing and popping
A “stack” is a last-in, first-out storage system. You can use address arithmetic to add
elements to a stack (pushing) or remove elements from the stack (popping). When
programmers refer to “the stack”, they typically mean the structure that is used by the C
compiler to store local Variables declared inside a function.
 Copying data
Here are three ways of copying data. The first uses the standard C function, memcpy(),
which copies n bytes from the src to the dst buffer.
 Testing for header inclusion
C uses “header” (“.h”) files that may contain declarations of functions and constants. A
header file may be included in a C code file by importing it using its name between angle
brackets when it is one of the headers supplied with your compiler (#include < string.h >)
or between double-quotes when it is a header that you have written: (#include
“mystring.h”).
 Parentheses – to use or not to use?
A competent and experienced C programmer will neither overuse nor underuse
parentheses the round bracket delimiters “(” and “)”. But what exactly is the correct way
to use parentheses?

 Arrays as addresses
Programmers who come to C from another language frequently get confused when C
treats an array as an address and vice versa. C is correct: an array is just the base address
of a block of memory, and the array notation you may have come across when learning a
language, such as Java or JavaScript, is merely syntactic sugar.

Array:
An array is a special type of variable used to store multiple values of same data type at a
time.
(Or)
An array is a collection of similar data items stored in continuous memory locations
with single name.
In c programming language, arrays are classified into two types. They are as follows...

 Single Dimensional Array / One Dimensional Array

 Two-Dimensional Array
 Single Dimensional Array:
In c programming language, single dimensional arrays are used to store list of values of
same data type. In other words, single dimensional arrays are used to store a row of
values. In single dimensional array, data is stored in linear form. Single dimensional
arrays are also called as one-dimensional arrays, Linear Arrays or simply 1-D Arrays.

Declaration of Single Dimensional Array

We use the following general syntax for declaring a single dimensional array...

Syntax :datatype arrayName [ size ] ;

Example Code:int rollNumbers [60] ;

The above declaration of single dimensional array reserves 60 continuous memory
locations of 2 bytes each with the name roll Numbers and tell the compiler to allow only
integer values into those memory locations.
Initialization of Single Dimensional Array

We use the following general syntax for declaring and initializing a single dimensional
array with size and initial values.

Syntax:datatype arrayName [ size ] = {value1, value2, ...} ;

Example Code: int marks [6] = { 89, 90, 76, 78, 98, 86 } ;
The above declaration of single dimensional array reserves 6 contiguous memory
locations of 2 bytes each with the name marks and initializes with value 89 in first
memory location, 90 in second memory location, 76 in third memory location, 78 in
fourth memory location, 98 in fifth memory location and 86 in sixth memory location.

We can also use the following general syntax to initialize a single dimensional array
without specifying size and with initial values...

datatype arrayName [ ] = {value1, value2, ...} ;

The array must be initialized if it is created without specifying any size. In this case, the
size of the array is decided based on the number of values initialized.

Example Code: int marks [] = { 89, 90, 76, 78, 98, 86 } ;

char studentName [] = "btechsmartclass" ;

In the above example declaration, size of the array 'marks' is 6 and the size of the array
'studentName' is 16. This is because in case of character array, compiler stores one extra
character called \0 (NULL) at the end.
Accessing Elements of Single Dimensional Array

In c programming language, to access the elements of single dimensional array we use

array name followed by index value of the element that to be accessed. Here the index
value must be enclosed in square braces. Index value of an element in an array is the
reference number given to each element at the time of memory allocation. The index
value of single dimensional array starts with zero (0) for first element and incremented by
one for each element. The index value in an array is also called as subscript or indices.

We use the following general syntax to access individual elements of single dimensional
array...

Syntax:arrayName [ indexValue ] Example Code: marks [2] = 99 ;

In the above statement, the third element of 'marks' array is assigned with value '99'.

 Two Dimensional Array:

The 2-D arrays are used to store data in the form of table. We also use 2-D arrays to
create mathematical matrices.
Declaration of Two Dimensional Array
We use the following general syntax for declaring a two dimensional array...

Syntax:datatype arrayName [ row Size ] [ column Size ] ;

Example Code:int matrixA [2][3] ;

The above declaration of two dimensional array reserves 6 continuous memory locations
of 2 bytes each in the form of 2 rows and 3 columns.
Initialization of Two Dimensional Array
We use the following general syntax for declaring and initializing a two dimensional array with
specific number of rows and coloumns with initial values.

datatype arrayName [rows][colmns] = {{r1c1value, r1c2value, ...},{r2c1, r2c2,...}...} ;

Example Code: int matrix A [2][3] = { {1, 2, 3},{4, 5, 6} } ;
The above declaration of two-dimensional array reserves 6 contiguous memory locations
of 2 bytes each in the form of 2 rows and 3 columns. And the first row is initialized with
values 1, 2 & 3 and second row is initialized with values 4, 5 & 6.
We can also initialize as follows...

Example Code

int matrix_A [2][3] = {

{1, 2, 3},
{4, 5, 6}
};
Accessing Individual Elements of Two Dimensional Array
In a c programming language, to access elements of a two-dimensional array we use
array name followed by row index value and column index value of the element that to be
accessed. Here the row and column index values must be enclosed in separate square
braces. In case of the two-dimensional array the compiler assigns separate index values
for rows and columns.

We use the following general syntax to access the individual elements of a two-
dimensional array...

Syntax:arrayName [ rowIndex ] [ columnIndex ]

Example Code:matrix A [0][1] = 10 ;

In the above statement, the element with row index 0 and column index 1 of matrix A
array is assigned with value 10.

One Dimensional Array with an example:

Single Dimensional Array (or) One Dimensional Array

In c programming language, single dimensional arrays are used to store list of values of
same data type. In other words, single dimensional arrays are used to store a row of
values. In single dimensional array, data is stored in linear form. Single dimensional
arrays are also called as one-dimensional arrays, Linear Arrays or simply 1-D Arrays.

Declaration of Single Dimensional Array

We use the following general syntax for declaring a single dimensional array...

Syntax :datatype arrayName [ size ] ;

Example Code:int rollNumbers [60] ;

The above declaration of single dimensional array reserves 60 continuous memory
locations of 2 bytes each with the name roll Numbers and tell the compiler to allow only
integer values into those memory locations.

Initialization of Single Dimensional Array

We use the following general syntax for declaring and initializing a single dimensional
array with size and initial values.

Syntax:datatype arrayName [ size ] = {value1, value2, ...} ;

Example Code: int marks [6] = { 89, 90, 76, 78, 98, 86 } ;
The above declaration of single dimensional array reserves 6 contiguous memory
locations of 2 bytes each with the name marks and initializes with value 89 in first
memory location, 90 in second memory location, 76 in third memory location, 78 in
fourth memory location, 98 in fifth memory location and 86 in sixth memory location.

We can also use the following general syntax to initialize a single dimensional array
without specifying size and with initial values...

datatype arrayName [ ] = {value1, value2, ...} ;

The array must be initialized if it is created without specifying any size. In this case, the
size of the array is decided based on the number of values initialized.

Example Code: int marks [] = { 89, 90, 76, 78, 98, 86 } ; char studentName [] =
"btechsmartclass" ;
In the above example declaration, size of the array 'marks' is 6 and the size of the array
'student Name' is 16. This is because in case of character array, compiler stores one extra
character called \0 (NULL) at the end.

Accessing Elements of Single Dimensional Array

In c programming language, to access the elements of single dimensional array we use

array name followed by index value of the element that to be accessed. Here the index
value must be enclosed in square braces. Index value of an element in an array is the
reference number given to each element at the time of memory allocation. The index
value of single dimensional array starts with zero (0) for first element and incremented by
one for each element. The index value in an array is also called as subscript or indices.

We use the following general syntax to access individual elements of single dimensional
array...
Syntax:arrayName [ indexValue ]
Example Code:marks [2] = 99 ;
In the above statement, the third element of 'marks' array is assigned with value '99'.

Two Dimensional Array with an example:

Two Dimensional Array:

The 2-D arrays are used to store data in the form of table. We also use 2-D arrays to
create mathematical matrices.
Declaration of Two Dimensional Array
We use the following general syntax for declaring a two dimensional array...
Syntax:datatype arrayName [ rowSize ] [ columnSize ] ;

Linked list:
When we want to work with an unknown number of data values, we use a linked list data
structure to organize that data. The linked list is a linear data structure that contains a
sequence of elements such that each element links to its next element in the sequence.
Each element in a linked list is called "Node".

Properties of Linked List

The linked list starts with a HEAD which denotes the starting point or the memory
location of first node.
Linked list ends with the last node pointing to NULL value.
Unlike array the elements are not stored in contiguous memory locations, but are stored
in random location.
Random allocation of memory location helps to add any number of elements to the lined
list.
Linked List does not waste memory space.
Representation of Linked List
A linked list is a chain of nodes, and each node has the following parts:
Data – Stores the information
Next – Stores the address to next node

How is Linked List Stored in the Memory?

The image on your right, shows a chunk of memory locations which range from 1 to 10.
The highlighted
portion contains data. Remember that the nodes of a linked list need not be in consecutive
memory locations. In our example, the nodes for the linked list are stored at addresses 1,
5, 7, 8, and 10.
In the diagram on the right, the variable HEAD is used to hold the address of the first
node. Since HEAD = 1 in this case, the initial data ‘H’ is stored at address 1. The address
of the next node is stored in the corresponding NEXT, which is 5. So we’ll go to address
5 to get the next data item.
E is the second data piece retrieved from address 5. We find the corresponding NEXT to
go to the next node. We receive the next address, 7, from the item in the NEXT, and L as
the data. This operation is repeated until we reach a place where the NEXT item contains
-1 or NULL and this denotes the end of linked list.

Real-life Example of Linked-List Data Structure

Below are some of the example of linked list which you must have come across:

The back and forward button on your browser to access previous and next URL.
Your music playlist, when your play the next song or the last played track.
The file browser on your system which allows you to go back to the previous directory.
Instagram stories of your peers are added as Linked List. Each tap you make on the
screen allows you to traverse through the list.
A few of the most popular applications of Linked Lists are:

Hash tables & Graphs

To maintain a directory of names
Represent sparse matrices
Dynamic memory allocation
Softwares having undo functionality
Implementation of stacks & queues
Implementation of Fibonacci Heap

Difference between Arrays and Linked Lists.

Arrays Linked Lists
Linked List is an ordered collection of
An array is a collection of elements of a
elementsof the same type in which each
similar data type.
element is connected to the next using
pointers.
Random accessing is not possible in linked
Array elements can be accessed
lists. The elements will have to be
randomly using the array index.
accessed sequentially.
New elements can be stored anywhere and a
Data elements are stored in contiguous
reference is created for the new element
locations in memory.
using pointers.
Insertion and Deletion operations are
Insertion and Deletion operations are fast
costlier since the memory locations are
and easy in a linked list.
consecutive and fixed.
Memory is allocated during the compile Memory is allocated during the run-time
time (Static memory allocation). (Dynamic memory allocation).
Size of the array must be specified Size of a Linked list grows/shrinks as and
at the time of array when new elements are
declaration/initialization. inserted/deleted.

Unit-II
Linked List and Types of Linked List:
 Single linked list
 Double linked list
 Circular linked list

 Single Linked list:

Simply a list is a sequence of data, and the linked list is a sequence of data linked with
each other.
The formal definition of a single linked list is as follows...
“Single linked list is a sequence of elements in which every element has link to its
next element in the sequence.”
In any single linked list, the individual element is called as "Node". Every "Node"
contains two fields, data field, and the next field. The data field is used to store actual
value of the node and next field is used to store the address of next node in
the sequence. The graphical representation of a node in a single linked list is as
follows...

Important Points to be Remembered

 In a single linked list, the address of the first node is always stored in a reference
node known as "front" (Sometimes it is also known as "head").
 Always next part (reference part) of the last node must be NULL.
Example

 Double linked list:

In a single linked list, every node has a link to its next node in the sequence. So, we can
traverse from one node to another node only in one direction and we can not traverse
back. We can solve this kind of problem by using a double linked list. A double linked
list can be defined as follows...

“Double linked list is a sequence of elements in which every element has links to its
previous element and next element in the sequence.”
In a double linked list, every node has a link to its previous node and next node. So, we
can traverse forward by using the next field and can traverse backward by using the
previous field. Every node in a double linked list contains three fields and they are shown
in the following figure...

Example

Important Points to be Remembered

 In double linked list, the first node must be always pointed by head.
 Always the previous field of the first node must be NULL.
 Always the next field of the last node must be NULL.

 Circular linked list:

In single linked list, every node points to its next node in the sequence and the last node
points NULL. But in circular linked list, every node points to its next node in the
sequence but the last node points to the first node in the list.
“A circular linked list is a sequence of elements in which every element has a link to
its next element in the sequence and the last element has a link to the first element.”
That means circular linked list is similar to the single linked list except that the last node
points to the first node in the list

Example

Operations on Single Linked List

The following operations are performed on a Single Linked List

 Insertion
 Deletion
 Display

Before we implement actual operations, first we need to set up an empty list. First,
perform the following steps before implementing actual operations.

 Step 1 - Include all the header files which are used in the program.
 Step 2 - Declare all the user defined functions.
 Step 3 - Define a Node structure with two members data and next
 Step 4 - Define a Node pointer 'head' and set it to NULL.
 Step 5 - Implement the main method by displaying operations menu and make
suitable function calls in the main method to perform user selected operation

 Insertion
In a single linked list, the insertion operation can be performed in three ways. They
are as follows...

 Inserting At Beginning of the list

 Inserting At End of the list
 Inserting At Specific location in the list

 Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the single linked
list...

 Step 1 - Create a newNode with given value.

 Step 2 - Check whether list is Empty (head == NULL)
 Step 3 - If it is Empty then, set newNode→next = NULL and head = newNode.
 Step 4 - If it is Not Empty then, set newNode→next = head and head = newNode.

 Inserting At End of the list

We can use the following steps to insert a new node at end of the single linked list...

 Step 1 - Create a newNode with given value and newNode → next as NULL.
 Step 2 - Check whether list is Empty (head == NULL).
 Step 3 - If it is Empty then, set head = newNode.
 Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.

the list (until temp → next is equal to NULL).

 Step 5 - Keep moving the temp to its next node until it reaches to the last node in

 Step 6 - Set temp → next = newNode.

 Inserting At Specific location in the list (After a Node)

We can use the following steps to insert a new node after a node in the single linked list...

 Step 1 - Create a newNode with given value.

 Step 3 - If it is Empty then, set newNode → next = NULL and head = newNode.
 Step 2 - Check whether list is Empty (head == NULL)

 Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.

which we want to insert the newNode (until temp1 → data is equal to location, here
 Step 5 - Keep moving the temp to its next node until it reaches to the node after

location is the node value after which we want to insert the newNode).
 Step 6 - Every time check whether temp is reached to last node or not. If it is
reached to last node then display 'Given node is not found in the list!!! Insertion not

 Step 7 - Finally, Set 'newNode → next = temp → next' and 'temp → next
possible!!!' and terminate the function. Otherwise move the temp to next node.

= newNode'

 Deletion
In a single linked list, the deletion operation can be performed in three ways. They
are as follows...

 Deleting from Beginning of the list

 Deleting from End of the list
 Deleting a Specific Node

 Deleting from Beginning of the list

We can use the following steps to delete a node from beginning of the single linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible'
and terminate the function.
 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with

 Step 4 - Check whether list is having only one node (temp → next == NULL)
head.

 Step 5 - If it is TRUE then set head = NULL and delete temp (Setting Empty list

 Step 6 - If it is FALSE then set head = temp → next, and delete temp.
conditions)

 Deleting from End of the list

We can use the following steps to delete a node from end of the single linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
 Steps 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and

 Step 4 - Check whether list has only one Node (temp1 → next == NULL)
initialize 'temp1' with head.

 Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And terminate the
function. (Setting Empty list condition)

Repeat the same until it reaches to the last node in the list. (until temp1 →
 Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node.

 Step 7 - Finally, Set temp2 → next = NULL and delete temp1.

next == NULL)

 Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the single linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.
 Step 3 - If it is Not Empty then, defines two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.
 Step 4 - Keep moving the temp1 until it reaches to the exact node to be deleted or to
the last node. And every time set 'temp2 = temp1' before moving the 'temp1' to its next
node.
 Step 5 - If it is reached to the last node then display 'Given node not found in the
list! Deletion not possible!!!'. And terminate the function.
 Step 6 - If it is reached to the exact node which we want to delete, then check
whether list is having only one node or not
 Step 7 - If list has only one node and that is the node to be deleted,
then set head = NULL and delete temp1 (free(temp1)).
 Step 8 - If list contains multiple nodes, then check whether temp1 is the first node in
the list (temp1 == head).
 Step 9 - If temp1 is the first node then move the head to the next node (head =

→ next) and delete temp1.

head

 Step 10 - If temp1 is not first node then check whether it is last node in the list

→ next == NULL).
(temp1

 Step 11 - If temp1 is last node then set temp2 → next = NULL and
delete temp1 (free(temp1)).

 Step 12 - If temp1 is not first node and not last node then set temp2 → next =

→ next and delete temp1 (free(temp1)).

temp1

 Display
We can use the following steps to display the elements of a single linked list...

 Step 1 - Check whether list is Empty (head == NULL)

 Step 2 - If it is Empty then, display 'List is Empty!!!' and terminate the function.
 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with

 Step 4 - Keep displaying temp → data with an arrow (--->) until temp reaches to the
head.

 Step 5 - Finally display temp → data with arrow pointing to NULL (temp → data
last node

---
 NULL).

Implementation of single linked list ADT:

Operations on Single Linked List

The following operations are performed on a Single Linked List

Insertion

Deletion

Display

Before we implement actual operations, first we need to set up an empty list. First,
perform the following steps before implementing actual operations.
Step 1 - Include all the header files which are used in the program.

Step 2 - Declare all the user defined functions.

Step 3 - Define a Node structure with two members data and next

Step 4 - Define a Node pointer 'head' and set it to NULL.

Step 5 - Implement the main method by displaying operations menu and make suitable
function calls in the main method to perform user selected operation.

Insertion

In a single linked list, the insertion operation can be performed in three ways. They are as
follows...

Inserting At Beginning of the list

Inserting At End of the list

Inserting At Specific location in the list

Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the single linked
list...

Step 1 - Create a newNode with given value.

Step 2 - Check whether list is Empty (head == NULL)

Step 3 - If it is Empty then, set newNode→next = NULL and head = newNode.

Step 4 - If it is Not Empty then, set newNode→next = head and head = newNode.

Inserting At End of the list

We can use the following steps to insert a new node at end of the single linked list...

Step 1 - Create a newNode with given value and newNode → next as NULL.

Step 2 - Check whether list is Empty (head == NULL).

Step 3 - If it is Empty then, set head = newNode.

Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.

(until temp → next is equal to NULL).

Step 5 - Keep moving the temp to its next node until it reaches to the last node in the list

Step 6 - Set temp → next = newNode.

Inserting At Specific location in the list (After a Node)

We can use the following steps to insert a new node after a node in the single linked list...

Step 1 - Create a newNode with given value.

Step 2 - Check whether list is Empty (head == NULL)

Step 3 - If it is Empty then, set newNode → next = NULL and head = newNode.

Step 4 - If it is Not Empty then, define a node pointer temp and initialize with head.

want to insert the newNode (until temp1 → data is equal to location, here location is the
Step 5 - Keep moving the temp to its next node until it reaches to the node after which we

node value after which we want to insert the newNode).

Step 6 - Every time check whether temp is reached to last node or not. If it is reached to
last node then display 'Given node is not found in the list!!! Insertion not possible!!!' and
terminate the function. Otherwise move the temp to next node.

Step 7 - Finally, Set 'newNode → next = temp → next' and 'temp → next = newNode'

Deletion

In a single linked list, the deletion operation can be performed in three ways. They are as
follows...

Deleting from Beginning of the list

Deleting from End of the list

Deleting a Specific Node

Deleting from Beginning of the list

We can use the following steps to delete a node from beginning of the single linked list...

Step 1 - Check whether list is Empty (head == NULL)

Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.

Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.

Step 4 - Check whether list is having only one node (temp → next == NULL)

Step 5 - If it is TRUE then set head = NULL and delete temp (Setting Empty list
conditions)

Step 6 - If it is FALSE then set head = temp → next, and delete temp.

Deleting from End of the list

We can use the following steps to delete a node from end of the single linked list...

Step 1 - Check whether list is Empty (head == NULL)

Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.

Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.

Step 4 - Check whether list has only one Node (temp1 → next == NULL)

Step 5 - If it is TRUE. Then, set head = NULL and delete temp1. And terminate the
function. (Setting Empty list condition)

Repeat the same until it reaches to the last node in the list. (until temp1 → next ==
Step 6 - If it is FALSE. Then, set 'temp2 = temp1 ' and move temp1 to its next node.

NULL)

Step 7 - Finally, Set temp2 → next = NULL and delete temp1.

Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the single linked list...

Step 1 - Check whether list is Empty (head == NULL)

Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not possible' and
terminate the function.

Step 3 - If it is Not Empty then, define two Node pointers 'temp1' and 'temp2' and
initialize 'temp1' with head.
Step 4 - Keep moving the temp1 until it reaches to the exact node to be deleted or to the
last node. And every time set 'temp2 = temp1' before moving the 'temp1' to its next node.

Step 5 - If it is reached to the last node then display 'Given node not found in the list!
Deletion not possible!!!'. And terminate the function.

Step 6 - If it is reached to the exact node which we want to delete, then check whether list
is having only one node or not

Step 7 - If list has only one node and that is the node to be deleted, then set head = NULL
and delete temp1 (free(temp1)).

Step 8 - If list contains multiple nodes, then check whether temp1 is the first node in the
list (temp1 == head).

Step 9 - If temp1 is the first node then move the head to the next node (head = head →
next) and delete temp1.

Step 10 - If temp1 is not first node then check whether it is last node in the list (temp1 →
next == NULL).

Step 11 - If temp1 is last node then set temp2 → next = NULL and delete temp1
(free(temp1)).

Step 12 - If temp1 is not first node and not last node then set temp2 → next = temp1 →
next and delete temp1 (free(temp1)).

Displaying a Single Linked List

We can use the following steps to display the elements of a single linked list...

Step 1 - Check whether list is Empty (head == NULL)

Step 2 - If it is Empty then, display 'List is Empty!!!' and terminate the function.

Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with head.

Step 4 - Keep displaying temp → data with an arrow (--->) until temp reaches to the last
node

Step 5 - Finally display temp → data with arrow pointing to NULL (temp → data --->
NULL).

Implementation of Single Linked List using C Programming

#include<stdio.h>

#include<conio.h>
#include<stdlib.h>

void insertAtBeginning(int);

void insertAtEnd(int);

void insertBetween(int,int,int);

void display();

void removeBeginning();

void removeEnd();

void removeSpecific(int);

struct Node

int data;

struct Node *next;

}*head = NULL;

void main()

int choice,value,choice1,loc1,loc2;

clrscr();

while(1){

mainMenu: printf("\n\n****** MENU ******\n1. Insert\n2. Display\n3. Delete\

n4. Exit\nEnter your choice: ");

scanf("%d",&choice);

switch(choice)

{
 case 1: printf("Enter the value to be insert: ");

scanf("%d",&value);

while(1){

printf("Where you want to insert: \n1. At Beginning\n2. At End\n3. Between\nEnter

your choice: ");

scanf("%d",&choice1);

switch(choice1)

case 1: insertAtBeginning(value);

break;

case 2: insertAtEnd(value);

break;

case 3: printf("Enter the two values where you wanto insert: ");

scanf("%d%d",&loc1,&loc2);

insertBetween(value,loc1,loc2);

break;

default: printf("\nWrong Input!! Try again!!!\n\n");

goto mainMenu;

goto subMenuEnd;

subMenuEnd:

break;

case 2: display();

break;
 case 3: printf("How do you want to Delete: \n1. From Beginning\n2. From End\
n3. Spesific\nEnter your choice: ");

scanf("%d",&choice1);

switch(choice1)

case 1: removeBeginning();

break;

case 2: removeEnd();

break;

case 3: printf("Enter the value which you wanto delete: ");

scanf("%d",&loc2);

removeSpecific(loc2);

break;

default: printf("\nWrong Input!! Try again!!!\n\n");

goto mainMenu;

break;

case 4: exit(0);

default: printf("\nWrong input!!! Try again!!\n\n");

void insertAtBeginning(int value)

struct Node *newNode;

 newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

if(head == NULL)

newNode->next = NULL;

head = newNode;

else

newNode->next = head;

head = newNode;

printf("\nOne node inserted!!!\n");

void insertAtEnd(int value)

struct Node *newNode;

newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

newNode->next = NULL;

if(head == NULL)

head = newNode;

else

struct Node *temp = head;

 while(temp->next != NULL)

temp = temp->next;

temp->next = newNode;

printf("\nOne node inserted!!!\n");

void insertBetween(int value, int loc1, int loc2)

struct Node *newNode;

newNode = (struct Node*)malloc(sizeof(struct Node));

newNode->data = value;

if(head == NULL)

newNode->next = NULL;

head = newNode;

else

struct Node *temp = head;

while(temp->data != loc1 && temp->data != loc2)

temp = temp->next;

newNode->next = temp->next;

temp->next = newNode;

printf("\nOne node inserted!!!\n");

}

void removeBeginning()

if(head == NULL)

printf("\n\nList is Empty!!!");

else

struct Node *temp = head;

if(head->next == NULL)

head = NULL;

free(temp);

else

head = temp->next;

free(temp);

printf("\nOne node deleted!!!\n\n");

void removeEnd()

if(head == NULL)
 {

printf("\nList is Empty!!!\n");

else

struct Node *temp1 = head,*temp2;

if(head->next == NULL)

head = NULL;

else

while(temp1->next != NULL)

temp2 = temp1;

temp1 = temp1->next;

temp2->next = NULL;

free(temp1);

printf("\nOne node deleted!!!\n\n");

void removeSpecific(int delValue)

struct Node *temp1 = head, *temp2;

while(temp1->data != delValue)
 {

if(temp1 -> next == NULL){

printf("\nGiven node not found in the list!!!");

goto functionEnd;

temp2 = temp1;

temp1 = temp1 -> next;

temp2 -> next = temp1 -> next;

free(temp1);

printf("\nOne node deleted!!!\n\n");

functionEnd:

void display()

if(head == NULL)

printf("\nList is Empty\n");

else

struct Node *temp = head;

printf("\n\nList elements are - \n");

while(temp->next != NULL)

{
printf("%d --->",temp->data);

temp = temp->next;

printf("%d --->NULL",temp->data);

UNIT-III Introduction to Stacks and Queues

STACK:

Stack is a linear data structure in which the insertion and deletion operations are
performed at only one end. In a stack, adding and removing of elements are performed at
a single position which is known as "top". That means, a new element is added at top of
the stack and an element is removed fromthe top of the stack. In stack, the insertion and
deletion operations are performed based on LIFO (Last In First Out) principle.

Operations on a Stack

The following operations are performed on the stack...

 Push (To insert an element on to the stack)

 Pop (To delete an element from the stack)
 Display (To display elements of the stack)

 Push (To insert an element on to the stack)

In a stack, push() is a function used to insert an element into the stack. In a stack, the new
element is always inserted at top position. Push function takes one integer value as
parameter and inserts that value into the stack.

Example

The elements are inserted in the order as A, B, C, D, E, it represents the stack of five
elements. In figure (a), we want to push ‘A’ element on the stack then the top becomes
zero (top=0), similarly the top=1 when ‘B’ element is pushed, top=2 when the ‘C’
element is pushed, top=3 when the ‘D’ element is pushed, and top=4 when the ‘E’
element is pushed.

So whatever the elements we have taken is placed in the stack, now the stack is full. If
you want to push another element there is no place in the stack, so it indicates the
overflow. Now the stack is full if you want to pop the element ‘E’ element has to be
deleted first. The push operation is shown in the below figure.

Fig: Push Operation

 Pop (To delete an element from the stack):

In a stack, pop() is a function used to delete an element from the stack. In a stack, the
element is always deleted from top position.
We have to use the pop operation to delete the elements in the stack. So just mention
pop() don’t write arguments in the pop because by default it deletes the top element. The
first ‘E’ element is deleted next ‘D’ element…..’ A’. When the top elements are deleting
then the top value decreases. When top=-1 the stack indicates underflow. The pop
operation is shown in the below figure.

Fig: POP Operation

So this is the explanation of how the elements are inserted and deleted in the stack by
using push and pop operation.

 Display :

Display() is used to display all the elements in the stack

It displays elements as follows E, D, C, B, A.

Stack using Linked List with an example:

Instead of using array, we can also use linked list to implement stack. Linked list
allocates the memory dynamically. However, time complexity in both the scenario is
same for all the operations i.e. push, pop and peek.

In linked list implementation of stack, the nodes are maintained non-contiguously in the
memory. Each node contains a pointer to its immediate successor node in the stack. Stack
is said to be overflown if the space left in the memory heap is not enough to create a
node.

Stack Operations using Linked List:

 Push (value) - Inserting an element into the Stack

Adding a node to the stack is referred to as push operation. Pushing an element to a stack
in linked list implementation is different from that of an array implementation. In order to
push an element onto the stack, the following steps are involved.

 Create a node first and allocate memory to it.

 If the list is empty then the item is to be pushed as the start node of the list. This
includes assigning value to the data part of the node and assign null to the address part of
the node.
 If there are some nodes in the list already, then we have to add the new element in the
beginning of the list (to not violate the property of the stack). For this purpose, assign the
address of the starting element to the address field of the new node and make the new
node, the starting node of the list.
 Deleting a node from the stack (POP operation)

Deleting a node from the top of stack is referred to as pop operation. Deleting a node
from the linked list implementation of stack is different from that in the array
implementation. In order to pop an element from the stack, we need to follow the
following steps :

 Check for the underflow condition: The underflow condition occurs when we try to
pop from an already empty stack. The stack will be empty if the head pointer of the list
points to null.
 Adjust the head pointer accordingly: In stack, the elements are popped only from
one end, therefore, the value stored in the head pointer must be deleted and the node must
be freed. The next node of the head node now becomes the head node.

 Display the nodes (Traversing)

Displaying all the nodes of a stack needs traversing all the nodes of the linked list
organized in the form of stack. For this purpose, we need to follow the following steps.

 Copy the head pointer into a temporary pointer.

 Move the temporary pointer through all the nodes of the list and print the value
field attached to every node.
Applications of Stack:
 Expression Evaluation and Conversion

 Backtracking

 Parenthesis Checking

 Function Call

 String Reversal

 Syntax Parsing

 Memory Management

Polish Notations
What is an Expression?
An expression is a collection of operators and operands that represents a specific value.
Expression Types
Based on the operator position, expressions are divided into THREE types. They are as
follows...

Infix Expression
Postfix Expression
Prefix Expression
Infix Expression
In infix expression, operator is used in between the operands.

Postfix Expression
In postfix expression, operator is used after operands. We can say that "Operator follows
the Operands".
Prefix Expression
In prefix expression, operator is used before operands. We can say that "Operands
follows the Operator".

Infix to Postfix Conversion

Any expression can be represented using three types of expressions (Infix, Postfix, and
Prefix). We can also convert one type of expression to another type of expression like
Infix to Postfix, Infix to Prefix, Postfix to Prefix and vice versa.

To convert any Infix expression into Postfix or Prefix expression we can use the
following procedure...

Find all the operators in the given Infix Expression.

Find the order of operators evaluated according to their Operator precedence.
Convert each operator into required type of expression (Postfix or Prefix) in the same
order.
Example
Consider the following Infix Expression to be converted into Postfix Expression...
D=A+B*C
Step 1 - The Operators in the given Infix Expression : = , + , *
Step 2 - The Order of Operators according to their preference : * , + , =
Step 3 - Now, convert the first operator * ----- D = A + B C *
Step 4 - Convert the next operator + ----- D = A BC* +
Step 5 - Convert the next operator = ----- D ABC*+ =
Finally, given Infix Expression is converted into Postfix Expression as follows...

DABC*+=
Infix to Postfix Conversion using Stack Data Structure
To convert Infix Expression into Postfix Expression using a stack data structure, We can
use the following steps...

Read all the symbols one by one from left to right in the given Infix Expression.
If the reading symbol is operand, then directly print it to the result (Output).
If the reading symbol is left parenthesis '(', then Push it on to the Stack.
If the reading symbol is right parenthesis ')', then Pop all the contents of stack until
respective left parenthesis is poped and print each poped symbol to the result.
If the reading symbol is operator (+ , - , * , / etc.,), then Push it on to the Stack. However,
first pop the operators which are already on the stack that have higher or equal
precedence than current operator and print them to the result.
Example
Consider the following Infix Expression...

(A+B)*(C-D)
The given infix expression can be converted into postfix expression using Stack data
Structure as follows...

Postfix Expression Evaluation

A postfix expression is a collection of operators and operands in which the operator is
placed after the operands. That means, in a postfix expression the operator follows the
operands.

Postfix Expression has following general structure...

Postfix Expression Evaluation using Stack Data Structure
A postfix expression can be evaluated using the Stack data structure. To evaluate a
postfix expression using Stack data structure we can use the following steps...

Read all the symbols one by one from left to right in the given Postfix Expression
If the reading symbol is operand, then push it on to the Stack.
If the reading symbol is operator (+ , - , * , / etc.,), then perform TWO pop operations and
store the two popped oparands in two different variables (operand1 and operand2). Then
perform reading symbol operation using operand1 and operand2 and push result back on
to the Stack.
Finally! perform a pop operation and display the popped value as final result.
Example
Consider the following Expression...
Queue :
Queue is a linear data structure in which the insertion and deletion operations are
performed at two different ends. In a queue data structure, adding and removing elements
are performed at two different positions. The insertion is performed at one end and
deletion is performed at another end. In a queue data structure, the insertion operation is
performed at a position which is known as 'rear' and the deletion operation is performed
at a position which is known as 'front'. In queue data structure, the insertion and deletion
operations are performed based on FIFO (First In First Out) principle.

Example

Queue after inserting 25, 30, 51, 60 and 85.

Implementation of Queues:
Queue data structure can be implemented in two ways. They are as follows...

 Using Array
 Using Linked List

When a queue is implemented using an array, that queue can organize an only limited
number of elements. When a queue is implemented using a linked list, that queue can
organize an unlimited number of elements.
 Queue Data structure Using Array

A Queue data structure can be implemented using one dimensional array. The queue
implemented using array stores only fixed number of data values. The implementation of
queue data structure using array is very simple. Just define a one dimensional array of
specific size and insert or delete the values into that array by using FIFO (First In First
Out) principle with the help of variables 'front' and 'rear'. Initially both 'front' and
'rear' are set to -1. Whenever, we want to insert a new value into the queue, increment
'rear' value by one and then insert at that position. Whenever we want to delete a value
from the queue, then delete the element which is at 'front' position and increment 'front'
value by one.
Queue Operations using Array
 enQueue(value) - Inserting value into the queue
In a queue data structure, enQueue() is a function used to insert a new element into the
queue. In a queue, the new element is always inserted at rear position. The enQueue()
function takes one integer value as a parameter and inserts that value into the queue.
 deQueue() - Deleting a value from the Queue
In a queue data structure, deQueue() is a function used to delete an element from the
queue. In a queue, the element is always deleted from front position. The deQueue()
function does not take any value as parameter.
display() - Displays the elements of a Queue
Queue Operations using Array
Queue data structure using array can be implemented as follows...

Before we implement actual operations, first follow the below steps to create an empty
queue.

Step 1 - Include all the header files which are used in the program and define a constant
'SIZE' with specific value.
Step 2 - Declare all the user defined functions which are used in queue implementation.
Step 3 - Create a one dimensional array with above defined SIZE (int queue[SIZE])
Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -
1, rear = -1)
Step 5 - Then implement main method by displaying menu of operations list and make
suitable function calls to perform operation selected by the user on queue.
enQueue(value) - Inserting value into the queue
In a queue data structure, enQueue() is a function used to insert a new element into the queue.
In a queue, the new element is always inserted at rear position. The enQueue() function takes
one integer value as a parameter and inserts that value into the queue. We can use the
following steps to insert an element into the queue...

Step 1 - Check whether queue is FULL. (rear == SIZE-1)

Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and
terminate the function.
Step 3 - If it is NOT FULL, then increment rear value by one (rear++) and set queue[rear] =
value.
deQueue() - Deleting a value from the Queue
In a queue data structure, deQueue() is a function used to delete an element from the queue.
In a queue, the element is always deleted from front position. The deQueue() function does
not take any value as parameter. We can use the following steps to delete an element from
the queue...

Step 1 - Check whether queue is EMPTY. (front == rear)

Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and
terminate the function.
Step 3 - If it is NOT EMPTY, then increment the front value by one (front ++). Then display
queue[front] as deleted element. Then check whether both front and rear are equal (front ==
rear), if it TRUE, then set both front and rear to '-1' (front = rear = -1).
display() - Displays the elements of a Queue
We can use the following steps to display the elements of a queue...

Step 1 - Check whether queue is EMPTY. (front == rear)

Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front+1'.
Step 4 - Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i'
value reaches to rear (i <= rear)

Implementation of Queue Datastructure using Array - C Programming

#include<stdio.h>
#include<conio.h>
#define SIZE 10

void enQueue(int);
void deQueue();
void display();

int queue[SIZE], front = -1, rear = -1;

void main()
{
int value, choice;
 clrscr();
while(1){
printf("\n\n***** MENU *****\n");
printf("1. Insertion\n2. Deletion\n3. Display\n4. Exit");
printf("\nEnter your choice: ");
scanf("%d",&choice);
switch(choice){
case 1: printf("Enter the value to be insert: ");
scanf("%d",&value);
enQueue(value);
break;
case 2: deQueue();
break;
case 3: display();
break;
case 4: exit(0);
default: printf("\nWrong selection!!! Try again!!!");
}
}
}
void enQueue(int value){
if(rear == SIZE-1)
printf("\nQueue is Full!!! Insertion is not possible!!!");
else{
if(front == -1)
front = 0;
rear++;
queue[rear] = value;
printf("\nInsertion success!!!");
}
}
void deQueue(){
if(front == rear)
printf("\nQueue is Empty!!! Deletion is not possible!!!");
else{
printf("\nDeleted : %d", queue[front]);
front++;
if(front == rear)
front = rear = -1;
}
}
void display(){
if(rear == -1)
printf("\nQueue is Empty!!!");
else{
 int i;
printf("\nQueue elements are:\n");
for(i=front; i<=rear; i++)
printf("%d\t",queue[i]);
}
}
 Queue Using Linked List
The major problem with the queue implemented using an array is, It will work for an
only fixed number of data values. That means, the amount of data must be specified at the
beginning itself. Queue using an array is not suitable when we don't know the size of data
which we are going to use. A queue data structure can be implemented using a linked list
data structure.
The queue which is implemented using a linked list can work for an unlimited number of
values. That means, queue using linked list can work for the variable size of data (No
need to fix the size at the beginning of the implementation). The Queue implemented
using linked list can organize as many data values as we want.

In linked list implementation of a queue, the last inserted node is always pointed by
'rear' and the first node is always pointed by 'front'.

In above example, the last inserted node is 50 and it is pointed by 'rear' and the first
inserted node is 10 and it is pointed by 'front'. The order of elements inserted is 10, 15,
22 and 50.
Operations
Following are basic operations of Queue:
Main Queue Operations:
1) EnQueue(): Inserts an element at the rear of the Queue. 2)DeQueue(): Remove and
return the front element of the Queue.

Operations
To implement queue using linked list, we need to set the following things before
implementing actual operations.

Step 1 - Include all the header files which are used in the program. And declare all the
user defined functions.
Step 2 - Define a 'Node' structure with two members data and next.
Step 3 - Define two Node pointers 'front' and 'rear' and set both to NULL.
Step 4 - Implement the main method by displaying Menu of list of operations and make
suitable function calls in the main method to perform user selected operation.
enQueue(value) - Inserting an element into the Queue
We can use the following steps to insert a new node into the queue...

Step 1 - Create a newNode with given value and set 'newNode → next' to NULL.
Step 2 - Check whether queue is Empty (rear == NULL)

Step 4 - If it is Not Empty then, set rear → next = newNode and rear = newNode.
Step 3 - If it is Empty then, set front = newNode and rear = newNode.

deQueue() - Deleting an Element from Queue

We can use the following steps to delete a node from the queue...

Step 1 - Check whether queue is Empty (front == NULL).

Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion is not possible!!!" and
terminate from the function

Step 4 - Then set 'front = front → next' and delete 'temp' (free(temp)).
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and set it to 'front'.

display() - Displaying the elements of Queue

We can use the following steps to display the elements (nodes) of a queue...

Step 1 - Check whether queue is Empty (front == NULL).

Step 2 - If it is Empty then, display 'Queue is Empty!!!' and terminate the function.

Step 4 - Display 'temp → data --->' and move it to the next node. Repeat the same until
Step 3 - If it is Not Empty then, define a Node pointer 'temp' and initialize with front.

'temp' reaches to 'rear' (temp → next != NULL).

Step 5 - Finally! Display 'temp → data ---> NULL'.

Implementation of Queue Datastructure using Linked List - C Programming

#include<stdio.h>
#include<conio.h>

{
struct Node

int data;

}*front = NULL,*rear = NULL;

struct Node *next;

void insert(int);
void delete();
void display();

{
void main()

int choice, value;

printf("\n:: Queue Implementation using Linked List ::\n");

clrscr();

while(1){
printf("\n****** MENU ******\n");
printf("1. Insert\n2. Delete\n3. Display\n4. Exit\n");
printf("Enter your choice: ");
scanf("%d",&choice);
switch(choice){

scanf("%d", &value);
case 1: printf("Enter the value to be insert: ");

insert(value);
break;
case 2: delete(); break;
case 3: display(); break;
case 4: exit(0);

}
default: printf("\nWrong selection!!! Please try again!!!\n");

}
}

{
void insert(int value)

newNode = (struct Node*)malloc(sizeof(struct Node));

struct Node *newNode;

newNode->data = value;
newNode -> next = NULL;
if(front == NULL)
front = rear = newNode;

rear -> next = newNode;

else{

rear = newNode;
}

}
printf("\nInsertion is Success!!!\n");

{
void delete()

if(front == NULL)
printf("\nQueue is Empty!!!\n");
else{
 struct Node *temp = front;
front = front -> next;
printf("\nDeleted element: %d\n", temp->data);

}
free(temp);

{
void display()

if(front == NULL)
printf("\nQueue is Empty!!!\n");

struct Node *temp = front;

else{

while(temp->next != NULL){

temp = temp -> next;

printf("%d--->",temp->data);

}
printf("%d--->NULL\n",temp->data);

}
Applications of Queues
Applications of Queues
Operating Systems (OS)
CPU Scheduling: The OS uses queues to manage processes waiting for CPU time, ensuring they are
executed fairly on a first-come, first-served basis (e.g., Round Robin scheduling uses a circular queue).
Memory Management: Queues are used for managing and allocating memory blocks as processes request
them.
Handling Interrupts: Hardware or software interrupts are placed in a queue and processed in the order they
arrive.
Computer Networking
Packet Management: Routers and switches use queues to buffer data packets as they arrive, managing
network traffic and ensuring orderly transmission.
Mail Queues: Email messages are stored in queues on a mail server to be delivered in the order they were
sent.
Load Balancing: In web servers and cloud computing, requests from multiple clients are placed in a queue
and distributed across various servers to prevent overload.
Peripheral Management
Printer Spooling: When multiple print jobs are sent to a single printer, they are stored in a queue and
processed one by one, preventing job conflicts and ensuring each document is printed in order.
I/O Buffers: Queues act as buffers between slow devices (like a keyboard or disk drive) and the fast CPU,
holding the data until the CPU is ready to process it.
Algorithms and Programming
Breadth-First Search (BFS): This essential graph traversal algorithm uses a queue to explore nodes level by
level, starting from an initial node and processing all its neighbors before moving to the next level.
Event Handling: In event-driven programming, events (like user clicks or system notifications) are stored in
an event queue and processed sequentially by event handlers.
Algorithm Implementations: Queues are fundamental to implementing other data structures and algorithms,
such as Huffman coding (using a priority queue) and certain job scheduling algorithms.
Real-World Simulations
Customer Service Systems: Call centers and helpdesks use queues to manage incoming calls, ensuring
customers are served in the order they called.
Traffic Management: Circular queues can be used to control traffic lights at intersections, cycling through
the light phases repeatedly.
Waiting Lines: Physical queues at ticket counters, ATM booths, and cashier lines are a direct real-life
analogy of the queue data structure.

Types of Queues:

 Simple Queue

As is clear from the name itself, simple queue lets us perform the operations simply. i.e.,
the insertion and deletions are performed likewise. Insertion occurs at the rear (end) of
the queue and deletions are performed at the front (beginning) of the queue list.

All nodes are connected to each other in a sequential manner. The pointer of the first
node points to the value of the second and so on.
The first node has no pointer pointing towards it whereas the last node has no pointer
pointing out from it.

 Circular Queue
Unlike the simple queues, in a circular queue each node is connected to the next node in
sequence but the last node’s pointer is also connected to the first node’s address. Hence,
the last node and the first node also gets connected making a circular link overall.

 Priority Queue

Priority queue makes data retrieval possible only through a pre-determined priority
number assigned to the data items.
While the deletion is performed in accordance to priority number (the data item with
highest priority is removed first), insertion is performed only in the order.

 Doubly Ended Queue (Dequeue)

The doubly ended queue or dequeue allows the insert and delete operations from both
ends (front and rear) of the queue.
Queues are an important concept of the data structures and understanding their types is
very necessary for working appropriately with them.
Heap
Max Heap Datastructure
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 some times also called as Binary Heap.

There are two types of heap data structures and they are as follows...

Max Heap
Min Heap
Every heap data structure has the following properties...

Property #1 (Ordering): Nodes must be arranged in an order according to their values

based on Max heap or Min heap.
Max Heap
Max heap data structure is a specialized full binary tree data structure. In a max heap
nodes are arranged based on node value.

Max heap is defined as follows...

Max heap is a specialized full binary tree in which every parent node contains greater or
equal value than its child nodes.
bove tree is satisfying both Ordering property and Structural property according to the
Max Heap data structure.

Operations on Max Heap

The following operations are performed on a Max heap data structure...

Finding Maximum
Insertion
Deletion
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.

Insertion Operation in Max Heap

Insertion Operation in max heap is performed as follows...

Step 1 - Insert the newNode as last leaf from left to right.

Step 2 - Compare newNode value with its Parent node.
Step 3 - If newNode value is greater than its parent, then swap both of them.
Step 4 - Repeat step 2 and step 3 until newNode value is less than its parent node (or)
newNode reaches to root.
Example
Consider the above max heap. Insert a new node with value 85.
Step 1 - Insert the newNode with value 85 as last leaf from left to right. That means
newNode is added as a right child of node with value 75. After adding max heap is as
follows...

Step 2 - Compare newNode value (85) with its Parent node value (75). That means 85 >
75

Step 3 - Here newNode value (85) is greater than its parent value (75), then swap both of
them. After swapping, max heap is as follows...
Step 4 - Now, again compare newNode value (85) with its parent node value (89).

Here, newNode value (85) is smaller than its parent node value (89). So, we stop
insertion process. Finally, max heap after insertion of a new node with value 85 is as
follows...
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. We use the following steps 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 above 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. After deleting node with value 90 from
heap, max heap is as follows...

Step 3 - Compare root node (75) with its left child (89).
Here, root value (75) is smaller than its left child value (89). So, compare left child (89)
with its right sibling (70).

Step 4 - Here, left child value (89) is larger than its right sibling (70), So, swap root (75)
with left child (89).
Step 5 - Now, again compare 75 with its left child (36).

Here, node with value 75 is larger than its left child. So, we compare node 75 with its
right child 85.
Step 6 - Here, node with value 75 is smaller than its right child (85). So, we swap both of
them. After swapping max heap is as follows...

Step 7 - Now, compare node with value 75 with its left child (15).
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-IV: Searching and Sorting

Linear Search Algorithm

What is Search?
Search is a process of finding a value in a list of values. In other words, searching is the process of
locating given value position in a list of values.

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.
Example
Consider the following list of elements and the element to be searched...
Implementation of Linear Search Algorithm using C Programming Language
#include<stdio.h>
#include<conio.h>

void main(){
int list[20],size,i,sElement;

printf("Enter size of the list: ");

scanf("%d",&size);

printf("Enter any %d integer values: ",size);

for(i = 0; i < size; i++)
scanf("%d",&list[i]);

printf("Enter the element to be Search: ");

scanf("%d",&sElement);

// Linear Search Logic

for(i = 0; i < size; i++)
{
if(sElement == list[i])
{
printf("Element is found at %d index", i);
break;
}
}
if(i == size)
printf("Given element is not found in the list!!!");
getch();
}

Binary Search Algorithm

What is Search?
Search is a process of finding a value in a list of values. In other words, searching is the process of
locating given value position in a list of values.

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 can not 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 sublist of the middle element. If the search
element is larger, then we repeat the same process for the right sublist of the middle element. We
repeat this process until we find the search element in the list or until we left with a sublist 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
sublist 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
sublist of the middle element.
Step 8 - Repeat the same process until we find the search element in the list or until sublist 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.
Example
Consider the following list of elements and the element to be searched...
Implementation of Binary Search Algorithm using C Programming Language
#include<stdio.h>
#include<conio.h>

void main()
{
int first, last, middle, size, i, sElement, list[100];
clrscr();

printf("Enter the size of the list: ");

scanf("%d",&size);

printf("Enter %d integer values in Assending order\n", size);

for (i = 0; i < size; i++)

scanf("%d",&list[i]);

printf("Enter value to be search: ");

scanf("%d", &sElement);

first = 0;
last = size - 1;
middle = (first+last)/2;

while (first <= last) {

if (list[middle] < sElement)
first = middle + 1;
else if (list[middle] == sElement) {
printf("Element found at index %d.\n",middle);
break;
}
else
last = middle - 1;

middle = (first + last)/2;

}
if (first > last)
printf("Element Not found in the list.");
 getch();
}

Static 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...

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.

Step by Step Process

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 comparision, 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.
Following is the sample code for selection sort...

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;
}
}
}
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 comparisions in the worst case. If the list is already sorted then it requires 'n'
number of comparisions.

Worst Case : O(n2)

Best Case : Ω(n2)
Average Case : Θ(n2)
Implementaion of Selection Sort Algorithm using C Programming Language
#include<stdio.h>
#include<conio.h>

void main(){

int size,i,j,temp,list[100];
clrscr();

printf("Enter the size of the List: ");

scanf("%d",&size);

printf("Enter %d integer values: ",size);

for(i=0; i<size; i++)
scanf("%d",&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;
}
}
}

printf("List after sorting is: ");

 for(i=0; i<size; i++)
printf(" %d",list[i]);

getch();
}

Insertion Sort Algorithm

Sorting is the process of arranging a list of elements in a particular order (Ascending or

Descending).

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.

Step by Step Process

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.
Following is the sample code for insertion sort...

Insertion Sort Logic

//Insertion sort logic
for i = 1 to size-1 {
temp = list[i];
j = i-1;
while ((temp < list[j]) && (j > 0)) {
list[j] = list[j-1];
j = j - 1;
}
list[j] = temp;
}
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 comparisions in the worst case. If the list is already sorted then it requires 'n'
number of comparisions.

Worst Case : O(n2)

Best Case : Ω(n)
Average Case : Θ(n2)
Implementaion of Insertion Sort Algorithm using C Programming Language
#include<stdio.h>
#include<conio.h>

void main(){

int size, i, j, temp, list[100];

printf("Enter the size of the list: ");

scanf("%d", &size);

printf("Enter %d integer values: ", size);

for (i = 0; i < size; i++)
scanf("%d", &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;
}

printf("List after Sorting is: ");

for (i = 0; i < size; i++)
printf(" %d", list[i]);
 getch();
}

Bubble Sort
ubble sort is a simple sorting algorithm. This sorting algorithm is comparison-based algorithm in
which each pair of adjacent elements is compared and the elements are swapped if they are not in
order. This algorithm is not suitable for large data sets as its average and worst case complexity are
of O(n2) where n is the number of items.

Bubble Sort Algorithm

Bubble sort with Example:

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 byone and sort them based on their values.

Bubble Sort is an elementary sorting algorithm, which works by repeatedly exchanging adjacent
elements, if necessary. When no exchanges are required, the file is sorted.

We assume list is an array of n elements. We further assume that swap function swaps the values of
the given array elements.

Step 1 − Check if the first element in the input array is greater than the next element in the array.
Step 2 − If it is greater, swap the two elements; otherwise move the pointer forward in the array.

Step 3 − Repeat Step 2 until we reach the end of the array.

Step 4 − Check if the elements are sorted; if not, repeat the same process (Step 1 to Step 3) from
the last element of the array to the first.

Step 5 − The final output achieved is the sorted array.

fori ← 1 to length [A] do

Algorithm: Sequential-Bubble-Sort (A)

for j ← length [A] down-to i +1 do

Exchange A[j] ⟷ A[j-1]

if A[A] < A[j-1] then

Pseudocode
We observe in algorithm that Bubble Sort compares each pair of array element unless the whole
array is completely sorted in an ascending order. This may cause a few complexity issues like what
if the array needs no more swapping as all the elements are already ascending.

To ease-out the issue, we use one flag variable swapped which will help us see if any swap has
happened or not. If no swap has occurred, i.e. the array requires no more processing to be sorted, it
will come out of the loop.

Pseudocode of bubble sort algorithm can be written as follows −

voidbubbleSort(int numbers[], intarray_size){

inti, j, temp;
for (i = (array_size - 1); i>= 0; i--)
for (j = 1; j <= i; j++)
if (numbers[j-1] > numbers[j]){
temp = numbers[j-1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}
Analysis
Here, the number of comparisons are

1 + 2 + 3 + ... + (n - 1) = n(n - 1)/2 = O(n2)

Clearly, the graph shows the n2 nature of the bubble sort.

In this algorithm, the number of comparison is irrespective of the data set, i.e. whether the provided
input elements are in sorted order or in reverse order or at random.

Memory Requirement
From the algorithm stated above, it is clear that bubble sort does not require extra memory.

Example
We take an unsorted array for our example. Bubble sort takes (n2) time so we're keeping it short
and precise.

Bubble sort starts with very first two elements, comparing them to check which one is
greater.

In this case, value 33 is greater than 14, so it is already in sorted locations. Next, we
compare 33 with 27.

We find that 27 is smaller than 33 and these two values must be swapped.

Next we compare 33 and 35. We find that both are in already sorted positions.
Then we move to the next two values, 35 and 10.

We know then that 10 is smaller 35. Hence they are not sorted. We swap these values. We

this −
find that we have reached the end of the array. After one iteration, the array should look like

To be precise, we are now showing how an array should look like after each
iteration. After the second iteration, it should look like this −

Notice that after each iteration, at least one value moves at the end.
And when there's no swap required, bubble sort learns that an array is
completely sorted.

#include <stdio.h>
void bubbleSort(int array[], int size){
for(int i = 0; i<size; i++) {
int swaps = 0; //flag to detect any swap is there or not
for(int j = 0; j<size-i-1; j++) {
if(array[j] > array[j+1]) { //when the current item is bigger than next
int temp;
temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
swaps = 1; //set swap flag
}
}
if(!swaps)
break; // No swap in this pass, so array is sorted
}
}
int main(){
 int n;
n = 5;
int arr[5] = {67, 44, 82, 17, 20}; //initialize an array
printf("Array before Sorting: ");
for(int i = 0; i<n; i++)
printf("%d ",arr[i]);
printf("\n");
bubbleSort(arr, n);
printf("Array after Sorting: ");
for(int i = 0; i<n; i++)
printf("%d ", arr[i]);
printf("\n");
}

Quick Sort 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".

Step by Step Process

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.
Following is the sample code for Quick sort...

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);
}
}
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)

Implementaion of Quick Sort Algorithm using C Programming Language

#include<stdio.h>
#include<conio.h>

void quickSort(int [10],int,int);

void main(){
int list[20],size,i;

printf("Enter size of the list: ");

scanf("%d",&size);

printf("Enter %d integer values: ",size);

for(i = 0; i < size; i++)
scanf("%d",&list[i]);

quickSort(list,0,size-1);

printf("List after sorting is: ");

for(i = 0; i < size; i++)
printf(" %d",list[i]);

getch();
}

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);
}
}

Merge sort:

Merge sort is one of the most efficient sorting algorithms. It works on the principle of
Divide and Conquer. Merge sort repeatedly breaks down a list into several sub lists until
each sub list consists of a single element and merging those sub lists in a manner that
results into a sorted list.

Algorithm forMerge Sort:

Step 1: Find the middle index of the array. Middle = 1 + (last – first)/2
Step 2: Divide the array from the middle.
Step 3: Call merge sort for the first half of the array Merge Sort(array, first, middle)
Step 4: Call merge sort for the second half of the array. Merge Sort(array, middle+1, last)
Step 5: Merge the two sorted halves into a single so rted array.

A merge sort works as follows:

Top-down Merge Sort Implementation:

The top-down merge sort approach is the methodology which uses recursion
mechanism. It starts at the Top and proceeds downwards, with each recursive turn
asking the same question such as “What is required to be done to sort the array?” and
having the answer as, “split the array into two, make a recursive call, and merge the
results.”, until one gets to the bottom of the array-tree.

Example: Let us consider an example to understand the approach better.

Unit-V Trees and Graphs

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. One
is known as a left child and the other is known as right child.

“A tree in which every node can have a maximum of two children is called Binary
Tree.”

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

 Strictly Binary Tree

 Complete Binary Tree
 Extended Binary Tree
1. Strictly Binary Tree:
“A binary tree in which every node has either two or zero number of children is called
Strictly Binary Tree”.

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

A strictly Binary Tree can be defined as follows...

Example: Strictly binary tree data structure is used to represent mathematical

expressions.

2 .Complete Binary Tree:

“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.”

In a binary tree, every node can have a maximum of two children. But in strictly binary
tree, every node should have exactly two children or none and 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. For example at level 2 there must be 2 2 = 4 nodes and at
level 3 there must be 23 = 8 nodes. Complete binary tree is also called as Perfect
Binary Tree

Example

 Extended Binary Tree:

“The full binary tree obtained by adding dummy nodes to a binary tree is called as
Extended Binary Tree.”

A binary tree can be converted into Full Binary tree by adding dummy nodes to existing
nodes wherever required. In above figure, a normal binary tree is converted into full
binary tree by adding dummy nodes (In pink colour).
Example:

Binary Tree Traversals.

Binary Tree Traversals: Displaying (or) visiting order of nodes in a binary tree is called
as Binary Tree Traversal.
There are three types of binary tree traversals.

 In - Order Traversal
 Pre - Order Traversal
 Post - Order Traversal

Consider the following binary tree...

 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 we go
for visiting the right child node. This in-order traversal is applicable for every root node
of all sub trees in the tree. This is performed recursively for all nodes in
the tree. 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 sub tree. so we try to visit its (B's) left child
'D' and again D is a root for sub tree 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.

That means here we have visited in the order of I - D - J - B - F - A - G - K - C - H

using In-Order Traversal.

 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 sub trees in the
tree. 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.

 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-

OrderTraversal Full Binary Tree ,Prefect Binary Tree:

 Full Binary Tree:
“A binary tree in which every node has either two or zero number of children is called Full
Binary Tree”.

In a binary tree, every node can have a maximum of two children. But in full binary tree,
every node should have exactly two children or none. That means every internal node
must have exactly two children. Full binary tree is also called as Full Binary Tree.

A Full Binary Tree can be defined as follows...

Example: Full binary tree data structure is used to represent mathematical expressions

 Perfect Binary Tree:

“A binary tree in which every internal node has exactly two children and all leaf nodes are
at same level is called Perfect Binary Tree.”

In a binary tree, every node can have a maximum of two children. But in strictly binary
tree, every node should have exactly two children or none and in Perfect binary tree all
the nodes must have exactly two children and at every level of Perfect binary tree there
must be 2level number of nodes. For example at level 2 there must be 2 2 = 4 nodes and at
level 3 there must be 23 = 8 nodes.
Example:
Applications of Binary Tree:

The following are the applications of binary trees:

Binary Search Tree - Used in many search applications that constantly show and hide
data, such as data. For example, map and set objects in many libraries.
Binary Space Partition - Used in almost any 3D video game to determine which
objects need to be rendered.
Binary Tries - Used in almost every high-bandwidth router to store router tables.
Syntax Tree - Constructed by compilers and (implicit) calculators to parse expressions.
Hash Trees - Used in P2P programs and special image signatures that require a hash to
be validated, but the entire file is not available.

Heaps - Used to implement efficient priority queues and also used in heap sort.
Treap - Randomized data structure for wireless networks and memory allocation.
T-Tree - Although most databases use a form of B-tree to store data on the drive,
databases that store all (most) data often use T-trees.

properties of a Tree:

Some basic properties of a binary tree:

 A binary tree can have a maximum of nodes at level if the level of the root is zero.
 When each node of a binary tree has one or two children, the number of leaf nodes
(nodes with no children) is one more than the number of nodes that have two children.
 There exists a maximum of nodes in a binary tree if its height is , and the height of a
leaf node is one.
 If there exist leaf nodes in a binary tree, then it has at least levels.
 A binary tree of nodes has minimum number of levels or minimum height.
 The minimum and the maximum height of a binary tree having nodes are and,
respectively.
 A binary tree of nodes has null references.

Expression Tree
Expression trees
Expression trees are those in which the leaf nodes have the values to be
operated, and internal nodes contain the operator on which the leaf node will
be performed.

Example
4 + ((7 + 9) * 2) will have an expression tree as follows

How to construct an expression tree?

To construct an Expression Tree for the given expression, we generally use
Stack Data Structure.

Initially we Iterate over the given postfix expression and follow the steps as
given below -

If we get an operand in the given expression, then push it in the stack. It will
become the root of the expression Tree.
If an operator gets two values in the expression, then add in the expression
tree as its child, and push them in the current node.
Repeat Step-1 and Step-2 until we do not complete over the given expression.
Now check if every root node contains nothing but operands and every child
node contains only values.

Construct a BST:

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.

A binary tree has the following time complexities...

Search Operation - O(n)

Insertion Operation - O(1)
Deletion Operation - O(n)
To enhance the performance of binary tree, we use a special type of binary tree known as
Binary Search Tree. 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.

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

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...
Different operations on a Binary Search Tree:

Operations on binary search tree:

The following operations are performed on binary search tree
 Search (Traversing)
 Insertion
 Deletion

Constructing a binary search tree:

 Take the first element as the root of the tree.
 Take the next element and compare with root node. If it is less than the root node then
it is added to left sub tree.
 If the element is greater than the root node, then it is added to right sub tree.
 Repeat the steps 2&3 until the last element.
Deletion:

 Deleting a node from binary search tree.

 A node can be deleted from BST, in 3 positions.
 A node is to be deleted which has no children can be done by placing null inits
parent node
Graphs

Graph and different types of Graphs:

Graph: A graph is a ordered pair of two sets i.e., G=(V,E)

 The elements of ‘v’ are called vertices, where V={V1,V2,V3, ... Vn} and
 The elements of ‘E’ are called edges, i.e,
E={E1,E2,E3,... En}each edge is identified with pair of distinct vertices
 A graph is a non-linear data structure

Multi Graph: If more than one edge joining a pair of vertices, is called multi-graph In

the above example C1, C2 is called the multi graph.

Loop:If an edge joining a vertex to itself it is called a Loop.

Connected Graph: A Graph is said to be connected if their path from one vertex to
another vertex i.e. we can travel from any one vertex to another vertex

(or)

A graph is said to be connected if there is a path between every pair of vertices

Non connected /Disconnected Graph: If there is nopath to travel from one vertex to
another vertex that graph is called non-connected (or) disconnected graph

Null Graph: If a graph with no edges is called null graph (or) totally disconnected graph

Complete graph: A graph in which every pair of vertices are adjacent then it is called
complete graph

Regular Graph:

A graph in which degree of all vertices is equal then it is called regular graph
Graph and its representation:

A graph representation is a technique to store graph into the memory of computer.

To represent a graph, we just need the set of vertices and for each vertex the neighbours
of the vertex (vertices which is directly connected to it by an edge). If it is a weighted
graph, then the weight will be associated with each edge.

There are different ways to optimally represent a graph, depending on the density of its
edges, type of operations to be performed and ease of use.

Example:

Consider the following undirected graph representation: Undirected graph

representation

Directed graph representation

See the directed graph representation:

Applications of Graph:

In Computer science graphs are used to represent the flow of computation.

 Google maps uses graphs for building transportation systems, where intersection of
two(or more) roads are considered to be a vertex and the road connecting two vertices is
considered to be an edge, thus their navigation system is based on the algorithm to
calculate the shortest path between two vertices.
 In Facebook, users are considered to be the vertices and if they are friends then there
is an edge running between them. Facebook’s Friend suggestion algorithm uses graph
theory. Facebook is an example of undirected graph.
 In World Wide Web, web pages are considered to be the vertices. There is an edge
from a page u to other page v if there is a link of page v on page u. This is an example

of Directed graph. It was the basic idea behind Google HYPERLINK

"[Link] HYPERLINK
"[Link] HYPERLINK
"[Link]
HYPERLINK "[Link]
implementation/" HYPERLINK "[Link]
algorithm-implementation/" HYPERLINK
"[Link] Page
HYPERLINK "[Link]
implementation/" HYPERLINK "[Link]
algorithm-implementation/" HYPERLINK
"[Link]
HYPERLINK "[Link]
implementation/" HYPERLINK "[Link]
algorithm-implementation/" HYPERLINK
"[Link]
implementation/" Ranking HYPERLINK "[Link]
rank-algorithm-implementation/" HYPERLINK
"[Link]
HYPERLINK "[Link]
implementation/" HYPERLINK "[Link]
implementation/"HYPERLINK "[Link]
implementation/" HYPERLINK "[Link]
algorithm-implementation/" Algorithm HYPERLINK
"[Link]
implementation/" HYPERLINK "[Link]
algorithm-implementation/" HYPERLINK
"[Link] .

 In Operating System, we come across the Resource Allocation Graph where each
process and resources are considered to be vertices. Edges are drawn from resources to
the allocated process, or from requesting process to the requested resource. If this leads to
any formation of a cycle then a deadlock will occur.

Tree Traverse Techniques:

Binary Tree Traversals: Displaying (or) visiting order of nodes in a binary tree is called as
Binary Tree Traversal.

There are three types of binary tree traversals.

 In - Order Traversal
 Pre - Order Traversal
 Post - Order Traversal

Consider the following binary tree...

 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 we go
for visiting the right child node. This in-order traversal is applicable for every root node
of all sub trees in the tree. This is performed recursively for all nodes in the
tree. 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 sub tree. so we try to visit its (B's) left child 'D'
and again D is a root for sub tree 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.

That means here we have visited in the order of I - D - J - B - F - A - G - K - C

- H using In-Order Traversal.

 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 sub trees in the
tree. 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.

 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.

Graph Traversal - DFS

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

DFS (Depth First Search)

BFS (Breadth First Search)
DFS (Depth First Search)
DFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a
graph without loops. We use Stack data structure with maximum size of total number of
vertices in the graph to implement DFS traversal.

We use the following steps 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
Back tracking is coming back to the vertex from which we reached the current vertex.

Graph Traversal - BFS

Graph traversal is a technique used for searching a 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...

DFS (Depth First Search)

BFS (Breadth First Search)
BFS (Breadth First Search)
BFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a
graph without loops. We use Queue data structure with maximum size of total number of
vertices in the graph to implement BFS traversal.

We use the following steps 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