Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001

Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Data Structures
Semester: 4th Course: BCA

UNIT-1
Introduction
Data Structure can be defined as the group of data elements which
provides an efficient way of storing and organizing data in the computer
so that it can be used efficiently. Some examples of Data Structures are
arrays, Linked List, Stack, Queue, etc. Data Structures are widely used
in almost every aspect of Computer Science i.e. Operating System,
Compiler Design, Artificial intelligence, Graphics and many more.

Data Structures are the main part of many computer science algorithms
as they enable the programmers to handle the data in an efficient way. It
plays a vital role in enhancing the performance of software or a program
as the main function of the software is to store and retrieve the user's
data as fast as possible

Basic Terminology
Data structures are the building blocks of any program or the software.
Choosing the appropriate data structure for a program is the most
difficult task for a programmer. Following terminology is used as far as
data structures are concerned

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 1
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Data: Data can be defined as an elementary value or the collection

of values, for example, student's name and its id are the data about
the student.
Group Items: Data items which have subordinate data items are
called Group item, for example, name of a student can have first
name and the last name.
Record: Record can be defined as the collection of various data
items, for example, if we talk about the student entity, then its
name, address, course and marks can be grouped together to form
the record for the student.
File: A File is a collection of various records of one type of entity,
for example, if there are 60 employees in the class, then there will
be 20 records in the related file where each record contains the data
about each employee.
Attribute and Entity: An entity represents the class of certain
objects. It contains various attributes. Each attribute represents the
particular property of that entity.
Field: Field is a single elementary unit of information representing
the attribute of an entity.

Need of Data Structures

As applications are getting complexed and amount of data is increasing
day by day, there may arise the following problems:

Processor speed: To handle very large amout of data, high speed

processing is required, but as the data is growing day by day to the
billions of files per entity, processor may fail to deal with that
much amount of data.
Data Search: Consider an inventory size of 106 items in a store, If
our application needs to search for a particular item, it needs to

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 2
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

traverse 106 items every time, results in slowing down the search
process.
Multiple requests: If thousands of users are searching the data
simultaneously on a web server, then there are the chances that a
very large server can be failed during that process

In order to solve the above problems, data structures are used. Data is
organized to form a data structure in such a way that all items are not
required to be searched and required data can be searched instantly.

Advantages of Data Structures

Efficiency: Efficiency of a program depends upon the choice of
data structures. For example: suppose, we have some data and we
need to perform the search for a perticular record. In that case, if
we organize our data in an array, we will have to search
sequentially element by element. hence, using array may not be
very efficient here. There are better data structures which can make
the search process efficient like ordered array, binary search tree or
hash tables.
Reusability: Data structures are reusable, i.e. once we have
implemented a particular data structure, we can use it at any other
place. Implementation of data structures can be compiled into
libraries which can be used by different clients.
Abstraction: Data structure is specified by the ADT which
provides a level of abstraction. The client program uses the data
structure through interface only, without getting into the
implementation details.

Data Structure Classification

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 3
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Linear Data Structures: A data structure is called linear if all of its

elements are arranged in the linear order. In linear data structures, the
elements are stored in non-hierarchical way where each element has the
successors and predecessors except the first and last element.

Types of Linear Data Structures are given below:

Arrays: An array is a collection of similar type of data items and
each data item is called an element of the array. The data type of
the element may be any valid data type like char, int, float or
double. The elements of array share the same variable name but
each one carries a different index number known as subscript. The
array can be one dimensional, two dimensional or

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 4
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

multidimensional. The individual elements of the array age are:

age[0], age[1], age[2], age[3],......... age[98], age[99].

Linked List: Linked list is a linear data structure which is used to

maintain a list in the memory. It can be seen as the collection of
nodes stored at non-contiguous memory locations. Each node of
the list contains a pointer to its adjacent node.

Stack: Stack is a linear list in which insertion and deletions are

allowed only at one end, called top. A stack is an abstract data type
(ADT), can be implemented in most of the programming
languages. It is named as stack because it behaves like a real-world
stack, for example: - piles of plates or deck of cards etc.

Queue: Queue is a linear list in which elements can be inserted

only at one end called rear and deleted only at the other end
called front. It is an abstract data structure, similar to stack. Queue
is opened at both end therefore it follows First-In-First-Out (FIFO)
methodology for storing the data items.

Non Linear Data Structures: This data structure does not form a
sequence i.e. each item or element is connected with two or more other
items in a non-linear arrangement. The data elements are not arranged in
sequential structure.

Types of Non Linear Data Structures are given below:

Trees: Trees are multilevel data structures with a hierarchical
relationship among its elements known as nodes. The bottommost
nodes in the hierarchy are called leaf node while the topmost node
is called root node. Each node contains pointers to point adjacent
nodes. Tree data structure is based on the parent-child relationship
among the nodes. Each node in the tree can have more than one
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 5
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

children except the leaf nodes whereas each node can have at most
one parent except the root node. Trees can be classfied into many
categories which will be discussed later in this tutorial.

Graphs: Graphs can be defined as the pictorial representation of

the set of elements (represented by vertices) connected by the links
known as edges. A graph is different from tree in the sense that a
graph can have cycle while the tree cannot have the one.

Operations on data structure

Traversing: Every data structure contains the set of data elements.
Traversing the data structure means visiting each element of the
data structure in order to perform some specific operation like
searching or sorting.

Example: If we need to calculate the average of the marks

obtained by a student in 6 different subject, we need to traverse the
complete array of marks and calculate the total sum, then we will
divide that sum by the number of subjects i.e. 6, in order to find the
average.

Insertion: Insertion can be defined as the process of adding the

elements to the data structure at any location. If the size of data
structure is n then we can only insert n-1 data elements into it.
Deletion: The process of removing an element from the data
structure is called Deletion. We can delete an element from the
data structure at any random location. If we try to delete an
element from an empty data structure then underflow occurs.
Searching: The process of finding the location of an element
within the data structure is called Searching. There are two
algorithms to perform searching, Linear Search and Binary Search.
We will discuss each one of them later in this tutorial.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 6
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Sorting: The process of arranging the data structure in a specific

order is known as Sorting. There are many algorithms that can be
used to perform sorting, for example, insertion sort, selection sort,
bubble sort, etc.
Merging: When two lists List A and List B of size M and N
respectively, of similar type of elements, clubbed or joined to
produce the third list, List C of size (M+N), then this process is
called merging.

Algorithm
An algorithm is a procedure having well defined steps for solving a
particular problem. Algorithm is finite set of logic or instructions,
written in order for accomplish the certain predefined task. It is not the
complete program or code, it is just a solution (logic) of a problem,
which can be represented either as an informal description using a
Flowchart or Pseudo code.

The major categories of algorithms are given below:

Sort: Algorithm developed for sorting the items in certain order.
Search: Algorithm developed for searching the items inside a data
structure.
Delete: Algorithm developed for deleting the existing element
from the data structure.
Insert: Algorithm developed for inserting an item inside a data
structure.
Update: Algorithm developed for updating the existing element
inside a data structure.
The performance of algorithm is measured on the basis of following properties:

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 7
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Time complexity: It is a way of representing the amount of time

needed by a program to run to the completion.
Space complexity: It is the amount of memory space required by
an algorithm, during a course of its execution. Space complexity is
required in situations when limited memory is available and for the
multi user system.

Each algorithm must have:

Specification: Description of the computational procedure.
Pre-conditions: The condition(s) on input.
Body of the Algorithm: A sequence of clear and unambiguous
instructions.
Post-conditions: The condition(s) on output.

Example: Design an algorithm to multiply the two numbers x and

y and display the result in z.

 Step 1 START
 Step 2 declare three integers x, y & z
 Step 3 define values of x & y
 Step 4 multiply values of x & y
 Step 5 store the output of step 4 in z
 Step 6 print z
 Step 7 STOP

Alternatively the algorithm can be written as?

 Step 1 START MULTIPLY
 Step 2 get values of x & y
 Step 3 z← x * y
 Step 4 display z
 Step 5 STOP
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 8
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Characteristics of an Algorithm
An algorithm must follow the mentioned below characteristics:
Input: An algorithm must have 0 or well defined inputs.
Output: An algorithm must have 1 or well defined outputs, and
should match with the desired output.
Feasibility: An algorithm must be terminated after the finite
number of steps.
Independent: An algorithm must have step-by-step directions
which is independent of any programming code.
Unambiguous: An algorithm must be unambiguous and clear.
Each of their steps and input/outputs must be clear and lead to only
one meaning.

Asymptotic Analysis
In mathematical analysis, asymptotic analysis of algorithm is a method
of defining the mathematical boundation of its run-time performance.
Using the asymptotic analysis, we can easily conclude about the average
case, best case and worst case scenario of an algorithm.

It is used to mathematically calculate the running time of any operation

inside an algorithm.

Example: Running time of one operation is x(n) and for another

operation it is calculated as f(n2). It refers to running time will increase
linearly with increase in 'n' for first operation and running time will
increase exponentially for second operation. Similarly the running time
of both operations will be same if n is significantly small.
Usually the time required by an algorithm comes under three types:
Worst case: It defines the input for which the algorithm takes the
huge time.
Average case: It takes average time for the program execution.
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 9
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Best case: It defines the input for which the algorithm takes the
lowest time.

Asymptotic Notations
The commonly used asymptotic notations used for calculating the
running time complexity of an algorithm is given below:
Big oh Notation (Ο))
Omega Notation (Ω))
Theta Notation (θ))

Big oh Notation (O)

It is the formal way to express the upper boundary of an algorithm
running time. It measures the worst case of time complexity or the
longest amount of time, algorithm takes to complete their operation. It is
represented as shown below:

For example: If f(n) and g(n) are the two functions defined for positive
integers, then f(n) is O(g(n)) as f(n) is big oh of g(n) or f(n) is on the
order of g(n)) if there exists constants c and no such that:

F(n)≤cg(n) for all n≥no

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 10
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

This implies that f(n) does not grow faster than g(n), or g(n) is an upper
bound on the function f(n).

Omega Notation (Ω))

It is the formal way to represent the lower bound of an algorithm's
running time. It measures the best amount of time an algorithm can
possibly take to complete or the best case time complexity.

If we required that an algorithm takes at least certain amount of time

without using an upper bound, we use big- Ω) notation i.e. the Greek
letter "omega". It is used to bound the growth of running time for large
input size.

If running time is Ω) (f(n)), then for the larger value of n, the running
time is at least k?f(n) for constant (k). It is represented as shown below:

Theta Notation (?)

It is the formal way to express both the upper bound and lower bound of
an algorithm running time.

Consider the running time of an algorithm is θ (n), if at once (n) gets

large enough the running time is at most k2-n and at least k1 ?n for
some constants k1 and k2. It is represented as shown below:

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 11
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Common Asymptotic Notations

constant - ?(1)
linear - ?(n)
logarithmic - ?(log n)
n log n - ?(n log n)
Exponential - 2?(n)
Cubic - ?(n3)
Polynomial - n?(1)
Quadratic - ?(n2)

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 12
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Pointer
Pointer is used to points the address of the value stored anywhere in the
computer memory. To obtain the value stored at the location is known as
dereferencing the pointer. Pointer improves the performance for
repetitive process such as:
 Traversing String
 Lookup Tables
 Control Tables
 Tree Structures

Pointer Details
Pointer arithmetic: There are four arithmetic operators that can
be used in pointers: ++, --, +, -

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 13
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Array of pointers: You can define arrays to hold a number of

pointers.
Pointer to pointer: C allows you to have pointer on a pointer and
so on.
Passing pointers to functions in C: Passing an argument by
reference or by address enable the passed argument to be changed
in the calling function by the called function.
Return pointer from functions in C: C allows a function to
return a pointer to the local variable, static variable and
dynamically allocated memory as well.

Program
Pointer
1. #include <stdio.h>
2.
3. int main( )
4. {
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 14
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

5. int a = 5;
6. int *b;
7. b = &a;
8.
9. printf ("value of a = %d\n", a);
10. printf ("value of a = %d\n", *(&a));
11. printf ("value of a = %d\n", *b);
12. printf ("address of a = %u\n", &a);
13. printf ("address of a = %d\n", b);
14. printf ("address of b = %u\n", &b);
15. printf ("value of b = address of a = %u", b);
16. return 0;
17. }
Output
 value of a = 5
 value of a = 5
 address of a = 3010494292
 address of a = 1284473004
 address of b = -3010494296
 value of b = address of a = 3010494292

Program

Pointer to Pointer
1. #include <stdio.h>
2.
3. int main( )
4. {
5. int a = 5;
6. int *b;
7. int **c;
8. b = &a;

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 15
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

9. c = &b;
10. printf ("value of a = %d\n", a);
11. printf ("value of a = %d\n", *(&a));
12. printf ("value of a = %d\n", *b);
13. printf ("value of a = %d\n", **c);
14. printf ("value of b = address of a = %u\n", b);
15. printf ("value of c = address of b = %u\n", c);
16. printf ("address of a = %u\n", &a);
17. printf ("address of a = %u\n", b);
18. printf ("address of a = %u\n", *c);
19. printf ("address of b = %u\n", &b);
20. printf ("address of b = %u\n", c);
21. printf ("address of c = %u\n", &c);
22. return 0;
23. }
Pointer to Pointer
 value of a = 5
 value of a = 5
 value of a = 5
 value of a = 5
 value of b = address of a = 2831685116
 value of c = address of b = 2831685120
 address of a = 2831685116
 address of a = 2831685116
 address of a = 2831685116
 address of b = 2831685120
 address of b = 2831685120
 address of c = 2831685128

Structure
A structure is a composite data type that defines a grouped list of
variables that are to be placed under one name in a block of memory. It
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 16
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

allows different variables to be accessed by using a single pointer to the

structure.
Syntax
1. struct structure_name
2. {
3. data_type member1;
4. data_type member2;
5. .
6. .
7. data_type memeber;
8. };

Advantages
It can hold variables of different data types.
We can create objects containing different types of attributes.
It allows us to re-use the data layout across programs.
It is used to implement other data structures like linked lists,
stacks, queues, trees, graphs etc.

Program
1. #include<stdio.h>
2. #include<conio.h>
3. void main( )
4. {
5. struct employee
6. {
7. int id ;
8. float salary ;
9. int mobile ;
10. };
11. struct employee e1,e2,e3 ;
12. clrscr();
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 17
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

13. printf ("\nEnter ids, salary & mobile no. of 3 employee\n"

14. scanf ("%d %f %d", &[Link], &[Link], &[Link]);
15. scanf ("%d%f %d", &[Link], &[Link], &[Link]);
16. scanf ("%d %f %d", &[Link], &[Link], &[Link]);
17. printf ("\n Entered Result ");
18. printf ("\n%d %f %d", [Link], [Link], [Link]);
19. printf ("\n%d%f %d", [Link], [Link], [Link]);
20. printf ("\n%d %f %d", [Link], [Link], [Link]);
21. getch();
22. }

UNIT-2
Array
Definition
Arrays are defined as the collection of similar type of data items
stored at contiguous memory locations.
Arrays are the derived data type in C programming language which
can store the primitive type of data such as int, char, double, float,
etc.
Array is the simplest data structure where each data element can be
randomly accessed by using its index number.
For example, if we want to store the marks of a student in 6
subjects, then we don't need to define different variable for the
marks in different subject. instead of that, we can define an array
which can store the marks in each subject at a the contiguous
memory locations.
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 18
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

The array marks[10] defines the marks of the student in 10 different

subjects where each subject marks are located at a particular subscript in
the array i.e. marks[0] denotes the marks in first
subject, marks[1] denotes the marks in 2nd subject and so on.

Properties of the Array

Each element is of same data type and carries a same size i.e. int =
4 bytes.
Elements of the array are stored at contiguous memory locations
where the first element is stored at the smallest memory location.
Elements of the array can be randomly accessed since we can
calculate the address of each element of the array with the given
base address and the size of data element.

for example, in C language, the syntax of declaring an array is

like following:

 int arr[10]; char arr[10]; float arr[5]

Need of using Array

In computer programming, the most of the cases requires to store the
large number of data of similar type. To store such amount of data, we
need to define a large number of variables. It would be very difficult to
remember names of all the variables while writing the programs. Instead
of naming all the variables with a different name, it is better to define an
array and store all the elements into it.

Following example illustrates, how array can be useful in writing code

for a particular problem.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 19
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

In the following example, we have marks of a student in six different

subjects. The problem intends to calculate the average of all the marks of
the student.

In order to illustrate the importance of array, we have created two

programs, one is without using array and other involves the use of array
to store marks.

Program without array:

#include <stdio.h>
void main ()
{
Int marks_1 = 56, marks_2 = 78, marks_3 = 88, marks_4 = 76, mar
ks_5 = 56, marks_6 = 89;
Float avg = (marks_1 + marks_2 + marks_3 + marks_4 + marks_5
+marks_6) / 6 ;
printf(avg);
}

Program by using array:

#include <stdio.h>
void main ()
{
int marks[6] = {56,78,88,76,56,89);
int i;
float avg;
for (i=0; i<6; i++ )
{
avg = avg + marks[i];
}
printf(avg);
}

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 20
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Complexity of Array operations

Time and space complexity of various array operations are described in
the following table.

Time Complexity

Algorithm Average Case Worst Case

Access O(1) O(1)

Search O(n) O(n)
Insertion O(n) O(n)
Deletion O(n) O(n)

Space Complexity
In array, space complexity for worst case is O(n).

Advantages of Array
Array provides the single name for the group of variables of the
same type therefore, it is easy to remember the name of all the
elements of an array.
Traversing an array is a very simple process, we just need to
increment the base address of the array in order to visit each
element one by one.
Any element in the array can be directly accessed by using the
index.

Memory Allocation of the array

Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 21
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

As we have mentioned, all the data elements of an array are stored at

contiguous locations in the main memory. The name of the array
represents the base address or the address of first element in the main
memory. Each element of the array is represented by a proper indexing.

The indexing of the array can be defined in three ways.

 0 (zero - based indexing) : The first element of the array will be

arr[0].
 1 (one - based indexing) : The first element of the array will be
arr[1].
 n (n - based indexing) : The first element of the array can reside at
any random index number.

In the following image, we have shown the memory allocation of

an array arr of size 5. The array follows 0-based indexing
approach. The base address of the array is 100th byte. This will be
the address of arr[0]. Here, the size of int is 4 bytes therefore each
element will take 4 bytes in the memory.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 22
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

In 0 based indexing, If the size of an array is n then the maximum index

number, an element can have is n-1. However, it will be n if we
use 1 based indexing.

Accessing Elements of an array

To access any random element of an array we need the following
information:
 Base Address of the array.
 Size of an element in bytes.
 Which type of indexing, array follows.

Address of any element of a 1D array can be calculated by using the

following formula:

 Byte address of element A[i] = base address + size * ( i - first inde

x)

Example :
 In an array, A[-10 ..... +2 ], Base address (BA) = 999,
 size of an element = 2 bytes,
 find the location of A[-1].
 L(A[-1]) = 999 + [(-1) - (-10)] x 2
 = 999 + 18
 = 1017

Passing array to the function:

As we have mentioned earlier that, the name of the array represents the
starting address or the address of the first element of the array. All the
elements of the array can be traversed by using the base address.

The following example illustrate, how the array can be passed to a

function.
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 23
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Example:

#include <stdio.h>
int summation(int[]);
void main ()
{
int arr[5] = {0,1,2,3,4};
int sum = summation(arr);
printf("%d",sum);
}

int summation (int arr[])

{
int sum=0,i;
for (i = 0; i<5; i++)
{
sum = sum + arr[i];
}
return sum;
}

The above program defines a function named as summation which

accepts an array as an argument. The function calculates the sum of all
the elements of the array and returns it.

2D Array
2D array can be defined as an array of arrays. The 2D array is organized
as matrices which can be represented as the collection of rows and
columns.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 24
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

However, 2D arrays are created to implement a relational database look

alike data structure. It provides ease of holding bulk of data at once
which can be passed to any number of functions wherever required.
How to declare 2D Array
The syntax of declaring two dimensional array is very much similar to
that of a one dimensional array, given as follows.

int arr[max_rows][max_columns];

however, It produces the data structure which looks like following.

Above image shows the two dimensional array, the elements are
organized in the form of rows and columns. First element of the first row
is represented by a[0][0] where the number shown in the first index is
the number of that row while the number shown in the second index is
the number of the column.

How do we access data in a 2D Array:

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 25
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Due to the fact that the elements of 2D arrays can be random accessed.
Similar to one dimensional arrays, we can access the individual cells in a
2D array by using the indices of the cells. There are two indices attached
to a particular cell, one is its row number while the other is its column
number.

However, we can store the value stored in any particular cell of a 2D

array to some variable x by using the following syntax.

int x = a[i][j];

where i and j is the row and column number of the cell respectively.

We can assign each cell of a 2D array to 0 by using the following code:

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

{
for (int j=0; j<n; j++)
{
a[i][j] = 0;
}
}

Initializing 2D Arrays
We know that, when we declare and initialize one dimensional array in
C programming simultaneously, we don't need to specify the size of the
array. However this will not work with 2D arrays. We will have to
define at least the second dimension of the array.

The syntax to declare and initialize the 2D array is given as follows.

int arr[2][2] = {0,1,2,3};

Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 26
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

The number of elements that can be present in a 2D array will always be

equal to (number of rows * number of columns).

Example: Storing User's data into a 2D array and printing it.

C Example:

#include <stdio.h>
void main ()
{
int arr[3][3],i,j;
for (i=0;i<3;i++)
{
for (j=0;j<3;j++)
{
printf("Enter a[%d][%d]: ",i,j);
scanf("%d",&arr[i][j]);
}
}
printf("\n printing the elements ....\n");
for(i=0;i<3;i++)
{
printf("\n");
for (j=0;j<3;j++)
{
printf("%d\t",arr[i][j]);
}
}
}

Mapping 2D array to 1D array

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 27
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

When it comes to map a 2 dimensional array, most of us might think that

why this mapping is required. However, 2 D arrays exists from the user
point of view. 2D arrays are created to implement a relational database
table lookalike data structure, in computer memory, the storage
technique for 2D array is similar to that of an one dimensional array.

The size of a two dimensional array is equal to the multiplication of

number of rows and the number of columns present in the array. We do
need to map two dimensional array to the one dimensional array in order
to store them in the memory.

A 3 X 3 two dimensional array is shown in the following image.

However, this array needs to be mapped to a one dimensional array in
order to store it into the memory.

There are two main techniques of storing 2D array elements into

memory

1. Row Major ordering

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 28
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

In row major ordering, all the rows of the 2D array are stored into the
memory contiguously. Considering the array shown in the above image,
its memory allocation according to row major order is shown as follows.

first, the 1st row of the array is stored into the memory completely, then
the 2nd row of the array is stored into the memory completely and so on
till the last row.

2. Column Major ordering

According to the column major ordering, all the columns of the 2D array
are stored into the memory contiguously. The memory allocation of the
array which is shown in in the above image is given as follows.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 29
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

first, the 1st column of the array is stored into the memory completely,
then the 2nd row of the array is stored into the memory completely and so
on till the last column of the array.

Calculating the Address of the random element of a 2D array

Due to the fact that, there are two different techniques of storing the two
dimensional array into the memory, there are two different formulas to
calculate the address of a random element of the 2D array.

By Row Major Order

If array is declared by a[m][n] where m is the number of rows while n is
the number of columns, then address of an element a[i][j] of the array
stored in row major order is calculated as,
Address(a[i][j]) = B. A. + (i * n + j) * size

where, B. A. is the base address or the address of the first element of the
array a[0][0] .
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 30
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Example:

a[10...30, 55...75], base address of the array (BA) = 0, size of an elem

ent = 4 bytes .
Find the location of a[15][68]
Address (a[15][68]) = 0 + ((15 - 10) x (68 - 55 + 1) + (68 - 55)) x 4
= (5 x 14 + 13) x 4
= 83 x 4
= 332 answer

By Column major order

If array is declared by a[m][n] where m is the number of rows while n is
the number of columns, then address of an element a[i][j] of the array
stored in row major order is calculated as,
Address (a[i][j]) = ((j*m)+i)*Size + BA

where BA is the base address of the array.

Example:
A [-5 ... +20][20 ... 70], BA = 1020, Size of element = 8 bytes.
Find the location of a[0][30]
Address [A[0][30]) = ((30-20) x 24 + 5) x 8 + 1020 = 245 x 8 + 1020
= 2980 bytes

Linked List
Linked List can be defined as collection of objects
called nodes that are randomly stored in the memory.
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 31
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

A node contains two fields i.e. data stored at that particular address
and the pointer which contains the address of the next node in the
memory.
The last node of the list contains pointer to the null.

Uses of Linked List

The list is not required to be contiguously present in the memory.
The node can reside any where in the memory and linked together
to make a list. This achieves optimized utilization of space.
list size is limited to the memory size and doesn't need to be
declared in advance.
Empty node cannot be present in the linked list.
We can store values of primitive types or objects in the singly
linked list.

Why use linked list over array?

Till now, we were using array data structure to organize the group of
elements that are to be stored individually in the memory. However,
Array has several advantages and disadvantages which must be known
in order to decide the data structure which will be used throughout the
program.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 32
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Array contains following limitations:

 The size of array must be known in advance before using it in the
program.
 Increasing size of the array is a time taking process. It is almost
impossible to expand the size of the array at run time.
 All the elements in the array need to be contiguously stored in the
memory. Inserting any element in the array needs shifting of all its
predecessors.

Linked list is the data structure which can overcome all the
limitations of an array. Using linked list is useful because,

 It allocates the memory dynamically. All the nodes of linked list

are non-contiguously stored in the memory and linked together
with the help of pointers.
 Sizing is no longer a problem since we do not need to define its
size at the time of declaration. List grows as per the program's
demand and limited to the available memory space.

Singly linked list or One way chain

Singly linked list can be defined as the collection of ordered set of
elements. The number of elements may vary according to need of the
program. A node in the singly linked list consist of two parts: data part
and link part. Data part of the node stores actual information that is to be
represented by the node while the link part of the node stores the address
of its immediate successor.

One way chain or singly linked list can be traversed only in one
direction. In other words, we can say that each node contains only next
pointer, therefore we cannot traverse the list in the reverse direction.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 33
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Consider an example where the marks obtained by the student in three

subjects are stored in a linked list as shown in the figure.

In the above figure, the arrow represents the links. The data part of every
node contains the marks obtained by the student in the different subject.
The last node in the list is identified by the null pointer which is present
in the address part of the last node. We can have as many elements we
require, in the data part of the list.

Complexity
D Time Complexity Space
S Compl
eity

Average Worst Worst

Access Search Insertion Deletion Access Search Insertion Deletion

SLL θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1) O(n)

Operations on Singly Linked List

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 34
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

There are various operations which can be performed on singly linked

list. A list of all such operations is given below.

Node Creation
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));

Insertion
The insertion into a singly linked list can be performed at different
positions. Based on the position of the new node being inserted, the
insertion is categorized into the following categories.
S Operation Description
N

1 Insertion It involves inserting any element at the front of

at the list. We just need to a few link adjustments
beginning to make the new node as the head of the list.
2 Insertion It involves insertion at the last of the linked list.
at end of The new node can be inserted as the only node
the list in the list or it can be inserted as the last one.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 35
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Different logics are implemented in each

scenario.
3 Insertion It involves insertion after the specified node of
after the linked list. We need to skip the desired
specified number of nodes in order to reach the node after
node which the new node will be inserted. .

Deletion and Traversing

The Deletion of a node from a singly linked list can be performed at
different positions. Based on the position of the node being deleted, the
operation is categorized into the following categories.
S Operation Description
N

1 Deletion at It involves deletion of a node from the

beginning beginning of the list. This is the simplest
operation among all. It just need a few
adjustments in the node pointers.
2 Deletion at It involves deleting the last node of the list. The
the end of list can either be empty or full. Different logic is
the list implemented for the different scenarios.
3 Deletion It involves deleting the node after the specified
after node in the list. we need to skip the desired
specified number of nodes to reach the node after which
node the node will be deleted. This requires
traversing through the list.
4 Traversing In traversing, we simply visit each node of the
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 36
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

list at least once in order to perform some

specific operation on it, for example, printing
data part of each node present in the list.
5 Searching In searching, we match each element of the list
with the given element. If the element is found
on any of the location then location of that
element is returned otherwise null is returned. .

Linked List in C: Menu Driven Program

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;

void beginsert ();

void lastinsert ();
void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 37
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

while(choice != 9)
{
printf("\n\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\
n===============================================\
n");
printf("\[Link] in begining\[Link] at last\[Link] at any ra
ndom location\[Link] from Beginning\n
[Link] from last\[Link] node after specified location\
[Link] for an element\[Link]\[Link]\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
randominsert();
break;
case 4:
begin_delete();
break;
case 5:
last_delete();
break;
case 6:
random_delete();
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 38
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr;
int item;
ptr = (struct node *) malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value\n");
scanf("%d",&item);
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted");
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 39
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node*)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr->data = item;
if(head == NULL)
{
ptr -> next = NULL;
head = ptr;
printf("\nNode inserted");
}
else
{
temp = head;
while (temp -> next != NULL)
{
temp = temp -> next;
}
temp->next = ptr;
ptr->next = NULL;
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 40
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

printf("\nNode inserted");

}
}
}
void randominsert()
{
int i,loc,item;
struct node *ptr, *temp;
ptr = (struct node *) malloc (sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter element value");
scanf("%d",&item);
ptr->data = item;
printf("\nEnter the location after which you want to insert ");
scanf("\n%d",&loc);
temp=head;
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\ncan't insert\n");
return;
}

}
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 41
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

ptr ->next = temp ->next;

temp ->next = ptr;
printf("\nNode inserted");
}
}
void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nList is empty\n");
}
else
{
ptr = head;
head = ptr->next;
free(ptr);
printf("\nNode deleted from the begining ...\n");
}
}
void last_delete()
{
struct node *ptr,*ptr1;
if(head == NULL)
{
printf("\nlist is empty");
}
else if(head -> next == NULL)
{
head = NULL;
free(head);
printf("\nOnly node of the list deleted ...\n");
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 42
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

else
{
ptr = head;
while(ptr->next != NULL)
{
ptr1 = ptr;
ptr = ptr ->next;
}
ptr1->next = NULL;
free(ptr);
printf("\nDeleted Node from the last ...\n");
}
}
void random_delete()
{
struct node *ptr,*ptr1;
int loc,i;
printf("\n Enter the location of the node after which you want to p
erform deletion \n");
scanf("%d",&loc);
ptr=head;
for(i=0;i<loc;i++)
{
ptr1 = ptr;
ptr = ptr->next;

if(ptr == NULL)
{
printf("\nCan't delete");
return;
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 43
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

}
}
ptr1 ->next = ptr ->next;
free(ptr);
printf("\nDeleted node %d ",loc+1);
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 44
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

}
if(flag==1)
{
printf("Item not found\n");
}
}

void display()
{
struct node *ptr;
ptr = head;
if(ptr == NULL)
{
printf("Nothing to print");
}
else
{
printf("\nprinting values . . . . .\n");
while (ptr!=NULL)
{
printf("\n%d",ptr->data);
ptr = ptr -> next;
}
}
}

Program to determine whether a given matrix is a sparse matrix

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 45
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Explanation
In this program, we need to check whether the given matrix is the sparse
matrix.

Sparse Matrix
A matrix is said to be sparse matrix if most of the elements of that
matrix are 0. It implies that it contains very less non-zero elements.

To check whether the given matrix is the sparse matrix or not, we first
count the number of zero elements present in the matrix. Then calculate
the size of the matrix. For the matrix to be sparse, count of zero elements
present in an array must be greater than size/2.

Number of zeroes present in above matrix is 6 and size of the matrix is 3

* 3 = 9. Since, 6 > 4.5 that means, most elements of given array are zero.
Hence, the above matrix is a sparse matrix.

Algorithm
Declare and initialize a two-dimensional array a.
Calculate the number of rows and columns present in the given
array and store it in variables rows and cols respectively.
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 46
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Loop through the array and count the number of zeroes present in
the given array and store in the variable count.
Calculate the size of the array by multiplying the number of rows
with many columns of the array.
If the count is greater than size/2, given matrix is the sparse matrix.
That means, most of the elements of the array are zeroes.
Else, the matrix is not a sparse matrix.

Why to use Sparse Matrix instead of simple matrix?

 Storage: There are lesser non-zero elements than zeros and thus
lesser memory can be used to store only those elements.
 Computing time: Computing time can be saved by logically
designing a data structure traversing only non-zero elements..
Example
00304
00570
00000
02600
Representing a sparse matrix by a 2D array leads to wastage of lots of
memory as zeroes in the matrix are of no use in most of the cases. So,
instead of storing zeroes with non-zero elements, we only store non-zero
elements. This means storing non-zero elements with triples- (Row,
Column, value).

Sparse Matrix Representations can be done in many ways following are

two common representations:
Array representation
Linked list representation
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 47
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Method 1: Using Arrays

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

#include <stdio.h>
int main()
{
int rows, cols, size, count = 0;
//Initialize matrix a
int a[][3] = {
{4, 0, 0},
{0, 5, 0},
{0, 0, 6}
};
//Calculates number of rows and columns present in given matrix
rows = (sizeof(a)/sizeof(a[0]));
cols = (sizeof(a)/sizeof(a[0][0]))/rows;

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 48
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

//Calculates the size of array

size = rows * cols;
//Count all zero element present in matrix
for(int i = 0; i < rows; i++){
for(int j = 0; j < cols; j++){
if(a[i][j] == 0)
count++;
}
}
if(count > (size/2))
printf("Given matrix is a sparse matrix");
else
printf("Given matrix is not a sparse matrix");
return 0;
}

Output:
Given matrix is a sparse matrix

Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined as:
Row: Index of row, where non-zero element is located
Column: Index of column, where non-zero element is located
Value: Value of the non zero element located at index – (row,
column)
Next node: Address of the next node

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 49
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

// C program for Sparse Matrix Representation

// using Linked Lists
#include<stdio.h>
#include<stdlib.h>

// Node to represent sparse matrix

struct Node
{
int value;
int row_position;
int column_postion;
struct Node *next;
};

// Function to create new node

void create_new_node(struct Node** start, int non_zero_element,
int row_index, int column_index )
{
struct Node *temp, *r;
temp = *start;
if (temp == NULL)
{
// Create new node dynamically
temp = (struct Node *) malloc (sizeof(struct Node));
temp->value = non_zero_element;
temp->row_position = row_index;
temp->column_postion = column_index;
temp->next = NULL;
*start = temp;

}
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 50
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

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

// Create new node dynamically

r = (struct Node *) malloc (sizeof(struct Node));
r->value = non_zero_element;
r->row_position = row_index;
r->column_postion = column_index;
r->next = NULL;
temp->next = r;

}
}

// This function prints contents of linked list

// starting from start
void PrintList(struct Node* start)
{
struct Node *temp, *r, *s;
temp = r = s = start;

printf("row_position: ");
while(temp != NULL)
{

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

temp = temp->next;
}
printf("\n");

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 51
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

printf("column_postion: ");
while(r != NULL)
{
printf("%d ", r->column_postion);
r = r->next;
}
printf("\n");
printf("Value: ");
while(s != NULL)
{
printf("%d ", s->value);
s = s->next;
}
printf("\n");
}

// Driver of the program

int main()
{
// Assume 4x5 sparse matrix
int sparseMatric[4][5] =
{
{0 , 0 , 3 , 0 , 4 },
{0 , 0 , 5 , 7 , 0 },
{0 , 0 , 0 , 0 , 0 },
{0 , 2 , 6 , 0 , 0 }
};

/* Start with the empty list */

struct Node* start = NULL;

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 52
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

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

for (int j = 0; j < 5; j++)

// Pass only those values which are non - zero

if (sparseMatric[i][j] != 0)
create_new_node(&start, sparseMatric[i][j], i, j);

PrintList(start);

return 0;
}
Output:
row_position: 0 0 1 1 3 3
column_postion: 2 4 2 3 1 2
Value: 3 4 5 7 2 6

UNIT-3
Linked Lists
Doubly linked list
Doubly linked list is a complex type of linked list in which a node
contains a pointer to the previous as well as the next node in the
sequence. Therefore, in a doubly linked list, a node consists of three
parts: node data, pointer to the next node in sequence (next pointer) ,
pointer to the previous node (previous pointer). A sample node in a
doubly linked list is shown in the figure.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 53
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

A doubly linked list containing three nodes having numbers from 1 to 3

in their data part, is shown in the following image.

In C, structure of a node in doubly linked list can be given as:

struct node
{
struct node *prev; int data; struct node *next;
}

The prev part of the first node and the next part of the last node will
always contain null indicating end in each direction.

In a singly linked list, we could traverse only in one direction, because

each node contains address of the next node and it doesn't have any
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 54
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

record of its previous nodes. However, doubly linked list overcome this
limitation of singly linked list. Due to the fact that, each node of the list
contains the address of its previous node, we can find all the details
about the previous node as well by using the previous address stored
inside the previous part of each node.

Memory Representation of a doubly linked list

Memory Representation of a doubly linked list is shown in the following
image. Generally, doubly linked list consumes more space for every
node and therefore, causes more expansive basic operations such as
insertion and deletion. However, we can easily manipulate the elements
of the list since the list maintains pointers in both the directions (forward
and backward).

In the following image, the first element of the list that is i.e. 13 stored at
address 1. The head pointer points to the starting address 1. Since this is
the first element being added to the list therefore the prev of the
list contains null. The next node of the list resides at address 4 therefore
the first node contains 4 in its next pointer.

We can traverse the list in this way until we find any node containing
null or -1 in its next part.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 55
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Operations on doubly linked list

Node Creation
struct node
{
struct node *prev;
int data;
struct node *next;
};
struct node *head;

All the remaining operations regarding doubly linked list are described
in the following table.

S Operation Description
N

1 Insertion at beginning Adding the node into the linked list at

beginning.
2 Insertion at end Adding the node into the linked list to the
end.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 56
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

3 Insertion after Adding the node into the linked list after the
specified node
specified node.

4 Deletion at beginning Removing the node from beginning of the

list
5 Deletion at the end Removing the node from end of the list.

6 Deletion of the node Removing the node which is present just

having given data
after the node containing the given data.

7 Searching Comparing each node data with the item to

be searched and return the location of the
item in the list if the item found else return
null.
8 Traversing Visiting each node of the list at least once in
order to perform some specific operation like
searching, sorting, display, etc.

Menu Driven Program in C to implement all the operations of doubly linked list
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void insertion_specified();
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 57
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

void deletion_beginning();
void deletion_last();
void deletion_specified();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\
n===============================================\
n");
printf("\[Link] in begining\[Link] at last\[Link] at any ra
ndom location\[Link] from Beginning\n
[Link] from last\[Link] the node after the given data\
[Link]\[Link]\[Link]\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
insertion_specified();
break;
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 58
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

case 4:
deletion_beginning();
break;
case 5:
deletion_last();
break;
case 6:
deletion_specified();
break;
case 7:
search();
break;
case 8:
display();
break;
case 9:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void insertion_beginning()
{
struct node *ptr;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 59
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

else
{
printf("\nEnter Item value");
scanf("%d",&item);

if(head==NULL)
{
ptr->next = NULL;
ptr->prev=NULL;
ptr->data=item;
head=ptr;
}
else
{
ptr->data=item;
ptr->prev=NULL;
ptr->next = head;
head->prev=ptr;
head=ptr;
}
printf("\nNode inserted\n");
}

}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 60
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

}
else
{
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
ptr->next = NULL;
ptr->prev = NULL;
head = ptr;
}
else
{
temp = head;
while(temp->next!=NULL)
{
temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
ptr->next = NULL;
}

}
printf("\nnode inserted\n");
}
void insertion_specified()
{
struct node *ptr,*temp;
int item,loc,i;
ptr = (struct node *)malloc(sizeof(struct node));
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 61
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

if(ptr == NULL)
{
printf("\n OVERFLOW");
}
else
{
temp=head;
printf("Enter the location");
scanf("%d",&loc);
for(i=0;i<loc;i++)
{
temp = temp->next;
if(temp == NULL)
{
printf("\n There are less than %d elements", loc);
return;
}
}
printf("Enter value");
scanf("%d",&item);
ptr->data = item;
ptr->next = temp->next;
ptr -> prev = temp;
temp->next = ptr;
temp->next->prev=ptr;
printf("\nnode inserted\n");
}
}
void deletion_beginning()
{
struct node *ptr;
if(head == NULL)
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 62
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
head = head -> next;
head -> prev = NULL;
free(ptr);
printf("\nnode deleted\n");
}

}
void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == NULL)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 63
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

else
{
ptr = head;
if(ptr->next != NULL)
{
ptr = ptr -> next;
}
ptr -> prev -> next = NULL;
free(ptr);
printf("\nnode deleted\n");
}
}
void deletion_specified()
{
struct node *ptr, *temp;
int val;
printf("\n Enter the data after which the node is to be deleted : ");
scanf("%d", &val);
ptr = head;
while(ptr -> data != val)
ptr = ptr -> next;
if(ptr -> next == NULL)
{
printf("\nCan't delete\n");
}
else if(ptr -> next -> next == NULL)
{
ptr ->next = NULL;
}
else
{
temp = ptr -> next;
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 64
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

ptr -> next = temp -> next;

temp -> next -> prev = ptr;
free(temp);
printf("\nnode deleted\n");
}
}
void display()
{
struct node *ptr;
printf("\n printing values...\n");
ptr = head;
while(ptr != NULL)
{
printf("%d\n",ptr->data);
ptr=ptr->next;
}
}
void search()
{
struct node *ptr;
int item,i=0,flag;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
while (ptr!=NULL)
{
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 65
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

if(ptr->data == item)
{
printf("\nitem found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
if(flag==1)
{
printf("\nItem not found\n");
}
}

Circular Singly Linked List

In a circular Singly linked list, the last node of the list contains a pointer
to the first node of the list. We can have circular singly linked list as
well as circular doubly linked list.
We traverse a circular singly linked list until we reach the same node
where we started. The circular singly liked list has no beginning and no
ending. There is no null value present in the next part of any of the
nodes.
The following image shows a circular singly linked list.
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 66
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Circular linked list are mostly used in task maintenance in operating

systems. There are many examples where circular linked list are being
used in computer science including browser surfing where a record of
pages visited in the past by the user, is maintained in the form of circular
linked lists and can be accessed again on clicking the previous button.

Memory Representation of circular linked list:

In the following image, memory representation of a circular linked list
containing marks of a student in 4 subjects. However, the image shows a
glimpse of how the circular list is being stored in the memory. The start
or head of the list is pointing to the element with the index 1 and
containing 13 marks in the data part and 4 in the next part. Which means
that it is linked with the node that is being stored at 4th index of the list.

However, due to the fact that we are considering circular linked list in
the memory therefore the last node of the list contains the address of the
first node of the list.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 67
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

We can also have more than one number of linked list in the memory
with the different start pointers pointing to the different start nodes in the
list. The last node is identified by its next part which contains the
address of the start node of the list. We must be able to identify the last
node of any linked list so that we can find out the number of iterations
which need to be performed while traversing the list.

Operations on Circular Singly Linked List:

Insertion
S Operation Description
N

1 Insertion at Adding a node into circular singly linked list

beginning at the beginning.

2 Insertion at end Adding a node into circular singly linked list

Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 68
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

at the end.

Deletion & Traversing

S Operation Description
N

1 Deletion at Removing the node from circular singly linked

beginning list at the beginning.

2 Deletion at Removing the node from circular singly linked

the end list at the end.

3 Searching Compare each element of the node with the

given item and return the location at which the
item is present in the list otherwise return null.
4 Traversing Visiting each element of the list at least once in
order to perform some specific operation.
Menu-driven program in C implementing all operations on circular singly linked list

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *head;

void beginsert ();

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 69
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

void lastinsert ();

void randominsert();
void begin_delete();
void last_delete();
void random_delete();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 7)
{
printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\
n===============================================\
n");
printf("\[Link] in begining\[Link] at last\[Link] from B
eginning\[Link] from last\[Link] for an element\[Link]\
[Link]\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
beginsert();
break;
case 2:
lastinsert();
break;
case 3:
begin_delete();
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 70
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

break;
case 4:
last_delete();
break;
case 5:
search();
break;
case 6:
display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
}
}
}
void beginsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter the node data?");
scanf("%d",&item);
ptr -> data = item;
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 71
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp->next != head)
temp = temp->next;
ptr->next = head;
temp -> next = ptr;
head = ptr;
}
printf("\nnode inserted\n");
}

}
void lastinsert()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
printf("\nEnter Data?");
scanf("%d",&item);
ptr->data = item;
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 72
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

if(head == NULL)
{
head = ptr;
ptr -> next = head;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> next = head;
}

printf("\nnode inserted\n");
}

void begin_delete()
{
struct node *ptr;
if(head == NULL)
{
printf("\nUNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 73
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

printf("\nnode deleted\n");
}

else
{ ptr = head;
while(ptr -> next != head)
ptr = ptr -> next;
ptr->next = head->next;
free(head);
head = ptr->next;
printf("\nnode deleted\n");

}
}
void last_delete()
{
struct node *ptr, *preptr;
if(head==NULL)
{
printf("\nUNDERFLOW");
}
else if (head ->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");

}
else
{
ptr = head;
while(ptr ->next != head)
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 74
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

{
preptr=ptr;
ptr = ptr->next;
}
preptr->next = ptr -> next;
free(ptr);
printf("\nnode deleted\n");
}
}

void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item)
{
printf("item found at location %d",i+1);
flag=0;
}
else
{
while (ptr->next != head)
{
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 75
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not found\n");
}
}
}

void display()
{
struct node *ptr;
ptr=head;
if(head == NULL)
{
printf("\nnothing to print");
}
else
{
printf("\n printing values ... \n");
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 76
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

while(ptr -> next != head)

{
printf("%d\n", ptr -> data);
ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
}
}

Circular Doubly Linked List

Circular doubly linked list is a more complexed type of data structure in
which a node contain pointers to its previous node as well as the next
node. Circular doubly linked list doesn't contain NULL in any of the
node. The last node of the list contains the address of the first node of
the list. The first node of the list also contain address of the last node in
its previous pointer.
A circular doubly linked list is shown in the following figure.

Due to the fact that a circular doubly linked list contains three parts in its
structure therefore, it demands more space per node and more expensive
basic operations. However, a circular doubly linked list provides easy
manipulation of the pointers and the searching becomes twice as
efficient.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 77
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Memory Management of Circular Doubly linked list

The following figure shows the way in which the memory is allocated
for a circular doubly linked list. The variable head contains the address
of the first element of the list i.e. 1 hence the starting node of the list
contains data A is stored at address 1. Since, each node of the list is
supposed to have three parts therefore, the starting node of the list
contains address of the last node i.e. 8 and the next node i.e. 4. The last
node of the list that is stored at address 8 and containing data as 6,
contains address of the first node of the list as shown in the image i.e. 1.
In circular doubly linked list, the last node is identified by the address of
the first node which is stored in the next part of the last node therefore
the node which contains the address of the first node, is actually the last
node of the list.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 78
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Operations on Dircular Doubly Linked List:

There are various operations which can be performed on circular doubly
linked list. The node structure of a circular doubly linked list is similar
to doubly linked list. However, the operations on circular doubly linked
list is described in the following table.
S Operation Description
N

1 Insertion at beginning Adding a node in circular doubly linked list

at the beginning.
2 Insertion at end Adding a node in circular doubly linked list
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 79
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

at the end.
3 Deletion at beginning Removing a node in circular doubly linked
list from beginning.
4 Deletion at end Removing a node in circular doubly linked
list at the end.

Traversing and searching in circular doubly linked list is similar to that

in the circular singly linked list.
C program to implement all the operations on circular doubly
linked list
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node *prev;
struct node *next;
int data;
};
struct node *head;
void insertion_beginning();
void insertion_last();
void deletion_beginning();
void deletion_last();
void display();
void search();
void main ()
{
int choice =0;
while(choice != 9)
{
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 80
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

printf("\n*********Main Menu*********\n");
printf("\nChoose one option from the following list ...\n");
printf("\n=============================\n");
printf("\[Link] in Beginning\[Link] at last\[Link] from
Beginning\[Link] from last\[Link]\[Link]\[Link]\n");
printf("\nEnter your choice?\n");
scanf("\n%d",&choice);
switch(choice)
{
case 1:
insertion_beginning();
break;
case 2:
insertion_last();
break;
case 3:
deletion_beginning();
break;
case 4:
deletion_last();
break;
case 5:
search();
break;
case 6:
display();
break;
case 7:
exit(0);
break;
default:
printf("Please enter valid choice..");
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 81
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

}
}
}
void insertion_beginning()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *)malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter Item value");
scanf("%d",&item);
ptr->data=item;
if(head==NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = ptr;
ptr -> prev = temp;
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 82
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

head -> prev = ptr;

ptr -> next = head;
head = ptr;
}
printf("\nNode inserted\n");
}
}
void insertion_last()
{
struct node *ptr,*temp;
int item;
ptr = (struct node *) malloc(sizeof(struct node));
if(ptr == NULL)
{
printf("\nOVERFLOW");
}
else
{
printf("\nEnter value");
scanf("%d",&item);
ptr->data=item;
if(head == NULL)
{
head = ptr;
ptr -> next = head;
ptr -> prev = head;
}
else
{
temp = head;
while(temp->next !=head)
{
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 83
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

temp = temp->next;
}
temp->next = ptr;
ptr ->prev=temp;
head -> prev = ptr;
ptr -> next = head;
}
}
printf("\nnode inserted\n");
}

void deletion_beginning()
{
struct node *temp;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
temp = head;
while(temp -> next != head)
{
temp = temp -> next;
}
temp -> next = head -> next;
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 84
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

head -> next -> prev = temp;

free(head);
head = temp -> next;
}
}

void deletion_last()
{
struct node *ptr;
if(head == NULL)
{
printf("\n UNDERFLOW");
}
else if(head->next == head)
{
head = NULL;
free(head);
printf("\nnode deleted\n");
}
else
{
ptr = head;
if(ptr->next != head)
{
ptr = ptr -> next;
}
ptr -> prev -> next = head;
head -> prev = ptr -> prev;
free(ptr);
printf("\nnode deleted\n");
}
}
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 85
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

void display()
{
struct node *ptr;
ptr=head;
if(head == NULL)
{
printf("\nnothing to print");
}
else
{
printf("\n printing values ... \n");

while(ptr -> next != head)

{
printf("%d\n", ptr -> data);
ptr = ptr -> next;
}
printf("%d\n", ptr -> data);
}
}

void search()
{
struct node *ptr;
int item,i=0,flag=1;
ptr = head;
if(ptr == NULL)
{
printf("\nEmpty List\n");
}
else
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 86
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

{
printf("\nEnter item which you want to search?\n");
scanf("%d",&item);
if(head ->data == item)
{
printf("item found at location %d",i+1);
flag=0;
}
else
{
while (ptr->next != head)
{
if(ptr->data == item)
{
printf("item found at location %d ",i+1);
flag=0;
break;
}
else
{
flag=1;
}
i++;
ptr = ptr -> next;
}
}
if(flag != 0)
{
printf("Item not found\n");
}
}
}
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 87
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

UNIT-4
Stacks & Queues
Stack
Stack is an ordered list in which, insertion and deletion can be
performed only at one end that is called top.
Stack is a recursive data structure having pointer to its top element.
Stacks are sometimes called as Last-In-First-Out (LIFO) lists i.e.
the element which is inserted first in the stack, will be deleted last
from the stack.

Applications of Stack
Recursion
Expression evaluations and conversions
Parsing
Browsers
Editors
Tree Traversals

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 88
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Operations on Stack
There are various operations which can be performed on stack.

Push : Adding an element onto the stack

Pop : Removing an element from the stack
Peek : Look all the elements of stack without removing them

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 89
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

How the stack grows?

Scenario 1: Stack is Empty
The stack is called empty if it doesn't contain any element inside it. At
this stage, the value of variable top is -1.

Scenario 2: Stack is not Empty:

Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 90
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Value of top will get increased by 1 every time when we add any
element to the stack. In the following stack, After adding first element,
top = 2.

Scenario 3: Deletion of an element

Value of top will get decreased by 1 whenever an element is deleted
from the stack.
In the following stack, after deleting 10 from the stack, top = 1.

Top and its Value:

Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 91
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Top position Status of stack

-1 Empty
0 Only one element in the stack
N-1 Stack is full
N Overflow

Array implementation of Stack

In array implementation, the stack is formed by using the array. All the
operations regarding the stack are performed using arrays. Lets see how
each operation can be implemented on the stack using array data
structure.

Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push
operation. Push operation involves following two steps.
Increment the variable Top so that it can now refere to the next
memory location.
Add element at the position of incremented top. This is referred to
as adding new element at the top of the stack.

Stack is overflown when we try to insert an element into a

completely filled stack therefore, our main function must always
avoid stack overflow condition.

C PROGRAM
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 92
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

#include <stdio.h>
int stack[100], i, j, choice=0,n,top=-1;
void push();
void pop();
void show();
void main ()
{
printf("Enter the number of elements in the stack ");
scanf("%d",&n);
printf("*********Stack operations using array*********");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("Chose one from the below options...\n");
printf("\[Link]\[Link]\[Link]\[Link]");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
show();
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 93
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{
printf("Please Enter valid choice ");
}
};
}
}

void push ()
{
int val;
if (top == n )
printf("\n Overflow");
else
{
printf("Enter the value?");
scanf("%d",&val);
top = top +1;
stack[top] = val;
}
}

void pop ()
{
if(top == -1)
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 94
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

printf("Underflow");
else
top = top -1;
}
void show()
{
for (i=top;i>=0;i--)
{
printf("%d\n",stack[i]);
}
if(top == -1)
{
printf("Stack is empty");
}
}
Linked list implementation of stack
Instead of using array, we can also use linked list to implement stack.
Linked list allocates the memory dynamically. However, time
complexity in both the scenario is same for all the operations i.e. push,
pop and peek.

In linked list implementation of stack, the nodes are maintained non-

contiguously in the memory. Each node contains a pointer to its
immediate successor node in the stack. Stack is said to be overflown if
the space left in the memory heap is not enough to create a node.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 95
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

The top most node in the stack always contains null in its address field.
Lets discuss the way in which, each operation is performed in linked list
implementation of stack.

Adding a node to the stack (Push operation)

Adding a node to the stack is referred to as push operation. Pushing an
element to a stack in linked list implementation is different from that of
an array implementation. In order to push an element onto the stack, the
following steps are involved.
Create a node first and allocate memory to it.
If the list is empty then the item is to be pushed as the start node of
the list. This includes assigning value to the data part of the node
and assign null to the address part of the node.
If there are some nodes in the list already, then we have to add the
new element in the beginning of the list (to not violate the property
of the stack). For this purpose, assign the address of the starting
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 96
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

element to the address field of the new node and make the new
node, the starting node of the list.

Time Complexity: O(1)

C PROGRAM
#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 97
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

void main ()
{
int choice=0;
printf("\n*********Stack operations using linked list*********\n");
printf("\n----------------------------------------------\n");
while(choice != 4)
{
printf("\n\nChose one from the below options...\n");
printf("\[Link]\[Link]\[Link]\[Link]");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting....");
break;
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 98
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

}
default:
{
printf("Please Enter valid choice ");
}
};
}
}
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;

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 99
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

}
printf("Item pushed");
}
}

void pop()
{
int item;
struct node *ptr;
if (head == NULL)
{
printf("Underflow");
}
else
{
item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");
}
}
void display()
{
int i;
struct node *ptr;
ptr=head;
if(ptr == NULL)
{
printf("Stack is empty\n");
}
else
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 100
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

{
printf("Printing Stack elements \n");
while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}

Queue
A queue can be defined as an ordered list which enables insert
operations to be performed at one end called REAR and delete
operations to be performed at another end called FRONT.
Queue is referred to be as First In First Out list.
For example, people waiting in line for a rail ticket form a queue.

Applications of Queue
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 101
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Due to the fact that queue performs actions on first in first out basis
which is quite fair for the ordering of actions. There are various
applications of queues discussed as below.
Queues are widely used as waiting lists for a single shared resource
like printer, disk, CPU.
Queues are used in asynchronous transfer of data (where data is
not being transferred at the same rate between two processes) for
eg. pipes, file IO, sockets.
Queues are used as buffers in most of the applications like MP3
media player, CD player, etc.
Queue are used to maintain the play list in media players in order
to add and remove the songs from the play-list.
Queues are used in operating systems for handling interrupts.

Complexity
DS Time Complexity Space
Compleit
y
Average Worst Worst

Acces Search Insertion Deletion Acces Search Insertion Deletion

s s

Queu θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1) O(n)
e

Array representation of Queue

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 102
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

We can easily represent queue by using linear arrays. There are two
variables i.e. front and rear, that are implemented in the case of every
queue. Front and rear variables point to the position from where
insertions and deletions are performed in a queue. Initially, the value of
front and queue is -1 which represents an empty queue. Array
representation of a queue containing 5 elements along with the
respective values of front and rear, is shown in the following figure.

The above figure shows the queue of characters forming the English
word "HELLO". Since, No deletion is performed in the queue till now,
therefore the value of front remains -1 . However, the value of rear
increases by one every time an insertion is performed in the queue. After
inserting an element into the queue shown in the above figure, the queue
will look something like following. The value of rear will become 5
while the value of front remains same.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 103
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

After deleting an element, the value of front will increase from -1 to 0.

however, the queue will look something like following.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 104
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Menu driven program to implement queue using array

#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
int front = -1, rear = -1;
int queue[maxsize];
void main ()
{
int choice;
while(choice != 4)
{
printf("\n**********Main Menu*************\n");
printf("\n============================\n");
printf("\[Link] an element\[Link] an element\[Link] t
he queue\[Link]\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 105
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
int item;
printf("\nEnter the element\n");
scanf("\n%d",&item);
if(rear == maxsize-1)
{
printf("\nOVERFLOW\n");
return;
}
if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else
{
rear = rear+1;
}
queue[rear] = item;
printf("\nValue inserted ");

}
void delete()
{
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 106
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

int item;
if (front == -1 || front > rear)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
item = queue[front];
if(front == rear)
{
front = -1;
rear = -1 ;
}
else
{
front = front + 1;
}
printf("\nvalue deleted ");
}
}

void display()
{
int i;
if(rear == -1)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
for(i=front;i<=rear;i++)
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 107
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

{
printf("\n%d\n",queue[i]);
}
}
}

Drawback of array implementation

Although, the technique of creating a queue is easy, but there are some
drawbacks of using this technique to implement a queue.
Memory Wastage: The space of the array, which is used to store
queue elements, can never be reused to store the elements of that
queue because the elements can only be inserted at front end and
the value of front might be so high so that, all the space before that,
can never be filled.

The above figure shows how the memory space is wasted in the array
representation of queue. In the above figure, a queue of size 10 having 3
elements is shown. The value of the front variable is 5, therefore, we
cannot reinsert the values in the place of already deleted element before
the position of front. That much space of the array is wasted and cannot
be used in the future (for this queue).
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 108
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Deciding the array size

On of the most common problem with array implementation is the size

of the array which requires to be declared in advance. Due to the fact
that, the queue can be extended at runtime depending upon the problem,
the extension in the array size is a time taking process and almost
impossible to be performed at runtime since a lot of reallocations take
place. Due to this reason, we can declare the array large enough so that
we can store queue elements as enough as possible but the main problem
with this declaration is that, most of the array slots (nearly half) can
never be reused. It will again lead to memory wastage.

Linked List implementation of Queue

Due to the drawbacks discussed in the previous section of this tutorial,
the array implementation cannot be used for the large scale applications
where the queues are implemented. One of the alternative of array
implementation is linked list implementation of queue.

The storage requirement of linked representation of a queue with n

elements is o(n) while the time requirement for operations is o(1).

In a linked queue, each node of the queue consists of two parts i.e. data
part and the link part. Each element of the queue points to its immediate
next element in the memory.

In the linked queue, there are two pointers maintained in the memory i.e.
front pointer and rear pointer. The front pointer contains the address of
the starting element of the queue while the rear pointer contains the
address of the last element of the queue.

Insertion and deletions are performed at rear and front end respectively.
If front and rear both are NULL, it indicates that the queue is empty.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 109
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

The linked representation of queue is shown in the following figure.

Menu-Driven Program implementing all the operations on Linked Queue

#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
struct node *front;
struct node *rear;
void insert();
void delete();
void display();
void main ()
{
int choice;
while(choice != 4)
{
printf("\n************Main Menu**************\n");
printf("\n===============================\n");
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 110
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

printf("\[Link] an element\[Link] an element\[Link] t

he queue\[Link]\n");
printf("\nEnter your choice ?");
scanf("%d",& choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
void insert()
{
struct node *ptr;
int item;

ptr = (struct node *) malloc (sizeof(struct node));

if(ptr == NULL)
{
printf("\nOVERFLOW\n");
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 111
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

return;
}
else
{
printf("\nEnter value?\n");
scanf("%d",&item);
ptr -> data = item;
if(front == NULL)
{
front = ptr;
rear = ptr;
front -> next = NULL;
rear -> next = NULL;
}
else
{
rear -> next = ptr;
rear = ptr;
rear->next = NULL;
}
}
}
void delete ()
{
struct node *ptr;
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 112
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

ptr = front;
front = front -> next;
free(ptr);
}
}
void display()
{
struct node *ptr;
ptr = front;
if(front == NULL)
{
printf("\nEmpty queue\n");
}
else
{ printf("\nprinting values .....\n");
while(ptr != NULL)
{
printf("\n%d\n",ptr -> data);
ptr = ptr -> next;
}
}
}

Circular Queue

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 113
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Deletions and insertions can only be performed at front and rear end
respectively, as far as linear queue is concerned.

Consider the queue shown in the following figure.

The Queue shown in above figure is completely filled and there can't be
nserted any more element due to the condition rear == max - 1
becomes true.

However, if we delete 2 elements at the front end of the queue, we still

cannot insert any element since the condition rear = max -1 still holds.

This is the main problem with the linear queue, although we have space
available in the array, but we cannot insert any more element in the
queue. This is simply the memory wastage and we need to overcome this
problem.

One of the solution of this problem is circular queue. In the circular

queue, the first index comes right after the last index. You can think of a
circular queue as shown in the following figure.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 114
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Circular queue will be full when front = -1 and rear = max-1.

Implementation of circular queue is similar to that of a linear queue.
Only the logic part that is implemented in the case of insertion and
deletion is different from that in a linear queue.

Complexity
Time Complexity
Front O(1)
Rear O(1)
enQueue() O(1)
deQueue() O(1)

Menu-Driven program implementing all the operations on a circular

queue
#include<stdio.h>
#include<stdlib.h>
#define maxsize 5
void insert();
void delete();
void display();
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 115
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

int front = -1, rear = -1;

int queue[maxsize];
void main ()
{
int choice;
while(choice != 4)
{
printf("\n**************Main Menu**************\n");
printf("\n================================\n");
printf("\[Link] an element\[Link] an element\[Link] t
he queue\[Link]\n");
printf("\nEnter your choice ?");
scanf("%d",&choice);
switch(choice)
{
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nEnter valid choice??\n");
}
}
}
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 116
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

void insert()
{
int item;
printf("\nEnter the element\n");
scanf("%d",&item);
if((rear+1)%maxsize == front)
{
printf("\nOVERFLOW");
return;
}
else if(front == -1 && rear == -1)
{
front = 0;
rear = 0;
}
else if(rear == maxsize -1 && front != 0)
{
rear = 0;
}
else
{
rear = (rear+1)%maxsize;
}
queue[rear] = item;
printf("\nValue inserted ");
}
void delete()
{
int item;
if(front == -1 & rear == -1)
{
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 117
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

printf("\nUNDERFLOW\n");
return;
}
else if(front == rear)
{
front = -1;
rear = -1;
}
else if(front == maxsize -1)
{
front = 0;
}
else
front = front + 1;
}

void display()
{
int i;
if(front == -1)
printf("\nCircular Queue is Empty!!!\n");
else
{
i = front;
printf("\nCircular Queue Elements are : \n");
if(front <= rear){
while(i <= rear)
printf("%d %d %d\n",queue[i++],front,rear);
}
else{
while(i <= maxsize - 1)
printf("%d %d %d\n", queue[i++],front,rear);
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 118
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

i = 0;
while(i <= rear)
printf("%d %d %d\n",queue[i++],front,rear);
}
}
}

Polish Notation
Prefix, Infix and Postfix expressions
The way to write arithmetic expression is known as a notation. An
arithmetic expression can be written in three different but equivalent
notations, i.e., without changing the essence or output of an expression.
These notations are −
Infix Notation
Prefix (Polish) Notation
Postfix (Reverse-Polish) Notation

These notations are named as how they use operator in expression. We

shall learn the same here in this chapter.

Infix Notation
We write expression in infix notation, e.g. a - b + c, where operators are
used in-between operands. It is easy for us humans to read, write, and
speak in infix notation but the same does not go well with computing
devices. An algorithm to process infix notation could be difficult and
costly in terms of time and space consumption.

Prefix Notation
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 119
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

In this notation, operator is prefixed to operands, i.e. operator is written

ahead of operands. For example, +ab. This is equivalent to its infix
notation a + b. Prefix notation is also known as Polish Notation.

Postfix Notation
This notation style is known as Reversed Polish Notation. In this
notation style, the operator is postfixed to the operands i.e., the operator
is written after the operands. For example, ab+. This is equivalent to its
infix notation a + b.
The following table briefly tries to show the difference in all three
notations –

[Link]. Infix Notation Prefix Notation Postfix Notation

1 a+b +ab ab+

2 (a + b) ∗ c ∗+abc ab+c∗

3 a ∗ (b + c) ∗a+bc abc+∗

4 a/b+c/d +/ab/cd ab/cd/+

5 (a + b) ∗ (c + d) ∗+ab+cd ab+cd+∗

6 ((a + b) ∗ c) - d -∗+abcd ab+c∗d-

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 120
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Parsing Expressions
As we have discussed, it is not a very efficient way to design an
algorithm or program to parse infix notations. Instead, these infix
notations are first converted into either postfix or prefix notations and
then computed.
To parse any arithmetic expression, we need to take care of operator
precedence and associativity also.

Precedence
When an operand is in between two different operators, which operator
will take the operand first, is decided by the precedence of an operator
over others. For example −

As multiplication operation has precedence over addition, b * c will be

evaluated first. A table of operator precedence is provided later.

Associativity
Associativity describes the rule where operators with the same
precedence appear in an expression. For example, in expression a + b −
c, both + and – have the same precedence, then which part of the
expression will be evaluated first, is determined by associativity of
those operators. Here, both + and − are left associative, so the
expression will be evaluated as (a + b) − c.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 121
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Precedence and associativity determines the order of evaluation of an

expression. Following is an operator precedence and associativity table
(highest to lowest) −
[Link] Operator Precedence Associativity
.

1 Exponentiation ^ Highest Right

Associative

2 Multiplication ( ∗ ) & Second Left

Division ( / ) Highest Associative

3 Addition ( + ) & Subtraction Lowest Left

(−) Associative

The above table shows the default behavior of operators. At any point
of time in expression evaluation, the order can be altered by using
parenthesis. For example −
In a + b*c, the expression part b*c will be evaluated first, with
multiplication as precedence over addition. We here use parenthesis
for a + b to be evaluated first, like (a + b)*c.

Postfix Evaluation Algorithm

We shall now look at the algorithm on how to evaluate postfix notation
−
Step 1 − scan the expression from left to right
Step 2 − if it is an operand push it to stack

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 122
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Step 3 − if it is an operator pull operand from stack and perform

operation
Step 4 − store the output of step 3, back to stack
Step 5 − scan the expression until all operands are consumed
Step 6 − pop the stack and perform operation

Infix notation is easier for humans to read and understand whereas for
electronic machines like computers, postfix is the best form of
expression to parse. We shall see here a program to convert and
evaluate infix notation to postfix notation −

Example:
#include<stdio.h>
#include<string.h>
//char stack
char stack[25];
int top = -1;

void push(char item) {

stack[++top] = item;
}

char pop() {
return stack[top--];
}

//returns precedence of operators

int precedence(char symbol) {

switch(symbol) {
case '+':
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 123
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

case '-':
return 2;
break;
case '*':
case '/':
return 3;
break;

case '^':
return 4;
break;

case '(':
case ')':
case '#':
return 1;
break;
}
}

//check whether the symbol is operator?

int isOperator(char symbol) {

switch(symbol) {
case '+':
case '-':
case '*':
case '/':
case '^':
case '(':
case ')':

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 124
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

return 1;
break;
default:
return 0;
}
}

//converts infix expression to postfix

void convert(char infix[],char postfix[]) {
int i,symbol,j = 0;
stack[++top] = '#';
for(i = 0;i<strlen(infix);i++) {
symbol = infix[i];
if(isOperator(symbol) == 0) {
postfix[j] = symbol;
j++;
} else {
if(symbol == '(') {
push(symbol);
} else {
if(symbol == ')') {
while(stack[top] != '(') {
postfix[j] = pop();
j++;
}
pop(); //pop out (.
} else {
if(precedence(symbol)>precedence(stack[top])) {
push(symbol);
} else {
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 125
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

while(precedence(symbol)<=precedence(stack[top]))
{
postfix[j] = pop();
j++;
}
push(symbol);
}
}
}
}
}
while(stack[top] != '#') {
postfix[j] = pop();
j++;
}
postfix[j]='\0'; //null terminate string.
}

//int stack
int stack_int[25];
int top_int = -1;

void push_int(int item) {

stack_int[++top_int] = item;
}

char pop_int() {
return stack_int[top_int--];
}

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 126
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

//evaluates postfix expression

int evaluate(char *postfix){

char ch;
int i = 0,operand1,operand2;

while( (ch = postfix[i++]) != '\0') {

if(isdigit(ch)) {
push_int(ch-'0'); // Push the operand
} else {
//Operator,pop two operands
operand2 = pop_int();
operand1 = pop_int();
switch(ch) {
case '+':
push_int(operand1+operand2);
break;
case '-':
push_int(operand1-operand2);
break;
case '*':
push_int(operand1*operand2);
break;
case '/':
push_int(operand1/operand2);
break;
}
}
}
return stack_int[top_int];
Prepared By: Er. Rathore Suhail (Scientist-C)
Website: [Link]

Page | 127
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

void main() {
char infix[25] = "1*(2+3)",postfix[25];
convert(infix,postfix);
printf("Infix expression is: %s\n" , infix);
printf("Postfix expression is: %s\n" , postfix);
printf("Evaluated expression is: %d\n" , evaluate(postfix));
}
If we compile and run the above program, it will produce the following result −

Output
Infix expression is: 1*(2+3)
Postfix expression is: 123+*
Result is: 5

Skip List Data Structure

A skip list is a data structure that is used for storing a sorted list of items
with a help of hierarchy of linked lists that connect increasingly sparse
subsequences of the items. A skip list allows the process of item look up
in efficient manner. The skip list data structure skips over many of the
items of the full list in one step, that’s why it is known as skip list.

Skip List

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 128
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Complexity
Average Case Worst Case
Space O(n) O(nlogn)
Search O(logn) O(n)
Insert O(logn) O(n)
Delete O(logn) O(n)

Structure of Skip List

A skip list is built up of layers. The lowest layer (i.e. bottom layer) is an
ordinary ordered linked list. The higher layers are like ‘express lane’
where the nodes are skipped (observe the figure).

Searching Process
When an element is tried to search, the search begins at the head element
of the top list. It proceeds horizontally until the current element is
greater than or equal to the target. If current element and target are
matched, it means they are equal and search gets finished.

If the current element is greater than target, the search goes on and
reaches to the end of the linked list, the procedure is repeated after
returning to the previous element and the search reaches to the
next lower list (vertically).

Implementation Details
The elements used for a skip list can contain more than
one pointers since they are allowed to participated in more than
one list.
Insertion and deletion operations are very similar to corresponding
linked list operations.

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 129
 Head Office: 2nd Floor Shah Complex Maharaj Bazar Opp Jan Bakery Srinagar, 190001
Branch Office: 1st Floor Khan Complex near HDFC Bank Nishat Srinagar, 191121
Cell: +91-7006968379, +91-9419058379 Email: training@[Link]

Insertion in Skip List

Applications of Skip List

Skip list are used in distributed applications. In distributed
systems, the nodes of skip list represents the computer systems
and pointers represent network connection.
Skip list are used for implementing highly scalable concurrent
priority queues with less lock contention (struggle for having a
lock on a data item).

Prepared By: Er. Rathore Suhail (Scientist-C)

Website: [Link]

Page | 130