Data Structure and Algorithms

DATA STRUCTURES
Code: ITDC0203
by
Dr Mohit Kumar
Department of Information Technology

Dr. B.R. Ambedkar National Institute of Technology
1
Jalandhar Punjab-144008
COURSE CODE: ITDC0203
COURSE TITLE: DATA STRUCTURES
COURSE DESIGNATION: REQUIRED
PRE-REQUISITES: NONE
CONTACT HOURS/CREDIT SCHEME: (L-T-P-C: 3-1-0-4)
COURSE ASSESSMENT METHODS: One sessional exams and one end-semester exam, along with
assignments, 3 class tests/quiz and presentations which may be conducted by the course coordinator in
lieu of internal assessment.
COURSE OUTCOMES: After the completion of the course, the students will be able to:
1.Understand the concepts of data structure, data type and array data structure.
2.Analyze algorithms and determine their time complexity.
3.Implement linked list data structure to solve various problems.
4.Understand and apply various data structure such as stacks, queues, trees and graphs to solve various computing
problems using C-programming language.
Course Program outcomes

Outcomes
PO1 PO2 PO3 PO4 PO5 PO6 PO7 PO8 PO9 PO10 PO11 PO12
CSPC-205
1. M L H L
1. H M M L M M
1. M M
Department of IT 2
1. M H L L
 TOPICS COVERED
Unit 1: Introduction: Basic Terminology, Elementary Data Organization, Algorithm,

Efficiency of an Algorithm, Time and Space Complexity, Asymptotic notations: Big-Oh,
Time-Space trade-off. Abstract Data Types (ADT),
Unit 2: Array and Linked lists: Arrays: Definition, Single and Multidimensional Arrays,
Representation of Arrays: Row Major Order, and Column Major Order, Application of
arrays, Sparse Matrices and their representations Singly Linked Lists, Doubly Linked
List, Circularly Linked List, Operations on a Linked List. Insertion, Deletion, Traversal,
Applications.
Unit 3: Stack and Queues: Stacks: Introduction, Stack operations: Push & Pop, Prefix and
Postfix Expressions, Applications, Operations on Queue: Create, Add, Delete, Full and
Empty, Circular queues, Dequeue, Priority Queue, Applications.
Department of IT 3
Unit 4: Trees: Basic Terminology, Binary Trees, Binary Tree Representation, Complete
Binary Tree, Tree Traversal algorithms, Huffman algorithm. Search Trees: Binary Search
Trees (BST), Insertion and Deletion in BST, Complexity of Search Algorithm, AVL trees,
Introduction to m-way Search Trees, B Trees & B+ Trees, Graphs: Terminology,
Representations of Graphs, Graph Traversal: Depth First Search and Breadth First Search,
Connected Component, Spanning Trees, Minimum Cost Spanning Trees: Prims and
Kruskals algorithm.
Unit 5: Searching and Sorting: Sequential Search, Binary Search, Comparison and
Analysis, Insertion Sort, Selection Sort, Bubble Sort, Quick Sort, Heap Sort, Radix Sort.
Hash Tables: Basic Hash Tables and Collision Resolution Techniques.
Department of IT 4
 TEXT BOOKS, AND/OR REFERENCE MATERIAL
1. Seymour Lipschutz, “Data Structures with C”, McGraw Hill Education

2. Horowitz and Sahani, “Fundamentals of data Structures”, Galgotia Publication
Pvt. Ltd., New Delhi.
3. R. Kruse etal, “Data Structures and Program Design in C”, Pearson Education
Asia, Delhi-2002
4. A. M. Tenenbaum, “Data Structures using C & C++”, Prentice-Hall of India Pvt.
Ltd., New Delhi.
5. Bruno R Preiss, “Data Structures and Algorithms with Object Oriented Design
Pattern in C++”, Jhon Wiley & Sons, Inc.
6. GilbergForozan , “Data Structure – A pseudo code approach with C++”,
Cengage Learning, New Delhi.
Department of IT 5
What is Data Structure?
 A data structure is a particular way of storing and organizing data
in a computer so that it can be used efficiently.
 They provide a means to manage large amounts of data efficiently,
such as large databases.
 Data are simply values or set of values and Database is organized
collection of data.
Department of IT
6
What is Data Structure? (…contd)
A data structure is a logical and mathematical model of a particular
organization of data.
The choice of particular data structure depends upon following
consideration:
1.It must be able to represent the inherent relationship of data in the

real world.
2.It must be simple enough so that it can be processed efficiently as

and when necessary.
Department of IT
7
THE STUDY OF DATA STRUCTURE
INCLUDE:
 Logical description of data structure
 Implementation of data structure
 Quantitative analysis of data structure, this include
amount of memory, processing time
Department of IT
8
Classification of Data Structure
Data Structures
Primitive Data Structures Non-Primitive Data Structures
Integer Real Character Boolean Linear Data Non -Linear

Structures Data Structures
Arrays Trees
Stack
Graphs
Linked
List
Queues
Department of IT
9
Classification (contd..)
A data structure can be broadly classified into
 Primitive data structure
 Non-primitive data structure
Primitive data structure :-The data structures, that are directly
operated upon by machine level instructions i.e. the
fundamental data types such as int, float in case of ‘c’ are
known as primitive data structures.
Non- Primitive data structure :-These are more complex data
structures. These data structures are derived from the primitive
data structures.
Department of IT
10
Classification (contd..)
Non-Primitive Data Structures can be further divided into two
categories:
 Linear Data Structures
 Non-Linear Data Structures.
Linear Data Structures:-In linear data structures, data elements
are organized sequentially and therefore they are easy to
implement in the computer’s memory. E.g. Arrays.
 Non-Linear Data Structures:-In nonlinear data structures, a
data element can be attached to several other data elements to
represent specific relationships that exist among them. E.g.
Graphs
Department of IT
11
Linear Data Structure Non-linear Data Structure
In a linear data structure, data elements are In a non-linear data structure, data elements
arranged in a linear order where each and are attached in hierarchically manner.
every element is attached to its previous and
next adjacent.
In linear data structure, single level is Whereas in non-linear data structure,
involved. multiple levels are involved.
Its implementation is easy in comparison to While its implementation is complex in
non-linear data structure. comparison to linear data structure.
In a linear data structure, memory is not While in a non-linear data structure, memory
utilized in an efficient way. is utilized in an efficient way.
Its examples are: array, stack, queue, linked Examples are: trees and graphs.
list, etc.
Applications of linear data structures are Applications of non-linear data structures are
mainly in application software development. in Artificial Intelligence and image
processing.
Performance is usually good for simple Performance can vary depending on the
operations like adding or removing at the structure and the operation, but can be
ends, but slower for operations like searching optimized for specific operations.
or removing elements in the middle. Department of IT 12
Array & Linked List
[0] [1] [2]

Array A B C
node
linked
Linked list A B C
Linked lists are unbounded

(maximum number of items limited only by memory)
Department of IT
13
Stack
 Stack
• New nodes can be added and removed only at the top
• Similar to a pile of dishes
• Last-in, first-out (LIFO)
 push
• Adds a new node to the top of the stack
 pop
• Removes a node from the top
Department of IT
14
Stack
 A stack is a list in which insertion and deletion take place at the
same end
• This end is called top
• The other end is called bottom.
Department of IT
15
Queue
 Queue
• Similar to a supermarket checkout line
• First-in, first-out (FIFO)
• Nodes are removed only from the front.
• Nodes are inserted only at the rear.
 Insert and remove operations
• Enqueue (insert) and dequeue (remove)
Department of IT
16
The Queue Operations
 A queue is like a line of people waiting for a bank
teller. The queue has a front and a rear.
$ $
Walking out
Rear(insertion) Front(Removal)
Department of IT
17
Tree
A tree T is a finite non empty set of elements. One of these
elements is called the root, and the remaining elements, if any, are
portioned into trees, which are called the sub trees of T.
Department of IT
18
Tree (example)
node
d ge
e
Department of IT
19
Graph
 A graph is defined as:
“Graph G is a ordered set (V,E), where V(G) represent the
set of elements, called vertices, and E(G) represents the
edges between these vertices.”
 Graphs can be
• Undirected
• Directed
Department of IT
20
Graph
Figure shows a sample graph
V(G)={v1,v2,v3,v4,v5}
E(G)={e1,e2,e3,e4,e5}
e2
v5
v1 e3
e5 v4
e1
v2 v3
e4
Fig . (a) Undirected Graph

Department of IT
21
Graph
e2
v5
v1 e3
e5 v4
e1
v2 v3
e4
Fig. (b) Directed Graph

In directed graph, an edge is represented by an ordered pair (u,v)
(i.e.=(u,v)), that can be traversed only from u toward v.
Department of IT
22
Data Structure Operations
Five major operations are associated with all data structures.
i. Creation:- Initialization of the beginning.
ii.Insertion: - Insertion means adding new details or new node
into the data structure.
iii.Deletion: - Deletion means removing a node from the data
structure.
iv.Traversal: - Traversing means accessing each node exactly
once so that the nodes of a data structure can be processed.
Traversing is also called as visiting.
v.Searching: - Searching means finding the location of node for
a given key value.
Department of IT
23
Data Structure Operations(contd..)
 Apart from the four operations mentioned above, there
are two more operations occasionally performed on data
structures. They are:
(a) Sorting: -Sorting means arranging the data in a
particular order.
(b) Merging: - Merging means joining two lists.
Department of IT
24
A first look on ADTs
 Solving a problem involves processing data, and an
important part of the solution is the efficient
organization of the data
 In order to do that, we need to identify:

1. The collection of data items
2. Basic operation that must be performed on them
Department of IT 25
Abstract Data Type (ADT)
 The word “abstract” refers to the user define data type where data
and the basic operations defined on it are being studied
independently of how they are implemented
 We think about what can be done with the data, not how it is done
Department of IT 26
Some ADT’s
Some user defined ADT’s are
 Stacks
 Queues
Department of IT
27
Stack ADT
We define a stack as an ADT as shown below:
Department of IT
28
Queue ADT
We define a queue as an ADT as shown below:
Department of IT
29
Algorithm
 We are surrounded with many real life problems for
which we are searching and implementing solutions or
optimal solutions.
 Algorithm is a tool to design the solutions for such
problems.
 Even, we can easily analyse solutions represented as
algorithmic form in order to find the optimal one.
Department of IT 30
Algorithm: Formal Definition
 A sequence of finite, precise and unambiguous instructions which are
applied either to perform a computation or to solve a computational
problem.
 A finite set of instructions that specify a sequence of operations to be
carried out in order to solve a specific problem or class of problems.
T(n)
n 4
Input Algorithm Output
• Algorithm vs Program????
Department of IT 31
Expressing Algorithm
 Can be represented in different ways using some sort of language, such as
pseudo code or the flowcharts.
 Example: Algorithm for searching the largest element from the list of given
elements
Max_Array(A,N)
Input: An array ‘A’ with ‘N’ elements
is given
Output: Display the minimum element
1.Set Largest=A[0]
2.for(i=1 to N-1)
if (A[i]>Largest) then
Set Largest=A[i]
3. Print (Largest)
Department of IT 32
(Pseudo code) (Flowchart)
Pseudo code
 Pseudo code is a combination of English and programming construct.
 It is the most preferred notation to describe algorithm
 It is less detailed than a programming solution because it focuses only
on fundamental operations instead of features of a programming
language i.e. it is independent from any programming language.
 Easy to analyse the maximum number of primitive operations in an
algorithm.
 To describe an algorithm, the pseudo code uses various basic
programming primitives, such as sequence, conditionals and looping
syntaxes.
Department of IT 33
What is Pseudo-Code ?
 A mixture of natural language and high-level programming concepts that
describes the main ideas behind a generic implementation of a data
structure or algorithm.
-Expressions: use standard mathematical symbols to describe
numeric and boolean expressions -use  for assignment (“=” in Java)
-use = for the equality relationship (“==” in Java)
-Method Declarations: -Algorithm name(param1, param2)
-Programming Constructs: - decision structures: if ... then ... [else ... ]
- while-loops: while ... do
- repeat-loops: repeat ... until ...
- for-loop: for ... do
- array indexing: A[i]
Department of IT 34
Properties of Algorithms
Algorithm generally share a set of properties
Input. An algorithm has zero or more inputs, i.e, quantities which are given to it
initially before the algorithm begins.
Output. An algorithm has one or more outputs i.e, quantities which have a specified
relation to the inputs.
Finiteness. An algorithm must always terminate after a finite number of steps.
Definiteness. Each step of an algorithm must be clear and unambiguous so that the
action can be carried out without any ambiguity
Effectiveness. An algorithm is also generally expected to be effective. This means
that all of the operations to be performed in the algorithm must be sufficiently basic
that they can in principle be done exactly and in a finite length of time.
Correctness. An algorithm must produce the correct output values for all legal input
instances of the problem.
Department of IT 35
Performance Analysis
 Measurement of the resources consumed by the algorithm
during its execution.
 In case of computing problems, the main resources are
the CPU time and RAM
 The algorithms that require less space and time are said to
be more efficient.
 Thus, analysis is divided into two categories:
1. Space Complexity
2. Time Complexity
Department of IT 36
Space Complexity
S(A)=S(C)+S(R)
Where,
S(A): Space required to run the algorithm (for formal parameters,
local variables, return address, variables, constants and identifiers)
S(R): Space required at compile time (space for instructions,

variables, constants and identifiers)
S(C): Constant Space required
Department of IT 37
Measuring the Running Time
 How should we measure the running time of an algorithm?
 Approach 1: Experimental Study
• Write a program that implements the algorithm
• Run the program with data sets of varying size and composition.
• Use a method like System.currentTimeMillis() to get an accurate
measure of the actual running time.
t (ms)
60
50
40
30
20
10
Department of IT n 38
0 50 100
Beyond Experimental Studies
 Experimental studies have several limitations:
• It is necessary to implement and test the algorithm in order to
determine its running time.
• Experiments can be done only on a limited set of inputs, and may
not be indicative of the running time on other inputs not included
in the experiment.
• In order to compare two algorithms, the same hardware and
software environments should be used.
Department of IT 39
Beyond Experimental Studies
 We will now develop a general methodology for analyzing the
running time of algorithms. In contrast to the "experimental
approach", this methodology:
• Uses a high-level description of the algorithm instead of testing
one of its implementations.
• Takes into account all possible inputs.
• Allows one to evaluate the efficiency of any algorithm in a way
that is independent from the hardware and software
environment.
Department of IT 40
Time Complexity: Simpler Way
• It is the time required to execute an algorithm
• Not physical time over a machine but related to the number
of instructions executed.
• Is the estimate of the number of basic operations executed by
an algorithm.
Execution time of an algorithm T(n)=Sum of total cost of all

statements
Where,
Total cost of the statement is= Cost of statement executing
once * No. of times a statement is executed
Department of IT 41
Process to measure running time
1. Identify basic operations (instructions).
2. Compute the total time taken by these basic operations as follows:
Total cost of basic operation= Cost of basic operation perform
once* Number of times the basic operations are performed
3. Total time T(n)= Sum of total cost of all the basic operations
obtained in step 2.
1.Set Largest=A[0]-------------------------C1
2.for(i=0 to N-1)----------------------------C2*n
if (A[i]==num)---------------------C3*n
print i----------------------------C4
break;----------------------------C5
T(n)=C1+C2*n+C3*n+C4+C5
Department of IT 42
Best Case vs Worst Case vs
Average Case Running Time
 An algorithm may run faster on certain data sets than on others.
 Finding the average case can be very difficult, so typically
algorithms are measured by the worst-case time complexity.
 Also, in certain application domains (e.g., air traffic control,
surgery, IP lookup) knowing the worst-case time complexity is of
crucial importance.
5 ms worst-case
4 ms
3 ms
}
average-case?
best-case
2 ms
1 ms
A B Department
C D of ITE F G 43
Input
The Sorting Problem
Input: A sequence of n numbers [a1, a2, … , an].

Output: A permutation or reordering [a'1, a'2, … , a'n ] of the input
sequence such that a'1  a'2  …  a'n .
An instance of the Sorting Problem:
Input: A sequence of 6 number [31, 41, 59, 26, 41, 58].
Expected output for given instance:
Expected
Output: The permutation of the input [26, 31, 41, 41, 58 , 59].
Department of IT 44
Insertion Sort
Insertion sort is
efficient algorithm for
sorting a small number
of elements.
Department of IT 45
Insertion Sort (cont.)
Department of IT 46
Department of IT 47
Algorithm of insertion sort
Department of IT 48
Example of insertion sort
8 2 4 9 3 6
Department
L1.49 of IT
8 2 4 9 3 6
Department
L1.50 of IT
8 2 4 9 3 6
2 8 4 9 3 6
Department
L1.51 of IT
8 2 4 9 3 6
2 8 4 9 3 6
Department
L1.52 of IT
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
Department
L1.53 of IT
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
Department
L1.54 of IT
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
Department
L1.55 of IT
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
Department
L1.56 of IT
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
Department
L1.57 of IT
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
Department
L1.58 of IT
8 2 4 9 3 6
2 8 4 9 3 6
2 4 8 9 3 6
2 4 8 9 3 6
2 3 4 8 9 6
2 3 4 6 8 9 done
Department
L1.59 of IT
Analysis of Insertion Sort
Time efficiency analysis …
Department of IT 60
Time Complexity
The running time of the algorithm is the sum of
running times for each statement executed;
Department of IT
61
Best Case Analysis
 The best case occurs if the array is already sorted. For each
j=2,3,4…..n. we then find that A[i]<= key in line 5 when i has
its initial value of j-1.
 Thus tj=1for j=2,3,4…..n. and the best-case running time is
This running time can be expressed as an+b for constants a and b that depend on
the statement costs ci; it is thus a linear function of n.
Department of IT
62
Worst Case Analysis
 If the array is in reverse sorted—the worst case results.
 We must compare each element A[j] with each element in the entire sorted
subarray A[1… j-1] and so tj=j for j=2,3,4….n
 Then,
and
We can express this result as an2+bn+c for constants a,b,c which depends
upon statement costs. Thus the complexity is ITa quadratic function of n
Department of 63
Growth of Functions
Department of IT 64
Growth of Functions
 For the large value of the input n only the higher order terms
matter.
 In order to compare solutions based on complexity it is better
to compare their complexity function order.
O(1)<O(logn)<O(n)<O(nlogn)<O(n2)<O(n3)….…O(nk)<O(2n)
Department of IT 65
Asymptotic Notation
 Special Symbols for comparing the growth rate of functions: ,
O, ,
 Running time of an algorithm is computed as a function of input
size n for large n.
 Expressed using only the highest-order term in the expression
for the exact running time.
• Instead of exact running time, say (n2).
 Describes behavior of function in the limit.
 Written using Asymptotic Notation.
Department of IT 66
Big-oh, O-notation
It is a formal method of expressing the upper
bound of an algorithm’s running time i.e. longest
time taken by an algorithm.
More formally, for non-negative functions f(n)
and g(n), if there exist an integer n0 and a
constant c>0 such that for all integer n  n0
0  f(n)  cg(n) for n  n0”
or
f(n) =O (g(n))
g(n) is an asymptotic upper bound for f(n).
Department of IT 67
Examples
 Prove that f(n)=O(g(n)) where f(n)=3n+2 and g(n)=n
 For n0>=1 and c=5
 Any linear function an + b is in O(n2). How?
 Show that 3n3=O(n4) for appropriate c and n0.
Department of IT 68
 -notation
For non-negative functions f(n)
and g(n), if there exist an integer
n0 and a constant c>0 such that for
all integer n  n0
0  cg(n)  f(n)
f(n) =  (g(n))
This makes g(n) as a lower bound

function. It describes the best that can
happen for given data size.
g(n) is an asymptotic lower bound for f(n).

Department of IT 69
Examples
 Prove that f(n)= (g(n)) where f(n)=3n+2 and g(n)=n
 For n0>=1 and c=3
Department of IT 70
-notation
The lower and upper bound for the
function f(n) is provided by the 
notation.
For non negative functions f(n) and
g(n), if there exist an integer an integer
n0 and positive constants c1, c2 >0 such
that for all integer n  n0
0  c1g(n)  f(n)  c2g(n)
Then
f(n) =(g(n))
g(n) is an asymptotically tight bound for f(n).

Department of IT 71
Relations Between , O, 
Department of IT 72
Asymptotic Notation in Equations
 Can use asymptotic notation in equations to replace
expressions containing lower-order terms.
 For example,
4n3 + 3n2 + 2n + 1 = 4n3 + 3n2 + (n)
= 4n3 + (n2) = (n3). How to interpret?
 In equations, (f(n)) always stands for an
anonymous function g(n)  (f(n))
• In the example above, (n2) stands for
3n2 + 2n + 1.
Department of IT 73
Some example to find Complexity
A()
{ Complexity is
int i,j;
for(i=1 to n) O(n2)
{
for(j=1 to n)
{
printf("RAM");
}
}
}
Department of IT 74
A(){ i= 1, 2, 3, 4, 5,.......n
int i,j,k,n; j= 1, 2, 3, 4, 5,.......n
for(i=1;i<=n;i++)
k= 1*10, 2*10, 3*10,......n*10 times
{
for(j=1;j<=i;j++)
{ t(n)=(1+2+3+4+5.....n)10
for(k=1;k<=10;k++) t(n)=n(n+1)/2*10
{ =O(n2)
printf("kps");
}
}
}
}
Department of IT 75
A() T(n)=log(n)
{
int a=1;
for(int i=1;i2<=n;i++)
print(“Ram”);
}
Department of IT 76
ARRAYS
 An array is a collection of elements of the same type
that are referenced by a common name.
 Compared to the basic data type (int, float & char)

it is an aggregate or derived data type.
 All the elements of an array occupy a set of contiguous

memory locations.
Department of IT
77
Why ARRAYS?
"We have a list of 1000 students' marks of an
integer type. If using the basic data type (int),
we will declare something like the following…"
int studMark0, studMark1, studMark2, ...,

studMark999;
 Can you imagine how long we have to write
the declaration part by using normal variable
declaration?
int main()
{
int studMark1, studMark2, studMark3,…………
studMark1000;
…………
return 0;
Department of IT
} 78

ARRAYS
By using an array, we just declare like this,
int studMark[1000];
 This will reserve 1000 contiguous memory locations for storing the
students’ marks.
 Graphically, this can be depicted as in the following figure.
Department of IT
79
Arrays in Memory
Assuming integer takes 2 bytes of storage
Department of IT
80
Arrays
One Dimensional Array: Declaration
 A single or one dimensional array declaration has the
following form,
array_data_type array_name[array_size];
 Here, array_data_type define the base type of the array,

which is the type of each element in the array.
 array_name is any valid C / C++ identifier name that
obeys the same rule for the identifier naming.
 array_size defines how many elements the array will
hold.
Department of IT
81
Arrays
 For example, to declare an array of 30 characters, that
construct a people name, we could declare,
char cName[30];
 Which can be depicted as follows,
 In this statement, the array character can store
up to 30 characters with the first character
occupying location cName[0] and the last
character occupying cName[29].
 Note that the index runs from 0 to 29. In C, an
index always starts from 0 and ends with array's
(size-1).
Department of IT
82
Arrays
Array Initialization
 An array may be initialized at the time of declaration.

 Initialization of an array may take the following form,
type array_name[size] = {a_list_of_value};
 For example:
int idNum[7] = {1, 2, 3, 4, 5, 6, 7};
float fFloatNum[5] = {5.6, 5.7, 5.8, 5.9, 6.1};
 The first line declares an integer array idNum and it
immediately assigns the values 1, 2, 3, ..., 7 to idNum[0],
idNum[1], idNum[2],..., idNum[6] respectively.
 The second line assigns the values 5.6 to
fFloatNum[0], 5.7 to fFloatNum[1], and so on.
Department of IT
83
Array Initialization
Examples
int num[6] = { 2, 4, 12, 5, 45, 5 } ;
int n[ ] = { 2, 4, 12, 5, 45, 5 } ;
float press[ ] = { 12.3, 34.2 -23.4, -11.3 } ;
Till the array elements are not given any specific values, they are supposed to
contain garbage values.
int B[20] = {2, 4, 8, 16, 32};
•Unspecified elements are guaranteed to be zero
int C[4] = {2, 4, 8, 16, 32};
•Error — compiler detects too many initial values
int E[5] = {1};
•Dynamically allocated array (automatic only). Zeroth element initialized to 1; all
other elements initialized to 0.
int E[5] = {0};
 All elements initialize to zero
Department of IT 84
1-D Array
 Homogeneous data:
a) Elements are represented through indexes.
b) Elements are saved in sequential in memory locations.
 Number of elements, N –> length or size of an array.
If:
UB : upper bound ( the largest index)
LB : lower bound (the smallest index)
Then: N = UB – LB + 1
Length = N = UB when LB = 1
Department of IT
85
Address Calculation in 1-D Array
 The process to determine the address in a memory:
a) First address –> base address.
b) Relative address to base address through index function.
Example: char X[100];

Let char uses 1 location storage.
If the base address is 1200 then the next element is in 1201.
Index Function is written as:
Loc (X[i]) = Loc(X[0]) + i , i is subscript and LB = 0
1200 1201 1202 1203
X[0] X[1] X[2]
Department of IT
86
Address Calculation in 1-D Array(..contd)
 In general, index function:
Loc (X[i]) = Loc(X[LB]) + w*(i-LB);
where w is length of memory location required.

For real number: 4 byte, integer: 4 byte and character: 1
byte.
 Example:
If LB = 5, Loc(X[LB]) = 1200, and w = 4, find Loc(X[8]) ?
Loc(X[8])= Loc(X[5]) + 4*(8 – 5)

= 1212
Department of IT
87
Address Calculation in 1-D Array(..contd)
Q1 Consider the linear arrays AAA[5:50], BBB [-5:10] and
CCC[1:18].
(a) Find the number of elements in each array
(b) Suppose Base(AAA) = 300 and w=4 words per memory cell for
AAA. Find the address of AAA[35] ,AAA[15], and AAA[55]
Department of IT 88
(a) Length = Upper Bound – Lower Bound +1
Length(AAA) = 50-5+1 = 46
Length(BBB) = 10-(-5)+1 = 16
Length(CCC) = 18-1+1 = 18
(b) Using the formula: LOC(AAA[k]) = Base(AAA)+w(K-

LB)
LOC(AAA[15] )= 300+4(15-5) = 340
LOC(AAA[35] )= 300+4(35-5) = 420
AAA[55] is not an element of AAA since 55 exceeds UB
= 50.
Department of IT 89
2-D Array
 Imagine now we want to keep 10 test scores for 30 students.
• How would we represent this in a program with what we’ve learned?
• Answer: You would need either 30 10-element arrays or
10 30-element arrays.
 What we have been working with so far are considered one
dimensional arrays, because they only extend along one
dimension (one set of data).
 “C” allows for higher dimensional arrays, for example, two
dimensional arrays.
• Two dimensional arrays can be though of having a table of rows and
columns in memory.
 So, a better solution to the above question is what?
• Answer: Have a 30 x 10 or a 10 x 30 two dimensional array!
Department of IT
90
Department of IT 91
Department of IT 92
Department of IT 93
Storage Order
Row-major order: the array is stored as a sequence of arrays
consisting of rows
(0,0)
0 1 2 3 4 5 6 (0,1)
(0,2)
0
Department of IT 94
Storage Order
Column-major order: The array is stored as a sequence of arrays
consisting of columns instead of rows
(0,0)
4 5 (1,0)
0 1 2 3 6
(0,1)
0
Department of IT 95
Address Calculation in 2-D Array
 When lower bound is not given.
The computer keeps track of Base (BA),:-
the address of the first element A[0][0] of A[M][N],
and computes address i.e. Loc (A[I][J]) of A[M][N] using
the formula
Loc(A[I][J])=Base (BA)+W[M*J + I] [Column Major]
Loc(A[I][J])=Base (BA)+W[N*I + J] {Row- Major}
 W denotes the size, i.e; number of bytes per data element of the
array A,
 M is total numbers of rows, and N is total number of columns in
the array.
Department of IT
96
Address Calculation in 2-D
Array(..contd)
 When lower bound is given
Loc(A[I][J])=Base (BA)+W[M*(J-LBC) + (I-LBR)] [Column Major]
Loc(A[I][J])=Base (BA)+W[N*(I-LBR) + (J-LBC)] {Row- Major}

 In case of ‘C’
 LBR=0 (Lower Bound Row)
 LBC=0 (Lower Bound Column)
Department of IT
97
Example
 Suppose element of array A[4][5] occupies 4 bytes, and the address
of the 1st element is 49. Find the address of the
element A(4,3) when the storage is row major.
= BA + [N * (I - LBR) + (J - LBC)] * W
= 49 + [5 * (4 – 0) + (3 - 0)] * 4
= 49 + [23] * 4
= 49 + 92
= 141
Department of IT
98
Sparse Matrix
 A matrix is sparse if many of its elements are zero
 A matrix that is not sparse is dense
 Two possible representations
• array
• linked list
Department of IT
99
Array Representation of Sparse Matrix
 The nonzero entries may be mapped into a 1D array in row-major
order
 To reconstruct the matrix structure, need to record the row and
column each nonzero comes from
Department of IT
100
Basic Operations
Following are the basic operations supported by an array.
 Traverse − print all the array elements one by one.
 Insertion − Adds an element at the given index.
 Deletion − Deletes an element at the given index.
 Search − Searches an element using the given index or by the
value.
Department of IT
101
Traversal
 Description: Here A is a linear array with lower
bound LB and upper bound UB. This algorithm
traverses array A and applies the operation
PROCESS to each element of the array.
1. Repeat For I = LB to UB
2. Apply PROCESS to A[I]
[End of For Loop]
3. Exit
Department of IT
102
Deletion algorithm
DELETE (LA, N, K, ITEM)
Here LA is a Linear Array with N elements and K is the positive
integer such that K<=N. This algorithm deletes the Kth element from
LA.
1. Set ITEM: = LA [k].
2. Repeat for J = K to N – 1.
[Move J + 1st element upward]

Set LA [J]: = LA [J +1].
[End of loop]
3. [Reset the number N of elements in LA] Set N: = N-1
4. EXIT
Department of IT
103
Insertion algorithm
INSERT (LA, N, K, ITEM)
1. [Initialize counter] Set J: = N.
2. Repeat Steps 3 and 4 while j >= k;
3. [Move jth element downward.] Set LA [J + 1]: =LA [J].
4. [Decrease counter] Set J: = J-1
[End of step 2 loop]
5. [Insert element] Set LA [K]:=ITEM.
6. [Reset N] Set N:=N+1
7. EXIT.
Department of IT
104
Linear Search
Linear Search ( Array A, Value x)
Step 1: Set i to 1
Step 2: if i > n then go to step 7
Step 3: if A[i] = x then go to step 6
Step 4: Set i to i + 1
Step 5: Go to Step 2
Step 6: Print Element x Found at index i and go to step 8
Step 7: Print element not found
Step 8: Exit
Department of IT
105
Introduction to Array (CO1)
Analysis of Linear Search

How long will our search take?
In the best case, the target value is in the first element of the
array.
So the search takes some tiny, and constant, amount of time.
In the worst case, the target value is in the last element of the
array.
So the search takes an amount of time proportional to the
length of the array. O(n)
Department of IT
106
Analysis of Linear Search

 In the average case, the target value is somewhere in the array.
 In fact, since the target value can be anywhere in the array, any element of
the array is equally likely.
 So on average, the target value will be in the middle of the array.
 So the search takes an amount of time proportional to half the length of the
array.
Department of IT
107
Binary Search
The general term for a smart search through sorted data is a binary
search.
1. The initial search region is the whole array.
2. Look at the data value in the middle of the search region.
3. If you’ve found your target, stop.
4. If your target is less than the middle data value, the new search
region is the lower half of the data.
5. If your target is greater than the middle data value, the new
search region is the higher half of the data.
6. Continue from Step 2.
Department of IT
108
Binary Search Example
Department of IT
109
Introduction to Array(CO1)
Department of IT
110
Department of IT
111
Binary Search
Department of IT
112
Binary Search Program

#include <stdio.h>
void main() else if (array[middle] == search)
{ {
int c, first, last, middle, n, printf("%d is present at pos %d.\
search, array[100]; n", search, middle+1);
printf("Enter number of elements:\ break;
n");
}
scanf("%d",&n);
printf("Enter %d integers:\n", n); else
for (c = 0; c < n; c++) last = middle - 1;
scanf("%d",&array[c]); middle = (first + last)/2;
printf("Enter the value to find:\n"); }
scanf("%d", &search); if (first > last)
first = 0;last = n - 1; printf("Not found! %d is not
middle = (first+last)/2; present in the list.\n", search);
while (first <= last) { }
if (array[middle] < search)
first = middle + 1; Department of IT
113
Time complexity of binary search

At each iteration, the array is divided by half. So Therefore
let’s say the length of array at any iteration is n Length of array = n⁄2k = 1
At Iteration 1, => n = 2k
Length of array = n 10 Applying log function on
At Iteration 2, both sides:
=> log2 (n) = log2 (2k)
Length of array = n⁄2 5
=> log2 (n) = k log2 (2)
At Iteration 3, => k = log2 (n)
Length of array = (n⁄2)⁄2 = n⁄22 2 Hence the time
Therefore, after Iteration k, complexity of Binary
Length of array = n⁄2k 1 Search is
Also, we know that after
After k divisions, the length of array becomes 1 log2 (n)
Department of IT
114
 Example
Insert element in array
 Input
Input array elements: 10, 20, 30, 40, 50

Input element to insert: 35
Input position where to insert: 4
Output
Elements of array are: 10, 20, 30, 35, 40, 50
Department of IT
115
Logic to insert element in array
Insert an element at position 4.
Department of IT
116
Logic to insert element in array
for(i=size; i>=pos; i--)

arr[i] = arr[i - 1];
Department of IT
117
arr[pos - 1] = num;
Department of IT
118
Program to insert element in array

#include <stdio.h> else
int main() {
{ int arr[100]; /* Make room for new array element by
shifting to right */
int i, size, num, pos; for(i=size; i>=pos; i--)
printf("Enter size of the array : "); {
scanf("%d", &size); arr[i] = arr[i-1];
}
printf("Enter elements in array : "); /* Insert new element at given position and
for(i=0; i<size; i++) increment size */
arr[pos-1] = num;
scanf("%d", &arr[i]);
size++;
printf("Enter element to insert : "); /* Print array after insert operation */
scanf("%d", &num); printf("Array elements after insertion : ");
for(i=0; i<size; i++)
printf("Enter the element position : "); {
scanf("%d", &pos); printf("%d\t", arr[i]);
if(pos > size+1 || pos <= 0) }
}
{ printf("Invalid position! Please enter return 0;
position between 1 to %d", size); Department
} of IT
119
}
 Example
Delete element from an array
Input
Input array elements: 10 20 30 40 50

Input position to delete: 2
Output
Array elements: 10, 30, 40, 50
Department of IT
120
Logic to remove element from array

Step by step descriptive logic to
remove element from array.
Move to the specified location

which you want to remove in
given array.
Copy the next element to the

current element of array. Which
is you need to perform array[i]
= array[i + 1].
Repeat above steps till last

element of array.
Department of IT
121
Finally decrement the size of
Program to delete an element from an

array
#include <stdio.h>
#define MAX_SIZE 100
int main()
{
int arr[MAX_SIZE];
int i, size, pos;
printf("Enter size of the array : ");
scanf("%d", &size);
printf("Enter elements in array : ");
{ scanf("%d", &arr[i]);
}
printf("Enter the element position to delete : ");
scanf("%d", &pos);
if(pos < 0 || pos > size)
{ printf("Please enter position between 1 to %d", size);
}
Department of IT
122
else
{
for(i=pos; i<=size-1; i++)
{
arr[i-1] = arr[i];
}
size--;
}
printf("\nElements of array after delete are : ");
{
printf("%d\t", arr[i]);
}
return 0;
}
Department of IT
123
Multi-dimensional Arrays in C
 Multidimensional array declaration
type name[size1][size2]...[sizeN];
 For example, the following declaration creates a three

dimensional integer array −
int threedim[5][10][4];
Department of IT
124
Two dimensional (2D) arrays

 An array of arrays is known as 2D array.
 The two dimensional (2D) array in C programming
is also known as matrix.
 A matrix can be represented as a table of rows and
columns.
Department of IT
125
Initializing Two-Dimensional Arrays

 Multidimensional arrays may be initialized by specifying bracketed
values for each row. Following is an array with 3 rows and each row
has 4 columns.
int a[3][4] = {
{0, 1, 2, 3} , /* initializers for row indexed by 0 */
{4, 5, 6, 7} , /* initializers for row indexed by 1 */
{8, 9, 10, 11} /* initializers for row indexed by 2 */
};
 The nested braces, which indicate the intended row, are optional. The
following initialization is equivalent to the previous example −
int a[3][4] = {0,1,2,3,4,5,6,7,8,9,10,11};
Department of IT 126
Things that you must consider while

initializing a 2D array
 /* Valid declaration*/
int abc[2][2] = {1, 2, 3 ,4 }
 /* Valid declaration*/
int abc[][2] = {1, 2, 3 ,4 }
 /* Invalid declaration – you must specify second dimension*/
int abc[][] = {1, 2, 3 ,4 }
 /* Invalid because of the same reason mentioned above*/
int abc[2][] = {1, 2, 3 ,4 }
Department of IT
127
Accessing Two-Dimensional Array Elements

 An element in a two-dimensional array is accessed by using the
subscripts, i.e., row index and column index of the array.
For example : int val = a[2][3];
#include <stdio.h>
void main () {
int a[5][2] = { {0,0}, {1,2}, {2,4}, {3,6},{4,8}};
int i, j;
for ( i = 0; i < 5; i++ ) {
for ( j = 0; j < 2; j++ ) {
printf("a[%d][%d] = %d\n", i,j, a[i][j] );
}
}
} Department of IT
128
To store the elements entered by user in 2D

#include<stdio.h> Array
void main()
{
int abc[5][4];
int i, j;
for(i=0; i<5; i++) {
for(j=0;j<4;j++) {
printf("Enter value for abc[%d][%d]:", i, j);
scanf("%d", &abc[i][j]);
}
}
}
Department of IT
129
Address Calculation in Two Dimensional

Array:
Department of IT
130
Department of IT
131
Address of an element of any array say “A[ I ][ J ]” is calculated in two forms as

given:
Row Major System:
Address of A [ I1 ][ I2 ] = B + W * [( I1 – L1 ) * N2+ ( I2 – L2 )]
Column Major System:
Address of A [ I1 ][ I2 ] Column Major Wise = B + W * [( I1 – L1 ) + N1 * ( I2 – L2 )]
Where,
B = Base address
I1 = Row subscript of element whose address is to be found
I2 = Column subscript of element whose address is to be found
W = Storage Size of one element stored in the array (in byte)
L1 = Lower limit of row/start row index of matrix, if not given assume 0 (zero)
L2 = Lower limit of column/start column index of matrix, if not given assume 0 (zero)
N1 = Number of row of the given matrix
Department of IT
132
N = Number of column of the given matrix
Q 1. An array X [-15……….10, 15……………40] requires one byte

of storage. If beginning location is 1500 determine the location of X
[15][20].
As you see here the number of rows and columns are not given in the
question. So they are calculated as:
Number or rows say N1 = (U1 – L1) + 1 = [10 – (- 15)] +1 = 26

Number or columns say N2 = (U2 – L2) + 1 = [40 – 15)] +1 = 26
(i) Column Major Wise Calculation of above equation

The given values are: B = 1500, W = 1 byte, I 1 = 15, I2 = 20, L1 = -15, L2 = 15,
N1 = 26
Address of A [ I1 ][ I2 ] =B + W * [( I1 – L1 ) + N1 * ( I2 – L2 )]
= 1500 + 1 * [(15 – (-15)) + 26 * (20 – 15)] = 1500 + 1 * [30 + 26 * 5] =
1500 + 1 * [160] = 1660 [Ans] Department of IT 133
Q 1. An array X [-15……….10, 15……………40] requires one

byte of storage. If beginning location is 1500 determine the
location of X [15][20].
(ii) Row Major Wise Calculation of above equation
The given values are: B = 1500, W = 1 byte, I1 = 15, I2 = 20, L1 =

-15, L2 = 15, N2 = 26
Address of A [ I1 ][ I2 ] =B + W * [( I1 – L1 )* N2 + ( I2 – L2 )]
= 1500 + 1* [26 * (15 – (-15))) + (20 – 15)] = 1500 + 1 * [26 *

30 + 5] = 1500 + 1 * [780 + 5] = 1500 + 785
= 2285 [Ans] Department of IT
134
Memory Location Formula for N- Dimensional

Array
Formula for 1 D Array –
A [ I1 ] = B + W * ( I1 – L1 )
Where I1 – Index whose location we want to find.
B – Base Address
W – Size of Data Type
L1 – Lower Bound of the array
Let ( I1 – L1 ) = E1 (Effective index of I1)

Where Ei – Effective index of Ii
A [ I1 ] = B + W * [E1 ]
Department of135
IT

Array
A [ I1 ][I2] = B + W * [( I1 – L1 )*N2+(I2-L2)]
Where I1, I2 – Index whose location we want to find.
B – Base Address
W – Size of Data Type
L1, L2 – Lower Bound of the array
Let ( I1 – L1 ) = E1 (Effective index of I1); ( I2 – L2 ) = E2

Where Ei – Effective index of Ii
A [ I1 ] [I2] = B + W * [E1*N2 + E2]

Department of IT
136

Array
A [ I1 ] [I2] = B + W * [E1*N2 + E2]
A [ I1 ] [I2] [I3] = B+W*[(E1*N2 + E2)*N3+E3]
A [ I1 ] [I2] [I3] [ I4 ]= B+W*[((E1*N2 + E2)*N3+E3)*N4+E4]
So on for N- Dimensional array ..

A [ I1 ] [I2] [I3] [ I4 ]….[In] = B+W*[(((E1*N2 + E2)*N3+E3)*N4+E4….En-
1)*Nn+En]
Three-Dimensional Array
Department of IT
138
Given an array [ 1..8, 1..5, 1..7 ] of integers. Calculate address of

element A[5,3,6], by using rows wise methods, if Base
Address=900?
Solution:- The dimensions of A are :
N1=8 , N2=5, N3=7, I1=5, I2=3, I3=6, W=2,L1=1,L2=1,L3=1
Rows - wise :
Location (A[I1, I2, I3]) = B + W*[(E1N2+E2)*N3+E3]
= B + W*[((I1-L1)*N2+(I2-
L2))*N3+(I3-L3)]
Location(A[5,3,6])= 900 + 2*[((5-1)*5+(3-1))*7+(6-1)]

= 900 + 2*[(4*5+2)*7+5]
Department of IT
= 900 +2*159 139
Initializing Three-Dimensional Array

Method 1:
int x[2][3][4] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23};
Method 2:
int x[2][3][4] =
{
{ {0,1,2,3}, {4,5,6,7}, {8,9,10,11} },
{ {12,13,14,15}, {16,17,18,19}, {20,21,22,23} }
};
For (i=0;i<n;i++0
{
For(j=0;j<n;j++)
{
For(k=0;k<n;k++)
{
scanf(“%d”,&a[i][j][k])
Department of IT
140
Applications of Arrays in C
● Arrays are used to Store List of values
● Arrays are used to Perform Matrix Operations
● Arrays are used to implement Search Algorithms
Linear Search Binary Search
● Arrays are used to implement Sorting Algorithms.
Insertion Sort Bubble Sort
Selection Sort Quick Sort Merge Sort, etc.,
● Arrays are used to implement Data structures.
Stack Using Arrays Queue Using Arrays
● Arrays are also used to implement CPU Scheduling Algorithms.
Department of IT
141
Pointer Notation
Consider the declaration,
int i = 3 ;
This declaration tells the C compiler to:
(a) Reserve space in memory to hold the integer value.
(b) Associate the name i with this memory location.
(c) Store the value 3 at this location.
What are Pointers?
• A pointer is a variable whose value is the address of another variable,
i.e., direct address of the memory location.
• Like any variable or constant, you must declare a pointer before using it
to store any variable address.
Pointer variable declaration:
type *var-name;
Here, type is the pointer's base type; it must be a valid C data type and
varname is the name of the pointer variable. The asterisk * used to
declare a pointer is the same asterisk used for multiplication.
Examples: some of the valid pointer declarations:
int *ip; /* pointer to an integer */
double *dp; /* pointer to a double */
float *fp; /* pointer to a float */
char *ch /* pointer to a character */of IT
Department 143
How to Use Pointers?
Three things need to do
(1) We define a pointer variable,
(2) Assign the address of a variable to a pointer, and
(3) Finally access the value at the address available in the pointer variable.
This is done by using unary operator *. Which says the value at the address.
main( ) output:
{
int i = 3 ; Address of i = 65524
printf ( "\nAddress of i = %u", &i ) ; Value of i = 3
printf ( "\nValue of i = %d", i ) ;
}
main( ) output
{
printf ( "\nAddress of i = %u", &i ) ; Value of i = 3
printf ( "\nValue of i = %d", i ) ; Value of i = 3
printf ( "\nValue of i = %d", *( &i ) ) ;
}
The expression &i gives the address of the variable i. This address can be
collected in a variable, by saying,
j = &i ;
But remember that j is not an ordinary variable like any other integer variable.
It is a variable that contains the address of other variable (i in this case).
j is a variable that contains the address of i, it is declared as,

int *j ;
main( ) The output of the above program would

{ be:
int *j ; Address of i = 65524
j = &i ; Address of j = 65522
printf ( "\nAddress of i = %u", &i ) ; Value of j = 65524
printf ( "\nAddress of i = %u", j ) ; Value of i = 3
printf ( "\nAddress of j = %u", &j ) ; Value of i = 3
printf ( "\nValue of j = %u", j ) ; Value of i = 3
printf ( "\nValue of i = %d", i ) ;
printf ( "\nValue of i = %d", *( &i ) ) ;
printf ( "\nValue of i = %d", *j ) ;
}
Pointer to Pointer or Double pointer
• A pointer to a pointer is a form of multiple indirection, or a chain of pointers.
• When we define a pointer to a pointer, the first pointer contains the address of
the second pointer, which points to the location that contains the actual value as
shown below.
int i=3;
int *j=&i;
int **k=&j;
Operation do not work with pointer
Do not attempt the following operations on pointers... they
would never work out.
(a) Addition of two pointers
(b) Multiplication of a pointer with a constant
(c) Division of a pointer with a constant
Recursion
Recursion
• Recursion is a process by which a function calls itself repeatedly,
until some specified condition has been satisfied
• The process is used for repetitive computations in which each action

is stated in terms of a previous result.
• To solve a problem recursively, two conditions must be satisfied.

• First, the problem must be written in a recursive form
• Second the problem statement must include a stopping condition
Department of IT 15
0
Recursion
Recursion
• There is base condition, that stops further calling of the
function
• Function call itself directly or indirectly, it should reach

towards base condition.
Department of IT 15
1
Recursion
Calculate Factorial of the number using
Recursion.
factorial of n  (n!) = n * n-1 – n-2* ………*2*1
n!= n* (n-1)! And 0! = 1
Department of IT 15
2
Recursion
Recursion Pros and Cons

• Pros
• The code may be much easier to write.
• To solve some problems which are naturally recursive
such as tower of Hanoi.
• Cons
• Recursive functions are generally slower than non-
recursive functions.
• May require a lot of memory to hold intermediate results
on the system stack.
• It is difficult to think recursively so one must be very
careful when writing recursive functions.
Department of IT
15
3
Recursion
 Difference Between Recursion and Iteration
BASIS FOR
RECURSION ITERATION
COMPARISON
Basic The statement in a body of Allows the set of instructions
function calls the function to be repeatedly executed.
itself.
Format In recursive function, only Iteration includes
termination condition (base initialization, condition,
case) is specified. execution of statement within
loop and update (increments
and decrements) the control
variable.
Termination A conditional statement is The iteration statement is
included in the body of the repeatedly executed until a
function to force the function certain condition is reached.
to return without recursion call
being executed.
Recursion
BASIS FOR COMPARISON RECURSION ITERATION
Condition If the function does not If the control condition in the
converge to some condition iteration statement never
called (base case), it leads to become false, it leads to
infinite recursion. infinite iteration.
Infinite Repetition Infinite recursion can crash the Infinite loop uses CPU cycles
system. repeatedly.
Applied Recursion is always applied to Iteration is applied to iteration
functions. statements or "loops".
Stack The stack is used to store the Does not uses stack.
set of new local variables and
parameters each time the
function is called.
Overhead Recursion possesses the No overhead of repeated
overhead of repeated function function call.
calls. Department of IT 155
Recursion
BASIS FOR
RECURSION ITERATION
COMPARISON
Speed Slow in execution. Fast in execution.
Size of Code Recursion reduces the size of Iteration makes the code
the code. longer.
Introduction to Link List(CO1)
What are Linked Lists

A linked list is a linear data
structure.
Nodes make up linked lists.
Nodes are structures made up of
data and a pointer to another node.
Usually the pointer is called next.
Linked List
•The elements of a linked list are not stored in adjacent memory

locations as in arrays.
•It is a linear collection of data elements, called nodes, where the

linear order is implemented by means of pointers.
Linked List
• In a linear or single-linked list, a node is connected to the next node
by a single link.
• A node in this type of linked list contains two types of fields

• data: which holds a list element
• next: which stores a link (i.e. pointer) to the next node in the list.
Introduction to Link List
Introduction to List and Linked Lists

• List is a term used to refer to a linear collection of data items. A
List can be implemented either by using arrays or linked lists.
• Usually, a large block of memory is occupied by an array which

may not be in use and it is difficult to increase the size of an
array.
• Another way of storing a list is to have each element in a list

contain a field called a link or pointer, which contains the
address of the next element in the list.
• The successive elements in the list need not occupy adjacent
space in memory. This type of data structure is called a linked
list.
Linked List
• The structure defined for a single linked list is implemented as
follows:
struct node
{
int data;
struct node *next;
};
}The structure declared for linear linked list holds two members
• An integer type variable ‘data’ which holds the elements and
• Another type ‘node’, which has next, which stores the address of the next
node in the list.
Figurative
Representation
Properties of Linked list

• The nodes in a linked list are not stored contiguously in the memory
• You don’t have to shift any element in the list
• Memory for each node can be allocated dynamically whenever the

need arises.
• The size of a linked list can grow or shrink dynamically
Operations on Linked List

• Creation:
• This operation is used to create a linked list
• Insertion / Deletion
• At/From the beginning of the linked list
• At/From the end of the linked list
• At/From the specified position in a linked list
• Traversing:
• Traversing may be either forward or backward
• Searching:
• Finding an element in a linked list
• Concatenation:
• The process of appending second list to the end of the first
list
Link List(CO1)
Arrays Vs Linked Lists

Arrays Linked list
Fixed size: Resizing is expensive Dynamic size
Insertions and Deletions are inefficient: Insertions and Deletions are efficient: No
Elements are usually shifted shifting
Random access i.e., efficient indexing No random access

 Not suitable for operations requiring accessing
elements by index such as sorting
No memory waste if the array is full or almost Since memory is allocated dynamically(acc. to
full; otherwise may result in much memory our need) there is no waste of memory.
waste.
Sequential access is faster [Reason: Elements in Sequential access is slow [Reason: Elements not
contiguous memory locations] in contiguous memory locations]
Types of Linked List

• Singly Linked List
• Doubly linked list
• Circular linked list
• Circular doubly linked list
Singly Linked List

• A singly linked list is a dynamic data structure which may grow or
shrink, and growing and shrinking depends on the operation made.
• In this type of linked list each node contains two fields one is data
field which is used to store the data items and another is next field
that is used to point the next node in the list.
info next info next info next
5 3 8 null
Creating a Linked List

• The head pointer is used to create and access unnamed nodes.
struct node
{ int data; // Data part of the node
struct node* next; // Pointer to the next node
};
Initialize the Head Pointer: The head pointer points to the first node in the
linked list. Initially, it is set to NULL because the list is empty.
struct node* head = NULL;
• The above statement obtains memory to store a node and assigns its address to
head which is a pointer variable.
Creating a Node
• To create a new node, we use the malloc function to dynamically
allocate memory for the new node.
• After creating the node, we can store the new item in the node using a
pointer to that node.
Nodetype *p;
p=(NodeType *) malloc (sizeof( NodeType ) ); p->info=50;
p->next = NULL;
• Note that p is not a node; instead it is a pointer to a node.
Creating an empty list
void createEmptyList(NodeType *head)

{
head=NULL;
}
OR SIMPLY
NodeType *head =Null;
1) Create Empty Link List Struct Node *Head;

Head Head = NULL;
NULL
2) Insert First Node Struct Node *NewNode;
NewNode = (struct Node*)malloc(sizeof(struct
Head 100
Node));
10 NULL NewNode = 100
100
3) Insert Second Node
Head
10 5 NULL
100 200
Struct Node *temp=head;

NewNode = (struct Node*)malloc(sizeof(struct Node));
temp->next = NewNode;
Inserting an Element
• While inserting an element or a node in a linked list, we have to
do following things:
• Allocate a node
• Assign a data to info field of the node.
• Adjust a pointer
• We can insert an element in following places

• At the beginning of the linked list
• At the end of the linked list
• At the specified position in a linked list
An algorithm to insert a node at the beginning of the singly linked list
Let *head be the pointer to first node in the current list

1.Create a new node using malloc function
NewNode=(NodeType*)malloc(sizeof(NodeType));
2.Assign data to the info field of new node

NewNode->info=newItem;
3.Set next of new node to head

NewNode->next=head;
4.Set the head pointer to the new node

head=NewNode;
5.End
Inserting a node at the beginning of the singly linked list
An algorithm to insert a node at the end of the singly linked list

let *head be the pointer to first node in the current list
3.Set next of new node to NULL
NewNode->next=NULL;
4.if (head ==NULL) then
Set head =NewNode.and exit.
5.Set temp=head;
6.while(temp->next!=NULL)
temp=temp->next; //increment temp
7.Set temp->next=NewNode;
8.End
An algorithm to insert a node at the end of the singly

linked list
An algorithm to insert a node after the given node in singly linked

list
and *p be the pointer to the node after which we want
to insert a new node.

3.Set next of new node to next of p

NewNode->next=p->next;
4.Set next of p to NewNode
p->next =NewNode
5.End
An algorithm to insert a node at the specified position in a linked list

3.Enter position of a node at which you want to insert a

new node. Let this position is pos.
4.Set temp=head;
5.if (head ==NULL)then
printf(“void insertion”); and exit(1).
6.for(i=1; i<pos; i++)
temp=temp->next;
7.Set NewNode->next=temp->next;
set temp->next =NewNode..
8.End
Deleting Nodes
• A node may be deleted:

• From the beginning of the linked list
• From the end of the linked list
• From the specified position in a linked list
Deleting Nodes
An algorithm to delete a node after the given
node in singly linked list
 Let *head be pointer to the first node in the current list and p* be
pointer to the node after which we want to delete a new node
 If (p==NULL or p->next== NULL) then

 Print “deletion not possible and exit”
 Set q=p->next;
 Set p->next=q->next;
 free (q);
 End
Searching an item in a linked list

• Let *head be the pointer to first node in the current list
1.If head==Null
Print “Empty List”
2.Else, enter an item to be searched as key
3.Set temp==head
4.While temp!=Null
If (temp->info == key)
Print “search success”
temp=temp->next;
5.If temp==Null
Print “Unsuccessful search”
Delete particular node from link list

1.Let *head be the pointer to first node in the current list, Declared Q pointer
2.If head==Null
3.Print “Empty List”
4.Else, enter a value of node, you want to delete.
5.Set temp = head; Declare Prev pointer.
6.// If head node itself holds the key to be deleted
7. if (head != NULL && head->data == key)
8. {
9. head = head->next; // Changed head
10. free(temp); // free old head
11. return;
12. }
Delete particular node from link list

14. // Search for the key to be deleted, keep track of the
15. // previous node as we need to change 'prev->next'
16. while (temp != NULL && temp->data != key)
17. {
18. prev = temp;
19. temp = temp->next;
20. }
21. // If key was not present in linked list

22. if (temp == NULL) return;
23. // Unlink the node from linked list

24. prev->next = temp->next;
25. free(temp); // Free memory
Circular Link List(CO1)
What is circular linked list?
• Circular linked list is a variation of

linked list in which the first elements
points to the next element and the last
element points to the
first element.
• Both singly and doubly linked list can be
made into a circular linked list.
• Circular linked list can be used to help
traverse the same list again and again if
needed. Department of IT 191
Fun
fact:
If you are worried about its implementation,
then stop doing that because instead of
placing NULL at the last node’s address field
you are placing the address of very first node!
Circular linked list vs. Linear
linked list
• A circularly linked list may be a natural option to represent
arrays
that are naturally circular, e.g. the corners of a polygon, a
pool
of buffers that are used and released in FIFO order, or a set
of processes that should be time-shared. In these
applications, a pointer to any node serves as a handle to
the whole list.
• With a circular list, a pointer to the last node gives easy
access also to the first node, by following one link. Thus, in
applications that require access to both ends of the list, a
circular structure allows one to handle the structure by a
single pointer, instead of two.
• The simplest representation for an empty circular list
(when such a thing makes sense) is a null pointer,
indicating that the list has no nodes. Without this choice,
Types of circular linked list:

1. Singly: The last node points to the first node and
there is only
link between the nodes of linked list.
2. Doubly: The last node points to the first node

and there are two links between the nodes of
linked list.
Advantages of Circular
linked lists:
1. Any node can be a starting point. We can traverse
the whole list by starting from any point. We just
need to stop when the first visited node is visited
again.
2. Circular lists are useful in applications to

repeatedly go around the list. For example: when
multiple applications are running on a PC, it is
common for the operating system to put the
running applications on a list and then to cycle
through them, giving each of them a slice of time to
execute, and then making them wait while the CPU
is given to another application. It is convenient for
the operating system to use a circular list so that
when it reaches the end of the list it can cycle
around to the front of the list.
3. Circular Doubly Linked Lists are used for
Disadvantages of Circular linked list

1. Depending on the implementation, inserting at start of list
would require doing a search for last node which could be
expensive.
2. Finding end of the list and loop control is harder ( no

NULL’s to mark the beginning and end).
Operations on singly circular

linked list
•Insertio
n
•Deletio
n
•Display
Insertion :
• Insertion can be of three types.
▫Insert at first
▫Insert at last
▫Insert after constant
• Note: insertion after constant in

circular and linear linked list is exact
same .
Insertion at first
Algorithm (Insertion)
Code
Void addfront(){
struct node *t=start;
struct node *n=(struct node*)malloc(sizeof(struct node));
printf(“\nenter the information”);
scanf(“%d”,&n->info);
if(start==NULL){
start=n;
start->next=start;}
else{
n->next=start;
while(t->next!=start)
t=t->next;
t->next=n;
start=n;
}
Insert at last
Algorithm to Insert at Last
• Start.
• Declare struct node *t.
• Set t:=start.
• Create a new node n by malloc function and enter the
information in info part.
• Check if start=NULL then,
set start:=n.
set start->next:=start.
else
• Set n->next:=start.
• Repeat step(a)
while(t!=NULL)
▫ (a) set t:=t->next.
• [end of loop]
• Set t->next=n.
• [end if] Department of IT 203
• Stop.
Program
Void addlast(){
struct node *n=(struct node*)malloc(sizeof(struc
node));
printf(“\nenter the information”); scanf(“%d”,&n
>info);
if(start==NULL){
start=n;
start->next=start;}
else{
n->next=start;
Department of ITt=t->next; 204
t->next=n;
Deletion :
• Deletion can be of three types.
▫Delete from front
▫Delete from last
▫Deletion from mid
• Note: deletion from mid in circular and

linear linked list is exact same .
Delete from front
Algorithm Progra
start.
Check if (start=NULL) then,
m
Void delfront(){
print “empty list” if (start==NULL)
Check if printf (“\nempty list”);
(start->next=start) then, else if (start->next==start){
declare free (t) free (t);
set start:=NULL otherwise start=NULL;}
Repeat step(a) while(t->next!=start)
else{
▫ (a) set t:=t->next
[end of loop] t=t->next;
start=start->next;
free(t->next);
t->next=start;
}
}
Algorithm
• set start:=start-
>next
• Declare free(t-
>next).
• Set t->next:=start.
• [end of if]
• stop
Delete from last
Algorithm Program
• start. Void dellast()
• Check if (start=NULL) {
then, print “empty list” struct node *t=start;
• Check if (start- if (start==NULL)
>next=start) printf(“\nempty list”);
then, else if (start-
declare free (t) set >next==start)
{
start:=NULL otherwise
• Repeat step(a) free (t); start=NULL ;
}
while(t->next->next! else
=start) {
▫ (a) set t:=t->next while(t->next->next!
• [end of loop] =start)
• Declare free(t->next). t=t->next; free(t->next);
• Set t->next:=start. t->next=start;
• [end if] }
• stop Department of IT } 210
Display
Algorithm Progra
• start. m
Void display()
• Set struct node {
*t:=start. if(start=NULL)
• Check printf (“\nempty
if(start=NULL) list”); else
then, print “empty {
list” otherwise while(t->next!
• Repeat step a and b =start)
while(t->next! {
=start) printf(“%d”, t->info);
t=t->next;
▫ (a) print t->info }
▫ (b) set t:=t->next printf(“%d”, t->info);
• [end of loop] }
• Print t->info [end Department of}IT 212
Link List(CO1)
Doubly Linked List

Doubly linked list is a type of linked list in which each node apart from
storing its data has two links. The first link points to the previous node in the
list and the second link points to the next node in the list. The first node of the
list has its previous link pointing to NULL similarly the last node of the list
has its next node pointing to NULL.
The two links help us to traverse the list in both backward and forward
direction. But storing an extra link requires some extra space.
Link List(CO1)
First we define the node.

struct node
{
int data; // Data
node *prev; // A reference to the previous node
node *next; // A reference to the next node
};
Link List(CO1)
Important Points to be Remembered In double linked list, the first node

must be always pointed by head. Always the previous field of the first
node must be NULL. Always the next field of the last node must be
NULL
Link List(CO1)
Operations on Double Linked List

In a double linked list, we perform the following operations...
1. Insertion
2. Deletion
3. Display
Link List(CO1)
Insertion
In a double linked list, the insertion operation can be performed in
three ways as follows...
1. Inserting At Beginning of the list
2. Inserting At End of the list
3. Inserting At Specific location in the list
Link List(CO1)
Inserting At Beginning of the list

We can use the following steps to insert a new node at beginning of the double
linked list...
• Step 1 - Create a newNode with given value and newNode → previous as NULL.
• Step 2 - Check whether list is Empty (head == NULL)
• Step 3 - If it is Empty then, assign NULL to newNode → next and newNode to
head.
• Step 4 - If it is not Empty then, assignnewNode → next=head, head->prev =
NULL and head= newNode.
Link List(CO1)
Inserting At End of the list
We can use the following steps to insert a new node at end of the double linked list...
• Step 1 - Create a newNode with given value and newNode → next as NULL.
• Step 3 - If it is Empty, then assign NULL to newNode → previous and newNode to
head.
• Step 4 - If it is not Empty, then, define a node pointer temp and initialize with head.
• Step 5 - Keep moving the temp to its next node until it reaches to the last node in the
list (until temp → next is equal to NULL).
• Step 6 - Assign newNode to temp → next and temp to newNode → previous.
Link List(CO1)
Inserting At Specific location in the list (After a Node)

• Step 1 - Create a newNode with given value.
• Step 3 - If it is Empty then, assign NULL to both newNode → previous & newNode
→ next and set newNode to head.
• Step 4 - If it is not Empty then, define a node pointers temp1 & temp2 and initialize
temp1 with head.
• Step 5 - Keep moving the temp1 to its next node until it reaches to the node after
which we want to insert the newNode (until temp1 → data is equal to location, here
location is the node value after which we want to insert the newNode).
• Step 6 - Every time check whether temp1 is reached to the last node. If it is reached to
the last node then display 'Given node is not found in the list!!! Insertion not
possible!!!' and terminate the function. Otherwise move the temp1 to next node.
• Step 7 - Assign newNode → next to temp1 → next and newNode → previous
=temp, temp1 → next to newNode to newNode → previous, temp->next->previous
to newnode
Link List(CO1)
Deletion
In a double linked list, the deletion operation can be performed in three
ways as follows...
1. Deleting from Beginning of the list

2. Deleting from End of the list
3. Deleting a Specific Node
Link List(CO1)
Deleting from Beginning of the list

We can use the following steps to delete a node from beginning of the
double linked list...
• Step 2 - If it is Empty then, display 'List is Empty!!! Deletion is not
possible' and terminate the function.
• Step 3 - If it is not Empty then, define a Node pointer 'temp' and
initialize with head.
• Step 4 - Check whether list is having only one node (temp →
previous and temp → next are NULL )
• Step 5 - If it is TRUE, then set head = NULL and delete temp
(Setting Empty list conditions)
• Step 6 - If it is FALSE, then assign head=temp → next,
head → previous =NULL and delete temp.
Link List(CO1)
Deleting from End of the list
We can use the following steps to delete a node from end of the double
linked list...
• Step 2 - If it is Empty, then display 'List is Empty!!! Deletion is not
possible' and terminate the function.
• Step 3 - If it is not Empty then, define a Node pointer 'temp' and
• Step 4 - Check whether list has only one Node (temp → previous
and temp → next both are NULL)
• Step 5 - If it is TRUE, then assign NULL to head and delete temp.
And terminate from the function. (Setting Empty list condition)
• Step 6 - If it is FALSE, then keep moving temp until it reaches to
the last node in the list. (until temp → next is equal to NULL)
• Step 7 - Assign NULL to temp → previous → next and delete
temp.
Link List(CO1)
Deleting a Specific Node from the list

We can use the following steps to delete a specific node from the
double linked list...
• Step 2 - If it is Empty then, display 'List is Empty!!! Deletion
is not possible' and terminate the function.
• Step 3 - If it is not Empty, then define a Node pointer 'temp'
and initialize with head.
• Step 4 - Keep moving the temp until it reaches to the exact
node to be deleted or to the last node.
• Step 5 - If it is reached to the last node, then display 'Given
node not found in the list! Deletion not possible!!!' and
terminate the fuction.
• Step 6 - If it is reached to the exact node which we want to
delete, then check whether list is having only one node or not
Link List(CO1)
Step 7 - If list has only one node and that is the node which is to be
deleted then set head to NULL and delete temp (free(temp)).
• Step 8 - If list contains multiple nodes, then check whether temp is
the first node in the list (temp == head).
• Step 9 - If temp is the first node, then move the head to the next node
(head = head → next), set head of previous to NULL (head →
previous = NULL) and delete temp.
• Step 10 - If temp is not the first node, then check whether it is the last
node in the list (temp → next == NULL).
• Step 11 - If temp is the last node then set temp of previous of next
to NULL (temp → previous → next = NULL) and delete temp
(free(temp)).
• Step 12 - If temp is not the first node and not the last node, then set
temp of previous of next to temp of next (temp → previous → next
= temp → next), temp of next of previous to temp of previous
(temp → next → previous = temp → previous) and delete temp
(free(temp)).
Link List(CO1)
Displaying a Double Linked List

We can use the following steps to display the elements of a double
linked list...
• Step 2 - If it is Empty, then display 'List is Empty!!!' and terminate
the function.
• Step 3 - If it is not Empty, then define a Node pointer 'temp' and
• Step 4 - Display 'NULL <--- '.
• Step 5 - Keep displaying temp → data with an arrow (<===>) until
temp reaches to the last node
• Step 6 - Finally, display temp → data with arrow pointing to NULL
(temp → data ---> NULL).
Link List(CO1)
Doubly Circular Linked List
Circular Doubly Linked List has properties of both doubly linked list and
circular linked list in which two consecutive elements are linked or connected
by previous and next pointer and the last node points to first node by next
pointer and also the first node points to last node by previous pointer.
Link List(CO1)
Advantages:
List can be traversed from both the directions i.e. from head to tail or
from tail to head.
Jumping from head to tail or from tail to head is done in constant time
O(1).
Circular Doubly Linked Lists are used for implementation of advanced
data structures like Fibonacci Heap.
Disadvantages
It takes slightly extra memory in each node to accommodate previous
pointer.
Lots of pointers involved while implementing or doing operations on a list.
So, pointers should be handled carefully otherwise data of the list may
get lost.
Applications of Circular doubly linked list

Managing songs playlist in media player applications.
Managing shopping cart in online shopping.
Link List(CO1)
Insertion at the beginning of the list:
Link List(CO1)
1. void insertBegin(int value) 11. // Pointer points to last Node

2. { 12. struct node *last = (head)->prev;
3. struct node* new_node = 13.
malloc(sizeof(struct node)); 14. // setting up previous and next of
new node
15. new_node->next = head;
4. new_node->data = value; 16. new_node->prev = last;
17.
5. if (head== NULL) 18. // Update next and previous pointers
6. { of start
19. // and last.
7. new_node->next = new_node->prev =
20. last->next = head->prev =
new_node;
new_node;
8. head= new_node; 21.
9. return; 22. // Update start pointer
10. } 23. head = new_node;
24. }
Link List(CO1)
Insertion at the end of list or in an empty list
Link List(CO1)
// Function to insert at the end // If list is not empty

void insertEnd( int value) /* Find last node */
{ struct node *last = (head)->prev;
// If the list is empty, create a single
node // head is going to be next of new_nod
struct node* new_node = new_node->next = head;
malloc(sizeof(struct node));
new_node->data = value; // Make new node previous of start
(head)->prev = new_node;
if (head == NULL)
{ // Make last preivous of new node
new_node->next = new_node; new_node->prev = last;
new_node->prev = new_node;
head = new_node; // Make new node next of old last
return; last->next = new_node;
} }
Link List(CO1)
Insertion in between the nodes of the list:
Link List(CO1)
// Function to insert node with value as value1.

// The new node is inserted after the node with value2
void insertAfter(int value1, int value2)
{
struct node* new_node = malloc(sizeof(struct node));
new_node->data = value1; // Inserting the data
// Find node having value2 and next node of it
struct Node *temp = head;
while (temp->data != value2){
if(temp->next==head){
printf(“\n value is not present in the link list”);
return;}
temp = temp->next;
}
struct Node *ptr = temp->next;
// insert new_node between temp and ptr.
temp->next = new_node;
new_node->prev = temp;
new_node->next = ptr;
ptr->prev = new_node; Department of IT 235
}
Link List(CO1)
Deletion from the beginning of the doubly circular

link list:
Link List(CO1)
Deletion from the beginning of the doubly circular

link list:
void delfrombeg()
{
struct node *temp,*last;
temp = head;
if(head == NULL)
{
printf(“Link List is empty”);
return;
}
else if(head->prev==headnext)
head = NULL;
free(temp);
else{
last = temp->prev;
head = temp->next;
head - >prev = last;
last->next = head;
free(temp);}
}
Link List(CO1)
Deletion from the end of the doubly circular link

list:
Link List(CO1)
Deletion from the end of the doubly circular link

list:
void delfromend()
{
struct node *temp,*curr;
if(head == NULL)
{
printf(“Link List is empty”);
return;
}
else if(head->prev==headnext)
head = NULL;
else{
curr = head>prev;
temp = curr->prev;
head - >prev = temp;
temp->next = head;}
free(curr);
}
Link List(CO1)
Delete A Node By Key From Circular Double Link List

void deleteNode(int key)
// If list has more than one node,
{ // check if it is the first node
if (head == NULL) if (curr == head) {
return; // Move prev_1 to last node
struct Node *curr = head, *prev_1 = NULL; prev_1 = (head)->prev;
while (curr->data != key) {
// Move start ahead
// If node is not present in the list head = (head)->next;
if (curr->next == head) {
printf("\nList doesn't have node value "); // Adjust the pointers of prev_1 and start
return; } node
prev_1->next = head;
prev_1 = curr; (head)->prev = prev_1;
curr = curr->next; } free(curr);
// If key is in first node and list has only one node }
if (curr->next == head && prev_1 == NULL) {
(head) = NULL;
free(curr); return; } Department of IT 240
Link List(CO1)
// check if it is the last node

else if (curr->next == head) {
// Adjust the pointers of prev_1 and start node
prev_1->next = head;
(head)->prev = prev_1;
free(curr);
}
else {
// create new pointer, points to next of curr node
struct Node* temp = curr->next;
// Adjust the pointers of prev_1 and temp node

prev_1->next = temp;
temp->prev = prev_1;
free(curr);
}
}
APPLICATIONS OF LINKED LIST
Applications of linked list in computer science

Implementation of stacks and queues
Implementation of graphs : Adjacency list representation of
graphs is most popular which is uses linked list to store adjacent
vertices.
Dynamic memory allocation : We use linked list of free blocks.
Maintaining directory of names
Manipulation of polynomials by storing constants in the node of
linked list
representing sparse matrices
Applications of linked list in computer science

Implementation of stacks and queues
Implementation of graphs : Adjacency list representation of
graphs is most popular which is uses linked list to store adjacent
vertices.
Dynamic memory allocation : We use linked list of free blocks.
Maintaining directory of names
Manipulation of polynomials by storing constants in the node of
linked list
representing sparse matrices
 Applications of linked list in real world-

 Image viewer – Previous and next images are linked, hence can
be accessed by next and previous button.
 Previous and next page in web browser – We can access

previous and next url searched in web browser by pressing back
and next button since, they are linked as linked list.
 Music Player – Songs in music player are linked to previous and

next song. you can play songs either from starting or ending of
the list.
Polynomial
sPolynomials are the algebraic expressions which consist
of variables and coefficients.
Example -
10x2 + 26x, here 10 and 26 are coefficients and 2, 1 is its exponential value.
Polynomial can be represented in the various ways. These are:
•By the use of arrays

•By the use of Linked List
Link List(CO1)
•Polynomia
ls
• Array Implementation:
• p1(x) = 8x3 + 3x2 + 2x + 6
• p2(x) = 23x4 + 18x - 3
p1(x) p2(x)
6 2 3 8 -3 18 0 0 23
0 2 0 2 4
Index
represents
exponents
Link List(CO1)
•This is why arrays aren’t good to

represent polynomials:
•p3(x) = 16x21 - 3x5 + 2x + 6
6 2 0 0 -3 0 ………… 0 16
WASTE OF
SPACE!
Link List(CO1)
Add Two Polynomials Using Arrays
Input: A[] = {5, 0, 10, 6} B[] = {1, 2, 4}

Output: sum[] = {6, 2, 14, 6}
The first input array represents "5 + 0x^1 + 10x^2 + 6x^3"

The second array represents "1 + 2x^1 + 4x^2"
And Output is "6 + 2x^1 + 14x^2 + 6x^3“
add(A[0..m-1], B[0..n01])
1) Create a sum array sum[] of size equal to maximum of 'm' and 'n'
2) Copy A[] to sum[].
3) Traverse array B[] and do following for every element B[i]
sum[i] = sum[i] + B[i]
4) Return sum[].
Link List(CO1)
•Advantages of using an Array:
• Only good for non-sparse polynomials.

• Ease of storage and retrieval.
•Disadvantages of using an Array:
• Have to allocate array size priorly.

• Huge array size required for sparse polynomials.
Waste of space and runtime.
Link List(CO1)
•Polynomial
Representation
•Linked list Implementation:

•p1(x) = 23x9 + 18x7 + 41x6 +
163x4 + 3
P •p2(x) = 4x + 10x + 12x + 8
23 18
6 41
4 163 4 3 0
7 6
1 9 Next (contains
pointer)
4 10 12 8
P
4 1 0
2 6
NODE (contains coefficient &

exponent) Department of IT 250
Link List(CO1)
Advantages of using a Linked list:
•Save space (don’t have to worry about sparse

polynomials) and easy to maintain.
•Don’t need to allocate list size and can declare

nodes (terms) only as needed.
Disadvantages of using a Linked list :
Can’t go backwards through the list can’t jump to

the beginning of the list from the end.
Link List(CO1)
Polynomials em 1 em 2
A(x) am 1 x am e0
x
2
Representation
struct polynode {
...
int coef;
int exp;
struct polynode * next;
a0 x
};
typedef struct polynode *polyptr;
coef exp next
Link List(CO1)
Sparse Matrix
 Any matrix is called as Sparse Matrix in C, if it contains more number of zeros.
 The mathematical formula behind this C Sparse Matrix is:
T >= (m * n )/2 where T is total number of zeros.
 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..
 Sparse Matrix Representations

Triplet Representation (Array Representation)
Linked Representation
Triplet Representation (Array


Representation)
In this representation, we consider only non-zero values along with their row and
column index values. In this representation, the 0 throw stores the total number of
rows, total number of columns and the total number of non-zero values in the
sparse matrix.
For example, consider a matrix of size 5 X 6 containing 6 number of non-zero

values. This matrix can be represented as shown in the image.
C Program that will convert 2D-representation to Sparse representation.
#include <stdio.h>
int main() // Defining final matrix
{ int sparse_matrix[4][5] = int matrix[3][size];
{ int k=0;
{0 , 0 , 7 , 0 , 9 }, // Computing final matrix
{0 , 0 , 5 , 7 , 0 }, for(int i=0; i<4; i++)
{0 , 0 , 0 , 0 , 0 }, {
{0 , 2 , 3 , 0 , 0 } for(int j=0; j<5; j++)
}; {
// size of matrix if(sparse_matrix[i][j]!=0)
int size = 0; {
for(int i=0; i<4; i++) matrix[0][k] = i;
{ matrix[1][k] = j;
for(int j=0; j<5; j++) matrix[2][k] = sparse_matrix[i][j];
{ k++;
if(sparse_matrix[i][j]!=0) }
{ }
size++; }
}
}
} Department of IT 256
// Displaying the final matrix

for(int i=0 ;i<3; i++)
{
for(int j=0; j<size; j++)
{
printf("%d ", matrix[i][j]);
printf("\t");
}
printf("\n");
}
return 0;
}
Linked Representation of Sparse Matrix

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
Introduction to Stack
Stack
A stack is a data structure in which

items can be inserted only from one
end and get items back from the
same end.
There , the last item inserted into

stack, is the the first item to be
taken out from the stack. In short
its also called Last in First out
[LIFO].
Example of Stack (LIFO)
● A Stack of book on table.
● Token stack in Bank.
● Stack of trays and plates.
Stack Operations
Top: Open end of the stack is called Top, From this end item can
be inserted.
Push: To insert an item from Top of stack is called push operation.

The push operation change the position of Top in stack.
POP: To put-off, get or remove some item from top of the stack is
the pop operation, We can POP only only from top of the stack.
Stack Operations
IsEmpty: Stack considered empty when there is no item on Top.

IsEmpty operation return true when no item in stack else false.
IsFull: Stack considered full if no other element can be inserted on

top of the stack. This condition normally occur when stack is
implemented through array.
Stack Abstract Data Type
ADT Stack {
Data/Attributes/Values:
int size; Top Type items;
Functions/Operations:
CreateStack (int size); --create stack of size Void
Push(int n); - - if stack is not full
Type Pop(); - - if stack is not empty return top item
Int isEmpty(); - - return true if empty otherwise false
Int isFull(); - - return true if full otherwise false }
Stack Example
Implementation of Stack
•Using Array
•Using Link List
Stack Implementation using Array ...
Stack Implementation using Array using array
A stack can be implemented using array as follows...
Before implementing actual operations, first follow the below steps to

create an empty stack.
Step 1 - Include all the header files which are used in the program
and define a constant 'SIZE' with specific value.
Step 2 - Declare all the functions used in stack implementation.
Step 3 - Create a one dimensional array with fixed size (int
stack[SIZE])
Step 4 - Define a integer variable 'top' and initialize with '-1'. (int top
= -1)
Step 5 - In main method, display menu with list of operations and
make suitable function calls to perform operation selected by the
user on the stack. Department of IT 269
push(value) - Inserting value into the stack using array
In a stack, push() is a function used to insert an element into the
stack. In a stack, the new element is always inserted
at top position. Push function takes one integer value as
parameter and inserts that value into the stack. We can use the
following steps to push an element on to the stack...
Step 1 - Check whether stack is FULL. (top == SIZE-1)


Step 2 - If it is FULL, then display "Stack is FULL!!! Insertion is


not possible!!!" and terminate the function.
Step 3 - If it is NOT FULL, then increment top value by one (top+


+) and set stack[top] to value (stack[top] = value).

pop() - Delete a value from the Stack using array

In a stack, pop() is a function used to delete an element from the
stack. In a stack, the element is always deleted from top position.
Pop function does not take any value as parameter. We can use
the following steps to pop an element from the stack...
Step 1 - Check whether stack is EMPTY. (top == -1)



Step 2 - If it is EMPTY, then display "Stack is EMPTY!!! Deletion
is not possible!!!" and terminate the function.
Step 3 - If it is NOT EMPTY, then delete stack[top] and


decrement top value by one (top--).
display() - Displays the elements of a Stack using

array
We can use the following steps to display the elements of a stack...
Step 1 - Check whether stack is EMPTY. (top == -1)



Step 2 - If it is EMPTY, then display "Stack is EMPTY!!!" and
terminate the function.
Step 3 - If it is NOT EMPTY, then define a variable 'i' and initialize


with top. Display stack[i] value and decrement i value by one (i--).
Step 3 - Repeat above step until


i value becomes '0'.
Stack Implementation using Link List
The major problem with the stack implemented using an array is, it
works only for a fixed number of data values.
Stack implemented using an array is not suitable, when we don't

know the size of data which we are going to use.
Stack implemented using linked list works for the variable size of
data.
So, there is no need to fix the size at the beginning of the

implementation.
In linked list implementation of a stack, every new element is inserted as 'top' element.
That means every newly inserted element is pointed by 'top’.
Whenever we want to remove an element from the stack, simply remove the node which
is pointed by 'top' by moving 'top' to its previous node in the list. The next field of the
first element must be always NULL.
To implement a stack using a linked list, we need to set the following

things before implementing actual operations.
Step 1 - Include all the header files which are used in the program.

And declare all the user defined functions.
Step 2 - Define a 'Node' structure with two members data and next.

Step 3 - Define a Node pointer 'top' and set it to NULL.


Step 4 - Implement the main method by displaying Menu with list of


operations and make suitable function calls in the main method.
push(value) - Inserting an element into the

Stack using Link List
We can use the following steps to insert a new node into the
stack...

Step 1 - Create a newNode with given value.
Step 2 - Check whether stack is Empty (top == NULL)



Step 3 - If it is Empty, then set newNode → next = NULL

.

Step 4 - If it is Not Empty, then set newNode → next = top.
Step 5 - Finally, set top = newNode.


pop() - Deleting an Element from a Stack using
Link List
We can use the following steps to delete a node from the stack...
Step 1 - Check whether stack is Empty (top == NULL).


Step 2 - If it is Empty, then display "Stack is Empty!!! Deletion is


not possible!!!" and terminate the function


Step 3 - If it is Not Empty, then define a Node pointer 'temp' and set
it to 'top’.
Step 4 - Then set 'top = top → next’.


Step 5 - Finally, delete 'temp'. (free(temp)).


Department of277
IT
display() - Displaying stack of elements using
Link List
We can use the following steps to display the elements (nodes) of a
stack...

Step 1 - Check whether stack is Empty (top == NULL).

Step 2 - If it is Empty, then display 'Stack is Empty!!!' and
terminate the function.

Step 3 - If it is Not Empty, then define a Node pointer 'temp' and
initialize with top.

Step 4 - Display 'temp → data --->' and move it to the next node.
Repeat the same until temp reaches to the first node in the stack.
(temp → next != NULL).
Step 5 - Finally! Display 'temp → data ---> NULL'.


Stack Application
Reversing a string: To reverse a string we can use following
algorithm.
1.Given the sting and a stack
2.While there is not end of string, do the following.
3.Read a character form the string
4.Push it on the stack
5.End while
6.Re-initialize string position
7.While stack is not Empty, do the following.
8.Pop a character from the stack
9.Insert the character popped into next position in string.
10.End While
Department of IT
Reverse String...
String is a b c d e f PUSH to SACK

Reverse String...
Reversed String: f e d c b a POP from SACK

What is an Expression?
In any programming language, if we want to perform any calculation or to frame
a condition etc., we use a set of symbols to perform the task. These set of symbols
makes an expression.
An expression can be defined as follows...
An expression is a collection of operators and operands that represents a

specific value.
In above definition, operator is a symbol which performs a particular task like

arithmetic operation or logical operation or conditional operation etc.,
Operands are the values on which the operators can perform the task. Here
operand can be a direct value or variable or address of memory location
Expression Types
Based on the operator position, expressions are divided into THREE
types. They are as follows...
1.Infix Expression
2.Postfix Expression
3.Prefix Expression
Infix, Postfix and Prefix Expression

Infix Expression: An expression in which the
operator is in between its two operands.
A+B
Prefix Expression: An expression in which operator precedes its
two operands is called an prefix expression.
+AB
Postfix Expression: An expression in
operator follows its two operands is called a postfix expression.
which
AB+
Infix to Postfix Conversion
Infix expression can be directly evaluated but the standard

practice in CS is that the infix expression converted to postfix
form and then the expression is evaluated.
During both processes stack is proved to be a useful data

structure.
C language operators Precedence and Associativity
Infix to Postfix By-Hand Algorithm

1. Given a expression in the infix form.
2. Find the highest precedence operator
3. If there are more then one operators with the same precedence
check associativity, i.e. pick the left most first.
4. Convert the operator and its operands from infix to postfix
(A + B)  A B+
1. Repeat steps 2 to 4, until all the operators in the given expression
are in the postfix form.
Q1. Convert the given infix expression 2*3/(2-1)+5*(4-1) to postfix
expression
Sol.
1.Enclosed in brackets, based on precedence and associativity
a. 2*3/(2-1)+5*(4-1)
b. (2*3)/(2-1)+5*(4-1)
c. ((2*3)/(2-1))+(5*(4-1))
d. ((2*3)/(2-1))+(5*(4-1))
e. ((2*3)/(2-1))+(5*(4-1))
f. (((2*3)/(2-1))+(5*(4-1)))
2. Convert each bracket in postfix expression one by one
a. (((2*3)/(2-1))+(5*(4-1)))
b. (((23*)/(2-1))+(5*(4-1)))
c. (((23*)/(21-))+(5*(4-1)))
d. (((23*)/(21-))+(5*(41-)))
e. (((23*)(21-)/)+(5*(41-)))
f. (((23*)(21-)/)+(5(41-)*))
f. (((23*)(21-)/)(5(41-)*)+)
Ans. 23*21-/541-*+
H.W
1. A+B*C-D^E^F
Infix to Prefix By-Hand Algorithm
1. Given a expression in the infix form.

2. Find the highest precedence operator
3. If there are more then one operators with the same
precedence check associativity, i.e. pick the left most first.
4. Convert the operator and its operands from infix to prefix A
+B --> +A B
5. Repeat steps 2 to 4, until all the operators in the given
expression are in the postfix form.
291 Introduction to Stack
Infix to Prefix Step by Step Conversion
Q1. A*B+C/D (Infix) Q2. A*(B+C/D)

((A*B)+(C/D)) (A*(B+(C/D)) )
*AB+C/D A*(B+/CD)
*AB+/CD A*(+B/CD)
+*AB/CD (Prefix) *A+B/CD
Exercise:
1. Infix ( (A * B) + (C / D) ) to Prefix
2.Infix ((A * (B + C) ) / D) to Prefix
3.Infix (A * (B + (C / D) ) ) to Prefix
Department of IT
Infix to Postfix using Stack (Convert in Reverse Polish Notation)
1. Examine the given Input Sequence.
2. If it is operand output it.
3. If it is ‘(‘ push it on the stack.
4. If it is an operator and
a) If the stack is empty push it on the stack.
b) If the top of the stack is ‘(‘ then push it on to the stack.
c) If it has higher priority than top of the stack, push it on to the
stack.
d) Otherwise pop operator from the stack and output it. And go
to step 4.
5. If it is ‘)’ then pop of the operators from the stack and output
them until ‘(‘ is encountered.
6. If there are more input sequence then go to step 1.
7. If there are no more input sequence, pop of remaining
elements from the stack and output them.
Infix to Postfix using stack

●
Example A*B+C become AB*C+
Infix to Postfix using stack ...

Example A * (B + C * D) + E becomes A B C D * + * E
+
Infix to Prefix using Stack (Convert in Polish Notation)
1.First, reverse the given infix expression.
2.Scan the characters one by one.
3.If the character is an operand, print it .
4.If the character is a closing parenthesis, then push it to the stack.
5.If the character is an opening parenthesis, pop the elements in the
stack until we find the corresponding closing parenthesis.
6.If the character scanned is an operator
•If the operator has precedence greater than or equal to the top of the
stack, push the operator to the stack.
•If the operator has precedence lesser than the top of the stack, pop the
operator and output it to the prefix notation output and then check the
above condition again with the new top of the stack.
7. After all the characters are scanned, reverse the prefix notation
output
Infix to Prefix using Stack..

Step 1: Reverse the infix expression i.e A+B*C will become C*B+A.
Note while reversing each ‘(‘ will become ‘)’ and each ‘)’ becomes
‘(‘.
Step 2: Obtain the postfix expression of the modified expression i.e

CB*A+.
Step 3: Reverse the postfix expression. Hence in our example prefix is

+A*BC.
Algorithm for Prefix
•Step 1: Reverse the infix string. Note that while reversing the string
you must interchange left and right parentheses.
•Step 2: Obtain the postfix expression of the infix expression Step 1.
•Step 3: Reverse the postfix expression to get the prefix expression
This is how you convert manually for theory question in the exam
Input String - Infix – ((a/b)+c)-(d+(e*f))
1.String after reversal – ))f*e(+d(-)c+)b/a((
2.String after interchanging right and left parenthesis – ((f*e)+d)-
(c+(b/a))
3.Apply postfix
4.Reverse Postfix Expression (Given After the table below)
Infix – ((a/b)+c)-(d+(e*f))  ))f*e(+d(-)c+)b/a((  ((f*e)+d)-(c+(b/a))
Sr. no. Expression Stack Prefix

0 ( (
1 ( ((
2 f (( f
3 * ((* f
4 e ((* fe
5 ) ( fe*
6 + (+ fe*
7 d (+ fe*d
8 ) fe*d+
9 – - fe*d+
10 ( -( fe*d+
11 c -( fe*d+c
12 + -(+ fe*d+c
13 ( -(+( fe*d+c
14 b -(+( fe*d+cb
15 / -(+(/ fe*d+cb
16 a -(+(/ fe*d+cba
17 ) -(+ fe*d+cba/
18 ) - fe*d+cba/+
19 fe*d+cba/+-
Department of IT -+/abc+d*ef 298

Infix – A*(B+D)/E-F*(G+H/K) --- > )K/H+G(*F-E/)D+B(*A -- > (K/H+G)*F-E/(D+B)*A
Sr. no. Expression Stack Prefix

1 ( (
2 K ( K
3 / (/ K
4 H (/ KH
5 + (+ KH/
6 G (+ KH/G
7 ) KH/G+
8 * * KH/G+
9 F * KH/G+F
10 - - KH/G+F*
11 E - KH/G+F*E
12 / -/ KH/G+F*E
13 ( -/( KH/G+F*E
14 D -/( KH/G+F*ED
15 + -/(+ KH/G+F*ED
16 B -/(+ KH/G+F*EDB
17 ) -/ KH/G+F*EDB+
18 * -/* KH/G+F*EDB+
19 A -/* KH/G+F*EDB+A
20 - KH/G+F*EDB+A*/-
Evaluating Arithmetic Postfix Expression
1) Create a stack to store operands (or values).

2) Scan the given expression and do following for every
scanned element.
…..a) If the element is a number, push it into the stack
…..b) If the element is a operator, pop two operands for the
operator from stack. Evaluate the operator and push the result
back to the stack
3) When the expression is ended, the number in the stack is the
final answer
Evaluating Arithmetic Postfix Expression

PostFix Expression 2 3 4 + * 5 *
Move Token Stack
1 2 2
2 3 23
3 4 234
4 + 27
(3+4=7)
5 * 14 (2*7=14)
6 5 14 5
7 * 70
(14*5=70)
Tower of Hanoi Problem
Tower of Hanoi is a mathematical puzzle where we have three rods

and n disks.
Department of IT 30
2
Tower of Hanoi Problem
The objective of the puzzle is to move the entire stack to another rod,
obeying the following simple rules:
1)Only one disk can be moved at a time.
2) Each move consists of taking the upper disk from one of the stacks
and placing it on top of another stack i.e. a disk can only be moved if it
is the uppermost disk on a stack.
3) No disk may be placed on top of a smaller disk.
Department of IT 30
3
Tower of Hanoi Problem Illustration
Department of IT 30
4
Tower of Hanoi Algorithm Concept
Department of IT 30
5
A recursive algorithm for Tower of Hanoi can be driven as follows
void towerOfHanoi(int n, char source, char aux, char dest)

{
if (n == 1)
{
printf("\n Move disk 1 from rod %c to rod %c", source, dest);
return;
}
towerOfHanoi(n-1, source, dest, aux);
printf("\n Move disk %d from rod %c to rod %c", n, source, dest);
towerOfHanoi(n-1, aux, source, dest);
}
Department of IT 30
6
Queue
Queue
• Queue is Linear Data Structure

• It follows First In First Out(FIFO) principal
• It has two pointers front and rear e.g.:
Front Rear
Queue
Implementation of Queue
1. Using Array
2. Using Link List
Application of Queue
Queues are used in a lot of applications, few of them are:
•Queue is used to implement many algorithms like Breadth First Search (BFS), etc.
•It can be also used by an operating system when it has to schedule jobs with equal priority
•Customers calling a call center are kept in queues when they wait for someone to pick up the
calls
Queue
Insertion in Queue using Array
A[0] A[1] A[2] A[3] A[4]

F=R=(-1)
10
A[0] A[1] A[2] A[3] A[4]
F=R=0
10 20
A[0] A[1] A[2] A[3] A[4]
F=0 R=1
Queue
Queue
Operations on Queue
Insertion:
Algorithm:
Step 1: If REAR = MAX – 1 then

Write “Queue is Overflow”
Goto step 4
[End of IF]
Step 2: IF FRONT=-1 and REAR=-1
SET FRONT=REAR=0
ELSE
SET REAR=REAR+1 [END OF IF]
Step 3: SET QUEUE [REAR] = NUM
Step 4: EXIT
Queue
Example of Deletion in Queue
10 20
A[0] A[1] A[2] A[3] A[4]
F=0 R=1
20
A[0] A[1] A[2] A[3] A[4]
F=R=1
Queue
Example of Deletion in Queue
10 20
A[0] A[1] A[2] A[3] A[4]
F=0 R=1
20
A[0] A[1] A[2] A[3] A[4]
F=R=1
Queue
Operations on Queue
Deletion:
Algorithm:
Step 1: IF FRONT = -1 OR FRONT>REAR

Write “Queue is Underflow”
ELSE
SET VAL=QUEUE [FRONT]
FRONT = FRONT + 1 [END OF IF]
Step 2: EXIT
Queue
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.
•Static Array Size
•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.
Queue using Linked List
Queue Operation (Insertion)
 Insertion Operation
 Step 1: Allocate the space for the new node PTR
 Step 2: SET PTR -> DATA = VAL
 Step 3: IF FRONT = NULL
SET FRONT = REAR = PTR
SET FRONT -> NEXT = REAR -> NEXT = NULL
ELSE
SET REAR -> NEXT = PTR
SET REAR = PTR
SET REAR -> NEXT = NULL
[END OF IF]
 Step 4: END
C Function
void insert(struct node *ptr, int item; ) {
ptr = (struct node *) malloc (sizeof(struct node));

if(ptr == NULL) {
printf("\nOVERFLOW\n");
return; }
else
{
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;
}
}
Deletion
 Deletion Algorithm
 Algorithm
 Step 1: IF FRONT = NULL
Write " Underflow "
Go to Step 5
[END OF IF]
 Step 2: SET PTR = FRONT
 Step 3: SET FRONT = FRONT -> NEXT
 Step 4: FREE PTR
 Step 5: END
C Function
void delete (struct node *ptr)
{
if(front == NULL)
{
printf("\nUNDERFLOW\n");
return;
}
else
{
ptr = front;
front = front -> next;
free(ptr);
}
}
Queue
Types Of Queue
1. Circular Queue
2. Priority Queue
3. Deque
4. Multiple Queue
Queue
Why Circular Queue is needed?
• Problem:
– Wastage of memory in standard queue in DEQUEUE
operation
Queue
What is Circular Queue?
• The Arrangement of the elements Q[0], Q[1], ..,Q[n] in a circular

fashion with Q[1] following Q[n] is called Circular Queue.
• The last node is connected to first

node to make a circle.
• Initially, Both Front and Rear pointerspoints to the

beginning of the array.
• It is also known as “Ring Buffer”.

Queue
Queue
Insertion in circular queue
Step 1 - Check whether Circular queue is FULL. Front ==
(Rear+1)%Max
Step 2 - If it is FULL, then display "Queue is FULL!!!

Insertion is not possible!!!" and terminate the function.
Step 3 - If it is NOT FULL, then check Front == -1,

then Front =0.
Step 4 - Rear = (Rear+1)%max,

set Cqueue[Rear] = value.
Queue
Deletion in circular queue
Step 1 - Check whether queue is EMPTY. (front == -1)
Step 2 - If it is EMPTY, then display “Circular Queue is

EMPTY!!! Deletion is not possible!!!" and terminate the
function.
Step 3 - Val = Cqueue[front];

Step 4 – if(front==rear)
front = rear = -1;
Step 5 – front = (front+1)%Max;
Step 6 – return Val
Queue
Application of Circular Queue
Traffic light functioning is the best example for circular queues. The colors
in the traffic light follow a circular pattern.
In page replacement algorithms, a circular list of pages is maintained and

when a page needs to be replaced, the page in the front of the queue will be
chosen.
Queue
display() - Displays the elements of a Circular Queue
We can use the following steps to display the elements of a circular queue...
Step 1 - Check whether queue is EMPTY. (front == -1)

Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the
function.
Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i =
front'.
Step 4 – for(i = front; i!=rear; i = (i+1)%Max)
Print Cqueue[i];
end
print(queue[rear]);
Step 5 - Exit
Queue
Deque / Double Ended Queue
• A list in which elements can be inserted or deleted either

end
• It is also known as “Head-Tail Linked List”
• It has two pointers LEFT and RIGHT, which point to either

end of the deque.
• Dequeue can be implemented using Circular Array or a

Circular doubly linked list where Dequeue[n-1] is followed
by Dequeue[0]
Queue
Types of Deque
• Input Restricted Deque:-

In this dequeue, insertion can be done only at one of the end,
while deletion can be done from both ends.
• Output Restricted Deque:-

In this dequeue, deletion can be done only at one of the ends,
while insertions can be done on both ends
Queue
Input Restricted Deque
Queue
Output Restricted Deque
Operations on Deque
The following are the operations applied on deque:
• Insert at front
• Delete from end
• insert at rear
• delete from rear
Other than insertion and deletion, we can also perform peek operation in deque.
Through peek operation, we can get the front and the rear element of the
dequeue.
The deque can be implemented using two data structures, i.e., circular array,
and doubly linked list.
Deque Using Circular Array
Insert At Right
void insert_right()
{
int added_item;
if((left == 0 && right == MAX-1) || (left == right+1))
{ printf("Queue Overflow\n");
return;}
if (left == -1) /* if queue is initially empty */
{ left = 0;
right = 0;}
else
if(right == MAX-1) /*right is at last position of queue */
right = 0;
else
right = right+1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[right] = added_item ;
}
Insert At Left
void insert_left()
{
int added_item;
if((left == 0 && right == MAX-1) || (left == right+1))
{ printf("Queue Overflow \n");
return; }
if (left == -1)/*If queue is initially empty*/
{
left = 0;
right = 0; }
else
if(left== 0)
left=MAX-1;
else
left=left-1;
printf("Input the element for adding in queue : ");
scanf("%d", &added_item);
deque_arr[left] = added_item ;
Delete from Left
void delete_left()
{
if (left == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",deque_arr[left]);
if(left == right) /*Queue has only one element */
{ left = -1;
right=-1;
}
else
if(left == MAX-1)
left = 0;
else
left = left+1;
Delete from right
void delete_right()
{
if (left == -1)
{
printf("Queue Underflow\n");
return ;
}
printf("Element deleted from queue is : %d\n",deque_arr[right]);
if(left == right) /*queue has only one element*/
{ left = -1;
right=-1; }
else
if(right == 0)
right=MAX-1;
else
right=right-1;
}
Deque Using Doubly Link List
Deque Using Doubly Link List
 Operations
 insertFront() : Adds an item at the front of Deque.
 insertRear() : Adds an item at the rear of Deque.
 deleteFront() : Deletes an item from front of Deque.
 deleteRear() : Deletes an item from rear of Deque.
 getFront() : Gets the front item from queue.
 getRear() : Gets the last item from queue.
 isEmpty() : Checks whether Deque is empty or not.
 size() : Gets number of elements in Deque.
 erase() : Deletes all the elements from Deque.
Insertion at Front end
 Working :
Declare two pointers front and rear of type Node,
where Node represents the structure of a node of a doubly linked
list. Initialize both of them with value NULL.
Insertion at Front end :
1. Allocate space for a newNode of doubly linked list.
2. IF newNode == NULL, then
3. print "Overflow"
4. ELSE
5. IF front == NULL, then
6. rear = front = newNode
7. ELSE
8. newNode->next = front
9. front->prev = newNode
10. front = newNode Department of IT 341
Insertion at Rear end
1. Allocate space for a newNode of doubly linked list.
2. IF newNode == NULL, then
3. print "Overflow"
4. ELSE
5. IF rear == NULL, then
6. front = rear = newNode
7. ELSE
8. newNode->prev = rear
9. rear->next = newNode
10. rear = newNode
Deletion from Front end :
1. IF front == NULL
2. print "Underflow"
3. ELSE
4. Initialize temp = front
5. front = front->next
6. IF front == NULL
7. rear = NULL
8. ELSE
9. front->prev = NULL
10 Deallocate space for temp
Deletion from Rear end
1. IF front == NULL
2. print "Underflow"
3. ELSE
4. Initialize temp = rear
5. rear = rear->prev
6. IF rear == NULL
7. front = NULL
8. ELSE
9. rear->next = NULL
10 Deallocate space for temp
Queue
Application of Deque –
Deque is a Double Ended Queue where operations(Add/Remove) can
be made on both ends of the queue.
1.A web browser's history. Recently visited URLs are added to the
front of the deque, and the URL at the back of the deque is removed
after some specified number of insertions at the front.
2.Another common application of the deque is storing a software

application's list of undo operations.
3.Have you see moneyControl App, it will show the stocks you last
visited, it will remove the stocks after some time and will add the
latest ones.
Queue
Priority Queue
• In priority queue, each element is assigned a priority.

• Priority of an element determines the order in which the
elements will be processed.
• Rules:
1. An element with higher priority will processed before an
element with a lower priority.
2. Two elements with the same priority are processed on a
First Come First Serve basis.
Priority Queue
Consider an Example
We have a priority queue that contains the following values:
1, 3, 4, 8, 14, 22
All the values are arranged in ascending order of their priority. Now, we will
observe how the priority queue will look after performing the following
operations:
poll(): This function will remove the highest priority element from the priority
queue. In the above priority queue, the '1' element has the highest priority, so it
will be removed from the priority queue.
add(2): This function will insert '2' element in a priority queue. As 2 is the
smallest element among all the numbers so it will obtain the highest priority.
poll(): It will remove '2' element from the priority queue as it has the highest
priority queue.
add(5): It will insert 5 element after 4 as 5 is larger than 4 and lesser than 8, so it
will obtain the third highest priority in a priority queue.
Queue
Types of Priority Queue
1. Ascending Priority Queue

In this type of priority queue, elements can be inserted into any
order but only the smallest priority element can be removed.
2. Descending Priority Queue

In this type of priority queue, elements can be inserted into any
order but only the largest priority element can be removed.
Queue
Array Representation of Priority Queue
Insertion Operation:
•While inserting elements in priority queue we will add it at the
appropriate position depending on its priority
•It is inserted in such a way that the elements are always

ordered either in Ascending or descending sequence
Queue
Array Insertion of Priority Queue
DATA PRIORTY DATA PRIORTY

NUMBER NUMBER
A 5 B 1
B 1 E 2
D 3 D 3
E 2 A 5
F 8 G 6
G 6 F 8
Queue
Array Representation of Priority Queue
Deletion Operation:
•While deletion, the element at the front
is always deleted.
DATA PRIORTY
NUMBER
B 1
E 2
D 3
A 5
G 6
F 8
Queue
Application of Priority Queue
1. Prim's algorithm implementation can be done using priority queues.
2. Dijkstra's shortest path algorithm implementation can be done using priority

queues.
3. A* Search algorithm implementation can be done using priority queues.
4. Priority queues are used to sort heaps.
5. Priority queues are used in operating system for load balancing and interrupt
handling.
6. Priority queues are used in huffman codes for data compression.
7. In traffic light, depending upon the traffic, the colors will be given priority.
Queue
C Program to implement Queue
• https://drive.google.com/open?id=1z-mqjdEQ3FPjgr-Vyjn1k6MWZEjW
lRyi
Faculty Video Links, Youtube & NPTEL
Video Links and Online Courses Details
 Self Made Video Link:
 Youtube/other Video Links
https://www.youtube.com/watch?v=PGWZUgzDMYI&list=PLBF3763AF2E1
C572F&index=3
https://www.youtube.com/watch?v=zp6pBNbUB2U&list=PLdo5W4Nhv31bb
KJzrsKfMpo_grxuLl8LU&index=41
https://www.youtube.com/watch?v=UpvDOm3prfI
Daily Quiz
1. What is Stack and where it can be used?

2. What is a Queue, how it is different from stack and how is it
implemented?
3. What are Infix, prefix, Postfix notations?
4. How to implement a stack using queue?
5. How to implement a queue using stack?
6. What is recursion and when should you use it?
7. Write a function to copy string (Iterative and Recursive).
8. Check if a number is Palindrome using recursion
9. Reverse a stack using recursion.
10. Sort a stack using recursion.
Weekly Assignment
Q 1 What do you understand by stable and in place sorting?
Q 2 Consider the following infix expression and convert into reverse

polish notation using stack. A + (B * C – (D / E ^ F) * H)
Q3 Recursive function to delete k-th node from linked list.
Q4. Write the C Program to implement queue using stack.
Q5. The initial configuration of a queue is p,q,r,s (‘p’ is in the front end
). To get the configuration s,r,q,p, how many minimum dequeue and
enqueue are required?
MCQ s
1. Process of inserting an element in stack is called ____________

a) Create
b) Push
c) Evaluation
d) Pop
2. Process of removing an element from stack is called __________

a) Create
b) Push
c) Evaluation
d) Pop
MCQ s
3. In a stack, if a user tries to remove an element from empty stack it is
called _________
a) Underflow
b) Empty collection
c) Overflow
d) Garbage Collection
4. Pushing an element into stack already having five elements and stack
size of 5, then stack becomes
a) Overflow
b) Crash
c) Underflow
d) User flow
MCQ s
5. Which of the following applications may use a stack?
a) A parentheses balancing program
b) Tracking of local variables at run time
c) Compiler Syntax Analyzer
d) Data Transfer between two asynchronous process
6. 1. Recursion is a method in which the solution of a problem depends

on ____________
a) Larger instances of different problems
b) Larger instances of the same problem
c) Smaller instances of the same problem
d) Smaller instances of different problems
MCQ s
7. Recursion is similar to which of the following?

a) Switch Case
b) Loop
c) If-else
d) if elif else
8. A queue follows __________

a) FIFO (First In First Out) principle
b) LIFO (Last In First Out) principle
c) Ordered array
d) Linear tree
MCQ s
9. If the elements “A”, “B”, “C” and “D” are placed in a queue and are
deleted one at a time, in what order will they be removed?
a) ABCD
b) DCBA
c) DCAB
d) ABDC
10. A data structure in which elements can be inserted or deleted

at/from both the ends but not in the middle is?
a) Queue
b) Circular queue
c) Dequeue
d) Priority queue
Expected Questions for University Exam
Q1. Define priority queue.

Q2. Write a program in C for implementation of a queue. Your
program should at least contain ADD, CREATE. DELETE, FULL and
EMPTY functions.
Q3. If an array is defined as int a[10] [20] in C, devise a formula to
calculate the address of an any variable say a[i] [j], for any valid value
of i and j.
Q4. Write a program to implement STACK using linked list.
Q5. If the Tower of Hanoi is operated on n=10 disks, calculate the total
number of moves.
Q6. Differentiate between overflow and underflow condition in a
linked list.
Q7. Convert the following infix expression into postfix expression:
B-C/D+A*(F-G/H).
Q8.Write a program in C to compute the factorial of given number
recursively.
Q9.Write a Program in C to implement all operations of a Stack using array.
Q10.Define Dequeue.
Q11. Write the syntax to check whether a given circular queue is full or
empty?
Q12. What is Recursion? Give disadvantages of recursion.
Q13.Explain Tower of Hanoi problem and write a recursive algorithm to
solve it.
Q14. Explain how a circular queue can be implemented using arrays. Write
all functions for circular queue operations.
Daily Quiz
Q1. What is the output of following function for start pointing to first node of
following linked list? 1->2->3->4->5->6
void fun(struct node* start)
{
if(start == NULL)
return;
printf("%d ", start->data);
if(start->next != NULL )
fun(start->next->next);
printf("%d ", start->data);
}
Q2. What type of memory allocation is referred for Linked lists?

Daily Quiz
Q3. Describe what is Node in link list? And name the types of Linked Lists?
Q4. Mention what is the difference between Linear Array and Linked List?
Q5. Mention what are the applications of Linked Lists?
Q6. What does the dummy header in linked list contain?
Q7. Mention what is the difference between singly and doubly linked lists?
Q8. Mention what is the biggest advantage of linked lists?
Q9. Mention how to insert a new node in linked list where free node will be
available?
Weekly Assignment
Q1. Assume that the structure of a Linked List node is as follows:

struct node
{
int data;
struct node *next;
};
What does the following function print for a given Linked List which has elements in the
order 1->2->3->4->5->6. Explain your answer.
1. void fun(struct node* head){
2. if(head == NULL)
3. return;
4. printf("%d ", head->data);
5. if(head->next != NULL )
6. fun(head->next->next);
7. printf("%d ", head->data);
8. }
Weekly Assignment
Q2. Write a C Program to reverse the link list
Q3. Write a C Program to merge two link list.
Q4. Write a C Program to alternate print the content of the list.
Q5. Write a program for printing the following in a given linked list:
a. maximum b. minim
Q6. Print the sum of all even numbers stored in a circular linked list.
Q7. Take N numbers as input from the user and create a doubly linked list.
Q 8. Find the smallest number in the doubly linked list.
Q 9. Delete the smallest number in the doubly linked list.
Q 10. Write the C Program to add all even number in the list.
MCQ s
1. Assume that reference of head of following doubly linked list is passed to above
function 1 <--> 2 <--> 3 <--> 4 <--> 5 <-->6. What should be the modified linked list
after the function call?
void fun(struct node **head_ref)

{
struct node *temp = NULL;
struct node *current = *head_ref;
while (current != NULL)

{
temp = current->prev;
current->prev = current->next;
current->next = temp;
current = current->prev;
}
if(temp != NULL )
*head_ref = temp->prev;
}
MCQ s
2. The following function reverse() is supposed to reverse a singly linked list. There is one line missing at the end.
struct node
{
int data;
struct node* next;
};
/* head_ref is a double pointer which points to head (or start) pointer of linked list */
static void reverse(struct node** head_ref)
{
struct node* prev = NULL;
struct node* current = *head_ref;
struct node* next;
while (current != NULL)
{
next = current->next;
current->next = prev;
prev = current;
current = next;
}
/*ADD A STATEMENT HERE*/
}
What should be added in place of "/*ADD A STATEMENT HERE*/", so that the function correctly reverses a
linked list.
MCQ s
3. The following C function takes a simply-linked list as input argument. It modifies the list by
moving the last element to the front of the list and returns the modified list. Some part of the code is
left blank. Choose the correct alternative to replace the blank line.
typedef struct node
{
int value;
struct node *next;
}Node;
Node *move_to_front(Node *head)

{
Node *p, *q;
if ((head == NULL: || (head->next == NULL))
return head;
q = NULL; p = head;
while (p-> next !=NULL)
{
q = p;
p = p->next;
}
_______________________________
return head;
}
MCQ s
4. In the worst case, the number of comparisons needed to search a singly linked
list of length n for a given element is (GATE CS 2002)
A log 2 n
B n/2
C log 2 n – 1
Dn
5. You are given pointers to first and last nodes of a singly linked list, which of
the following operations are dependent on the length of the linked list?
A Delete the first element
B Insert a new element as a first element
C Delete the last element of the list
D Add a new element at the end of the list
MCQ s
6. Consider the following function to traverse a linked list.

void traverse(struct Node *head) {
while (head->next != NULL)
{
printf("%d ", head->data);
head = head->next;
}
}
Which of the following is FALSE about above function?

A The function may crash when the linked list is empty
B The function doesn't print the last node when the linked list is not empty
C The function is implemented incorrectly because it changes head
MCQ s
7. The concatenation of two lists is to be performed in O(1) time. Which of the

following implementations of a list should be used?
A singly linked list
B doubly linked list
C circular doubly linked list
D array implementation of lists
8. In a doubly linked list, the number of pointers affected for an insertion

operation will be
A4 B0 C1 D None of these
Q1. Write a program in c to delete a specific element in single linked list. Double linked
list takes more space than single linked list for storing one extra address. Under what
condition, could a double linked list more beneficial than single linked list.
Q2. What is a doubly linked list? How is it different from the single linked list?
Q3. What are the advantages and disadvantages of array over linked list?
Q4 . Write a program to implement linear linked list, showing all the operations that
can be performed on a linked list.
Q5. Implement Doubly Circular link list and insert an element at a given position in the
doubly circular link list.
References
1.Fundamentals of Data Structures in C by Horowitz, Sahni and

Anderson-Freed.
2.Data Structures Through C in Depth by S.K Srivastava, Deepali
Srivastava.
3.Data Structure using c by R Krishanamoorty.
4. Data Structures by Lipschutz, Schaum’s Outline Series, Tata McGraw-hill Education
(India) Pvt. Ltd.
5. Data Structure Using C by Reema Thareja, Oxford Higher Education.
6. Data Structure Using C by AK Sharma, Pearson Education India.
MCQ
Q1. program P reads in 500 integers in the range [0..100] exepresenting

the scores f 500 students. It then prints the frequency of each score above
50. What would be the best way for P to store the frequencies?
A.An array of 50 numbers

B.An array of 100 numbers
C.An array of 500 numbers
D.A dynamically allocated array of 550 numbers
Q2. Which of the following operations is not O(1) for an array of sorted
data. You may assume that array elements are distinct.
A. Find the ith largest element
B. Delete an element
C. Find the ith smallest element
D. All of the above
MCQ
Q3. Which of the following correctly declares an array?

A. int geeks[20]; B. int geeks;
C. geeks{20}; D. array geeks[20];
Q4. # include <stdio.h>

void print(int arr[])
{
int n = sizeof(arr)/sizeof(arr[0]);
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
}
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8};
print(arr);
return 0;
}
MCQ
Q5. Consider a two dimensional array A[20][10]. Assume 4 words per

memory cell, the base address of array A is 100, elements are stored in
row-major order and first element is A[5][0]. What is the address of A[11]
[5] ?
Q6. Output of following program?

#include<stdio.h>
int main()
{
int a[] = {1, 2, 3, 4, 5, 6};
int *ptr = (int*)(&a+1);
printf("%d ", *(ptr-1) );
return 0;
}
MCQ
Q7.Predict the output of the below program:
#include <stdio.h>
#define SIZE(arr) sizeof(arr) / sizeof(*arr);
void fun(int* arr, int n)
{
int i;
*arr += *(arr + n - 1) += 10;
}
void printArr(int* arr, int n)
{
int i;
for(i = 0; i < n; ++i)
}
int main()
{
int arr[] = {10, 20, 30};
int size = SIZE(arr);
fun(arr, size);
printArr(arr, size);
return 0; Department of IT 379
}
MCQ
Q8. Predict output of following program
int main()
{
int i;
int arr[5] = {1};
for (i = 0; i < 5; i++)
return 0;
}
MCQ
Q9. Consider the following C-function in which a[n] and b[m] are two sorted
integer arrays and c[n + m] be another integer array.
void xyz(int a[], int b [], int c[])
{
int i, j, k;
i = j = k = O;
while ((i<n) && (j<m))
if (a[i] < b[j]) c[k++] = a[i++];
else c[k++] = b[j++];
}
Which of the following condition(s) hold(s) after the termination of the while loop?
((i) j < m, k = n+j-1, and a[n-1] < b[j] if i = n

(ii) i < n, k = m+i-1, and b[m-1] <= a[i] if j = m
Summary
We consider two fundamental data types for storing collections of

objects: the stack and the queue.
We implement each using either a singly-linked list or a resizing

array.
We introduce two advanced Java features—generics and iterators

—that simplify client code.
Finally, we consider various applications of stacks and queues

ranging from parsing arithmetic expressions to simulating
queueing systems.
References
[1] Aaron M. Tenenbaum, Yedidyah Langsam and Moshe J.

Augenstein, “Data Structures Using C and C++”, PHI Learning
Private Limited, Delhi India
[2] Horowitz and Sahani, “Fundamentals of Data Structures”,
Galgotia Publications Pvt Ltd Delhi India.
[3] Lipschutz, “Data Structures” Schaum’s Outline Series, Tata
McGraw-hill Education (India) Pvt. Ltd.
[4] Thareja, “Data Structure Using C” Oxford Higher Education.
[5] AK Sharma, “Data Structure Using C”, Pearson Education
India.
Thank you

Data Structure and Algorithms

Uploaded by

Copyright:

Available Formats

Data Structure and Algorithms

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Data Structure and Algorithms

Uploaded by

Copyright:

Available Formats

DATA STRUCTURES

Department of Information Technology

3.Implement linked list data structure to solve various problems.

Course Program outcomes

Unit 1: Introduction: Basic Terminology, Elementary Data Organization, Algorithm,

1. Seymour Lipschutz, “Data Structures with C”, McGraw Hill Education

1.It must be able to represent the inherent relationship of data in the

2.It must be simple enough so that it can be processed efficiently as

Primitive Data Structures Non-Primitive Data Structures

Integer Real Character Boolean Linear Data Non -Linear

[0] [1] [2]

Linked lists are unbounded

Fig . (a) Undirected Graph

Fig. (b) Directed Graph

 In order to do that, we need to identify:

Input Algorithm Output

S(R): Space required at compile time (space for instructions,

S(C): Constant Space required

Execution time of an algorithm T(n)=Sum of total cost of all

Input: A sequence of n numbers [a1, a2, … , an].

An instance of the Sorting Problem:

Input: A sequence of 6 number [31, 41, 59, 26, 41, 58].

Expected output for given instance:

0  f(n)  cg(n) for n  n0”

g(n) is an asymptotic upper bound for f(n).

This makes g(n) as a lower bound

g(n) is an asymptotic lower bound for f(n).

g(n) is an asymptotically tight bound for f(n).

 Compared to the basic data type (int, float & char)

 All the elements of an array occupy a set of contiguous

int studMark0, studMark1, studMark2, ...,

 Here, array_data_type define the base type of the array,

 An array may be initialized at the time of declaration.

Example: char X[100];

1200 1201 1202 1203

X[0] X[1] X[2]

where w is length of memory location required.

Loc(X[8])= Loc(X[5]) + 4*(8 – 5)

(b) Using the formula: LOC(AAA[k]) = Base(AAA)+w(K-

Loc(A[I][J])=Base (BA)+W[N*(I-LBR) + (J-LBC)] {Row- Major}

1. Set ITEM: = LA [k].

[Move J + 1st element upward]

3. [Reset the number N of elements in LA] Set N: = N-1

2. Repeat Steps 3 and 4 while j >= k;

3. [Move jth element downward.] Set LA [J + 1]: =LA [J].

4. [Decrease counter] Set J: = J-1

[End of step 2 loop]

5. [Insert element] Set LA [K]:=ITEM.

6. [Reset N] Set N:=N+1

Analysis of Linear Search

Analysis of Linear Search

Binary Search Example

Binary Search Program

Time complexity of binary search

Input array elements: 10, 20, 30, 40, 50

Elements of array are: 10, 20, 30, 35, 40, 50

Logic to insert element in array

Insert an element at position 4.

Logic to insert element in array

for(i=size; i>=pos; i--)

Location(A[5,3,6])= 900 + 2[((5-1)5+(3-1))*7+(6-1)]