www.gradeup.

co

1
1
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

1 C PROGRAMMING

All C programs must have a function in it called main

(a) Execution starts in function main
(b) C is case sensitive
(c) Comments start with /* and end with */. Comments may span over many lines.
(d) C is a “free format” language
(e) All C statements must end in a semicolon (;).
(f) The #include <stdio.h> statement instructs the C compiler to insert the entire contents of file
stdio.h in its place and compile the resulting file.

1. PRINTF() FUNCTION IN C LANGUAGE

▪ In C programming language, printf() function is used to print the “character, string, float,
integer, octal and hexadecimal values” onto the output screen.

Data Type Format Specifier

ffgff %d

char %c

float %f

double %lf

short int %hd

unsigned int %u

long int %li

long long int %lli

unsigned long int %lu

unsigned long long int %llu

signed char %c

unsigned char %c

long double %Lf

Here's a list of commonly used C data types and their format specifiers.

2
2
www.gradeup.co

Example Program for printf in C

#include <stdio.h>
int main()
{
char ch = 'A';
char str[20] = "gradeup2u.co ";
float flt = 10.234;
int no = 150;
double dbl = 20.123456;
printf("Character is %c \n", ch);
printf("String is %s \n" , str);
printf("Float value is %f \n", flt);
printf("Integer value is %d\n" , no);
printf("Double value is %lf \n", dbl);
printf("Double value upto 2 decimal is %2lf \n", dbl);
printf("Octal value is %o \n", no);
printf("Hexadecimal value is %x \n", no);
return 0;
}
Output-
Character is A
String is gradeup2u.co
Float value is 10.234000
Integer value is 150
Double value is 20.123456
Double value upto 2 decimal is 20.12
Octal value is 226
Hexadecimal value is 96

2. SCANF() FUNCTION IN C LANGUAGE

▪ In C programming language, scanf() function is used to read character, string, numeric

data from keyboard.
▪ Consider below example program where user enters a character. This value is assigned to
the variable “ch” and then displayed.
▪ Then, user enters a string and this value is assigned to the variable “str” and then
displayed.

3
3
www.gradeup.co

Example-
#include <stdio.h>
int main()
{
char ch;
char str[100];
printf("Enter any character \n");
scanf("%c", &ch);
printf("Entered character is %c \n", ch);
printf("Enter any string ( upto 100 character ) \n");
scanf("%s", &str);
printf("Entered string is %s \n", str);
}
Output-
Enter any character
a
Entered character is a
Enter any string ( upto 100 character )
hai
Entered string is hai
▪ The format specifier %d is used in scanf() statement. So that, the value entered is received
as an integer and %s for string.
▪ Ampersand is used before variable name “ch” in scanf() statement as &ch.

3. C – DATA TYPES

There are four data types in C language. They are

Types Data Types

Basic data types Int, char, float, double

Enumeration data type enum

Derived data type Pointer, array, structure, union

Void data type void

4
4
www.gradeup.co

3.1. Integer type

Integers are used to store whole numbers.

Type Size(bytes) Range

int or signed int 2 -32,768 to 32767

unsigned int 2 0 to 65535

short int or signed short int 1 -128 to 127

unsigned short int 1 0 to 255

long int or signed long int 4 -2,147,483,648 to 2,147,483,647

unsigned long int 4 0 to 4,294,967,295

3.2. Floating point type

Floating types are used to store real numbers.
Size and range of Integer type on 16-bit machine

Type Size(bytes) Range

Float 4 3.4E-38 to 3.4E+38

double 8 1.7E-308 to 1.7E+308

long double 10 3.4E-4932 to 1.1E+4932

3.3. Character type

Character types are used to store characters value.
Size and range of Integer type on 16-bit machine

Type Size(bytes) Range

char or signed char 1 -128 to 127

unsigned char 1 0 to 255

void type
void type means no value. This is usually used to specify the type of functions which
returns nothing. We will get acquainted to this datatype as we start learning more
advanced topics in C language, like functions, pointers etc.

5
5
www.gradeup.co

4. C TOKENS

The smallest individual units are known as C tokens. C has six types of tokens: Keywords,
Identifiers, Constants, Operators, Delimiters / Separators and Special symbols.
4.1. Keywords: All keywords are basically the sequences of characters that have one or more
fixed meanings.
• Keywords are pre-defined words in a C compiler.
• Each keyword is meant to perform a specific function in a C program.
• Since keywords are referred names for compiler, they can’t be used as variable name.
• All C keywords must be written in lowercase letters.

auto double case enum

int struct register typedef

const float default goto

short unsigned sizeof volatile

break else char extern

long switch return union

continue for do if

signed void static while

4.2. Identifiers: A C identifier is a name used to identify a variable, function, or any other
user-defined item.
RULES FOR CONSTRUCTING IDENTIFIER NAME IN C:
• First character should be an alphabet or underscore.
• Succeeding characters might be digits or letter.
• Punctuation and special characters aren’t allowed except underscore.
• Identifiers should not be keywords.
4.3. Constants: Fixed values that do not change during the execution of a C program.
Example: 100 is integer constant, 'a' is character constant, etc.
4.4. Operators: Operator is a symbol that tells computer to perform certain mathematical or
logical manipulations.
Example: Arithmetic operators (+, -, *, /), Logical operators, Bitwise operators, etc.
4.5. Delimiters / Separators: These are used to separate constants, variables and
statements.
Example: comma, semicolon, apostrophes, double quotes, blank space etc.
4.6. Strings: String constants are specified in double quotes.
Example: "gateexam" is string constant

6
6
www.gradeup.co

5. TYPES OF OPERATORS

Figure 2

Operators Symbols
Arithmetic operators +, -, *, /, %, ++, --
Assignment operator =, +=, -=, *=, etc
Relational operators <, <=, >, >=, !=, ==
Logical operators &&, ||, !
Bitwise operators &, |, ~, ^, <<, >>
Special operators sizeof(), comma, →
Pointer operators * - Value at address (indirection), & - Address Operator
Table 2
5.1. Post Increment & Pre Increment

int i, x; int i, x;

i = 2; i = 2;

x = ++i; x = i++;

// now i = 3, x = 3 // now i = 3, x = 2

7
7
www.gradeup.co

6. OPERATOR PRECEDENCE RELATIONS

Operator precedence relations are given below from highest to lowest order:

Precedence Operator Description Associativity

++ -- Suffix/postfix increment and decrement
() Function call
[] Array subscripting
1 Left-to-right
. Structure and union member access
-> Structure and union member access through pointer
(type){list} Compound literal(C99)
++ -- Prefix increment and decrement
+- Unary plus and minus
!~ Logical NOT and bitwise NOT
(type) Type cast
2 Right-to-left
* Indirection (dereference)
& Address-of
sizeof Size-of
_Alignof Alignment requirement(C11)
3 */% Multiplication, division, and remainder
4 +- Addition and subtraction
5 << >> Bitwise left shift and right shift
< <= For relational operators < and ≤ respectively
6
> >= For relational operators > and ≥ respectively
7 == != For relational = and ≠ respectively Left-to-right
8 & Bitwise AND
9 ^ Bitwise XOR (exclusive or)
10 | Bitwise OR (inclusive or)
11 && Logical AND
12 || Logical OR
13 ?: Ternary conditional
= Simple assignment
+= -= Assignment by sum and difference
Right-to-Left
14 *= /= %= Assignment by product, quotient, and remainder
<<= >>= Assignment by bitwise left shift and right shift
&= ^= |= Assignment by bitwise AND, XOR, and OR
15 , Comma Left-to-right

Table 2

8
8
www.gradeup.co

7. C VARIABLE

• C variable is a named location in a memory where a program can manipulate the data. This
location is used to hold the value of the variable.
• The value of the C variable may get change in the program.
• C variable might be belonging to any of the data type like int, float, char etc.
7.1. DECLARING & INITIALIZING C VARIABLE:
• Variables should be declared in the C program before to use.
• Memory space is not allocated for a variable while declaration. It happens only on
variable definition.
• Variable initialization means assigning a value to the variable.

Type Syntax

data_type variable_name;
Variable declaration
Example: int x, y, z; char flat, ch;

data_type variable_name = value;

Variable initialization
Example: int x = 50, y = 30; char flag = ‘x’, ch=’l’;

THERE ARE THREE TYPES OF VARIABLES IN C PROGRAM THEY ARE,

1. Local variable
2. Global variable
3. Environment variable
7.1.1 LOCAL VARIABLE IN C:
• The scope of local variables will be within the function only.
• These variables are declared within the function and can’t be accessed outside the
function.
7.1.2 GLOBAL VARIABLE IN C:
• The scope of global variables will be throughout the program. These variables can be
accessed from anywhere in the program.
• This variable is defined outside the main function. So that, this variable is visible to
main function and all other sub functions.
7.1.3 ENVIRONMENT VARIABLES IN C:
• Environment variable is a variable that will be available for all C applications and C
programs.
• We can access these variables from anywhere in a C program without declaring and
initializing in an application or C program.
• The inbuilt functions which are used to access, modify and set these environment
variables are called environment functions.

9
9
www.gradeup.co

8. TYPE CONVERSIONS

8.1. Implicit Type Conversion: There are certain cases in which data will get automatically
converted from one type to another:
8.1.1. When data is being stored in a variable, if the data being stored does not match
the type of the variable.
8.1.2. The data being stored will be converted to match the type of the storage variable.
8.1.3. When an operation is being performed on data of two different types. The "smaller"
data type will be converted to match the "larger" type.
• The following example converts the value of x to a double precision value before
performing the division. Note that if the 3.0 were changed to a simple 3, then integer
division would be performed, losing any fractional values in the result.
• average = x / 3.0;
8.1.4. When data is passed to or returned from functions.
8.2. Explicit Type Conversion: Data may also be expressly converted, using the typecast
operator. The following example converts the value of x to a double precision value before
performing the division. ( y will then be implicitly promoted, following the guidelines listed
above. )
8.2.1. average = ( double ) x / y;
8.2.2. Note that x itself is unaffected by this conversion.

9. C FLOW CONTROL STATEMENTS

Control statement is one of the instructions, statements or group of statement in a

programming language which determines the sequence of execution of other instructions or
statements. C provides two styles of flow controls.
a. Branching (conditional) (deciding what action to take)
b. Looping(iterative) (deciding how many times to take a certain action)
c. Unconditional
9.1. If Statement:
It takes an expression in parenthesis and a statement or block of statements. Expressions
will be assumed to be true, if evaluated values are non-zero.
Syntax of if Statement:
(i)
if (condition) statement
(ii)
if (condition)
{
statement1
statement2
:
}

10
10
www.gradeup.co

9.1.1. If else statement

#include <stdio.h>
if (condition)
int main()
{statements} { int m=40,n=20;
else if (m == n)
{ printf("m and n are equal"); }
{statements}
else
{ printf("m and n are not equal"); }
}

Output- m and n are not equal

9.2. The switch Statement:

The switch statement tests the value of a given variable (or expression) against a list of
case values and when a match is found, a block of statements associated with that case
is executed:
switch (control variable)
{ Example3;

case constant-1: statement(s); Main ()

break; inti I = 10;

case constant-2: statement(s); (

break; Case 10 : print f (“case 10”);

: Case 15 : print f (“case 15”);

case constant-n: statement(s); Case 20 : print f (“case 20”);

break; Default : printf (“default case”);

default: statement(s); Output case 10 case 15 case 20

} default case
Note: Here constant can be either character or Reason:
integer Missing break after each
9.3. The Conditional Operators (? : ): case, leads to execution of all the
The ? : operators are just like an if-else statement except
cases from that because
matching it is an operator
case.
we can use it within expressions. ? : are a ternary operators in that it takes three values.
They are the only ternary operator in C language.
Syntax→ Boolean Expression ? First Statement : Second Statement
flag = (x < 0) ? 0 : 1;
This conditional statement can be evaluated as following with equivalent if else statement.
if (x < 0) flag = 0;
else flag = 1;
Example- int a=100, b=200,c=300,x;
x = (a>b) ? ((a>c)? a : c) : ((b>c) ? b : c);
Soln- a>b → false therefore, x=c,
Hence x=300

11
11
www.gradeup.co

9.4. Loop Control Structure :

Loops provide a way to repeat commands and control. This involves repeating some
portion of the program either a specified numbers of times until a particular condition is
satisfied.
9.4.1. while Loop:
The syntax of the while loop is:
while (testExpression)
{
// statements inside the body of the loop
}
• Variable initialization. (e.g int x = 0;)
• Condition (e.g while(x <= 10))
• Variable increment or decrement ( x++ or x-- or x = x + 2 )
(a) Entry Controlled Loop
(b) A while loop in C programming repeatedly executes a target statement as long as a
given condition is true.
Example-:
While loop with Break:
#include <stdio.h>
int main()
{ int num = 5;
while (num > 0)
{ if (num == 3)
break;
printf("%d\n", num);
num--;
}
}
Output: 5 4
9.4.2. do while Loop:
The syntax of the do...while loop is:
do
{
// statements inside the body of the loop
}
while (testExpression);
(a) Exit Controlled Loop

12
12
www.gradeup.co

(b) The do while loops runs atleast once in any condition(even if the loops control
condition is false)

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

int main() int main()
{ {
int i=0; int i=0;
do while(i==1)
{ {
printf("Gradeup "); printf("Gradeup ");
} while(i==1); }
printf("Hello"); printf("Hello");
} }

Output- Gradeup Hello Output- Hello

9.4.3. for Loop:

The syntax of the for loop is:
for (initializationStatement; testExpression; updateStatement)
{
// statements inside the body of loop
}
Example-
#include <stdio.h>
int main()
{
int num=10, count, sum = 0;
printf("Enter a positive integer: ");
scanf("%d", &num);
// for loop terminates when num is less than count
for(count = 1; count <= num; ++count)
{
sum += count;
}

printf("Sum = %d", sum);

return 0;
}
Output- 55

13
13
www.gradeup.co

9.5. Unconditional Flow Control Statements

(break, continue, goto, return)
9.5.1. The break Statement: The break statement is used to jump out of a loop
instantly, without waiting to get back to the conditional test.

9.5.2. The continue Statement: The 'continue' statement is used to take the control
to the beginning of the loop, by passing the statement inside the loop, which have not
yet been executed.

9.5.3. goto Statement: C supports an unconditional control statement, goto, to transfer

the control from one point to another in a C program.
Below is the syntax for goto statement in C.
{
…….
go to label;
…….
…….
LABEL:
statements;
}

****

14
14
www.gradeup.co

15
15
www.gradeup.co

1
16
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

2 OOPs CONCEPTS

OOPs Concept
Object-Oriented Programming or OOPs refers to languages that uses objects in programming. Object-
oriented programming aims to implement real-world entities like inheritance, hiding, polymorphism
etc in programming. The main aim of OOP is to bind together the data and the functions that operate
on them so that no other part of the code can access this data except that function. The primary
purpose of object-oriented programming is to increase the flexibility and maintainability of programs.

Let us learn about the different characteristics of an Object-Oriented Programming language:

1. WHAT IS AN OBJECT

Object: is a bundle of data and its behaviour (often known as methods).

An object consists of:
State : It is represented by attributes of an object. It also reflects the properties of an object.
Behavior : It is represented by methods of an object. It also reflects the response of an object
with other objects.

2
17
www.gradeup.co

Identity : It gives a unique name to an object and enables one object to interact with other
objects.
Examples of states and behaviors
Example 1:
Object: House
State: Address, Color, Area
Behavior: Open door, close door

2. CLASS

A class is a user defined blueprint or prototype from which objects are created. It represents
the set of properties or methods that are common to all objects of one type. In general, class
declarations can include these components, in order:
a. Modifiers: A class can be public or has default access (Refer this for details).
b. Class name: The name should begin with a initial letter (capitalized by convention).
c. Superclass(if any): The name of the class’s parent (superclass), if any, preceded by the
keyword extends. A class can only extend (subclass) one parent.
d. Interfaces (if any): A comma-separated list of interfaces implemented by the class, if
any, preceded by the keyword implements. A class can implement more than one interface.
e. Body: The class body surrounded by braces, { }.

3. METHOD

A method is a collection of statements that perform some specific task and return result to the
caller. A method can perform some specific task without returning anything. Methods allow us
to reuse the code without retyping the code. In Java, every method must be part of some class
which is different from languages like C, C++ and Python.
Methods are time savers and help us to reuse the code without retyping the code.
3.1. Method Declaration
In general, method declarations has six components:
a. Access Modifier: Defines access type of the method i.e. from where it can be
accessed in your application. In Java, there 4 type of the access specifiers.
➢ public: accessible in all class in your application.
➢ protected: accessible within the package in which it is defined and in its
subclass(es)(including subclasses declared outside the package)
➢ private: accessible only within the class in which it is defined.
➢ default (declared/defined without using any modifier): accessible within same
class and package within which its class is defined.

3
18
www.gradeup.co

b. The return type: The data type of the value returned by the method or void if does
not return a value.
c. Method Name: the rules for field names apply to method names as well, but the
convention is a little different.
d. Parameter list: Comma separated list of the input parameters are defined, preceded
with their data type, within the enclosed parenthesis. If there are no parameters, you
must use empty parentheses ().
e. Exception list: The exceptions you expect by the method can throw, you can specify
these exception(s).
f. Method body: it is enclosed between braces. The code you need to be executed to
perform your intended operations.
methods in java

4. POLYMORPHISM

Polymorphism refers to the ability of OOPs programming languages to differentiate between

entities with the same name efficiently. Polymorphism is a object oriented programming feature
that allows us to perform a single action in different ways.
Types of Polymorphism
1) Static Polymorphism
2) Dynamic Polymorphism
4.1. Static Polymorphism:
Polymorphism that is resolved during compiler time is known as static polymorphism.
Method overloading can be considered as static polymorphism example.
Method Overloading: This allows us to have more than one methods with same name
in a class that differs in signature.
4.2. Dynamic Polymorphism
It is also known as Dynamic Method Dispatch. Dynamic polymorphism is a process in
which a call to an overridden method is resolved at runtime rather, that’s why it is called
runtime polymorphism.

4
19
www.gradeup.co

5. INHERITANCE

The process by which one class acquires the properties and functionalities of another class is
called inheritance. Inheritance provides the idea of reusability of code and each sub class
defines only those features that are unique to it, rest of the features can be inherited from the
parent class.
Important terminology:
• Super Class: The class whose features are inherited is known as superclass(or a base class
or a parent class).
• Sub Class: The class that inherits the other class is known as subclass(or a derived class,
extended class, or child class). The subclass can add its own fields and methods in addition
to the superclass fields and methods.
• Reusability: Inheritance supports the concept of “reusability”, i.e. when we want to create
a new class and there is already a class that includes some of the code that we want, we
can derive our new class from the existing class. By doing this, we are reusing the fields and
methods of the existing class.
Types of Inheritance:
5.1. Single Inheritance: refers to a child and parent class relationship where a class extends
the another class.
5.2. Multilevel inheritance: refers to a child and parent class relationship where a class
extends the child class. For example class A extends class B and class B extends class C.
5.3. Hierarchical inheritance: refers to a child and parent class relationship where more
than one classes extends the same class. For example, class B extends class A and class
C extends class A.
5.4. Multiple Inheritance: refers to the concept of one class extending more than one
classes, which means a child class has two parent classes.

6. ENCAPSULATION

Encapsulation is defined as the wrapping up of data under a single unit. It is the mechanism
that binds together code and the data it manipulates. Another way to think about encapsulation
is, it is a protective shield that prevents the data from being accessed by the code outside this
shield.
• Technically in encapsulation, the variables or data of a class is hidden from any other class
and can be accessed only through any member function of own class in which they are
declared.
• As in encapsulation, the data in a class is hidden from other classes, so it is also known
as data-hiding.

5
20
www.gradeup.co

• Encapsulation can be achieved by Declaring all the variables in the class as private and
writing public methods in the class to set and get the values of variables.

7. ABSTRACTION

Data Abstraction is the property by virtue of which only the essential details are displayed to
the user. The trivial or the non-essentials units are not displayed to the user. Ex: A car is
viewed as a car rather than its individual components.
Data Abstraction may also be defined as the process of identifying only the required
characteristics of an object ignoring the irrelevant details. The properties and behaviours of an
object differentiate it from other objects of similar type and also help in classifying/grouping
the objects.

8. ABSTRACT CLASS AND METHODS IN OOPs CONCEPTS

8.1. Abstract method:

1) A method that is declared but not defined. Only method signature no body.
2) Declared using the abstract keyword
3) Example :
abstract public void playInstrument();
5) Used to put some kind of compulsion on the class who inherits the class has abstract
methods. The class that inherits must provide the implementation of all the abstract
methods of parent class else declare the subclass as abstract.
6) These cannot be abstract
• Constructors
• Static methods
• Private methods
• Methods that are declared “final”
8.2. Abstract Class
An abstract class outlines the methods but not necessarily implements all the methods.
abstract class A{
abstract void myMethod();
void anotherMethod(){
//Does something
}
}

6
21
www.gradeup.co

Note 1: There can be some scenarios where it is difficult to implement all the methods
in the base class. In such scenarios one can define the base class as an abstract class
which signifies that this base class is a special kind of class which is not complete on its
own.
A class derived from the abstract base class must implement those methods that are not
implemented(means they are abstract) in the abstract class.
Note 2: Abstract class cannot be instantiated which means you cannot create the object
of abstract class. To use this class, you need to create another class that extends this
abstract class provides the implementation of abstract methods, then you can use the
object of that child class to call non-abstract parent class methods as well as implemented
methods(those that were abstract in parent but implemented in child class).
Note 3: If a child does not implement all the abstract methods of parent class(the
abstract class), then the child class must need to be declared abstract.

9. MESSAGE PASSING

Objects communicate with one another by sending and receiving information to each other. A
message for an object is a request for execution of a procedure and therefore will invoke a
function in the receiving object that generates the desired results. Message passing involves
specifying the name of the object, the name of the function and the information to be sent.
Questions For Practice-
1. Which is known as a generic class?
a) Abstract class
b) Final class
c) Template class
d) Efficient Code
Answer: c
Explanation: Template classes are known to be generic classes because those can be used for
any data type value and the same class can be used for all the variables of different data types.
2. Which class can have member functions without their implementation?
a) Default class
b) String class
c) Template class
d) Abstract class
Answer: d
Explanation: Abstract classes can have member functions with no implementation, where the
inheriting subclasses must implement those functions.

7
22
www.gradeup.co

3. Which among the following is false?

a) Object must be created before using members of a class
b) Memory for an object is allocated only after its constructor is called
c) Objects can’t be passed by reference
d) Objects size depends on its class data members
Answer: c
Explanation: Objects can be passed by reference. Objects can be passed by value also. If the
object of a class is not created, we can’t use members of that class.
4. The object can’t be __________
a) Passed by reference
b) Passed by value
c) Passed by copy
d) Passed as function
Answer: d
Explanation: Object can’t be passed as function as it is an instance of some class, it’s not a
function. Object can be passed by reference, value or copy. There is no term defined as pass
as function for objects.
5. If same message is passed to objects of several different classes and all of those can respond
in a different way, what is this feature called?
a) Inheritance
b) Overloading
c) Polymorphism
d) Overriding
Answer: c
Explanation: The feature defined in question defines polymorphism features. Here the different
objects are capable of responding to the same message in different ways, hence polymorphism.
6. Which among the following can’t be used for polymorphism?
a) Static member functions
b) Member functions overloading
c) Predefined operator overloading
d) Constructor overloading
Answer: a
Explanation: Static member functions are not property of any object. Hence it can’t be
considered for overloading/overriding. For polymorphism, function must be property of object,
not only of class.

****

8
23
www.gradeup.co

9
24
www.gradeup.co

1
25
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

3 FUNCTIONS

Functions
In c, we can divide a large program into the basic building blocks known as function. The function
contains the set of programming statements enclosed by {}. A function can be called multiple times
to provide reusability and modularity to the C program. In other words, we can say that the collection
of functions creates a program.
Advantage of functions in C
There are the following advantages of C functions.
• By using functions, we can avoid rewriting same logic/code again and again in a program.
• We can call C functions any number of times in a program and from any place in a program.
• We can track a large C program easily when it is divided into multiple functions.
• Reusability is the main achievement of C functions.
• However, Function calling is always a overhead in a C program.

1. FUNCTION ASPECTS

There are three aspects of a C function.

1.1Function declaration A function must be declared globally in a c program to tell the
compiler about the function name, function parameters, and return type.
1.2Function call Function can be called from anywhere in the program. The parameter list
must not differ in function calling and function declaration. We must pass the same
number of functions as it is declared in the function declaration.
1.3Function definition It contains the actual statements which are to be executed. It is the
most important aspect to which the control comes when the function is called. Here, we
must notice that only one value can be returned from the function.
The syntax of creating function in c language is given below:
return_type function_name(data_type parameter...)
{
//code to be executed
}

2
26
www.gradeup.co

SN C function aspects Syntax

1 Function declaration return_type function_name (argument list);

2 Function call function_name (argument_list)

3 Function definition return_type function_name (argument list) {function body;}

2. TYPES OF FUNCTIONS

There are two types of functions in C programming:

1. Library Functions: are the functions which are declared in the C header files such as
scanf(), printf(), gets(), puts(), ceil(), floor() etc.
2. User-defined functions: are the functions which are created by the C programmer, so that
he/she can use it many times. It reduces the complexity of a big program and optimizes the
code.

3. RETURN VALUE

A C function may or may not return a value from the function. If you don't have to return any
value from the function, use void for the return type.
Let's see a simple example of C function that doesn't return any value from the function.
Example without return value:
void hello(){
printf("hello c");
}
If you want to return any value from the function, you need to use any data type such as int,
long, char, etc. The return type depends on the value to be returned from the function.
Let's see a simple example of C function that returns int value from the function.
Example with return value:
int get(){
return 10;
}
In the above example, we have to return 10 as a value, so the return type is int. If you want
to return floating-point value (e.g., 10.2, 3.1, 54.5, etc), you need to use float as the return
type of the method.
float get(){
return 10.2;
}
Now, you need to call the function, to get the value of the function.

3
27
www.gradeup.co

4. DIFFERENT ASPECTS OF FUNCTION CALLING

A function may or may not accept any argument. It may or may not return any value. Based
on these facts, There are four different aspects of function calls.
a) function without arguments and without return value
b) function without arguments and with return value
c) function with arguments and without return value
d) function with arguments and with return value

5. TYPES OF FUNCTION CALL

5.1. Call by value in C

• In call by value method, the value of the actual parameters is copied into the formal
parameters. In other words, we can say that the value of the variable is used in the
function call in the call by value method.
• In call by value method, we can not modify the value of the actual parameter by the
formal parameter.
• In call by value, different memory is allocated for actual and formal parameters since
the value of the actual parameter is copied into the formal parameter.
• The actual parameter is the argument which is used in the function call whereas formal
parameter is the argument which is used in the function definition.
Let's try to understand the concept of call by value in c language by the example given
below:
void change(int num) {
printf("Before adding value inside function num=%d \n",num);
num=num+100;
printf("After adding value inside function num=%d \n", num);
}
int main() {
int x=100;
printf("Before function call x=%d \n", x);
change(x);//passing value in function
printf("After function call x=%d \n", x);
return 0;
}
Output-
Before function call x=100
Before adding value inside function num=100
After adding value inside function num=200
After function call x=100

4
28
www.gradeup.co

5.2. Call by reference in C

In call by reference, the address of the variable is passed into the function call as the
actual parameter.
The value of the actual parameters can be modified by changing the formal parameters
since the address of the actual parameters is passed.
In call by reference, the memory allocation is similar for both formal parameters and
actual parameters. All the operations in the function are performed on the value stored
at the address of the actual parameters, and the modified value gets stored at the same
address.
Consider the following example for the call by reference.
#include<stdio.h>
void change(int *num) {
printf("Before adding value inside function num=%d \n",*num);
(*num) += 100;
printf("After adding value inside function num=%d \n", *num);
}
int main() {
int x=100;
printf("Before function call x=%d \n", x);
change(&x);//passing reference in function
printf("After function call x=%d \n", x);
return 0;
}
Output
Before function call x=100
Before adding value inside function num=100
After adding value inside function num=200
After function call x=200
Difference between call by value and call by reference in c

5
29
www.gradeup.co

6. POINTERS

The pointer in C language is a variable which stores the address of another variable. This
variable can be of type int, char, array, function, or any other pointer. The size of the pointer
depends on the architecture.

No. Call by value Call by reference

A copy of the value is passed into the An address of value is passed into the
1
function function
Changes made inside the function is limited Changes made inside the function validate
to the function only. The values of the actual outside of the function also. The values of
2
parameters do not change by changing the the actual parameters do change by
formal parameters. changing the formal parameters.
Actual and formal arguments are created at Actual and formal arguments are created at
3
the different memory location the same memory location

Consider the following example to define a pointer which stores the address of an integer.
int n = 10;
int* p = &n; // Variable p of type pointer is pointing to the address of the variable n of type i
nteger.
6.1. Declaring a pointer
The pointer in c language can be declared using * (asterisk symbol). It is also known as
indirection pointer used to dereference a pointer.
int *a; //pointer to int
char *c; //pointer to char

To use pointers in C, we must understand below two operators.

• To access address of a variable to a pointer, we use the unary operator & (ampersand)
that returns the address of that variable.
• One more operator is unary * (Asterisk) which is used for two things :
To declare a pointer variable: When a pointer variable is declared in C/C++, there must
a * before its name.

6
30
www.gradeup.co

To access the value stored in the address we use the unary operator (*) that returns the
value of the variable located at the address specified by its operand.
Example-
int number=50;
int *p;
p=&number; //stores the address of number variable
printf("Address of p variable is %x \n",p); // p contains the address of the number the
refore
printing p gives the address of number.
printf("Value of p variable is %d \n",*p); // As we know that * is used to dereference
a
pointer therefore if we print *p, we will get
the value stored at the address contained by p.
Output
Address of number variable is fff4
Address of p variable is fff4
Value of p variable is 50
6.1.1 Pointer to array
int arr[10];
int *p[10]=&arr; // Variable p of type pointer is pointing to the address of an integ
er array arr.
6.1.2 Pointer to a function
void show (int);
void(*p)(int) = &display; // Pointer p is pointing to the address of a function
6.1.3 Pointer to structure
struct st {
int i;
float f;
}ref;
1. struct st *p = &ref;

2.

7
31
www.gradeup.co

6.1.4 NULL Pointer

A pointer that is not assigned any value but NULL is known as the NULL pointer. If you
don't have any address to be specified in the pointer at the time of declaration, you can
assign NULL value. It will provide a better approach.
int *p=NULL;
In the most libraries, the value of the pointer is 0 (zero).
6.2. Advantage of pointer
• Pointer reduces the code and improves the performance, it is used to retrieving
strings, trees, etc. and used with arrays, structures, and functions.
• We can return multiple values from a function using the pointer.
• It makes you able to access any memory location in the computer's memory.
6.3. Usage of pointer
There are many applications of pointers in c language.
• Dynamic memory allocation
In c language, we can dynamically allocate memory using malloc() and calloc() functions
where the pointer is used.
• Arrays, Functions, and Structures
Pointers in c language are widely used in arrays, functions, and structures. It reduces the
code and improves the performance.
6.4. How to read the pointer: int (*p)[10].
To read the pointer, we must see that () and [] have the equal precedence. Therefore,
their associativity must be considered here. The associativity is left to right, so the priority
goes to ().
Inside the bracket (), pointer operator * and pointer name (identifier) p have the same
precedence. Therefore, their associativity must be considered here which is right to left,
so the priority goes to p, and the second priority goes to *.
The pointer will be read as p is a pointer to an array of integers of size 10.
Example- How to read the following pointer?
int (*p)(int (*)[2], int (*)void))
Explanation-
This pointer will be read as p is a pointer to such function which accepts the first
parameter as the pointer to a one-dimensional array of integers of size two and the
second parameter as the pointer to a function which parameter is void and return type is
the integer.
6.5. Pointer Expressions and Pointer Arithmetic
A limited set of arithmetic operations can be performed on pointers. A pointer may be:
• incremented ( ++ )

8
32
www.gradeup.co

• decremented ( — )
• an integer may be added to a pointer ( + or += )
• an integer may be subtracted from a pointer ( – or -= )
Pointer arithmetic is meaningless unless performed on an array.
Note : Pointers contain addresses. Adding two addresses makes no sense, because there
is no idea what it would point to. Subtracting two addresses lets you compute the offset
between these two addresses.
Example 1- The output of following program is ________.
int main()
{
int a = 5;
int *ptr ;
ptr = &a;
*ptr = *ptr
* 3;
printf("%d",
a);

return 0;
}

Output: 15
Explanation:
ptr = &a; copies the address of a in ptr making *ptr = a and the statement *ptr = *ptr
* 3; can be written as a = a * 3; making a as 15.
Example 2- The output of following program is ________.
int main()
{
int x = 10;
int *y, **z;
y = &x;
z = &y;
printf("x = %d, y = %d, z = %d\n", x, *y, **z);
return 0;
}
Output: x=10 y=10 z=10

9
33
www.gradeup.co

Explanation:
*y is a pointer variable whereas **z is a pointer to a pointer variable. *y gives the value
at the address it holds and **z searches twice i.e., it first takes the value at the address
it holds and then gives the value at that address.

7. RECURSION IN C

Recursion is the process which comes into existence when a function calls a copy of itself to
work on a smaller problem. Any function which calls itself is called recursive function, and such
function calls are called recursive calls. Recursion involves several numbers of recursive calls.
However, it is important to impose a termination condition of recursion. Recursion code is
shorter than iterative code however it is difficult to understand.
Recursion cannot be applied to all the problem, but it is more useful for the tasks that can be
defined in terms of similar subtasks. For Example, recursion may be applied to sorting,
searching, and traversal problems.
In the following example, recursion is used to calculate the factorial of a number.
int fact(int n)
{
if (n==0)
{
return 0;
}
else if ( n == 1)
{
return 1;
}
else
{
return n*fact(n-1);
}
}
Output
// let n=5
factorial = 120
We can understand the above program of the recursive method call by the figure given below:

10
34
www.gradeup.co

7.1. Recursive Function

A recursive function performs the tasks by dividing it into the subtasks. There is a
termination condition defined in the function which is satisfied by some specific subtask.
After this, the recursion stops and the final result is returned from the function.
The case at which the function doesn't recur is called the base case whereas the instances
where the function keeps calling itself to perform a subtask, is called the recursive case.
All the recursive functions can be written using this format.
Pseudocode for writing any recursive function is given below.
if (test_for_base)
{
return some_value;
}
else if (test_for_another_base)
{
return some_another_value;
}
else
{
// Statements;
recursive call;
}
Example of recursion in C
Let's see an example to find the nth term of the Fibonacci series.
int fibonacci (int n)
{
if (n==0)
return 0;
else if (n == 1)
return 1;
else
return fibonacci(n-1)+fibonacci(n-2);
}
Output
Enter the value of n?12
144
Example-2 Which of the following is correct output for the program code given below?
Main ( )

11
35
www.gradeup.co

{
Void fun ( );
fun ( );
fun ( );
}
void fun ( );
{
static int i = 1;
auto int j = 5;
printf (“%d”, (i++));
printf (“%d”, (j++));
}
A. 1 5 2 6 3 7
B. 2 6 3 7 4 8
C. 1 5 2 5
D. 1 5 2 5 3 5
Answer-C
Solution :
(c)
An object whose storage class is auto, is reinitialized at every function call whereas an
object a whose storage class static persist its value between different function calles.
When the function fun ( ) is called for the first time, value of i and j are printed and
sequentially incremented. During the second function call, i return its incremented value
whereas j is reintialized, h ence i will print 2 and j will print 5 gain.

8. STORAGE CLASSES IN C

Storage classes in C are used to determine the lifetime, visibility, memory location, and initial
value of a variable. There are four types of storage classes in C
• Automatic
• External
• Static
• Register

12
36
www.gradeup.co

Storage Storage Default

Scope Lifetime
Classes Place Value
Garbage
auto RAM Local Within function
Value
Till the end of the main program Maybe
extern RAM Zero Global
declared anywhere in the program
Till the end of the main program, Retains
static RAM Zero Local
value between multiple functions call
Garbage
register Register Local Within the function
Value

8.1. Automatic
• Automatic variables are allocated memory automatically at runtime.
• The visibility of the automatic variables is limited to the block in which they are defined.
• The scope of the automatic variables is limited to the block in which they are defined.
• The automatic variables are initialized to garbage by default.
• The memory assigned to automatic variables gets freed upon exiting from the block.
• The keyword used for defining automatic variables is auto.
• Every local variable is automatic in C by default.
Example 1
#include <stdio.h>
int main()
{
int a = 10,i;
printf("%d ",++a);
{
int a = 20;
for (i=0;i<3;i++)
{
printf("%d ",a); // 20 will be printed 3 times since it is the local value of a
}
}
printf("%d ",a); // 11 will be printed since the scope of a = 20 is ended.
}
Output:
11 20 20 20 11

13
37
www.gradeup.co

8.2. Static
• The variables defined as static specifier can hold their value between the multiple
function calls.
• Static local variables are visible only to the function or the block in which they are
defined.
• A same static variable can be declared many times but can be assigned at only one
time.
• Default initial value of the static integral variable is 0 otherwise null.
• The visibility of the static global variable is limited to the file in which it has declared.
• The keyword used to define static variable is static.
Example 1
#include<stdio.h>
void sum()
{
static int a = 10;
static int b = 24;
printf("%d %d \n",a,b);
a++;
b++;
}
void main()
{
int i;
for(i = 0; i< 3; i++)
{
sum(); // The static variables holds their value b/w multiple function calls.
}
}
Output:
10 24
11 25
12 26
8.3. Register
• The variables defined as the register is allocated the memory into the CPU registers
depending upon the size of the memory remaining in the CPU.
• We cannot dereference the register variables, i.e., we can not use &operator for the
register variable.

14
38
www.gradeup.co

• The access time of the register variables is faster than the automatic variables.
• The initial default value of the register local variables is 0.
• The register keyword is used for the variable which should be stored in the CPU
register. However, it is compilers choice whether or not; the variables can be stored
in the register.
• We can store pointers into the register, i.e., a register can store the address of a
variable.
• Static variables can not be stored into the register since we can not use more than one
storage specifier for the same variable.
8.4. External
• The external storage class is used to tell the compiler that the variable defined as
extern is declared with an external linkage elsewhere in the program.
• The variables declared as extern are not allocated any memory. It is only declaration
and intended to specify that the variable is declared elsewhere in the program.
• The default initial value of external integral type is 0 otherwise null.
• We can only initialize the extern variable globally, i.e., we can not initialize the external
variable within any block or method.
• An external variable can be declared many times but can be initialized at only once.
• If a variable is declared as external then the compiler searches for that variable to be
initialized somewhere in the program which may be extern or static. If it is not, then
the compiler will show an error.
Example-1
#include <stdio.h>
int a = 20;
int main()
{
extern int a;
printf("%d",a);
}
Output
20

****

15
39
www.gradeup.co

16
40
www.gradeup.co

1
41
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

4 ARRAYS

1. ARRAYS

• Array is a collection of similar elements having same data type, accessed using a common
name.
• An array is a collection of items stored at contiguous memory locations. The idea is to store
multiple items of the same type together. This makes it easier to calculate the position of
each element by simply adding an offset to a base value, i.e., the memory location of the
first element of the array.
• Array elements occupy contiguous memory locations.
• If first element is “i” and last element is “j” then:
Number of elements before j = j - i
Number of elements including j = j – i + 1
1.1. Declaration of an Array:
type variable[num_elements];
Example: int A[100];
• It creates an array A with 100 integer elements.
• The size of an array A can’t be changed.
• We cannot declare an array without assigning size. If we declare an array without size,
it will throw compile time error.
• The number between the brackets must be a constant.

2. TYPES OF ARRAYS

2.1. One dimensional (1-D) arrays or Linear arrays:

In it each element is represented by a single subscript. The elements are stored in
consecutive memory locations. E.g. A [1], A [2], ….., A [N].
The [] is used for dimensional or the sub-script of the array that is generally used for
declaring the elements of the array. For Accessing the Element from the array we can
use the Subscript of the Array like this
a[3]=4

2
42
www.gradeup.co

This will set the value of 4th element of array.

2.2. Two dimensional (2-D) arrays or Matrix arrays:

In it each element is represented by two subscripts. Thus, a two dimensional m x n array
A has m rows and n columns and contains m*n elements. It is also called matrix array
because in it the elements form a matrix. E.g. A [3] [4] has 3 rows and 4 columns and
3*4 = 12 elements.

Column1 Column2 Column3 Column4

Row1 a[0] [0] a[0] [1] a[0] [2] a[0] [3]

Row2 a[1] [0] a[1] [1] a[1] [2] a[1] [3]

Row3 a[2] [0] a[2] [1] a[2] [1] a[2] [3]

3. INITIALIZATION OF AN ARRAY

• int A[5]= {1,2,3,4,5}; /*Array can be initialized during declaration*/

• int A[5]={1,2,3}; /* Remaining elements are automatically initialized to zero*/
• int A[5]={1,[1]=2, 3,4,[4]=0};/* Array element can be initialized by specifying its index
location*/

Note:

In programming we use * or dereference operator to find the value of the location.

4. POINTERS & ARRAYS

int a[10] : It will be read as an array of 10 elements with integer data type.
• Every array contains a base address which is the address of the first element of the array.
• An array variable is just a pointer to the first element in the array.
• You can access array elements using array notation or pointers.
• print a will print the base address of the array.
• a[0] is the same as *a
• a[1] is the same as *(a + 1)
• a[2] is the same as *(a + 2)
• a = a+0 = &a[0]
• a+1 = &a[1]

3
43
www.gradeup.co

• a+i = &a[i]
• &(*(a+i)) = &a[i] = a+i
• *(&a[i]) = *(a+i) = a[i]
• Address of an element i of array a = a + i * sizeof(element)
Let b be the 2- Dimensional Array b[i][j]
• *(*(b + i) + j) is equivalent to b[i][j], here first * is used to select the rows and the second
* selects the element.
• &b +1 means whole 2-D array is skipped.
• &b gives the base address of the array.
• *b + 1 skips one element.
• *(b + i) + j is equivalent to &b[i][j]
• *(b[i] + j) is equivalent to b[i][j]
• b[i] + j is equivalent to &b[i][j]
• (*(b+i))[j] is equivalent to b[i][j]

5. CALCULATING LOCATION OF AN ELEMENT IN AN ARRAY

5.1. 1-D Arrays

Consider a single dimensional array as A[lb------ub]
The base address of array = BA
Size of each element in array = c
Total elements in array is given by (ub-lb+1)

Then address of any random element A[i] is given by :

Location[A[i]] = BA + (i-lb)*c , where c is size of the element

Example 1: Let A [78……380] , Base address = 1000, size of element = 10

Then LOC (A [250]) = 1000 + (250 – 78) * 10
= 1000 + 2150
= 3150
Example 2: Let A[ -50……100] , Base Address = 1000, size of element = 10
Then LOC( A [60]) = 1000 + (60 – (-50)) * 10
= 1000 + 1100
= 2100
5.2. 2-D Arrays
2-D arrays can be stored in the system in two ways: Row Major order and Column Major
order.
Consider a 2-D array as A[lb1-----ub1] [lb2------ub2]

4
44
www.gradeup.co

The base address of array = BA

Size of each element in array = c
Number of rows = ub1-lb1+1
Number of columns = ub2-lb2+1
In Row Major order, then address of any random element A[i][j] is given by :

Location[A[i][j]] = BA + [(i-lb1)*(ub2-lb2+1)+(j-lb2)]*c, where c is the size of an element.

Where, (i-lb1) gives the number of rows before i,

(ub2-lb2+1) gives the number of column and
(j-lb2) tells the number of columns before j
In Column Major order, then address of any random element A[i][j] is given by :

Location[A[i][j]] = BA + [(j-lb2)*(ub1-lb1+1)+(i-lb1)]*c, where c is the size of an element.

Where, (j-lb2) gives the number of column before j ,

(ub1-lb1+1) gives the number of rows and
(i-lb1) tells the number of rows before i
Example 3: Let A [30…….80 , 3……150] , Base Address = 1000 , size of element = 10
Find LOC( A[73][120]).
Sol: Number of columns = 150 – 3 + 1 = 152
Number of rows = 80 – 30 + 1 = 51
Using Row major:
LOC( A[73][120]) = 1000 + [ (73 – 30)* 152 + (120 – 3)] * 10
= 1000 + 54920
= 55920
Using Column Major:
LOC( A[73][120]) = 1000 + [ (120 – 3)* 51 + (73 – 30)]*10
= 1000 + 59713
= 60713
Example 4: Let A [-25…….75, -35…….125] , Base address = 1000, Size of element = 10
Find LOC( A[50][40])
Sol: Number of columns = 75 – (-25) + 1 = 101
Number of rows = 125 – (-35) + 1 = 161
Using Row major:
LOC( A[50][40]) = 1000 + [ (50-(-25))*101 + (40 – (-35)) *10
= 1000 + (75 *101 + 75) * 10
= 77500
Using Column Major:
LOC( A[50][40]) = 1000 + [ (40 – (-35)) * 161 + ((50-(-25))] *10
= 1000 + 121500
= 122500

5
45
www.gradeup.co

6. STRINGS

• Strings are defined as an array of characters. The difference between a character array and
a string is the string is terminated with a special character ‘\0’.
• A string is a sequence of characters terminated with a null character \0
• Declaring a string is as simple as declaring a 1- Dimensional array.
• Below is the basic syntax for declaring a string in C programming language.
char str_name[size];
String Declration
1. char str [] = {‘A’, ‘B’, ‘C’, ‘D’, ‘\0’};
2. char st [] = “ABCD”;
⇓
‘\0’ would automatically
Inserted at the end in this type of declaration
Example 5: The string "hello world" contains 12 characters including '\0'
• Before the string class, the abstract idea of a string was implemented with just an array of
characters. For example, here is a string:
char label[] = "Single";
The array in the memory will be as follows:
S i n g l e \0
where the beginning of the array is at some location in computer memory.
• A character array can have more characters than the abstract string held in it, as below:
char label [10] = "Single";
The array will look like:

S i n g l e \0

(where 3 array elements are currently unused).

****

6
46
www.gradeup.co

7
47
www.gradeup.co

1
48
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

5 STRUCTURES

Structures-
Structure is a user-defined datatype in C language which allows us to combine data of different types
together. Structure helps to construct a complex data type which is more meaningful. It is somewhat
similar to an Array, but an array holds data of similar type only. But structure on the other hand, can
store data of any type, which is practical more useful.

1. DEFINING A STRUCTURE

struct keyword is used to define a structure. struct defines a new data type which is a collection
of primary and derived datatypes.
Syntax:
struct [structure_tag]
{
//member variable 1
//member variable 2
//member variable 3
...
}[structure_variables];
As you can see in the syntax above, we start with the struct keyword, then it's optional to
provide your structure a name, we suggest you to give it a name, then inside the curly braces,
we have to mention all the member variables, which are nothing but normal C language
variables of different types like int, float, array etc.
After the closing curly brace, we can specify one or more structure variables, again this is
optional.
Note: The closing curly brace in the structure type declaration must be followed by a
semicolon(;).
Example of Structure
struct Student
{
char name[25];
int age;

2
49
www.gradeup.co

char branch[10];
// F for female and M for male
char gender;
};
Here struct Student declares a structure to hold the details of a student which consists of 4
data fields, namely name, age, branch and gender. These fields are called structure
elements or members.
Each member can have different datatype, like in this case, name is an array of char type
and age is of int type etc. Student is the name of the structure and is called as the structure
tag.

2. DECLARING STRUCTU RE VARIABLES

It is possible to declare variables of a structure, either along with structure definition or after
the structure is defined. Structure variable declaration is similar to the declaration of any
normal variable of any other datatype. Structure variables can be declared in following two
ways:
2.1. Declaring Structure variables separately
struct Student
{
char name[25];
int age;
char branch[10];
//F for female and M for male
char gender;
};
struct Student S1, S2; //declaring variables of struct Student
2.2. Declaring Structure variables with structure definition
struct Student
{
char name[25];
int age;
char branch[10];
//F for female and M for male
char gender;
}S1, S2;
Here S1 and S2 are variables of structure Student. However this approach is not much
recommended.

3
50
www.gradeup.co

3. ACCESSIN G STRUCTURE MEMBERS

Structure members can be accessed and assigned values in a number of ways. Structure
members have no meaning individually without the structure. In order to assign a value to any
structure member, the member name must be linked with the structure variable using a
dot . operator also called period or member access operator.
For example:
#include<stdio.h>
#include<string.h>
struct Student
{
char name[25];
int age;
char branch[10]; //F for female and M for male
char gender;
};
int main()
{
struct Student s1; /*s1 is a variable of Student type and age is a member of Student*/
s1.age = 18; /* using string function to add name */
strcpy(s1.name, "Camy"); /*displaying the stored values*/
printf("Name of Student 1: %s\n", s1.name);
printf("Age of Student 1: %d\n", s1.age);
return 0;
}

Name of Student 1: Camy

Age of Student 1: 18
We can also use scanf() to give values to structure members through terminal.
scanf(" %s ", s1.name);
scanf(" %d ", &s1.age);

4. STRUCTURE INITIALIZATION

Like a variable of any other datatype, structure variable can also be initialized at compile time.
struct Patient
{
float height;
int weight;

4
51
www.gradeup.co

int age;
};

struct Patient p1 = { 180.75 , 73, 23 }; //initialization

or,
struct Patient p1;
p1.height = 180.75; //initialization of each member separately
p1.weight = 73;
p1.age = 23;

5. ARRAY OF STRUCTURE

We can also declare an array of structure variables. in which each element of the array will
represent a structure variable. Example : struct employee emp[5];
The below program defines an array emp of size 5. Each element of the array emp is of
type Employee.
#include<stdio.h>
struct Employee
{
char ename[10];
int sal;
};

struct Employee emp[5];

int i, j;
void ask()
{
for(i = 0; i < 3; i++)
{
printf("\nEnter %dst Employee record:\n", i+1);
printf("\nEmployee name:\t");
scanf("%s", emp[i].ename);
printf("\nEnter Salary:\t");
scanf("%d", &emp[i].sal);
}
printf("\nDisplaying Employee record:\n");
for(i = 0; i < 3; i++)
{

5
52
www.gradeup.co

printf("\nEmployee name is %s", emp[i].ename);

printf("\nSalary is %d", emp[i].sal);
}
}
void main()
{
ask();
}

6. NESTED STRUCTURES

Nesting of structures, is also permitted in C language. Nested structures means, that one
structure has another structure as member variable.
Example:
struct Student
{
char[30] name;
int age;
/* here Address is a structure */
struct Address
{
char[50] locality;
char[50] city;
int pincode;
}addr;
};

7. STRUCTURE AS FUNCT ION ARGUMENTS

We can pass a structure as a function argument just like we pass any other variable or an array
as a function argument.
Example:
#include<stdio.h>
struct Student
{
char name[10];
int roll;
};
void show(struct Student st);

6
53
www.gradeup.co

void main()
{
struct Student std;
printf("\nEnter Student record:\n");
printf("\nStudent name:\t");
scanf("%s", std.name);
printf("\nEnter Student rollno.:\t");
scanf("%d", &std.roll);
show(std);
}
void show(struct Student st)
{
printf("\nstudent name is %s", st.name);
printf("\nroll is %d", st.roll);
}

8. C STRUCTS AND POI NTERS

In this tutorial, you'll learn to use pointers to access members of structs in C programming.
You will also learn to dynamically allocate memory of struct types.
C Pointers to struct
Here's how you can create pointers to structs
struct name {
member1;
member2;
---
---
};
int main()
{
struct name *ptr, Harry;
}
Here, ptr is a pointer to struct.
Example: Access members using Pointer
To access members of a structure using pointers, we use the -> operator.
#include <stdio.h>
struct person
{

7
54
www.gradeup.co

int age;
float weight;
};
int main()
{
struct person *personPtr, person1;
personPtr = &person1;

printf("Enter age: ");

scanf("%d", &personPtr->age);

printf("Enter weight: ");

scanf("%f", &personPtr->weight);

printf("Displaying:\n");
printf("Age: %d\n", personPtr->age);
printf("weight: %f", personPtr->weight);

return 0;
}
In this example,
the address of person1 is stored in the personPtr pointer using personPtr = &person1;.
Now, you can access the members of person1 using the personPtr pointer.
By the way,
• personPtr->age is equivalent to (*personPtr).age
• personPtr->weight is equivalent to (*personPtr).weight

8
55
www.gradeup.co

9. SELF REFERENTIAL STRUCTURES

Self Referential structures are those structures that have one or more pointers which point to
the same type of structure, as their member.
In other words, structures pointing to the same type of structures are self-referential in nature.
Example:
struct node {
int data1;
char data2;
struct node* link;
};

int main()
{
struct node ob;
return 0;
}
In the above example ‘link’ is a pointer to a structure of type ‘node’. Hence, the structure ‘node’
is a self-referential structure with ‘link’ as the referencing pointer.
An important point to consider is that the pointer should be initialized properly before accessing,
as by default it contains garbage value.
Types of Self Referential Structures
1. Self Referential Structure with Single Link
2. Self Referential Structure with Multiple Links
9.1. Self Referential Structure with Single Link: These structures can have only one self-
pointer as their member. The following example will show us how to connect the objects
of a self-referential structure with the single link and access the corresponding data
members. The connection formed is shown in the following figure.

#include <stdio.h>
struct node {
int data1;
char data2;
struct node* link;
};

9
56
www.gradeup.co

int main()
{
struct node ob1; // Node1

// Initialization
ob1.link = NULL;
ob1.data1 = 10;
ob1.data2 = 20;

struct node ob2; // Node2

// Initialization
ob2.link = NULL;
ob2.data1 = 30;
ob2.data2 = 40;

// Linking ob1 and ob2

ob1.link = &ob2;

// Accessing data members of ob2 using ob1

printf("%d", ob1.link->data1);
printf("\n%d", ob1.link->data2);
return 0;
}
Output:
30
40
9.2. Self Referential Structure with Multiple Links: Self referential structures with
multiple links can have more than one self-pointers. Many complicated data structures
can be easily constructed using these structures. Such structures can easily connect to
more than one nodes at a time. The following example shows one such structure with
more than one links.
The connections made in the above example can be understood using the following figure.

10
57
www.gradeup.co

10. APPLICATIONS

Self referential structures are very useful in creation of other complex data structures like:
• Linked Lists
• Stacks
• Queues
• Trees
• Graphs etc.

****

11
58
www.gradeup.co

12
59
www.gradeup.co

1
60
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

6 LINKED LISTS

1. LINKED LIST

• Linked List is a very commonly used linear data structure which consists of group
of nodes in a sequence.
• Each node holds its own data and the address of the next node hence forming a chain
like structure.
• Linked Lists are used to create trees and graphs.
1.1. Representation of linked list:

A linked list is represented by a pointer to the first node of the linked list. The first node
is called the head. If the linked list is empty, then the value of the head is NULL.
Each node in a list consists of at least two parts:
1) data
2) Pointer (Or Reference) to the next node
1.2. Advantages of Linked Lists
• They are a dynamic in nature which allocates the memory when required.
• Insertion and deletion operations can be easily implemented.
• Stacks and queues can be easily executed.
• Linked List reduces the access time.
1.3. Disadvantages of Linked Lists

• Extra memory space for a pointer is required with each element of the list.

• No element can be accessed randomly; it must access each node sequentially.

• Reverse Traversing is difficult in linked list.

• In Linked Lists we don't need to know the size in advance.

2
61
www.gradeup.co

1.4. Applications of Linked Lists

• Linked lists are used to implement stacks, queues, graphs, etc.
• Linked Lists can also be used to implement Graphs. (Adjacency list representation of
Graph).
• Implementing Hash Tables: Each Bucket of the hash table can itself be a linked list.
(Open chain hashing).
• Undo functionality in Photoshop or Word. Linked list of states.
• A polynomial can be represented in an array or in a linked list by simply storing the
coefficient and exponent of each term.
• However, for any polynomial operation , such as addition or multiplication of
polynomials , linked list representation is more easier to deal with.
• Linked lists are useful for dynamic memory allocation.
• The real-life application where the circular linked list is used is our Personal Computers,
where multiple applications are running.
• All the running applications are kept in a circular linked list and the OS gives a fixed
time slot to all for running. The Operating System keeps on iterating over the linked
list until all the applications are completed.

2. TYPES OF LINKED LIST

2.1. Singly Linked list:

• Each node has a single link to another node is called Singly Linked List.
• Singly Linked List does not store any pointer any reference to the previous node.
• Each node stores the contents of the node and a reference to the next node in the list.
• In a singly linked list, last node has a pointer which indicates that it is the last node.
It requires a reference to the first node to store a single linked list.
• It has two successive nodes linked together in linear way and contains address of the
next node to be followed.
• It has successor and predecessor. First node does not have predecessor while last
node does not have successor. Last node has successor reference as NULL.
• It has only single link for the next node.

Singly Linked List

3
62
www.gradeup.co

• In the above figure, the address of the first node is always store in a reference node
known as Head or Front. Reference part of the last node must be null.
Advantage
1) Insertions and Deletions can be done easily.
2) It does not need movement of elements for insertion and deletion.
3) Space is not wasted as we can get space according to our requirements.
5) It can be extended or reduced according to requirements as size is not fixed.
6) Elements may or may not be stored in consecutive memory available, even then we
can store the data in computer.
7) It is less expensive.
Disadvantage
1) It requires more space as pointers are also stored with the data.
2) Different amount of time is required to access each element.
3) If we have to go to a particular element then we have to go through all those
elements that come before that element.
4) We cannot traverse it from last & only from the beginning.
5) It is not easy to sort the elements stored in the linear linked list.
2.2. Doubly linked list
• Doubly linked list is a sequence of elements in which every node has link to its
previous node and next node.
• Traversing can be done in both directions and displays the contents in the whole list.

Doubly Linked List

• In the above figure, Link1 field stores the address of the previous node and Link2
field stores the address of the next node. The Data Item field stores the actual value
of that node. If we insert a data into the linked list, it will be look like as follows:

Doubly Linked List

4
63
www.gradeup.co

• First node is always pointed by head.

• Previous field of the first node is always NULL, and the next field of the last must be
NULL.
• Doubly linked list contains three fields. Link of two nodes allow traversal of the list in
either direction. There is no need to traverse the list to find the previous node. We
can traverse from head to tail as well as tail to head.
Advantages of Doubly Linked List
• Doubly linked list can be traversed in both forward and backward directions.
• To delete a node in singly linked list, the previous node is required, while in doubly
linked list, we can get the previous node using previous pointer.
• It is very convenient than singly linked list. Doubly linked list maintains the links for
bidirectional traversing.
Disadvantages of Doubly Linked List
• In doubly linked list, each node requires extra space for previous pointer.
• All operations such as Insert, Delete, Traverse etc. require extra previous pointer to
be maintained.
2.3. Circular Linked List:
• Circular linked list is similar to singly linked list. The only difference is that in circular
linked list, the last node points to the first node in the list.
• It is a sequence of elements in which every element has link to its next element in the
sequence and has a link to the first element in the sequence.

Circular Singly Linked List

5
64
www.gradeup.co

Doubly Linked Circular list

• In the above figure we see that, each node points to its next node in the sequence
but the last node points to the first node in the list. The previous element stores the
address of the next element and the last element stores the address of the starting
element. It forms a circular chain because the element points to each other in a
circular way.
• In circular linked list, the memory can be allocated when it is required because it has
a dynamic size.
• Circular linked list is used in personal computers, where multiple applications are
running. The operating system provides a fixed time slot for all running applications
and the running applications are kept in a circular linked list until all the applications
are completed.
• Elements can be inserted anywhere in circular linked list, but in the array, elements
cannot be inserted anywhere in the list because it is in the contiguous memory.
Advantages:
• If we are at a node, then we can go to any node. But in linear linked list it is not
possible to go to previous node.
• It saves time when we must go to the first node from the last node. It can be done in
single step because there is no need to traverse the in between nodes. But in double
linked list, we will have to go through in between nodes.
Disadvantages:
• It is not easy to reverse the linked list.
• If proper care is not taken, then the problem of infinite loop can occur.
• Circular lists are complex as compared to singly linked lists.
• Like singly and doubly lists, circular linked lists also don’t supports direct accessing of
elements.

6
65
www.gradeup.co

3. CREATION OF A NODE

a. Singly Linked List:

Creation of a Node:
Structure of a Node:
#include <stdio.h>
struct Node {
#include <stdlib.h>
int data;
struct node
struct Node* next;
{
};
int data;

struct node *next;

};
int main()
{

struct node *prev,*head,*p;

p=malloc(sizeof(struct node));
scanf("%d",&p->data);
p->next=NULL;
return 0;
}

p= malloc(sizeof(struct node)) : We are allocating the space required for a node by the malloc
function. Now, ‘p’ points to a node (or space allocated for the node).
scanf("%d",&p->data) : We are giving a value to the ‘data’ of ‘p’ after taking the input from
the user.
p->next=NULL : We have given the value to ‘data’ in the previous line and a value of the
pointer ‘next’ (NULL) in this line and thus making our node ‘p’ complete.

7
66
www.gradeup.co

b. Doubly Linked List:

Structure of a Node: Creation of a Node:

struct node void addNode(int data) {

{ //Create a new node

int data; struct node *newNode = (struct no

de*)malloc(sizeof(struct node));
struct node *next; // Pointer to
next node newNode->data = data;

struct node *prev; // Pointer to

previous node

};

c. Circular Linked List:

Creation of a Node:

void create()

node *newnode;

newnode=(node*)malloc(sizeof(node));

printf("\nEnter the node value : ");

scanf("%d",&newnode->info);

newnode->next=NULL;

if(rear==NULL)

front=rear=newnode;

else

rear->next=newnode;

rear=newnode;

rear->next=front;

8
67
www.gradeup.co

4. OPERATIONS ON LINKED LIST

4.1. Single Linked List:

i. Insertion:
a. At Beginning-
1. allocate node
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
2. put in the data
new_node->data = new_data;
3. Make next of new node as head */
new_node->next = (*head_ref);
4. Move the head to point to the new node */
(*head_ref) = new_node;
b. At End-
1. allocate node
struct Node* new_node = (struct Node*) malloc(sizeof(struct Node));
struct Node *last = *head_ref;
2. put in the data
new_node->data = new_data;
3. This new node is going to be the last node, so make next
of it as NULL
new_node->next = NULL;
4. If the Linked List is empty, then make the new node as head
if (*head_ref == NULL)
{
*head_ref = new_node;
return;
}
5. Else traverse till the last node
while (last->next != NULL)
last = last->next;
6. Change the next of last node
last->next = new_node;
return;
c. In the Middle:
Step 1 - Allocate memory and store data for new node
struct node *newNode;
newNode = malloc(sizeof(struct node));
newNode->data = 4;

9
68
www.gradeup.co

Step 2 – Traverse to node just before the required position of new node
struct node *temp = head;
if(temp->next != NULL) {
temp = temp->next;
}
}
Step 3 - Change next pointers to include new node in between
newNode->next = temp->next;
temp->next = newNode;
ii. Deletion:
a. At Beginning:
Step 1 - The first node of the list is to be deleted, therefore, we just need to make the
head, point to the next of the head. This will be done by using the following statements.
ptr = head;
head = ptr->next;
Step 2 - Now, free the pointer ptr which was pointing to the head node of the list. This
will be done by using the following statement.
free(ptr)
b. At End-
Step 1 - If head → next = NULL , then the only node head of the list will be assigned to
null.
ptr = head
head = NULL
free(ptr)
Step 2 - The condition head → next = NULL would fail and therefore, so traverse the
node in order to reach the last node of the list.
For this purpose, declare a temporary pointer temp and assign it to head of the list and
also keep track of the second last node of the list. For this purpose, two pointers ptr and
ptr1 will be used where ptr will point to the last node and ptr1 will point to the second
last node of the list.
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}

10
69
www.gradeup.co

Step 3 - Now, make the pointer ptr1 point to the NULL and the last node of the list that
is pointed by ptr will become free. It will be done by using the following statements.
ptr1->next = NULL;
free(ptr);
c. In the Middle:
Step 1 – If head is null.
if (head == NULL)
return NULL;
if (head->next == NULL)
{
delete head;
return NULL;
}
Step 2 – If had is not null then. Initialize slow and fast pointers to reach the middle of
linked list .
struct Node *slow_ptr = head;
struct Node *fast_ptr = head;
Step 3 - Find the middle and previous of middle.
struct Node *prev; // To store previous of slow_ptr
while (fast_ptr != NULL && fast_ptr->next != NULL)
{
fast_ptr = fast_ptr->next->next;
prev = slow_ptr;
slow_ptr = slow_ptr->next;
}
Step 4 - Delete the middle node
prev->next = slow_ptr->next;
delete slow_ptr;
return head;
}
4.2. Doubly Linked List
i. Insertion:
a. At end-
Step 1 - Create a HEAD pointer which points to the first node of the linked list.
Step 2 - Create a new node TEMP.
Temp ->Data = New_Value;
Temp->Prev = Null;
Temp->Next = Null;

11
70
www.gradeup.co

Step 3 –
if (HEAD ==NULL)
Then, move the address of the new node TEMP into HEAD
else,
Traverse pointer until reached the last node,
Assign HEAD to TEMP->prev and TEMP to Head->next.
b. At beginning-
Step 1 - Allocate the space for the new node in the memory. This will be done by using
the following statement.
ptr = (struct node *)malloc(sizeof(struct node));
Step 2 - Check whether the list is empty or not. The list is empty if the condition head
== NULL holds. In that case, the node will be inserted as the only node of the list and
therefore the prev and the next pointer of the node will point to NULL and the head
pointer will point to this node.
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
Step 3 - In the second scenario, the condition head == NULL become false and the
node will be inserted in beginning. The next pointer of the node will point to the existing
head pointer of the node. The prev pointer of the existing head will point to the new node
being inserted.
ptr->next = head;
head→prev=ptr;
c. In the middle-
Step 1 - Allocate the memory for the new node. Use the following statements for this.
ptr = (struct node *)malloc(sizeof(struct node));
Step 2 - Traverse the list by using the pointer temp to skip the required number of nodes
in order to reach the specified node.
temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL) // the temp will be //null if the list doesn't last long //up to
mentioned location
{
return;
}
}

12
71
www.gradeup.co

Step 3 - The temp would point to the specified node at the end of the for loop. The new
node needs to be inserted after this node therefore we need to make a few pointer
adjustments here. Make the next pointer of ptr point to the next node of temp.
ptr → next = temp → next;
Step 4 - Make the prev of the new node ptr point to temp.
ptr → prev = temp;
Step 5 - Make the next pointer of temp point to the new node ptr.
temp → next = ptr;
Step 6 - Make the previous pointer of the next node of temp point to the new node.
temp → next → prev = ptr;
ii. Deletion:
a. At end-
Step 1 - Traverse to second last element
struct node* temp = head;
while(temp->next->next!=NULL){
temp = temp->next;
}
Step 2 - Change its next pointer to null
temp->next = NULL;
b. At Beginning-
Step 1 - Copy the head pointer to pointer ptr and shift the head pointer to its next.
Ptr = head;
head = head → next;
Step 2 - Now make the prev of this new head node point to NULL. This will be done by
using the following statements.
head → prev = NULL
Step 3 - Now free the pointer ptr by using the free function.
free(ptr)
c. In the Middle-
Step 1 - Traverse to element before the element to be deleted
for(int i=2; i< position; i++) {
if(temp->next!=NULL) {
temp = temp->next;
}
}
Step 2 - Change next pointers to exclude the node from the chain
temp->next = temp->next->next;

13
72
www.gradeup.co

4.3. Circular Linked list

i. Insertion:
a. At beginning
Step 1 - Allocate the memory space for the new node by using the malloc method of C
language.
struct node *ptr = (struct node *)malloc(sizeof(struct node));
Step 2 - In the first scenario, the condition head == NULL will be true. Since, the list in
which, we are inserting the node is a circular singly linked list, therefore the only node of
the list (which is just inserted into the list) will point to itself only. We also need to make
the head pointer point to this node.
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
Step 3 - In the second scenario, the condition head == NULL will become false which
means that the list contains at least one node. In this case, we need to traverse the list
in order to reach the last node of the list. This will be done by using the following
statement.
temp = head;
while(temp->next != head)
temp = temp->next;
Step 4 - At the end of the loop, the pointer temp would point to the last node of the list.
Since, in a circular singly linked list, the last node of the list contains a pointer to the first
node of the list. Therefore, we need to make the next pointer of the last node point to
the head node of the list and the new node which is being inserted into the list will be the
new head node of the list therefore the next pointer of temp will point to the new node
ptr.
temp -> next = ptr;
Step 5 - The next pointer of temp will point to the existing head node of the list.
ptr->next = head;
Step 6 - Now, make the new node ptr, the new head node of the circular singly linked
list.
head = ptr;
b. At End-
Step 1 - Allocate the memory space for the new node by using the malloc method of C
language.
struct node *ptr = (struct node *)malloc(sizeof(struct node));

14
73
www.gradeup.co

Step 2 - In the first scenario, the condition head == NULL will be true. Since, the list in
which, we are inserting the node is a circular singly linked list, therefore the only node of
the list (which is just inserted into the list) will point to itself only. We also need to make
the head pointer point to this node. This will be done by using the following statements.
if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
Step 3 - In the second scenario, the condition head == NULL will become false which
means that the list contains at least one node. In this case, traverse the list in order to
reach the last node of the list.
temp = head;
while(temp->next != head)
temp = temp->next;
Step 4 - At the end of the loop, the pointer temp would point to the last node of the list.
Since, the new node which is being inserted into the list will be the new last node of the
list. Therefore, the existing last node i.e. temp must point to the new node ptr.
temp -> next = ptr;
Step 5 - The new last node of the list i.e. ptr will point to the head node of the list.
ptr -> next = head;
c. In the Middle-
Step 1: Declaring head and tail pointer as null.
struct node *head = NULL;
struct node *tail = NULL;
int size = 0;
Step 2: Creating new node.
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = data;
Step 3: Checks if the list is empty. If list is empty, both head and tail would point to
new node.
if(head == NULL){
head = newNode;
tail = newNode;
newNode->next = head;
}else {
tail->next = newNode;
tail = newNode;
tail->next = head;
}

15
74
www.gradeup.co

Step 4: Adding node int the middle.

if(head == NULL){
//If list is empty, both head and tail would point to new node.
head = newNode;
tail = newNode;
newNode->next = head;
}
else{
struct node *temp, *current = NULL;
//Store the mid-point of the list
int count = (size % 2 == 0) ? (size/2) : ((size+1)/2);
//temp will point to head
temp = head;
for(i = 0; i < count; i++){
//Current will point to node previous to temp.
current = temp;
//Traverse through the list till the middle of the list is reached
temp = temp->next;
}
//current will point to new node
current->next = newNode;
//new node will point to temp
newNode->next = temp;
}
ii. Deletion:
a. At Beginning
Step 1 - If the list is empty then the condition head == NULL will become true, in this
case, print underflow on the screen and make exit.
if(head == NULL)
{
printf("\nUNDERFLOW");
return;
}
Step 2 - If the list contains single node then, the condition head → next == head will
become true. In this case, delete the entire list and make the head pointer free.
if(head->next == head)
{
head = NULL;
free(head);
}

16
75
www.gradeup.co

Step 3 - If the list contains more than one node then, in that case, traverse the list by
using the pointer ptr to reach the last node of the list.

ptr = head;
while(ptr -> next != head)
ptr = ptr -> next;
Step 4 - At the end of the loop, the pointer ptr point to the last node of the list. Since,
the last node of the list points to the head node of the list. Therefore, this will be changed
as, the last node of the list will point to the next of the head node.
ptr->next = head->next;
Step 5 - Free the head pointer by using the free() method in C language.
free(head);
Step 6 - Make the node pointed by the next of the last node, the new head of the list.
head = ptr->next;
b. At End:
Step 1 - If the list is empty then the condition head == NULL will become true, in this
case, print underflow on the screen and make exit.
if(head == NULL)
{
printf("\nUNDERFLOW");
return;
}
Step 2 - If the list contains single node then, the condition head → next == head will
become true. In this case, delete the entire list and make the head pointer free.
if(head->next == head)
{
head = NULL;
free(head);
}
Step 3 - If the list contains more than one element, then in order to delete the last
element, we need to reach the last node. We also need to keep track of the second last
node of the list. For this purpose, the two pointers ptr and preptr are defined.
ptr = head;
while(ptr ->next != head)
{
preptr=ptr;
ptr = ptr->next;
}

17
76
www.gradeup.co

Step 4 - Make just one more pointer adjustment. Make the next pointer of preptr point
to the next of ptr (i.e. head) and then make pointer ptr free.
preptr->next = ptr -> next;
free(ptr);
c. In the Middle:
Step 1: Find length of list
int len = Length(*head);
int count = 1;
struct Node *previous = *head, *next = *head;
Step 2: Check if list doesn't have any node.
if (*head == NULL) {
printf("\nDelete Last List is empty\n");
return;
}
Step 3: Check whether given index is in list or not
if (index >= len || index < 0) {
printf("\nIndex is not Found\n");
return;
}
Step 4: Delete first node and traverse to the last node and delete the required node.
if (index == 0) {
DeleteFirst(head);
return;
}
while (len > 0) {
if (index == count) {
previous->next = next->next;
free(next);
return;
}
previous = previous->next;
next = previous->next;
len--;
count++;
}

return;
}

18
77
www.gradeup.co

5. TIME COMPLEXITY

Insertion Deletion

At Starting At Middle At End At Starting At Middle At End

Singly Linked List 0(1) 0(n) 0(1) 0(n) 0(n) 0(n)

Doubly Linked List 0(1) 0(n) 0(1) 0(1) 0(n) 0(n)

Circular
0(1) 0(n) 0(1) 0(n) 0(n) 0(n)
Linked List

Example 1: Consider the below code, which deletes a node from the beginning of a
list:
Void deletefront()
{
If (head == Null)
return;
else
{
……………….
.………………
……………….
}
}
Which lines will correctly implement else part of above code?
(a) if (head → next == Null )
head = head → next;
(b) if ( head == tail )
head = tail = Null;
else
head = head → next;
(c) if ( head == tail == null)
Head = head → next;
(d) head = head -> next;
Example 2: What does the following function do for a given linked list :
void fun1(struct Node* head)
{
if(head == NULL)
return;
fun1(head->next);
printf("%d ", head->data);
}

19
78
www.gradeup.co

Sol: fun1() prints the given Linked List in reverse manner. For Linked List 1->2->3->4->5,
fun1() prints 5->4->3->2->1.
Example 3: Consider the following function that takes reference to head of a Doubly Linked
List as parameter. Assume that a node of doubly linked list has previous pointer as prev and
next pointer as next.
void fun(struct node **head_ref)
{
struct node *temp = NULL;
struct node *current = *head_ref;
while (current != NULL)
{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}

if(temp != NULL )
*head_ref = temp->prev;
}
Assume that reference of head of following doubly linked list is passed to above
function.
1 2 3 4 5 6.
What should be the modified linked list after the function call?
(a) 2 1 4 3 6 5
(b) 5 4 3 2 1 6.
(c) 6 5 4 3 2 1.
(d) 6 5 4 3 1 2
Sol. The given function reverses the given doubly linked list.
Hence, option C is correct.
Example 4 : The following C function takes a simply-linked list as input argument. It modifies
the list by moving the last element to the front of the list and returns the modified list. Some
part of the code is left blank. Choose the correct alternative to replace the blank line.
typedef struct node
{
int value;
struct node *next;

20
79
www.gradeup.co

}Node;
Node *move_to_front(Node *head)
{
Node *p, *q;
if ((head == NULL: || (head->next == NULL))
return head;
q = NULL; p = head;
while (p-> next !=NULL)
{
q = p;
p = p->next;
}
return head;
}
(a) q = NULL; p->next = head; head = p;
(b) q->next = NULL; head = p; p->next = head;
(c) head = p; p->next = q; q->next = NULL;
(d) q->next = NULL; p->next = head; head = p;
Sol: Option D is correct.
****

21
80
www.gradeup.co

22
81
www.gradeup.co

1
82
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

7 STACKS

1. STACKS

• A stack is a last in first out (LIFO) abstract data type and data structure.
• There are basically three operations that can be performed on stacks. They are:
a) PUSH: Inserting an item into a stack
b) POP: Deleting an item from the stack.
c) PEEK: Displaying the contents of the stack.

The operations work as follows:

1. A pointer called TOP is used to keep track of the top element in the stack.
2. When initializing the stack, we set its value to -1 so that we can check if the stack is empty
by comparing TOP == -1.
3. On pushing an element, we increase the value of TOP and place the new element in the
position pointed to by TOP.
4. On popping an element, we return the element pointed to by TOP and reduce its value.
5. Before pushing, we check if stack is already full.
6. Before popping, we check if stack is already empty.
Time Complexities of operations on stack:
push(), pop() and peek() all take O(1) time as we do not run any loop in any of these
operations.

2
83
www.gradeup.co

2. IMPLEMENTATION OF STACK

2.1. Array Implementation: Array implementation aims to create an array where the first
element inserted is placed at stack[0] and it will be deleted last. In array implementation
track of the element inserted at the top must be kept.
Implementing PUSH:
void push (int val,int n) //n is size of the stack
{
if (top == n )
printf("\n Overflow");
else
{
top = top +1;
stack[top] = val;
}
}

Implementing POP:
int pop ()
{
if(top == -1)
{
printf("Underflow");
return 0;
}
else
{
return stack[top - - ];
}
}
2.2. Linked List Implementation: It is also called as dynamic implementation as the stack
size can grow and shrink as the elements are added or removed respectively from the
stack.
• The PUSH operation on stack is same as insert a node in Single linked list.
• The POP operation is same as delete a node in Single linked List.

3
84
www.gradeup.co

Implementing PUSH:
void push ()
{
int val;
struct node *ptr =(struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("not able to push the element");
}
else
{
printf("Enter the value");
scanf("%d",&val);
if(head==NULL)
{
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;

}
printf("Item pushed");

}
}
Implementing POP:
void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{

4
85
www.gradeup.co

printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");
}
}
2.3. Queue Implementation: A stack can be implemented using two queues. Let stack to
be implemented be ‘s’ and queues used to implement be ‘q1’ and ‘q2’. Stack ‘s’ can be
implemented as:
Newly entered element is always at the front of ‘q1’, so that pop operation just dequeues
from ‘q1’. ‘q2’ is used to put every new element at front of ‘q1’.
a) push(s, x) operation’s step are described below:
• Enqueue x to q2
• One by one dequeue everything from q1 and enqueue to q2.
• Swap the names of q1 and q2
b) pop(s) operation’s function are described below:
• Dequeue an item from q1 and return it.

3. EXPRESSION NOTATION

a) Infix Expression: Here, the binary operator comes between the operands.
Eg: a+b
b) Postfix Expression: Here, the binary operator comes after both the operands. It is also
known as Polish Notation.
Eg: ab+
c) Prefix Expression: Here, the binary operator comes before both the operands. . It is also
known as Reverse Polish Notation.
Eg: +ab

5
86
www.gradeup.co

4. APPLICATIONS OF STACK

4.1. Infix to Postfix:

Operator stack is used for infix to postfix conversion.
Step 1: Scan the Infix string from left to right.
Step 2: Initialize an empty stack.
Step 3: If the scanned character is an operand, add it to the Postfix string.
Step 4: If the scanned character is an operator and if the stack is empty push the
character to stack.
Step 5: If the scanned character is an Operator and the stack is not empty, compare the
precedence of the character with the element on top of the stack.
Step 6: If top Stack has higher precedence over the scanned character pop the stack
else push the scanned character to stack. Repeat this step until the stack is not empty
and top Stack has precedence over the character.
Step 7: Repeat 4 and 5 steps till all the characters are scanned.
Step 8: After all characters are scanned, we have to add any character that the stack
may have to the Postfix string.
If stack is not empty add top Stack to Postfix string and Pop the stack.
Repeat this step as long as stack is not empty.
EXAMPLE:
A+(B*C-(D/E-F)*G)*H

Stack Input Output

Empty A+(B*C-(D/E-F)*G)*H -
Empty +(B*C-(D/E-F)*G)*H A
+ (B*C-(D/E-F)*G)*H A
+( B*C-(D/E-F)*G)*H A
+( *C-(D/E-F)*G)*H AB
+(* C-(D/E-F)*G)*H AB
+(* -(D/E-F)*G)*H ABC
+(- (D/E-F)*G)*H ABC*
+(-( D/E-F)*G)*H ABC*
+(-( /E-F)*G)*H ABC*D
+(-(/ E-F)*G)*H ABC*D
+(-(/ -F)*G)*H ABC*DE
+(-(- F)*G)*H ABC*DE/
+(-(- F)*G)*H ABC*DE/
+(-(- )*G)*H ABC*DE/F
+(- *G)*H ABC*DE/F-

6
87
www.gradeup.co

+(-* G)*H ABC*DE/F-

+(-* )*H ABC*DE/F-G
+ *H ABC*DE/F-G*-
+* H ABC*DE/F-G*-
+* End ABC*DE/F-G*-H
Empty End ABC*DE/F-G*-H*+

4.2. Postfix Evaluation:

• Operand stack is used for evaluation. Scan the postfix expression.
• When an operand encounters while scanning, push on to stack.
• While scanning postfix expression, if operator found then
I. POP top two operands on those
II. Perform the operation on those two operands.
III. PUSH result on top of stack.
• Finally, the stack contains only one value, which represents result of the expression.
Example: 456*+

postfix evolutions through stack in C

Input
Step Operation Stack Calculation
Symbol
1. 4 Push 4
2. 5 Push 4,5
3. 6 Push 4,5,6
4. * Pop (2 elements & Evaluate) 4 5*6 = 30
5. Push result (30) 4,30
6. + Pop (2 elements & Evaluate) Empty 4 + 30 = 34
7. Push result (34) 34
8. No-more elements (pop) Empty 34 (Result)

For eg: 82/ will evaluate to 8/2=4

138*+ will evaluate to (1+3*8)= 25

7
88
www.gradeup.co

4.3. Prefix Evaluation

• Accept a prefix string from the user.
Say (-*+ABCD), let A = 4, B = 3, C = 2, D = 5
i.e. (-*+4325) is the input perfix string.
• Start scanning the string from the right one character at a time.
• If it is an operand, push it in stack.
• If it is an operator, pop opnd1, opnd2 and perform the operation, specified by the
operator. Push the result in the stack.
• Repeat these stepds until arr of input perfix string ends.
Example: -*+4325

Symbol Opnd1 Opnd2 Value Opndstack

5 5

2 5, 2

3 5, 2, 3

4 5, 2, 3, 4

+ 4 3 7 5, 2

5, 2, 7

* 7 2 14 5

5, 14

4.4. Prefix to Postfix:

Step 1: Iterate the given expression from right to left, one character at a time
Step 2: If the character is operand, push it to the stack.
Step 3: If the character is operator,
a. Pop an operand from the stack, say it’s s1.
b. Pop an operand from the stack, say it’s s2.
c. perform (s1 s2 operator) and push it to stack.
Step 4: Once the expression iteration is completed, initialize the result string and pop
out from the stack and add it to the result.
Step 5: Return the result.
(+-435) → (43-5+)

8
89
www.gradeup.co

Symbol Opnd1 Opnd2 Value Opndstack

5 5
3 5, 3
4 5, 3, 4
- 4 3 43- 5
5, 43-
+ 43- 5 43-5+
43-5+
Equivalent Post fix notation: 43-5+
4.5. Infix to Prefix:
Steps to convert infix to prefix expression:
1. Scan the valid infix expression from right to left.
2. Initialize the empty character stack and empty prefix string.
3. If the scanned character is an operand, add it to prefix string.
4. If the scanned character is closing parenthesis, push it to the stack.
5. If the scanned character is opening parenthesis, pop all the characters of the stack
and concatenate to the end of the prefix string until closing parenthesis occurs.
6. Pop the closing parenthesis.
7. If the scanned character is an Operator and the stack is not empty, compare the
precedence of the character with the element on top of the stack. If top element of
the Stack has higher precedence over the scanned character, pop the stack else push
the scanned character to stack. Repeat this step until the stack is not empty and top
Stack has precedence over the character.
8. Repeat steps 3 to 7 until all characters are scanned.
9. If the stack is empty, reverse and return the prefix string.
10. Else, pop the elements of the stack and add it to prefix string, and then reverse and
return the prefix string.
Example 1: Convert the following infix expression to prefix expression:
(a+ (b*c)/(d-e)) = +a/*bc-de
Scan the infix in reverse order i.e. right to left:

Symbol Prefix Stack

) Empty )
) Empty ))
e e ))
- e ))-
d de ))-
( -de )

9
90
www.gradeup.co

/ -de )/
) -de )/)
c c-de )/)
* c-de )/)*
b bc-de )/)*
( *bc-de )/
+ /*bc-de )+
a a/*bc-de )+
( +a/*bc-de Empty

4.6. Recursion using Stacks:

• "Recursion" is technique of solving any problem by calling same function again and
again until some breaking (base) condition where recursion stops and it starts calculating
the solution from there on. For eg. calculating factorial of a given number
• In recursion last function called needs to be completed first.
• As Stack is a LIFO data structure i.e. (Last In First Out) and hence it is used to
implement recursion.
• The High level Programming languages, such as Pascal , C etc. that provides support
for recursion use stack for book keeping.
• In each recursive call, there is need to save the
1. current values of parameters,
2. local variables and
3. the return address (the address where the control has to return from the call).
• Also, as a function calls to another function, first its arguments, then the return address
and finally space for local variables is pushed onto the stack.
Example 2: Convert A * (B + C) * D to postfix notation.
a. ABC+*D
b. AB+C*D
c. ABC+D*
d. None
Answer: A

10
91
www.gradeup.co

Move Current Token Stack Output

1 A empty A
2 * * A
3 ( (* A
4 B (* AB
5 + +(* AB
6 C +(* ABC
7 ) * ABC+
8 * * ABC+*
9 D * ABC+*D
10 empty

Example 3: What is the result of the given postfix expression? abc*+ where a=1,
b=2, c=3.
a) 4
b) 5
c) 6
d) 7
Answer: D
The infix expression is a+b*c. Evaluating it, we get 1+2*3=7
Example 4: +9*26
a. 22
b. 23
c. 21
d. 20
Character Stack (Front to
Explanation
Scanned Back)
6 6 6 is an operand, push to Stack

2 62 2 is an operand, push to Stack

* is an operator, pop 6 and 2, multiply them and push
* 12 (6*2)
result to Stack
9 12 9 9 is an operand, push to Stack
+ is an operator, pop 12 and 9 add them and push
+ 21 (12 + 9)
result to Stack.

Result: 21

11
92
www.gradeup.co

Example 5: Convert *-A/BC-/AKL

a. ABC/-AK/L-*
b. ABC*-/AK/L-*
c. ABC-/AKL-*
d. ABC/-A/K-*
Sol: Option A

Token Action Stack Notes

L Push L to stack [L]

K Push K to stack [L, K]

A Push A to stack [L, K, A]

Pop A from stack [L, K]

Pop two operands from stack, A and K. Perform AK/and
/ Pop K from stack [L]
push AK/to stack
Push AK/to stack [L, AK/]
Pop AK/from
[L]
stack
Pop two operands from stack, AK/and L. Perform AK/L-
- Pop L from stack []
and push AK/L- to stack
Push AK/L-to
[AK/L-]
stack
C Push C to stack [AK/L-, C]
[AK/L-, C,
B Pop B to stack
B]
Pop B from stack [AK/L-, C]

Pop C from stack [AK/L-] Pop two operands from stack, B and C. Perform BC/
/
and push BC/to stack
[AK/L-,
Push BC/ to stack
BC/]
[AK/L-,
A Push A to stack
BC/,A]
[AK/L-,
Pop A from stack
BC/]
Pop BC/ from Pop two operands from stack, A and BC. Perform ABC/-
- [AK/L-]
stack and push ABC/-to stack
Push ABC/- to [AK/L-,
stack ABC/-]
Pop ABC/- from
[AK/L-]
stack
Pop AK/L- from Pop two operands from stack, ABC/- and AK/L-.
* []
stack Perform ABC/-AK/L-* and push ABC/-AK/L-* to stack
Push ABC/-AK/L- [ABC/-
* to stack AK/L-*]
Postfix Expression: ABC/-AK/L-*

****

12
93
www.gradeup.co

13
94
www.gradeup.co

1
95
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

8 QUEUES

1. QUEUES

Queue is an abstract data structure, somewhat similar to Stacks. Unlike stacks, a queue is
open at both its ends.
One end is always used to insert data (enqueue) and the other is used to remove data
(dequeue).
Queues follow the First In First Out (FIFO) i.e. the first element that is added to the queue
is the first one to be removed.
Elements are always added to the back and removed from the front.

2. TYPES OF QUEUE

2.1. Simple Queue

A simple queue performs 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.
Adding an element will be performed after checking whether the queue is full or not. If
rear < n which indicates that the array is not full then store the element at arr[rear] and
increment rear by 1 but if rear == n then it is said to be an Overflow condition as the
array is full.
An element can only be deleted when there is at least an element to delete i.e. rear > 0.
Now, element at arr[front] can be deleted but all the remaining elements have to shifted
to the left by one position in order for the dequeue operation to delete the second element
from the left on another dequeue operation.

2
96
www.gradeup.co

2. 2. 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.
A circular queue overcomes the problem of un-utilized space in linear queues
implemented as arrays. We can make following assumptions for circular queue.
• If : (Rear+1) % n == Front, then queue is Full
• If Front = Rear, the queue will be empty.
• Each time a new element is inserted into the queue, the Rear is incremented by 1. Rear
= (Rear + 1) ) % n
• Each time, an element is deleted from the queue, the value of Front is incremented by
one. Front = (Front + 1) % n
2.3. 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.

3
97
www.gradeup.co

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

3. OPERATIONS ON QUEUE

In queue, we always dequeue (or access) data, pointed by front pointer and while enqueuing
(or storing) data in the queue we take help of rear pointer.
3.1. Enqueue:
Add (store) an item to the queue.
If the queue is not full, this function adds an element to the back of the queue, else it
prints “OverFlow”.
Step 1: Check if the queue is full.
Step 2: If the queue is full, produce overflow error and exit.
Step 3: If the queue is not full, increment rear pointer to point the next empty space.
Step 4: Add data element to the queue location, where the rear is pointing.
Step 5: return success.
procedure enqueue(data)
Pseudo Code of Enqueue:
procedure enqueue(data)
if queue is full
return overflow
endif
rear ← rear + 1
queue[rear] ← data
return true
end procedure
Implementation of enqueue() in C program:
void enqueue(int queue[], int element, int& rear, int arraySize) {
if(rear == arraySize) // Queue is full

4
98
www.gradeup.co

printf(“OverFlow\n”);
else{
queue[rear] = element; // Add the element to the back
rear++; }
}
3.2. Dequeue:
Remove (access) an item from the queue. Accessing data from the queue is a process
of two tasks − access the data where front is pointing and remove the data after
access.
If the queue is not empty, this function removes the element from the front of the
queue, else it prints “UnderFlow”.
Step 1: Check if the queue is empty.
Step 2: If the queue is empty, produce underflow error and exit.
Step 3: If the queue is not empty, access the data where front is pointing.
Step 4: Increment front pointer to point to the next available data element.
Step 5: Return success.

Pseudo Code of Dequeue:

procedure dequeue
if queue is empty
return underflow
end if
data = queue[front]
front ← front + 1
return true
end procedure

1
Implementation of enqueue() in C program:
void dequeue(int queue[], int& front, int rear) {
if(front == rear) // Queue is empty
printf(“UnderFlow\n”);
else {
queue[front] = 0; // Delete the front element
front++;
}
}

5
99
www.gradeup.co

Time Complexities:
• queue insertion i.e. Enqueue takes O(1).
• queue deletion i.e. Dequeue takes O(1).
• Access time is O(n).

4. APPLICATIONS OF QUEUE

4.1. BFS using queue:

• Queues operate on a first in, first out (FIFO) principle of item access. It is like a standard
line at the grocery story. Anyone that enters the line will be served in the order in which
they entered.
• When enqueue is performed, element is pushing the element onto the array (think of
this as getting in line at the store).
• When an element is dequeued, it is removed from the queue, and the next element is
then ready to be dequeued (ie. you check out of the grocery line, and the next customer
is ready to be served at the register).

One area where this comes into play is breadth first search. Let’s say you have a tree of
nodes:

The root node (1), would have a data property of 1, with a children array of nodes 8, 5,
and 2. The node with the data property of 8 would have children array of nodes 6, 4, and
3, and so on.

6
100
www.gradeup.co

4.2. Priority Queue

• A priority queue is a special type of queue in which each element is associated with a
priority and is served according to its priority.
• If elements with the same priority occur, they are served according to their order in the
queue.
Generally, the value of the element itself is considered for assigning the priority.
For example: The element with the highest value is considered as the highest priority
element. However, in other case, we can assume the element with the lowest value as
the highest priority element. In other cases, we can set priority according to our need.
There are two types of priority queue:
a) Ascending Priority Queue: It is a collection of items in which items can be inserted
arbitrarily and from which only the smallest items can be removed.
b) Descending Priority Queue: It is a collection of items in which items can be inserted
arbitrarily and from which only the largest items can be removed.

4.2.1. Priority Queue Applications

Priority queues have many applications and below are few of them:
• Data compression: Huffman Coding algorithm
• Shortest path algorithms: Dijkstra’s algorithm
• Minimum spanning tree algorithms: Prim’s algorithm
• Event-driven simulation: customers in a line
• Selection problem: Finding kth -smallest element

7
101
www.gradeup.co

5. IMPLEMENTING QUEUE USING STACK

The following algorithm will implement a queue using two stacks.

Step 1: When calling the enqueue method, simply push the elements into the stack 1.
Step 2: If the dequeue method is called, push all the elements from stack 1 into stack 2, which
reverses the order of the elements. Now pop from stack 2.
For example: Suppose we push "a", "b, "c" to a stack. If we are trying to implement a queue
and we call the dequeue method 3 times, we actually want the elements to come out in the
order: "a", "b, "c", which is in the opposite order they would come out if we popped from the
stack. So, basically, we need to access the elements in the reverse order that they exist in the
stack.

6. APPLICATIONS OF QUEUE

• Breadth first Search can be implemented.

• CPU Scheduling
• Handling of interrupts in real-time systems
• Routing Algorithms
• Computation of shortest paths
• Computation a cycle in the graph
****

8
102
www.gradeup.co

9
103
www.gradeup.co

1
104
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

9 TREES

1. TREES

• A tree is a non-linear data structure designated at a special node called the root and
elements are arranged in levels without containing cycles.
• All the elements are arranged in layers.
• A unique path traverses from root to any node of tree.
• Every child has only one parent, but the parent can have many children.
• If a tree has N vertices(nodes) than the number of edges is always one less than the number
of nodes(vertices) i.e N-1. If it has more than N-1 edges it is called a graph not a tree.

• A is the root of the tree

• A is Parent of B, C and D
• B is child of A
• B, C and D are siblings
• A is grand-parent of E, F, G, H and I

2
105
www.gradeup.co

2. TYPES OF TREES

2.1. Binary Tree:

It is a special type of tree where each node of tree contains either 0 or 1 or 2 children.
(or)
Binary Tree is either empty, or it consists of a root with two binary
Properties of binary tree :
• Binary tree partitioned into three parts.
• First subset contains root of tree
• Second subset is called left subtree
• Another subset is called right subtree
• Each subtree is a binary tree.
• Degree of any node is 0/1/2.
• The maximum number of nodes in a tree with height ‘h’ is 2 h+1 – 1.
• The maximum number of nodes at level ‘i’ is 2i-1.
• For any non-empty binary tree, the number of terminal nodes with n2, nodes of degree
2 is N0 = n2 + 1
• The maximum number of nodes in a tree with depth d is 2 d-1.

• Time Complexities:
Insertion: O(n) {Every Case}
Deletion: O(n) {Every Case}
2n
Number of different Binary Tree possible with ‘n’ labelled nodes = Cn
 n!
n+1

2𝑛𝐶𝑛
Number of different Binary Tree possible with ‘n’ unlabelled nodes =
𝑛+1

3
106
www.gradeup.co

2.1.1. Types of Binary Trees:

a. Full Binary Tree

• If each node of binary tree has either two children or no child at all, is said to be
a Full Binary Tree.
• Full binary tree is also called as Strictly Binary Tree.

• Every node in the tree has either 0 or 2 children.

• Full binary tree is used to represent mathematical expressions.
b. Complete Binary Tree
• If all levels of tree are completely filled except the last level and the last level has all
keys as left as possible, is said to be a Complete Binary Tree.
• Complete binary tree is also called as Perfect Binary Tree.

4
107
www.gradeup.co

• In a complete binary tree, every internal node has exactly two children and all leaf
nodes are at same level.
• For example, at Level 2, there must be 22 = 4 nodes and at Level 3 there must be 23 =
8 nodes.
c. Skewed Binary Tree
• If a tree which is dominated by left child node or right child node, is said to be
a Skewed Binary Tree.
• In a skewed binary tree, all nodes except one have only one child node. The remaining
node has no child.

• In a left skewed tree, most of the nodes have the left child without corresponding right
child.
• In a right skewed tree, most of the nodes have the right child without corresponding
left child.
d. Strict Binary Tree:
• If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is
called a strict binary tree.
• A strict binary tree with n leaves always contains 2n -1 nodes.

• If every non-leaf node in a binary tree has nonempty left and right subtrees,
the tree is termed a strict binary tree. Or, to put it another way, all of the nodes in
a strict binary tree are of degree zero or two, never degree one.

5
108
www.gradeup.co

f. Rooted Binary Tree:

A rooted binary tree is a binary tree in which only the root is allowed to have degree 2.
The remaining nodes have degree equal to either 1 or 3.

1. Binary Search Tree:

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned
properties −
a. All the elements of the left sub-tree of a node has a key less than or equal to its parent
node's key.
b. All the elements of the the right sub-tree of a node has a key greater than to its parent
node's key.
Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-
tree and can be defined as −
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
• Time Complexities:
Insertion: O(n) {worst Case}
O(1) { Best Case}
O(logn) { Average Case}

Deletion: O(n) {worst Case}

O(1) { Best Case}
O(logn) { Average Case}

6
109
www.gradeup.co

3. TREE TRAVERSAL

Binary tree traversing methods :

The binary tree contains 3 parts :
V = root
L = Left subtree
R = Right Subtree
3.1. Pre-order : (V, L, R)
• Visit root of the tree first
• Traverse the left-subtree in pre-order
• Traverse the right-subtree in perorder
3.2. In-order : (L, V, R)
• Traverse the left-subtree in in-order
• Visit Root of the tree
• Traverse right-sub tree in in-order
3.3. Post-order : (L, R, V)
• Traverse the left subtree in post-order
• Traverse the Right-subtree in post-order
• Visit root of the tree
Example 1 :

Pre-order : A B D F E C G I H J
In-order : F D B E A G I C H J
Post-order : F D E B I G J H C A
Pre-order, In-order and post-order uniquely identify the tree.

7
110
www.gradeup.co

4. OPERATIONS ON BINARY SEARCH TREE

4.1. BST Insertion:

Insert function is used to add a new element in a binary search tree at appropriate
location. Insert function is to be designed in such a way that, it must node violate the
property of binary search tree at each value.
1. Allocate the memory for tree.
2. Set the data part to the value and set the left and right pointer of tree, point to NULL.
3. If the item to be inserted, will be the first element of the tree, then the left and right
of this node will point to NULL.
4. Else, check if the item is less than the root element of the tree, if this is true, then
recursively perform this operation with the left of the root.
5. If this is false, then perform this operation recursively with the right sub-tree of the
root.
Example 2: Insert 43, 10, 79, 90, 12, 54, 11, 9, 50 in a BST.
1. Insert 43 into the tree as the root of the tree.
2. Read the next element, if it is lesser than the root node element, insert it as the root
of the left sub-tree.
3. Otherwise, insert it as the root of the right of the right sub-tree.
The process of creating BST by using the given elements, is shown in the image below.

8
111
www.gradeup.co

4.2. BST Deletion:

Delete function is used to delete the specified node from a binary search tree. However,
we must delete a node from a binary search tree in such a way, that the property of
binary search tree doesn't violate. There are three situations of deleting a node from
binary search tree.
CASE 1: The node to be deleted is a leaf node
It is the simplest case, in this case, replace the leaf node with the NULL and simple free
the allocated space.
Here node 85 is deleted, since the node is a leaf node, therefore the node will be replaced
with NULL and allocated space will be freed.

CASE 2: The node to be deleted has only one child.

In this case, replace the node with its child and delete the child node, which now contains
the value which is to be deleted. Simply replace it with the NULL and free the allocated
space.
In the following image, the node 12 is to be deleted. It has only one child. The node will
be replaced with its child node and the replaced node 12 (which is now leaf node) will
simply be deleted.

CASE 3: The node to be deleted has two children.

It is a bit complexed case compare to other two cases. However, the node which is to be
deleted, is replaced with its in-order successor or predecessor recursively until the node
value (to be deleted) is placed on the leaf of the tree. After the procedure, replace the
node with NULL and free the allocated space.

9
112
www.gradeup.co

In the following image, the node 50 is to be deleted which is the root node of the tree.
The in-order traversal of the tree given below.
6, 25, 30, 50, 52, 60, 70, 75.
replace 50 with its in-order successor 52. Now, 50 will be moved to the leaf of the tree,
which will simply be deleted.

NOTE:

The inorder traversal of BST is in sorted order.

Example 3: Which of the following list of nodes corresponds to post order traversal of
the binary tree shown below?

(A) A B C D E F G H I J
(B) J I H G F E D C B A
(C) D H E B I F J G C A
(D) D E H F I G J B C A
Sol: The correct option is C as in post oredr traversal we follow left child, right child, root.
Hence DHEBIFJGCA.
9. A binary search tree is generated by inserting in order the following integers :
55, 15, 65, 5, 25, 59, 90, 2, 7, 35, 60, 23
The number of nodes in the left subtree and right sub tree of the root respectively are
(A) 8, 3
(B) 7, 4
(C) 3, 8
(D) 4, 7

10
113
www.gradeup.co

Ans. 55, 15, 65, 5, 25, 59, 90, 2, 7, 35, 60, 23

Here 55 is the root node so, all the elements smaller than 55 will go on the left of all the
elements greater than 55 will go on the RHS.
Hence, option B is correct
Example 4 : How many distinct binary search trees can be constructed out of 4
distinct keys?
a. 14
b. 24
c. 35
d. 5
Solution-
Number of distinct binary search trees possible with 4 distinct keys
= 2n
Cn / n+1
= 2×4
C4 / 4+1
= C4 / 5
8

= 14
Thus, Option (A) is correct.
Example 5: Consider we want to draw all the binary trees possible with 3
unlabelled nodes.
Sol: Number of binary trees possible with 3 unlabelled nodes
= 2x3
C3 / (3 + 1)
= 6C3 / 4
=5

11
114
www.gradeup.co

5. HEAPS

• Heap is a special case of balanced binary tree data structure where the root-node key is
compared with its children and arranged accordingly.
• Heaps also has an additional property that all leaves should be at h or h-1 levels, where h
is the height of the tree.
Min-Heap − Where the value of the root node is less than or equal to either of its children.
The same property must be true for all subtrees.

Max-Heap − Where the value of the root node is greater than or equal to either of its children.
The same property must be true for all subtrees.

5.1. Implementation of a Heap in an array

To implement a min-heap using an array, put the min-heap in the image above into an
array:

10 14 19 26 31 42 27 10 26 14

By looking at the i-th index in an array:

• Parent is at the floor (i-1)/2 index.
• Left child is at 2 * i + 1 index.
• Right child is at 2 *i + 2 index.
In complete binary trees, each level is filled up before another level is added and the
levels are filled from left to right.

12
115
www.gradeup.co

5.2. Heapifying an element:

After inserting an element into heap, it may not form a heap as it may not satisfy the
heap property. In that case, adjust the location of the heap to make it heap again. This
process is called heapifying.
In max-heap, to heapify an element, find the maximum of its children and swap it with
the current element and continue this process until the heap property is satisfied at every
node.

One important property of heap is that, if an element is not satisfying the heap property
then all the elements from that element to root will also have the same problem.
In below example, element 1 is not satisfying the heap property and its parent 31 is also
having the issue. Similarly, if we heapify an element then all the elements from that
element to root will also satisfy the heap property automatically.
In the above heap, the element 1 is not satisfying the heap property so, heapifying this
element.
To heapify 1, find maximum of its children and swap with that.

Continue this process until the element satisfies the heap properties. Now, swap 1 with
8.

Now the tree is satisfying the heap property.

13
116
www.gradeup.co

5.3. Inserting an Element:

Insertion of an element is very much similar to heapify and deletion process.
Increase the heap size
Keep the new element at the end of the heap (tree)
Heapify the element from bottom to top (root)
Here inserting the element 19 at the end of the heap, the heap property is not satisfied.

In-order to heapify this element (19), compare it with its parent and adjust them.
Swapping 19 and 14 gives :

Again swap 19 and 16 :

Now the tree is satisfying the heap property.

14
117
www.gradeup.co

5.4. Deleting an Element:

Deleting an element at any intermediary position in the heap can be costly, so replace
the element to be deleted by the last element and delete the last element of the Heap.
• Replace the root or element to be deleted by the last element.
• Delete the last element from the Heap.
• Since, the last element is placed at the position of the root node. So, it may not follow
the heap property. Therefore, heapify the last node placed at the position of root.
Example 6: Suppose the Heap is a Max-Heap as:
10
/ \
5 3
/\
2 4
The element to be deleted is root, i.e. 10.
Sol: Here, the last element is 4.
Step 1: Replace the last element with root, and delete it.
4
/ \
5 3
/
2
Step 2: Heapify root.
Final Heap:
5
/ \
4 3
/
2

15
118
www.gradeup.co

6. AVL TREE

• AVL tree is a height balanced tree.

• It is a self-balancing binary search tree.
• AVL tree is another balanced binary search tree.
• AVL trees have a faster retrieval.
• In AVL tree, heights of left and right subtree cannot be more than one for all nodes.
• To find out the balanced factor:

Balanced factor = Height of left subtree – Height of Right subtree

• The above tree is AVL tree because the difference between heights of left and right subtrees
for every node is less than or equal to 1.
• The above tree is not AVL because the difference between heights of left and right subtrees
for 9 and 19 is greater than 1.
• It checks the height of the left and right subtree and assures that the difference is not more
than 1. The difference is called balance factor.
• Time Complexities:
Insertion: O(logn)
Deletion: O(logn)
• The minimum number of nodes with height h is:

N(h) = minimum number of nodes with height h-1 + minimum number of nodes with height h-2 + 1

6.1. Operations on AVL:

a. Insertion:
• Insertion in AVL tree is performed in the same way as it is performed in a binary search
tree. The new node is added into AVL tree as the leaf node. However, it may lead to
violation in the AVL tree property and therefore the tree may need balancing.
• The tree can be balanced by applying rotations. Rotation is required only if, the balance
factor of any node is disturbed upon inserting the new node, otherwise the rotation is not
required.
• Depending upon the type of insertion, the Rotations are categorized into four categories

16
119
www.gradeup.co

i. Left Rotation
If a tree becomes unbalanced, when a node is inserted into the right subtree of the right
subtree, then we perform a single left rotation −

Here, node A has become unbalanced as a node is inserted in the right subtree of A's
right subtree. Hence, left rotation is performed by making A the left-subtree of B.
ii. Right Rotation
AVL tree may become unbalanced, if a node is inserted in the left subtree of the left
subtree. The tree then needs a right rotation.

Here, the unbalanced node becomes the right child of its left child by performing a right
rotation.
iii. Left-Right Rotation
A left-right rotation is a combination of left rotation followed by right rotation.

17
120
www.gradeup.co

State Action

A node has been inserted into the right subtree of the left subtree. This makes C an
unbalanced node. These scenarios cause AVL tree to perform left-right rotation.

first perform the left rotation on the left subtree of C. This makes A, the left subtree
of B.

Node C is still unbalanced, however now, it is because of the left-subtree of the left-
subtree.

Now right-rotate the tree, making B the new root node of this subtree. C now
becomes the right subtree of its own left subtree.

The tree is now balanced.

18
121
www.gradeup.co

4. Right-Left Rotation
The second type of double rotation is Right-Left Rotation. It is a combination of right
rotation followed by left rotation.

State Action

A node has been inserted into the left subtree of the right subtree. This makes A,
an unbalanced node with balance factor 2.

First, perform the right rotation along C node, making C the right subtree of its
own left subtree B. Now, B becomes the right subtree of A.

Node A is still unbalanced because of the right subtree of its right subtree and
requires a left rotation.

A left rotation is performed by making B the new root node of the

subtree. A becomes the left subtree of its right subtree B.

The tree is now balanced.

19
122
www.gradeup.co

Example 7: Construct an AVL tree by inserting the following elements in the

given order.
63, 9, 19, 27, 18, 108, 99, 81
• At each step,the balance factor for every node is calculated.
• If it is found to be other than -1,0,1 then we need a rotation to rebalance the tree.
• The type of rotation will be estimated by the location of the inserted element with
respect to the critical node.
All the elements are inserted in order to maintain the order of binary search tree.

b. Deletion:
Delete(T,k) means delete a node with the key k from the AVL tree T.
I) Find the node x where k is stored
II) Delete the contents of node x
There are three possible cases:
1) If x has no children (i.e., is a leaf), delete x.
2) If x has one child, let x' be the child of x.

20
123
www.gradeup.co

Notice: x' cannot have a child, since subtrees of T can differ in

height by at most one
-replace the contents of x with the contents of x'
-delete x' (a leaf)
3) If x has two children,
-find x's successor z (which has no left child)
-replace x's contents with z's contents, and
-delete z.
[since z has at most one child, so we use case (1) or (2) to delete z]
III) Third: Go from the deleted leaf towards the
root and at each ancestor of that leaf:
-update the balance factor
-rebalance with rotations if necessary.
Example 8: Delete the node 30 from the AVL tree shown in the following image.

Sol: In this case, the node B has balance factor 0, therefore the tree will be rotated by
using R0 rotation as shown in the following image. The node B(10) becomes the root,
while the node A is moved to its right. The right child of node B will now become the left
child of node A.

21
124
www.gradeup.co

7. B- TREE

• B Tree is a specialized m-way tree that can be widely used for disk access.
• A B-Tree of order m can have at most m-1 keys and m children.
• One of the main reason of using B tree is its capability to store large number of keys in a
single node and large key values by keeping the height of the tree relatively small.

• Time Complexities:
Insertion: O(logn)
Deletion: O(logn)

8. B+ TREE

• B+ Tree is an extension of B Tree which allows efficient insertion, deletion and search
operations.
• In B Tree, Keys and records both can be stored in the internal as well as leaf nodes. Whereas,
in B+ tree, records (data) can only be stored on the leaf nodes while internal nodes can only
store the key values.
• The leaf nodes of a B+ tree are linked together in the form of a singly linked lists to make
the search queries more efficient.

• Time Complexities:
Insertion: O(logn)
Deletion: O(logn)
Example 9: Construct minimal AVL trees of height 0, 1, 2, 3, and 4. What is the number of
nodes in a minimal AVL tree of height 5?
Sol. Let n(h) be the number of nodes in a minimal AVL tree with height h.
N(0) = 1

22
125
www.gradeup.co

N(1) = 2

N(h) = 1 + N (h – 1) + N(h – 2)

N(2) = 1 + N(1) + N(0)

=1+2+1=4

N(3) = 1 + N(2) + n(1)

=1+4+2=7

N(4) = 1 + N(3) + N(2)

= 1 + 7 + 4 = 12
****

23
126
www.gradeup.co

24
127
www.gradeup.co

1
128
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

9 TREES

1. TREES

• A tree is a non-linear data structure designated at a special node called the root and
elements are arranged in levels without containing cycles.
• All the elements are arranged in layers.
• A unique path traverses from root to any node of tree.
• Every child has only one parent, but the parent can have many children.
• If a tree has N vertices(nodes) than the number of edges is always one less than the number
of nodes(vertices) i.e N-1. If it has more than N-1 edges it is called a graph not a tree.

• A is the root of the tree

• A is Parent of B, C and D
• B is child of A
• B, C and D are siblings
• A is grand-parent of E, F, G, H and I

2
129
www.gradeup.co

2. TYPES OF TREES

2.1. Binary Tree:

It is a special type of tree where each node of tree contains either 0 or 1 or 2 children.
(or)
Binary Tree is either empty, or it consists of a root with two binary
Properties of binary tree :
• Binary tree partitioned into three parts.
• First subset contains root of tree
• Second subset is called left subtree
• Another subset is called right subtree
• Each subtree is a binary tree.
• Degree of any node is 0/1/2.
• The maximum number of nodes in a tree with height ‘h’ is 2 h+1 – 1.
• The maximum number of nodes at level ‘i’ is 2i-1.
• For any non-empty binary tree, the number of terminal nodes with n2, nodes of degree
2 is N0 = n2 + 1
• The maximum number of nodes in a tree with depth d is 2 d-1.

• Time Complexities:
Insertion: O(n) {Every Case}
Deletion: O(n) {Every Case}
2n
Number of different Binary Tree possible with ‘n’ labelled nodes = Cn
 n!
n+1

2𝑛𝐶𝑛
Number of different Binary Tree possible with ‘n’ unlabelled nodes =
𝑛+1

3
130
www.gradeup.co

2.1.1. Types of Binary Trees:

a. Full Binary Tree

• If each node of binary tree has either two children or no child at all, is said to be
a Full Binary Tree.
• Full binary tree is also called as Strictly Binary Tree.

• Every node in the tree has either 0 or 2 children.

• Full binary tree is used to represent mathematical expressions.
b. Complete Binary Tree
• If all levels of tree are completely filled except the last level and the last level has all
keys as left as possible, is said to be a Complete Binary Tree.
• Complete binary tree is also called as Perfect Binary Tree.

4
131
www.gradeup.co

• In a complete binary tree, every internal node has exactly two children and all leaf
nodes are at same level.
• For example, at Level 2, there must be 22 = 4 nodes and at Level 3 there must be 23 =
8 nodes.
c. Skewed Binary Tree
• If a tree which is dominated by left child node or right child node, is said to be
a Skewed Binary Tree.
• In a skewed binary tree, all nodes except one have only one child node. The remaining
node has no child.

• In a left skewed tree, most of the nodes have the left child without corresponding right
child.
• In a right skewed tree, most of the nodes have the right child without corresponding
left child.
d. Strict Binary Tree:
• If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is
called a strict binary tree.
• A strict binary tree with n leaves always contains 2n -1 nodes.

• If every non-leaf node in a binary tree has nonempty left and right subtrees,
the tree is termed a strict binary tree. Or, to put it another way, all of the nodes in
a strict binary tree are of degree zero or two, never degree one.

5
132
www.gradeup.co

f. Rooted Binary Tree:

A rooted binary tree is a binary tree in which only the root is allowed to have degree 2.
The remaining nodes have degree equal to either 1 or 3.

1. Binary Search Tree:

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned
properties −
a. All the elements of the left sub-tree of a node has a key less than or equal to its parent
node's key.
b. All the elements of the the right sub-tree of a node has a key greater than to its parent
node's key.
Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-
tree and can be defined as −
left_subtree (keys) ≤ node (key) ≤ right_subtree (keys)
• Time Complexities:
Insertion: O(n) {worst Case}
O(1) { Best Case}
O(logn) { Average Case}

Deletion: O(n) {worst Case}

O(1) { Best Case}
O(logn) { Average Case}

6
133
www.gradeup.co

3. TREE TRAVERSAL

Binary tree traversing methods :

The binary tree contains 3 parts :
V = root
L = Left subtree
R = Right Subtree
3.1. Pre-order : (V, L, R)
• Visit root of the tree first
• Traverse the left-subtree in pre-order
• Traverse the right-subtree in perorder
3.2. In-order : (L, V, R)
• Traverse the left-subtree in in-order
• Visit Root of the tree
• Traverse right-sub tree in in-order
3.3. Post-order : (L, R, V)
• Traverse the left subtree in post-order
• Traverse the Right-subtree in post-order
• Visit root of the tree
Example 1 :

Pre-order : A B D F E C G I H J
In-order : F D B E A G I C H J
Post-order : F D E B I G J H C A
Pre-order, In-order and post-order uniquely identify the tree.

7
134
www.gradeup.co

4. OPERATIONS ON BINARY SEARCH TREE

4.1. BST Insertion:

Insert function is used to add a new element in a binary search tree at appropriate
location. Insert function is to be designed in such a way that, it must node violate the
property of binary search tree at each value.
1. Allocate the memory for tree.
2. Set the data part to the value and set the left and right pointer of tree, point to NULL.
3. If the item to be inserted, will be the first element of the tree, then the left and right
of this node will point to NULL.
4. Else, check if the item is less than the root element of the tree, if this is true, then
recursively perform this operation with the left of the root.
5. If this is false, then perform this operation recursively with the right sub-tree of the
root.
Example 2: Insert 43, 10, 79, 90, 12, 54, 11, 9, 50 in a BST.
1. Insert 43 into the tree as the root of the tree.
2. Read the next element, if it is lesser than the root node element, insert it as the root
of the left sub-tree.
3. Otherwise, insert it as the root of the right of the right sub-tree.
The process of creating BST by using the given elements, is shown in the image below.

8
135
www.gradeup.co

4.2. BST Deletion:

Delete function is used to delete the specified node from a binary search tree. However,
we must delete a node from a binary search tree in such a way, that the property of
binary search tree doesn't violate. There are three situations of deleting a node from
binary search tree.
CASE 1: The node to be deleted is a leaf node
It is the simplest case, in this case, replace the leaf node with the NULL and simple free
the allocated space.
Here node 85 is deleted, since the node is a leaf node, therefore the node will be replaced
with NULL and allocated space will be freed.

CASE 2: The node to be deleted has only one child.

In this case, replace the node with its child and delete the child node, which now contains
the value which is to be deleted. Simply replace it with the NULL and free the allocated
space.
In the following image, the node 12 is to be deleted. It has only one child. The node will
be replaced with its child node and the replaced node 12 (which is now leaf node) will
simply be deleted.

CASE 3: The node to be deleted has two children.

It is a bit complexed case compare to other two cases. However, the node which is to be
deleted, is replaced with its in-order successor or predecessor recursively until the node
value (to be deleted) is placed on the leaf of the tree. After the procedure, replace the
node with NULL and free the allocated space.

9
136
www.gradeup.co

In the following image, the node 50 is to be deleted which is the root node of the tree.
The in-order traversal of the tree given below.
6, 25, 30, 50, 52, 60, 70, 75.
replace 50 with its in-order successor 52. Now, 50 will be moved to the leaf of the tree,
which will simply be deleted.

NOTE:

The inorder traversal of BST is in sorted order.

Example 3: Which of the following list of nodes corresponds to post order traversal of
the binary tree shown below?

(A) A B C D E F G H I J
(B) J I H G F E D C B A
(C) D H E B I F J G C A
(D) D E H F I G J B C A
Sol: The correct option is C as in post oredr traversal we follow left child, right child, root.
Hence DHEBIFJGCA.
9. A binary search tree is generated by inserting in order the following integers :
55, 15, 65, 5, 25, 59, 90, 2, 7, 35, 60, 23
The number of nodes in the left subtree and right sub tree of the root respectively are
(A) 8, 3
(B) 7, 4
(C) 3, 8
(D) 4, 7

10
137
www.gradeup.co

Ans. 55, 15, 65, 5, 25, 59, 90, 2, 7, 35, 60, 23

Here 55 is the root node so, all the elements smaller than 55 will go on the left of all the
elements greater than 55 will go on the RHS.
Hence, option B is correct
Example 4 : How many distinct binary search trees can be constructed out of 4
distinct keys?
a. 14
b. 24
c. 35
d. 5
Solution-
Number of distinct binary search trees possible with 4 distinct keys
= 2n
Cn / n+1
= 2×4
C4 / 4+1
= C4 / 5
8

= 14
Thus, Option (A) is correct.
Example 5: Consider we want to draw all the binary trees possible with 3
unlabelled nodes.
Sol: Number of binary trees possible with 3 unlabelled nodes
= 2x3
C3 / (3 + 1)
= 6C3 / 4
=5

11
138
www.gradeup.co

5. HEAPS

• Heap is a special case of balanced binary tree data structure where the root-node key is
compared with its children and arranged accordingly.
• Heaps also has an additional property that all leaves should be at h or h-1 levels, where h
is the height of the tree.
Min-Heap − Where the value of the root node is less than or equal to either of its children.
The same property must be true for all subtrees.

Max-Heap − Where the value of the root node is greater than or equal to either of its children.
The same property must be true for all subtrees.

5.1. Implementation of a Heap in an array

To implement a min-heap using an array, put the min-heap in the image above into an
array:

10 14 19 26 31 42 27 10 26 14

By looking at the i-th index in an array:

• Parent is at the floor (i-1)/2 index.
• Left child is at 2 * i + 1 index.
• Right child is at 2 *i + 2 index.
In complete binary trees, each level is filled up before another level is added and the
levels are filled from left to right.

12
139
www.gradeup.co

5.2. Heapifying an element:

After inserting an element into heap, it may not form a heap as it may not satisfy the
heap property. In that case, adjust the location of the heap to make it heap again. This
process is called heapifying.
In max-heap, to heapify an element, find the maximum of its children and swap it with
the current element and continue this process until the heap property is satisfied at every
node.

One important property of heap is that, if an element is not satisfying the heap property
then all the elements from that element to root will also have the same problem.
In below example, element 1 is not satisfying the heap property and its parent 31 is also
having the issue. Similarly, if we heapify an element then all the elements from that
element to root will also satisfy the heap property automatically.
In the above heap, the element 1 is not satisfying the heap property so, heapifying this
element.
To heapify 1, find maximum of its children and swap with that.

Continue this process until the element satisfies the heap properties. Now, swap 1 with
8.

Now the tree is satisfying the heap property.

13
140
www.gradeup.co

5.3. Inserting an Element:

Insertion of an element is very much similar to heapify and deletion process.
Increase the heap size
Keep the new element at the end of the heap (tree)
Heapify the element from bottom to top (root)
Here inserting the element 19 at the end of the heap, the heap property is not satisfied.

In-order to heapify this element (19), compare it with its parent and adjust them.
Swapping 19 and 14 gives :

Again swap 19 and 16 :

Now the tree is satisfying the heap property.

14
141
www.gradeup.co

5.4. Deleting an Element:

Deleting an element at any intermediary position in the heap can be costly, so replace
the element to be deleted by the last element and delete the last element of the Heap.
• Replace the root or element to be deleted by the last element.
• Delete the last element from the Heap.
• Since, the last element is placed at the position of the root node. So, it may not follow
the heap property. Therefore, heapify the last node placed at the position of root.
Example 6: Suppose the Heap is a Max-Heap as:
10
/ \
5 3
/\
2 4
The element to be deleted is root, i.e. 10.
Sol: Here, the last element is 4.
Step 1: Replace the last element with root, and delete it.
4
/ \
5 3
/
2
Step 2: Heapify root.
Final Heap:
5
/ \
4 3
/
2

15
142
www.gradeup.co

6. AVL TREE

• AVL tree is a height balanced tree.

• It is a self-balancing binary search tree.
• AVL tree is another balanced binary search tree.
• AVL trees have a faster retrieval.
• In AVL tree, heights of left and right subtree cannot be more than one for all nodes.
• To find out the balanced factor:

Balanced factor = Height of left subtree – Height of Right subtree

• The above tree is AVL tree because the difference between heights of left and right subtrees
for every node is less than or equal to 1.
• The above tree is not AVL because the difference between heights of left and right subtrees
for 9 and 19 is greater than 1.
• It checks the height of the left and right subtree and assures that the difference is not more
than 1. The difference is called balance factor.
• Time Complexities:
Insertion: O(logn)
Deletion: O(logn)
• The minimum number of nodes with height h is:

N(h) = minimum number of nodes with height h-1 + minimum number of nodes with height h-2 + 1

6.1. Operations on AVL:

a. Insertion:
• Insertion in AVL tree is performed in the same way as it is performed in a binary search
tree. The new node is added into AVL tree as the leaf node. However, it may lead to
violation in the AVL tree property and therefore the tree may need balancing.
• The tree can be balanced by applying rotations. Rotation is required only if, the balance
factor of any node is disturbed upon inserting the new node, otherwise the rotation is not
required.
• Depending upon the type of insertion, the Rotations are categorized into four categories

16
143
www.gradeup.co

i. Left Rotation
If a tree becomes unbalanced, when a node is inserted into the right subtree of the right
subtree, then we perform a single left rotation −

Here, node A has become unbalanced as a node is inserted in the right subtree of A's
right subtree. Hence, left rotation is performed by making A the left-subtree of B.
ii. Right Rotation
AVL tree may become unbalanced, if a node is inserted in the left subtree of the left
subtree. The tree then needs a right rotation.

Here, the unbalanced node becomes the right child of its left child by performing a right
rotation.
iii. Left-Right Rotation
A left-right rotation is a combination of left rotation followed by right rotation.

17
144
www.gradeup.co

State Action

A node has been inserted into the right subtree of the left subtree. This makes C an
unbalanced node. These scenarios cause AVL tree to perform left-right rotation.

first perform the left rotation on the left subtree of C. This makes A, the left subtree
of B.

Node C is still unbalanced, however now, it is because of the left-subtree of the left-
subtree.

Now right-rotate the tree, making B the new root node of this subtree. C now
becomes the right subtree of its own left subtree.

The tree is now balanced.

18
145
www.gradeup.co

4. Right-Left Rotation
The second type of double rotation is Right-Left Rotation. It is a combination of right
rotation followed by left rotation.

State Action

A node has been inserted into the left subtree of the right subtree. This makes A,
an unbalanced node with balance factor 2.

First, perform the right rotation along C node, making C the right subtree of its
own left subtree B. Now, B becomes the right subtree of A.

Node A is still unbalanced because of the right subtree of its right subtree and
requires a left rotation.

A left rotation is performed by making B the new root node of the

subtree. A becomes the left subtree of its right subtree B.

The tree is now balanced.

19
146
www.gradeup.co

Example 7: Construct an AVL tree by inserting the following elements in the

given order.
63, 9, 19, 27, 18, 108, 99, 81
• At each step,the balance factor for every node is calculated.
• If it is found to be other than -1,0,1 then we need a rotation to rebalance the tree.
• The type of rotation will be estimated by the location of the inserted element with
respect to the critical node.
All the elements are inserted in order to maintain the order of binary search tree.

b. Deletion:
Delete(T,k) means delete a node with the key k from the AVL tree T.
I) Find the node x where k is stored
II) Delete the contents of node x
There are three possible cases:
1) If x has no children (i.e., is a leaf), delete x.
2) If x has one child, let x' be the child of x.

20
147
www.gradeup.co

Notice: x' cannot have a child, since subtrees of T can differ in

height by at most one
-replace the contents of x with the contents of x'
-delete x' (a leaf)
3) If x has two children,
-find x's successor z (which has no left child)
-replace x's contents with z's contents, and
-delete z.
[since z has at most one child, so we use case (1) or (2) to delete z]
III) Third: Go from the deleted leaf towards the
root and at each ancestor of that leaf:
-update the balance factor
-rebalance with rotations if necessary.
Example 8: Delete the node 30 from the AVL tree shown in the following image.

Sol: In this case, the node B has balance factor 0, therefore the tree will be rotated by
using R0 rotation as shown in the following image. The node B(10) becomes the root,
while the node A is moved to its right. The right child of node B will now become the left
child of node A.

21
148
www.gradeup.co

7. B- TREE

• B Tree is a specialized m-way tree that can be widely used for disk access.
• A B-Tree of order m can have at most m-1 keys and m children.
• One of the main reason of using B tree is its capability to store large number of keys in a
single node and large key values by keeping the height of the tree relatively small.

• Time Complexities:
Insertion: O(logn)
Deletion: O(logn)

8. B+ TREE

• B+ Tree is an extension of B Tree which allows efficient insertion, deletion and search
operations.
• In B Tree, Keys and records both can be stored in the internal as well as leaf nodes. Whereas,
in B+ tree, records (data) can only be stored on the leaf nodes while internal nodes can only
store the key values.
• The leaf nodes of a B+ tree are linked together in the form of a singly linked lists to make
the search queries more efficient.

• Time Complexities:
Insertion: O(logn)
Deletion: O(logn)
Example 9: Construct minimal AVL trees of height 0, 1, 2, 3, and 4. What is the number of
nodes in a minimal AVL tree of height 5?
Sol. Let n(h) be the number of nodes in a minimal AVL tree with height h.
N(0) = 1

22
149
www.gradeup.co

N(1) = 2

N(h) = 1 + N (h – 1) + N(h – 2)

N(2) = 1 + N(1) + N(0)

=1+2+1=4

N(3) = 1 + N(2) + n(1)

=1+4+2=7

N(4) = 1 + N(3) + N(2)

= 1 + 7 + 4 = 12
****

23
150
www.gradeup.co

24
151
www.gradeup.co

1
152
www.gradeup.co

PROGRAMMING & DATA STRUCTURES

10 MODERN PROGRAMMING LANGUAGE

Modern Programming Language

Modern programming languages are developed to take the full advantages of modern computer
hardware (Multi-Core CPU, GPU, TPU), mobile devices, large-set of data, fast networking, Container,
and Cloud. Also, most of the modern programming languages offer much higher developer
Ergonomics as given below:
• Concise and terse code (less boilerplate coding)
• Built-in support for concurrency
• Null pointer safety
• Type Inference
• The much simpler feature set
• Lower cognitive load
• Blending the best features of all programming paradigms
Second, many programming languages of the list are disruptive and will change the software
industry forever. Some of them are already mainstream programming languages, while others are
poised to make the breakthrough. It is wise to learn those languages at least as a second programming
language.

1. JAVA

Java is a powerful general-purpose programming language. It is used to develop desktop and

mobile applications, big data processing, embedded systems, and so on. According to Oracle,
the company that owns Java, Java runs on 3 billion devices worldwide, which makes Java one
of the most popular programming languages.
1. Java Environment: The programming environment of Java consists of three components
mainly:
• JDK
• JRE
• JVM
2. Java Basic Syntax: Every programming language has its own set of rules to declare, define
and work on its components. Reading and learning about all of them together is difficult.

2
153
www.gradeup.co

Therefore here is a simple task of printing “Hello World” in Java. During this process, major
components and their syntaxes are explained clearly.
3. Comments in Java: In a program, comments take part in making the program become more
human-readable by placing the detail of code involved and proper use of comments makes
maintenance easier and finding bugs easily. Comments are ignored by the compiler while
compiling the code.
4. Data Types in Java: Each variable in Java has an associated data type. Each data type
requires different amounts of memory and has some specific operations which can be
performed over it.
5. Variables in Java: A variable is the name given to a memory location. It is the basic unit of
storage in a program.
6. Keywords in Java: Keywords or Reserved words are the words in a language that are used
for some internal process or represent some predefined actions. These words are therefore
not allowed to use as variable names or objects. Doing this will result in a compile-time
error.
7. Operators in Java: Operators are the foundation of any programming language. Thus the
functionality of Java programming language is incomplete without the use of operators. We
can define operators as symbols that help us to perform specific mathematical and logical
computations on operands. In other words, we can say that an operator operates the
operands.
8. Decision Making (Control Statements) in Java: Decision Making in programming is similar to
decision making in real life. In programming also we face some situations where we want a
certain block of code to be executed when some condition is fulfilled.
A programming language uses control statements to control the flow of execution of the
program based on certain conditions. These are used to cause the flow of execution to
advance and branch based on changes to the state of a program.
9. Loops in Java: Looping in programming languages is a feature which facilitates the execution
of a set of instructions/functions repeatedly while some condition evaluates to true.
Java provides three ways for executing the loops. While all the ways provide similar basic
functionality, they differ in their syntax and condition checking time.
1.1. How JVM Works – JVM Architecture?
JVM (Java Virtual Machine) acts as a run-time engine to run Java applications. JVM is the
one that calls the main method present in a java code. JVM is a part of JRE (Java Runtime
Environment).
JVM (Java Virtual Machine) Architecture
1. Java Virtual Machine
2. Internal Architecture of JVM

3
154
www.gradeup.co

JVM (Java Virtual Machine) is an abstract machine. It is a specification that provides

runtime environment in which java bytecode can be executed.
JVMs are available for many hardware and software platforms (i.e. JVM is platform
dependent).
What is JVM
It is:
1. A specification where working of Java Virtual Machine is specified. But
implementation provider is independent to choose the algorithm. Its implementation
has been provided by Oracle and other companies.
2. An implementation Its implementation is known as JRE (Java Runtime
Environment).
3. Runtime Instance Whenever you write java command on the command prompt to
run the java class, an instance of JVM is created.
What it does
The JVM performs following operation:
• Loads code
• Verifies code
• Executes code
• Provides runtime environment
• JVM provides definitions for the:
• Memory area
• Class file format
• Register set
• Garbage-collected heap
• Fatal error reporting etc.
1.2. Definition of OOP Concepts in Java
OOP concepts in Java are the main ideas behind Java’s Object Oriented Programming.
They are an abstraction, encapsulation, inheritance, and polymorphism. Grasping them
is key to understanding how Java works. Basically, Java OOP concepts let us create
working methods and variables, then re-use all or part of them without compromising
security.
List of OOP Concepts in Java
There are four main OOP concepts in Java. These are:
• Abstraction. Abstraction means using simple things to represent complexity. We all
know how to turn the TV on, but we don’t need to know how it works in order to enjoy it.
In Java, abstraction means simple things like objects, classes, and variables represent
more complex underlying code and data. This is important because it lets avoid repeating
the same work multiple times.

4
155
www.gradeup.co

• Encapsulation. This is the practice of keeping fields within a class private, then
providing access to them via public methods. It’s a protective barrier that keeps the data
and code safe within the class itself. This way, we can re-use objects like code
components or variables without allowing open access to the data system-wide.
• Inheritance. This is a special feature of Object Oriented Programming in Java. It lets
programmers create new classes that share some of the attributes of existing classes.
This lets us build on previous work without reinventing the wheel.
• Polymorphism. This Java OOP concept lets programmers use the same word to mean
different things in different contexts. One form of polymorphism in Java is method
overloading. That’s when different meanings are implied by the code itself. The other
form is method overriding. That’s when the different meanings are implied by the
values of the supplied variables. See more on this below.
1.3. What is String in java
Generally, String is a sequence of characters. But in Java, string is an object that
represents a sequence of characters. The java.lang.String class is used to create a string
object.
How to create a string object?
There are two ways to create String object:
1. By string literal
2. By new keyword
1) String Literal
Java String literal is created by using double quotes. For Example:
1. String s="welcome";
Each time you create a string literal, the JVM checks the "string constant pool" first. If
the string already exists in the pool, a reference to the pooled instance is returned. If the
string doesn't exist in the pool, a new string instance is created and placed in the pool.
For example:
1. String s1="Welcome";
2. String s2="Welcome";//It doesn't create a new instance
In the above example, only one object will be created. Firstly, JVM will not find any string
object with the value "Welcome" in string constant pool, that is why it will create a new
object. After that it will find the string with the value "Welcome" in the pool, it will not
create a new object but will return the reference to the same instance.
Note: String objects are stored in a special memory area known as the "string constant
pool".
Why Java uses the concept of String literal?

5
156
www.gradeup.co

To make Java more memory efficient (because no new objects are created if it exists
already in the string constant pool).
2) By new keyword
1. String s=new String("Welcome");//creates two objects and one reference variable
In such case, JVM will create a new string object in normal (non-pool) heap memory, and
the literal "Welcome" will be placed in the string constant pool. The variable s will refer
to the object in a heap (non-pool).
Java String Example
public class StringExample{
public static void main(String args[]){
String s1="java";//creating string by java string literal
char ch[]={'s','t','r','i','n','g','s'};
String s2=new String(ch);//converting char array to string
String s3=new String("example");//creating java string by new keyword
System.out.println(s1);
System.out.println(s2);
System.out.println(s3);
}}
Output-
java
strings
example
1.4. Exception Handling in Java
The Exception Handling in Java is one of the powerful mechanism to handle the
runtime errors so that normal flow of the application can be maintained.
In this page, we will learn about Java exceptions, its type and the difference between
checked and unchecked exceptions.
What is Exception in Java
Dictionary Meaning: Exception is an abnormal condition.
In Java, an exception is an event that disrupts the normal flow of the program. It is an
object which is thrown at runtime.
What is Exception Handling
Exception Handling is a mechanism to handle runtime errors such as
ClassNotFoundException, IOException, SQLException, RemoteException, etc.
Advantage of Exception Handling

6
157
www.gradeup.co

The core advantage of exception handling is to maintain the normal flow of the
application. An exception normally disrupts the normal flow of the application that is
why we use exception handling. Let's take a scenario:
statement 1;
statement 2;
statement 3;
statement 4;
statement 5;//exception occurs
statement 6;
statement 7;
statement 8;
statement 9;
statement 10;
Suppose there are 10 statements in your program and there occurs an exception at
statement 5, the rest of the code will not be executed i.e. statement 6 to 10 will not be
executed. If we perform exception handling, the rest of the statement will be executed.
That is why we use exception handling in Java.
Java Exception Keywords
There are 5 keywords which are used in handling exceptions in Java.
Keyword Description

try The "try" keyword is used to specify a block where we should place exception
code. The try block must be followed by either catch or finally. It means, we can't
use try block alone.
catch The "catch" block is used to handle the exception. It must be preceded by try
block which means we can't use catch block alone. It can be followed by finally
block later.
finally The "finally" block is used to execute the important code of the program. It is
executed whether an exception is handled or not.
throw The "throw" keyword is used to throw an exception.

throws The "throws" keyword is used to declare exceptions. It doesn't throw an

exception. It specifies that there may occur an exception in the method. It is
always used with method signature.

1.5. Java inner class

Java inner class or nested class is a class which is declared inside the class or interface.
We use inner classes to logically group classes and interfaces in one place so that it can
be more readable and maintainable.

7
158
www.gradeup.co

Additionally, it can access all the members of outer class including private data members
and methods.
Syntax of Inner class
class Java_Outer_class{
//code
class Java_Inner_class{
//code
}
}
Advantage of java inner classes
There are basically three advantages of inner classes in java. They are as follows:
1) Nested classes represent a special type of relationship that is it can access all the
members (data members and methods) of outer class including private.
2) Nested classes are used to develop more readable and maintainable
code because it logically group classes and interfaces in one place only.
3) Code Optimization: It requires less code to write.
1.6. Multithreading in Java
Multithreading in Java is a process of executing multiple threads simultaneously.
A thread is a lightweight sub-process, the smallest unit of processing. Multiprocessing
and multithreading, both are used to achieve multitasking.
However, we use multithreading than multiprocessing because threads use a shared
memory area. They don't allocate separate memory area so saves memory, and context-
switching between the threads takes less time than process
Java Multithreading is mostly used in games, animation, etc.
Advantages of Java Multithreading
1) It doesn't block the user because threads are independent and you can perform
multiple operations at the same time.
2) You can perform many operations together, so it saves time.
3) Threads are independent, so it doesn't affect other threads if an exception occurs in
a single thread.
Multitasking
Multitasking is a process of executing multiple tasks simultaneously. We use multitasking
to utilize the CPU. Multitasking can be achieved in two ways:
• Process-based Multitasking (Multiprocessing)
• Thread-based Multitasking (Multithreading)
1) Process-based Multitasking (Multiprocessing)

8
159
www.gradeup.co

• Each process has an address in memory. In other words, each process allocates a
separate memory area.
• A process is heavyweight.
• Cost of communication between the process is high.
• Switching from one process to another requires some time for saving and
loading registers, memory maps, updating lists, etc.
2) Thread-based Multitasking (Multithreading)
• Threads share the same address space.
• A thread is lightweight.
• Cost of communication between the thread is low.
1.6. What is Thread in java
A thread is a lightweight subprocess, the smallest unit of processing. It is a separate path
of execution.
Threads are independent. If there occurs exception in one thread, it doesn't affect other
threads. It uses a shared memory area.
Java Multithreading

As shown in the above figure, a thread is executed inside the process. There is context-
switching between the threads. There can be multiple processes inside the OS, and one
process can have multiple threads.

2. (DOT) .NET

The .Net framework is a software development platform developed by Microsoft. The framework
was meant to create applications, which would run on the Windows Platform. The first version
of the .Net framework was released in the year 2002.

9
160
www.gradeup.co

The version was called .Net framework 1.0. The .Net framework has come a long way since
then, and the current version is 4.7.1.
The .Net framework can be used to create both - Form-based and Web-
based applications. Web services can also be developed using the .Net framework.
The framework also supports various programming languages such as Visual Basic and C#. So
developers can choose and select the language to develop the required application. In this
chapter, you will learn some basics of the .Net framework.
• Net Framework Architecture
The basic architecture of the .Net framework is as shown below.

• net framework architecture diagram

• NET Components
The architecture of the .Net framework is based on the following key components;
2.1. Common Language Runtime
The "Common Language Infrastructure" or CLI is a platform on which the .Net programs
are executed.
The CLI has the following key features:
• Exception Handling - Exceptions are errors which occur when the application is
executed.
Examples of exceptions are:
o If an application tries to open a file on the local machine, but the file is not present.
o If the application tries to fetch some records from a database, but the connection to the
database is not valid.
• Garbage Collection - Garbage collection is the process of removing unwanted resources
when they are no longer required.
Examples of garbage collection are
o A File handle which is no longer required. If the application has finished all operations
on a file, then the file handle may no longer be required.

10
161
www.gradeup.co

o The database connection is no longer required. If the application has finished all
operations on a database, then the database connection may no longer be required.
• Working with Various programming languages –
As noted in an earlier section, a developer can develop an application in a variety of .Net
programming languages.
1. Language - The first level is the programming language itself, the most common ones
are VB.Net and C#.
2. Compiler – There is a compiler which will be separate for each programming language.
So underlying the VB.Net language, there will be a separate VB.Net compiler. Similarly,
for C#, you will have another compiler.
3. Common Language Interpreter – This is the final layer in .Net which would be used to
run a .net program developed in any programming language. So the subsequent compiler
will send the program to the CLI layer to run the .Net application.

2.2. Class Library

The .NET Framework includes a set of standard class libraries. A class library is a collection
of methods and functions that can be used for the core purpose.
For example, there is a class library with methods to handle all file-level operations. So
there is a method which can be used to read the text from a file. Similarly, there is a
method to write text to a file.
Most of the methods are split into either the System.* or Microsoft.* namespaces. (The
asterisk * just means a reference to all of the methods that fall under the System or
Microsoft namespace)
A namespace is a logical separation of methods. We will learn these namespaces more in
detail in the subsequent chapters.
2.3. Languages
The types of applications that can be built in the .Net framework is classified broadly into
the following categories.

11
162
www.gradeup.co

• WinForms – This is used for developing Forms-based applications, which would run on
an end user machine. Notepad is an example of a client-based application.
• ASP.Net – This is used for developing web-based applications, which are made to run
on any browser such as Internet Explorer, Chrome or Firefox.
o The Web application would be processed on a server, which would have Internet
Information Services Installed.
o Internet Information Services or IIS is a Microsoft component which is used to execute
an Asp.Net application.
o The result of the execution is then sent to the client machines, and the output is shown
in the browser.
• ADO.Net – This technology is used to develop applications to interact with Databases
such as Oracle or Microsoft SQL Server.
Microsoft always ensures that .Net frameworks are in compliance with all the supported
Windows operating systems.
.Net Framework Design Principle
The following design principles of the .Net framework is what makes it very relevant to
create .Net based applications.
1. Interoperability - The .Net framework provides a lot of backward support. Suppose if
you had an application built on an older version of the .Net framework, say 2.0. And if
you tried to run the same application on a machine which had the higher version of the
.Net framework, say 3.5. The application would still work. This is because with every
release, Microsoft ensures that older framework versions gel well with the latest version.
2. Portability- Applications built on the .Net framework can be made to work on any
Windows platform. And now in recent times, Microsoft is also envisioning to make
Microsoft products work on other platforms, such as iOS and Linux.
3. Security - The .NET Framework has a good security mechanism. The inbuilt security
mechanism helps in both validation and verification of applications. Every application can
explicitly define their security mechanism. Each security mechanism is used to grant the
user access to the code or to the running program.
4. Memory management - The Common Language runtime does all the work or memory
management. The .Net framework has all the capability to see those resources, which
are not used by a running program. It would then release those resources accordingly.
This is done via a program called the "Garbage Collector" which runs as part of the .Net
framework.
The garbage collector runs at regular intervals and keeps on checking which system
resources are not utilized, and frees them accordingly.

12
163
www.gradeup.co

5. Simplified deployment - The .Net framework also have tools, which can be used to
package applications built on the .Net framework. These packages can then be distributed
to client machines. The packages would then automatically install the application.
Summary
• .Net is a programming language developed by Microsoft. It was designed to build
applications which could run on the Windows platform.
• The .Net programming language can be used to develop Forms based applications, Web
based applications, and Web services.
• Developers can choose from a variety of programming languages available on the .Net
platform. The most common ones are VB.Net and C#.

3. PHP

The PHP Hypertext Preprocessor (PHP) is a programming language that allows web developers
to create dynamic content that interacts with databases. PHP is basically used for developing
web based software applications.
What is PHP?
• PHP know as Hypertext Preprocessor is a recursive acronym.
• PHP is a server side scripting which is embedded with HTML.
• PHP used to manage CMS, dynamic content, databases, ecommerce sites, and application
tool.
• PHP is free to use and download. it is a open source scripting language.
• PHP support most of all databases like as MySQL, PostgreSQL, Sybase, Oracle, MicrosoftSQL.
• POP3, IMAP, LDAP and a large number of major protocols support PHP
Where I can use PHP – PHP Common Use:
• PHP performs dynamic content management function by generate dynamic page content
• Collect data from databases and user input by PHP
• Databases Creation, modification and deletion can be perform by PHP.
• File on server can be open read, write and close by PHP.
• Cookies can be send or receive by PHP.
• Data encryption can be by PHP.
• Users can decline to access webpages and web site by PHP.
• Data can send through E-mail by PHP.
A PHP script is executed on the server, and the plain HTML result is sent back to the browser.
3.1. Basic PHP Syntax
A PHP script can be placed anywhere in the document.
A PHP script starts with <?php and ends with ?>:

13
164
www.gradeup.co

<?php
// PHP code goes here
?>
The default file extension for PHP files is ".php".
A PHP file normally contains HTML tags, and some PHP scripting code.
Below, we have an example of a simple PHP file, with a PHP script that uses a built-in
PHP function "echo" to output the text "Hello World!" on a web page:
Example-
<!DOCTYPE html>
<html>
<body>
<h1>My first PHP page</h1>
<?php
echo "Hello World!";
?>
</body>
</html>
Note: PHP statements end with a semicolon (;).
3.2. PHP Case Sensitivity
In PHP, keywords (e.g. if, else, while, echo, etc.), classes, functions, and user-defined
functions are not case-sensitive.
In the example below, all three echo statements below are equal and legal:
Example-
<!DOCTYPE html>
<html>
<body>
<?php
ECHO "Hello World!<br>";
echo "Hello World!<br>";
EcHo "Hello World!<br>";
?>
</body>
</html>
3.3. PHP Variables
Variables are "containers" for storing information.
Creating (Declaring) PHP Variables
In PHP, a variable starts with the $ sign, followed by the name of the variable:

14
165
www.gradeup.co

Example-
<?php
$txt = "Hello world!";
$x = 5;
$y = 10.5;
?>
After the execution of the statements above, the variable $txt will hold the value Hello
world!, the variable $x will hold the value 5, and the variable $y will hold the value 10.5.
Note: When you assign a text value to a variable, put quotes around the value.
Note: Unlike other programming languages, PHP has no command for declaring a
variable. It is created the moment you first assign a value to it.
3.4. PHP Variables
A variable can have a short name (like x and y) or a more descriptive name (age,
carname, total_volume).
Rules for PHP variables:
• A variable starts with the $ sign, followed by the name of the variable
• A variable name must start with a letter or the underscore character
• A variable name cannot start with a number
• A variable name can only contain alpha-numeric characters and underscores (A-z, 0-
9, and _ )
• Variable names are case-sensitive ($age and $AGE are two different variables)
PHP Variables Scope
In PHP, variables can be declared anywhere in the script.
The scope of a variable is the part of the script where the variable can be
referenced/used.
PHP has three different variable scopes:
• local
• global
• static
3.5. PHP echo and print Statements
With PHP, there are two basic ways to get output: echo and print.
echo and print are more or less the same. They are both used to output data to the
screen.
The differences are small: echo has no return value while print has a return value of 1 so
it can be used in expressions. echo can take multiple parameters (although such usage
is rare) while print can take one argument. echo is marginally faster than print.

15
166
www.gradeup.co

The PHP echo Statement:

The echo statement can be used with or without parentheses: echo or echo().
The PHP print Statement
The print statement can be used with or without parentheses: print or print().
3.6. PHP Data Types
Variables can store data of different types, and different data types can do different
things.
PHP supports the following data types:
• String
• Integer
• Float (floating point numbers - also called double)
• Boolean
• Array
• Object
• NULL
• Resource
PHP String
A string is a sequence of characters, like "Hello world!".
$x = "Hello world!";
$y = 'Hello world!';
A string can be any text inside quotes. You can use single or double quotes:
PHP Integer
An integer data type is a non-decimal number between -2,147,483,648 and
2,147,483,647.
Rules for integers:
• An integer must have at least one digit
• An integer must not have a decimal point
• An integer can be either positive or negative
• Integers can be specified in: decimal (base 10), hexadecimal (base 16), octal (base
8), or binary (base 2) notation

4. PYTHON

What is Python?
Python is a popular programming language. It was created by Guido van Rossum, and
released in 1991.
It is used for:
• web development (server-side),
• software development,
• mathematics,

16
167
www.gradeup.co

• system scripting.
What can Python do?
• Python can be used on a server to create web applications.
• Python can be used alongside software to create workflows.
• Python can connect to database systems. It can also read and modify files.
• Python can be used to handle big data and perform complex mathematics.
• Python can be used for rapid prototyping, or for production-ready software development.
Why Python?
• Python works on different platforms (Windows, Mac, Linux, Raspberry Pi, etc).
• Python has a simple syntax similar to the English language.
• Python has syntax that allows developers to write programs with fewer lines than some
other programming languages.
• Python runs on an interpreter system, meaning that code can be executed as soon as it is
written. This means that prototyping can be very quick.
• Python can be treated in a procedural way, an object-orientated way or a functional way.
Good to know
• The most recent major version of Python is Python 3, which we shall be using in this
tutorial. However, Python 2, although not being updated with anything other than security
updates, is still quite popular.
• In this tutorial Python will be written in a text editor. It is possible to write Python in an
Integrated Development Environment, such as Thonny, Pycharm, Netbeans or Eclipse
which are particularly useful when managing larger collections of Python files.
Python Syntax compared to other programming languages
• Python was designed for readability, and has some similarities to the English language
with influence from mathematics.
• Python uses new lines to complete a command, as opposed to other programming
languages which often use semicolons or parentheses.
• Python relies on indentation, using whitespace, to define scope; such as the scope of
loops, functions and classes. Other programming languages often use curly-brackets for
this purpose.
4.1. Execute Python Syntax
As we learned in the previous page, Python syntax can be executed by writing directly
in the Command Line:
>>> print("Hello, World!")
Hello, World!
Or by creating a python file on the server, using the .py file extension, and running it in
the Command Line:

17
168
www.gradeup.co

4.2. Python Indentation

• Indentation refers to the spaces at the beginning of a code line.
• Where in other programming languages the indentation in code is for readability only,
the indentation in Python is very important.
• Python uses indentation to indicate a block of code.
Example-
if 5 > 2:
print("Five is greater than two!")
indentation followed→ No error here.
Example-
if 5 > 2:
print("Five is greater than two!")
indentation not followed→ Syntax Error
Note- Python will give you an error if you skip the indentation.
4.3. Python Variables
In Python, variables are created when you assign a value to it:
Example
Variables in Python:
x=5
y = "Hello, World!"
Python has no command for declaring a variable.
Creating Variables
• Variables are containers for storing data values.
• Unlike other programming languages, Python has no command for declaring a variable.
• A variable is created the moment you first assign a value to it.
• String variables can be declared either by using single or double quotes:
Example
x=5
y = "John"
print(x)
print(y)
Note- Variables do not need to be declared with any particular type and can even change
type after they have been set.
Example
x = 4 # x is of type int
x = "Sally" # x is now of type str
print(x)

18
169
www.gradeup.co

Variable Names
A variable can have a short name (like x and y) or a more descriptive name (age,
carname, total_volume). Rules for Python variables:
• A variable name must start with a letter or the underscore character
• A variable name cannot start with a number
• A variable name can only contain alpha-numeric characters and underscores (A-z, 0-9,
and _ )
• Variable names are case-sensitive (age, Age and AGE are three different variables)
Assign Value to Multiple Variables
• Python allows you to assign values to multiple variables in one line:
Example
x, y, z = "Orange", "Banana", "Cherry"
print(x)
print(y)
print(z)
• And you can assign the same value to multiple variables in one line:
Example
x = y = z = "Orange"
print(x)
print(y)
print(z)
4.4. Python Data Types
Built-in Data Types
In programming, data type is an important concept.
Variables can store data of different types, and different types can do different things.
Python has the following data types built-in by default, in these categories:

Text Type: str

Numeric Types: int, float, complex

Sequence Types: list, tuple, range

Mapping Type: dict

Set Types: set, frozenset

Boolean Type: bool

Binary Types: bytes, bytearray, memoryview

19
170
www.gradeup.co

Getting the Data Type

You can get the data type of any object by using the type() function:
Example
Print the data type of the variable x:
x=5
print(type(x))

5. GOLANG

• Golang or Go Programming Language is a statically-typed and procedural programming

language having syntax similar to C language.
• It was developed in 2007 by Robert Griesemer, Rob Pike, and Ken Thompson at Google. But
they launched it in 2009 as an open-source programming language.
• It provides a rich standard library, garbage collection, and dynamic-typing capability and
also provides support for the environment adopting patterns alike to dynamic languages.
Key Features

5.1. Identifiers and Keywords

Identifiers are the user-defined name of the program components. In Go language, an
identifier can be a variable name, function name, constant, statement labels, package
name, or types.
5.2. Data Types
Data types specify the type of data that a valid Go variable can hold. In Go language,
the type is divided into four categories which are as follows:
1. Basic type: Numbers, strings, and booleans come under this category.
2. Aggregate type: Array and structs come under this category.
3. Reference type: Pointers, slices, maps, functions, and channels come under this
category.

20
171
www.gradeup.co

4. Interface type
Here, we will discuss Basic Data Types in the Go language. The Basic Data Types are
further categorized into three subcategories which are:
1. Numbers
2. Booleans
3. Strings
Numbers: In Go language, numbers are divided into three sub-categories that are:
• Integers: In Go language, both signed and unsigned integers are available in four
different sizes as shown in the below table. The signed int is represented by int and the
unsigned integer is represented by uint.
DATA TYPE DESCRIPTION
int8 8-bit signed integer
int16 16-bit sinned integer
int32 32-bit signed integer
int64 64-bit signed integer
uint8 8-bit unsigned integer
uint16 16-bit unsigned integer
uint32 32-bit unsigned integer
uint64 64-bit unsigned integer
int Both in and uint contain same size, either 32 or 64 bit.
uint Both in and uint contain same size, either 32 or 64 bit.
rune It is a synonym of int32 and also represent Unicode code points.
byte It is a synonym of int8.
uintptr It is an unsigned integer type. Its width is not defined, but its can hold
all the bits of a pointer value.

• Floating-Point Numbers: In Go language, floating-point numbers are divided

into two categories as shown in the below table:

DATA TYPE DESCRIPTION

Float32 32-bit IEEE 754 floating-point number
Float64 64-bit IEEE 754 floating-point number

• Complex Numbers: The complex numbers are divided into two parts are shown in
the below table. float32 and float64 are also part of these complex numbers. The in-
built function creates a complex number from its imaginary and real part and in-built
imaginary and real function extract those parts.

21
172
www.gradeup.co

DATA TYPE DESCRIPTION

Complex64 Complex numbers which contain float32 as a real and imaginary component.
Complex128 Complex numbers which contain float64 as a ral and imaginary component

5.3. Variables
A Variable is a placeholder of the information which can be changed at runtime. And
variables allow to Retrieve and Manipulate the stored information.
Rules for Naming Variables:
• Variable names must begin with a letter or an underscore(_). And the names may
contain the letters ‘a-z’ or ’A-Z’ or digits 0-9 as well as the character ‘_’.
• Gradeup, garte, _goprep23 // valid variable
• 123Gradeup, 23grade // invalid variable
• A variable name should not start with a digit.
• The name of the variable is case sensitive.
gradeup and Gradeup are two different variables
• Keywords is not allowed to use as a variable name.
• There is no limit on the length of the name of the variable, but it is advisable to use
an optimum length of 4 – 15 letters only.
There are two ways to declare a variable in Golang as follows:
1. Using var Keyword: In Go language, variables are created using var keyword of a
particular type, connected with name and provide its initial value.
Syntax:
var variable_name type = expression
2. Using short variable declaration: The local variables which are declared and
initialize in the functions are declared by using short variable declaration.
Syntax:
variable_name:= expression

****

22
173
www.gradeup.co

23
174