www.android.universityupdates.in | www.universityupdates.in | https://telegram.

me/jntua

Arrays

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Introduction
• An array is a collection of similar data elements.
• These data elements have the same data type.
• Elements of arrays are stored in consecutive memory locations and are
referenced by an index (also known as the subscript).
• Declaring an array means specifying three things:
Data type - what kind of values it can store. For example, int, char, float
Name - to identify the array
Size - the maximum number of values that the array can hold
• Arrays are declared using the following syntax:
type name[size];
1st 2nd 3rd 4th 5th 6th 7th 8th 9th 10th
element element element element element element element element element element
marks[0] marks[1] marks[2] marks[3] marks[4] marks[5] marks[6] marks[7] marks[8] marks[9]

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Accessing Elements of an Array

• To access all the elements of an array, we must use a loop.
• That is, we can access all the elements of an array by varying
the value of the subscript into the array.
• But note that the subscript must be an integral value or an
expression that evaluates to an integral value.

int i, marks[10];
for(i=0;i<10;i++)
marks[i] = -1;

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Calculating the Address of Array Elements

• Address of data element, A[k] = BA(A) + w( k – lower_bound)
where
A is the array
k is the index of the element whose address we have to calculate
BA is the base address of the array A
w is the word size of one element in memory. For example, size of
int is 2
99 67 78 56 88 90 34 85
marks[0] marks[1] marks[2] marks[3] marks[4] marks[5] marks[6] marks[7]
1000 1002 1004 1006 1008 1010 1012 1014

marks[4] = 1000 + 2(4 – 0)

= 1000 + 2(4) = 1008

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Storing Values in Arrays

Initialize the elements

Store values in the array Input values for the elements

Assign values to the elements

Initializing Arrays during declaration

int marks [5] = {90, 98, 78, 56, 23};

Inputting Values from Keyboard Assigning Values to Individual Elements

int i, marks[10]; int i, arr1[10], arr2[10];
for(i=0;i<10;i++) for(i=0;i<10;i++)
scanf(“%d”, &marks[i]); arr2[i] = arr1[i];

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Calculating the Length of an Array

Length = upper_bound – lower_bound + 1
where
upper_bound is the index of the last element
lower_bound is the index of the first element in the array

99 67 78 56 88 90 34 85
marks[0] marks[1] marks[2] marks[3] marks[4] marks[5] marks[6 marks[7]]

Here, lower_bound = 0, upper_bound = 7

Therefore, length = 7 – 0 + 1 = 8

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

OPERATIONS ON ARRAYS
Traversing an array
Inserting an element in an array
Searching an element in an array
Deleting an element from an array
Merging two arrays
Sorting an array in ascending or descending order

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm for array traversal

step 1: [initialization] set i = lower_bound

step 2: repeat steps 3 to 4 while i <= upper_bound
step 3: apply process to a[i]
step 4: set i = i + 1
[end of loop]
step 5: exit

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

WAP to Read and Display N Numbers using

an Array
#include<stdio.h> scanf(“%d”, &num[i]);
#include<conio.h> }
int main() printf(“\n The array elements are ”);
{ for(i=0;i<n;i++)
int i=0, n, arr[20]; printf(“arr[%d] = %d\t”, i, arr[i]);
clrscr(); return 0;
printf(“\n Enter the number of elements : ”); }
scanf(“%d”, &n);
printf(“\n Enter the elements : ”);
for(i=0;i<n;i++)
{
printf(“\n arr[%d] = ”, i);

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Inserting an Element in an Array

Algorithm to insert a new element to the end of an array
Step 1: Set upper_bound = upper_bound + 1
Step 2: Set A[upper_bound] = VAL
Step 3; EXIT

Algorithm INSERT( A, N, POS, VAL) to insert an element VAL at

position POS
Step 1: [INITIALIZATION] SET I = N
Step 2: Repeat Steps 3 and 4 while I >= POS
Step 3: SET A[I + 1] = A[I]
Step 4: SET I = I – 1
[End of Loop]
Step 5: SET N = N + 1
Step 6: SET A[POS] = VAL
Step 7: EXIT

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Deleting an Element from an Array

Algorithm to delete an element from the end of the array

Step 1: Set upper_bound = upper_bound - 1

Step 2: EXIT

Algorithm DELETE( A, N, POS) to delete an element at POS

Step 1: [INITIALIZATION] SET I = POS

Step 2: Repeat Steps 3 and 4 while I <= N-1
Step 3: SET A[I] = A[I + 1]
Step 4: SET I = I + 1
[End of Loop]
Step 5: SET N = N - 1
Step 6: EXIT
© Oxford University Press 2014. All rights reserved.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Passing Arrays to Functions

1D Arrays For Inter Function
Communication

Passing individual elements Passing entire array

Passing data values Passing addresses

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Passing Arrays to Functions

Passing data values
main() void func(int num)
{ {
int arr[5] ={1, 2, 3, 4, 5}; printf("%d", num);
func(arr[3]); }
}

Passing addresses
main() void func(int *num)
{ {
int arr[5] ={1, 2, 3, 4, 5}; printf("%d", *num);
func(&arr[3]); }
}

Passing the entire array

main() void func(int arr[5])
{ {
int arr[5] ={1, 2, 3, 4, 5}; int i;
func(arr); for(i=0;i<5;i++)
} printf("%d", arr[i]);
© Oxford University Press } 2014. All rights reserved.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Pointers and Arrays

•Concept of array is very much bound to the concept of pointer.
•Name of an array is actually a pointer that points to the first
element of the array.
int *ptr;
ptr = &arr[0];
•If pointer variable ptr holds the address of the first element in the
array, then the address of the successive elements can be calculated
by writing ptr++.
int *ptr = &arr[0];
ptr++;
printf (“The value of the second element in the array is %d”, *ptr);

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Arrays of Pointers
•An array of pointers can be declared as:
int *ptr[10];
•The above statement declares an array of 10 pointers where each
of the pointer points to an integer variable. For example, look at the
code given below.
int *ptr[10]; ptr[2]=&r;
int p=1, q=2, r=3, s=4, t=5; ptr[3]=&s;
ptr[0]=&p; ptr[4]=&t
Can you tell what will be the output of the following
ptr[1]=&q;
statement?
printf(“\n %d”, *ptr[3]);
© Oxford University Press 2014. All rights reserved.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Two-dimensional Arrays
A two-dimensional array is specified using two subscripts where one
subscript denotes row and the other denotes column.

C looks at a two-dimensional array as an array of one-dimensional

arrays.

A two-dimensional array is declared as:

First Dimension
data_type
array_name[row_size][column_size];

Second Dimension

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Two-dimensional Arrays
Therefore, a two dimensional m×n array is an array that contains m×n
data elements and each element is accessed using two subscripts, i
and j, where i<=m and j<=n

int marks[3][5];

Col 0 Col 1 Col2 Col 3 Col 4

Rows/Columns
Row 0 Marks[0][0] Marks[0][1] Marks[0][2] Marks[0][3] Marks[0][4]
Row 1 Marks[1][0] Marks[1][1] Marks[1][2] Marks[1][3] Marks[1][4]
Row 2 Marks[2][0] Marks[2][1] Marks[2][2] Marks[2][3] Marks[2][4]

Two Dimensional Array

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Memory Representation of a Array

• There are two ways of storing a 2-D array in memory. The first
way is row-major order and the second is column-major order.

• In the row-major order the elements of the first row are stored
before the elements of the second and third rows. That is, the
elements of the array are stored row by row where n elements of
the first row will occupy the first nth locations.

(0,0) (0, 1) (0,2) (0,3) (1,0) (1,1) (1,2) (1,3) (2,0) (2,1) (2,2) (2,3)

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Memory Representation of a Array

• However, when we store the elements in a column major order,
the elements of the first column are stored before the elements of
the second and third columns. That is, the elements of the array
are stored column by column where n elements of the first column
will occupy the first nth locations.

(0,0) (1,0) (2,0) (3,0) (0,1) (1,1) (2,1) (3,1) (0,2) (1,2) (2,2) (3,2)

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Passing 2D Arrays to Functions

2D Array for Inter Function
Communication

Passing individual elements Passing a row Passing the entire 2D

array

There are three ways of passing two-dimensional arrays to a

function.
First, we can pass individual elements of the array. This is exactly
same as we passed element of a one-dimensional array.

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Passing 2D Arrays to Functions

Passing a row
Calling function
main()
{
int arr[2][3]= ( {1, 2, 3}, {4, 5, 6} };
func(arr[1]);
}
Called function
void func(int arr[])
{
int i;
for(i=0;i<3;i++)
printf("%d", arr[i] * 10);
}

Passing the entire 2D array

To pass a two dimensional array to a function, we use the array
name as the actual parameter. (The same we did in case of a 1D
array.) However, the parameter in the called function must indicate
that the array has two dimensions.
© Oxford University Press 2014. All rights reserved.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Pointers and 2D Arrays

Individual elements of the array mat can be accessed using either:
mat[i][j] or *(*(mat + i) + j) or*(mat[i]+j);
Pointer to a one-dimensional array can be declared as:
int arr[]={1,2,3,4,5};
int *parr;
parr=arr;
Similarly, pointer to a two-dimensional array can be declared as:
int arr[2][2]={{1,2},{3,4}};
int (*parr)[2];
parr=arr;

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Initializing Multi-dimensional Arrays

A two and multi-dimensional array is initialized in the same was as

a single dimensional array is initialized. For example,

int marks[2][3]={90, 87, 78, 68, 62, 71};

int marks[2][3]={{90,87,78},{68, 62, 71}};

•A multi-dimensional array is declared and initialized the same

way as we declare and initialize one- and two-dimensional arrays.

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Multi-dimensional Arrays
• A multi-dimensional array is an array of arrays.
• Like we have one index in a single dimensional array, two indices in a
two-dimensional array, in the same way we have n indices in a n-
dimensional array or multi-dimensional array.
• Conversely, an n dimensional array is specified using n indices.
• An n dimensional m1 x m2 x m3 x ….. mn array is a collection of
m1×m2×m3× ….. ×mn elements.
• In a multi-dimensional array, a particular element is specified by using
n subscripts as A[I1][I2][I3]…[In], where
I1<=M1 I2<=M2 I3 <= M3 ……… In <= Mn

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Multi-dimensional Arrays

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Pointers and Three-dimensional Arrays

A pointer to a three-dimensional array can be declared as:
int arr[2][2][2]={1,2,3,4,5,6,7,8};
int (*parr)[2][2];
parr=arr;

We can access an element of a three-dimensional array by writing:

arr[i][j][k]= *(*(*(arr+i)+j)+k)

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Applications of Arrays
• Arrays are widely used to implement mathematical vectors,
matrices and other kinds of rectangular tables.
• Many databases include one-dimensional arrays whose
elements are records.
• Arrays are also used to implement other data structures like
heaps, hash tables, deques, queues, stacks and string. We will
read about these data structures in the subsequent chapters.
• Arrays can be used for dynamic memory allocation.

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

static memory allocation dynamic memory

allocation
memory is allocated at memory is allocated at
compile time. run time.
memory can't be memory can be increased
increased while while executing program.
executing program.
used in array. used in linked list.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

dynamic memory allocation.

malloc() allocates single block of
requested memory.
calloc() allocates multiple block of
requested memory.
realloc() reallocates the memory
occupied by malloc() or calloc()
functions.

free() frees the dynamically allocated

memory.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

malloc() function in C:
• The malloc() function allocates single block of requested
memory.
• It returns NULL if memory is not sufficient.
• The syntax of malloc() function is given below:

ptr=(cast-type*)malloc(byte-size)

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua
#include<stdio.h>
#include<stdlib.h>
int main(){
int n,i,*ptr,sum=0;
printf("Enter number of elements: ");
scanf("%d",&n);
ptr=(int*)malloc(n*sizeof(int)); //memory allocated using malloc
if(ptr==NULL)
{
printf("Sorry! unable to allocate memory");
exit(0);
}
prinftf("Enter elements of array: ");
for(i=0;i<n;++i)
{
scanf("%d",ptr+i);
sum+=*(ptr+i);
}
printf("Sum=%d",sum);
free(ptr);
return 0;
}
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

calloc() function in C:
• The calloc() function allocates multiple block of requested
memory.
• It initially initialize all bytes to zero.
• It returns NULL if memory is not sufficient.
• The syntax of calloc() function is given below:
ptr=(cast-type*)calloc(number, byte-size)

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua
#include<stdio.h>
#include<stdlib.h>
int main(){
int n,i,*ptr,sum=0;
printf("Enter number of elements: ");
scanf("%d",&n);
ptr=(int*)calloc(n,sizeof(int)); //memory allocated using calloc()
if(ptr==NULL)
{
printf("Sorry! unable to allocate memory");
exit(0);
}
printf("Enter elements of array: ");
for(i=0;i<n;++i)
{
scanf("%d",ptr+i);
sum+=*(ptr+i);
}
printf("Sum=%d",sum);
free(ptr);
return 0;
}
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

realloc() function in C:
• If memory is not sufficient for malloc() or
calloc(), you can reallocate the memory by
realloc() function. In short, it changes the memory
size.
• Let's see the syntax of realloc() function.
ptr=realloc(ptr, new-size)

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

• The memory occupied by malloc() or calloc() functions must be

released by calling free() function. Otherwise, it will consume
memory until program exit.
• Let's see the syntax of free() function.
free(ptr)

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

C Functions
In c, we can divide a large program into the basic
building blocks known as function.
The function contains the set of programming
statements enclosed by {}.
A function can be called multiple times to provide
reusability and modularity to the C program

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Advantage of functions in C
There are the following advantages of C functions.
o By using functions, we can avoid rewriting same logic/code
again and again in a program.
o We can call C functions any number of times in a program and
from any place in a program.
o We can track a large C program easily when it is divided into
multiple functions.
o Reusability is the main achievement of C functions.
o However, Function calling is always a overhead in a C program.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Function Aspects
o Function declaration A function must be declared globally in a c
program to tell the compiler about the function name, function
parameters, and return type.
o Function call Function can be called from anywhere in the
program. The parameter list must not differ in function calling
and function declaration. We must pass the same number of
functions as it is declared in the function declaration.

o Function definition It contains the actual statements which are

to be executed. It is the most important aspect to which the
control comes when the function is called. Here, we must notice
that only one value can be returned from the function.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

S.No C function Syntax
www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

aspects

1 Function return_type function_name (argument

declaration list);

2 Function call function_name (argument_list)

3 Function return_type function_name(argument

definition list)
{
function body;
}
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua
Types of Functions
There are two types of functions in C programming:

1.Library Functions: are the functions which are declared in the C

header files such as scanf(), printf(), gets(), puts(), ceil(), floor()
etc.

2.User-defined functions: are the functions which are created by

the C programmer, so that he/she can use it many times. It
reduces the complexity of a big program and optimizes the
code.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Return Value
A C function may or may not return a value from the function. If you don't have to return any
value from the function, use void for the return type.

Example without return value:

void hello()
{
printf("hello c");
}

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Example with return value:

int get() float get()

{ {
return 10; return 10.2;
} }

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

User-defined functions:
o function without arguments and without return
value
o function without arguments and with return value
o function with arguments and without return value
o function with arguments and with return value

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Example for Function without argument and without return value

#include<stdio.h>
#include<stdio.h> void sum();
void printName(); void main()
void main () {
{ printf("\ncalculating the sumof two numbers:");
printf("Hello "); sum();
printName(); }
void sum()
} {
void printName() int a,b;
{ printf("\nEnter two numbers");
printf("welcome"); scanf("%d %d",&a,&b);
} printf("The sum is %d",a+b);
}

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua
Example for Function without argument and with return value
#include<stdio.h>
int sum();
void main()
{
int result;
printf("\nGoing to calculate the sum of two numbers:");
result = sum();
printf("%d",result);
}
int sum()
{
int a,b;
printf("\nEnter two numbers");
scanf("%d %d",&a,&b);
return a+b;
}
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Example for Function with argument and without return value

#include<stdio.h>
void sum(int, int);
void main()
{
int a,b,result;
printf("\nGoing to calculate the sum of t
wo numbers:");
printf("\nEnter two numbers:");
scanf("%d %d",&a,&b);
sum(a,b);
}
void sum(int a, int b)
{
printf("\nThe sum is %d",a+b);
}
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Example for Function with argument and with return value

#include<stdio.h>
int sum(int, int);
void main()
{
int a,b,result;
printf("\nGoing to calculate the sum of t
wo numbers:");
printf("\nEnter two numbers:");
scanf("%d %d",&a,&b);
result = sum(a,b);
printf("\nThe sum is : %d",result);
}
int sum(int a, int b)
{
return a+b;
}
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Recursion in C
Recursion is the process which comes into existence when a function calls a
copy of itself to work on a smaller problem. Any function which calls itself is
called recursive function, and such function calls are called recursive calls.
Recursion involves several numbers of recursive calls. However, it is important
to impose a termination condition of recursion. Recursion code is shorter than
iterative code however it is difficult to understand.

For Example, recursion may be applied to sorting,

searching, and traversal problems.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

#include <stdio.h> www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

int fact (int);

int main()
{
int n,f;
printf("Enter the number whose factorial you want to calculate?");
scanf("%d",&n);
f = fact(n);
printf("factorial = %d",f);
}
int fact(int n)
{
if (n==0)
{
return 0;
}
else if ( n == 1)
{
return 1;
}
else
{
return n*fact(n-1);
} }
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
#include<stdio.h>
www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

int fibonacci(int);
void main ()
{
int n,f;
printf("Enter the value of n?");
scanf("%d",&n);
f = fibonacci(n);
printf("%d",f);
}
int fibonacci (int n)
{
if (n==0)
{
return 0;
}
else if (n == 1)
{
return 1;
}
else
{ return fibonacci(n-1)+fibonacci(n-2);
}
}
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Call by value and Call by reference in C

There are two methods to pass the data into the function in
C language, i.e., call by value and call by reference.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Call by value in C
o In call by value method, the value of the actual parameters is copied
into the formal parameters.
o In call by value method, we can not modify the value of the actual
parameter by the formal parameter.
o In call by value, different memory is allocated for actual and formal
parameters since the value of the actual parameter is copied into the
formal parameter.
o The actual parameter is the argument which is used in the function
call whereas formal parameter is the argument which is used in the
function definition.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

#include<stdio.h>
void change(int num) {
printf("Before adding value inside functio
n num=%d \n",num);
num=num+100;
printf("After adding value inside function
num=%d \n", num);
}
int main() {
int x=100;
printf("Before function call x=%d \n", x);

change(x);//passing value in function

printf("After function call x=%d \n", x);
return 0;
}

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

#include <stdio.h>
void swap(int *, int *); //prototype of the function
int main()
{
int a = 10;
int b = 20;
printf("Before swapping the values in main a = %d, b = %d\n",a,b); // printing the value of a and b in main

swap(&a,&b);
printf("After swapping values in main a = %d, b = %d\n",a,b); /*The values of actual parameters do change
in call by reference, a = 10, b = 20 */
}
void swap (int *a, int *b)
{
int temp;
temp = *a;
*a=*b;
*b=temp;
printf("After swapping values in function a = %d, b = %d\n",*a,*b); // Formal parameters, a = 20, b = 10
}

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

No. Call by value Call by reference

1 A copy of the value is An address of value is passed into

passed into the function the function

2 Changes made inside the Changes made inside the function

function is limited to the validate outside of the function
function only. The values of also. The values of the actual
the actual parameters do parameters do change by changing
not change by changing the the formal parameters.
formal parameters.
3 Actual and formal Actual and formal arguments are
arguments are created at created at the same memory
the different memory location
location
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

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

Declaring a pointer
The pointer in c language can be declared using * (asterisk symbol). It is also known as
indirection pointer used to dereference a pointer.

int *a; //pointer to int

char *c; //pointer to char

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

#include<stdio.h>
int main()
{
int number=50;
int *p;
p=&number;//stores the address of number variable
printf("Address of p variable is %x \n",p);
/* p contains the address of the number therefore printing p gives the address of number */
printf("Value of p variable is %d \n",*p);
/*As we know that * is used to dereference a pointer therefore if we print *p, we will get the val
ue stored at the address contained by p. */
return 0;
}

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Linked Lists

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

LINKED LISTS
• A linked list is a linear data structure, in which
the elements are not stored at contiguous
memory locations. The elements in a linked
list are linked using pointers as shown in the
below image:

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Types of Linked List

• Singly Linked List:

• Circular Linked List:
• Doubly Linked List:

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Singly Linked List:

• It is the simplest type of linked list in which every
node contains some data and a pointer to the next
node of the same data type. The node contains a
pointer to the next node means that the node stores
the address of the next node in the sequence. A
single linked list allows the traversal of data only in
one way. Below is the image for the same:

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Introduction to linked lists

• Like arrays, Linked List is a linear data
structure. Unlike arrays, linked list elements
are not stored at a contiguous location; the
elements are linked using pointers. They
includes a series of connected nodes. Here,
each node stores the data and the address of
the next node.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Why Linked List?

Arrays can be used to store linear data of similar types, but arrays
have the following limitations.
1.The size of the arrays is fixed
2.Insertion of a new element / Deletion of a existing element in
an array of elements is expensive
For example, in a system, if we maintain a sorted list of IDs in
an array id[].
id[] = [1000, 1010, 1050, 2000, 2040].
And if we want to insert a new ID 1005, then to maintain the sorted
order, we have to move all the elements after 1000 (excluding
1000).
Deletion is also expensive with arrays until unless some special
techniques are used. For example, to delete 1010 in id[], everything
after 1010 has to be moved due to this so much work is being done
which affects the efficiency of the code.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Representation
of LL
• A linked list is represented by a pointer to the first
node of the linked list. The first node is called the
head. If the linked list is empty, then the value of
the head points to NULL.
• Each node in a list consists of at least two parts:
• A Data Item (we can store integer, strings or any
type of data).
• Pointer (Or Reference) to the next node (connects
one node to another) or An address of another
node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm for traversing a linked list

Step 1: [Initialize] Set Ptr = Start

Step 2: Repeat Steps 3 And 4 While Ptr != Null
Step 3: Apply Process To Ptr -> Data
Step 4: Set Ptr = Ptr -> Next
[End Of Loop]
Step 5: Exit

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to print the number of nodes in a linked list

Step 1: [Initialize] Set Count =0

Step 2: [Initialize] Set Ptr = Start
Step 3: Repeat steps 4 And 5 While Ptr != Null
Step 4: Set Count = +1
Step 5: Set Ptr = Ptr -> Next
[End Of Loop]
Step 6: Write Count
Step 7: Exit

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to search a linked list

Step 1: [Initialize] Set Ptr = Start
Step 2: Repeat Step 3 While Ptr != Null
Step 3: If Val = Ptr ->Data
Set Pos = Ptr
Go To Step 5
Else
Set Ptr = Ptr -> Next
[End Of If]
[End Of Loop]
Step 4: Set Pos = Null
Step 5: Exit

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Inserting a New Node in a Linked List

Case 1: The new node is inserted at the beginning.
Case 2: The new node is inserted at the end.
Case 3: The new node is inserted after a given node.
Case 4: The new node is inserted before a given node.

Step 1: If Avail = Null

Write Overflow
Go To Step 7
[End Of If]
Step 2: Set New_node = Avail
Step 3: Set Avail = Avail -> Next
Step 4: Set New_node ->Data = Val
Step 5: Set New_node -> Next = Start
Step 6: Set Start = New_node
Step 7: Exit
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm new node is inserted at the end

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm new node is inserted after a given node.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm new node is inserted before a given node.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete the first node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete the last node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete the node after a given node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

CIRCULAR LINKED LISTS

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Circular linked list

A circular linked list is that in which the last node
contains the pointer to the first node of the list. While
traversing a circular linked list, we can begin at any node and
traverse the list in any direction forward and backward until
we reach the same node we started. Thus, a circular linked list
has no beginning and no end. Below is the image for the same:

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Inserting a New Node in a Circular Linked List

Case 1: The new node is inserted at the beginning of the circular linked list.
Case 2: The new node is inserted at the end of the circular linked list.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm new node is inserted at the end of the circular linked list

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete the first node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete the last node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

DOUBLY LINKED LISTS

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Doubly linked list

• A doubly linked list or a two-way linked list is a more complex
type of linked list which contains a pointer to the next as well
as the previous node in sequence, Therefore, it contains three
parts are data, a pointer to the next node, and a pointer to the
previous node. This would enable us to traverse the list in the
backward direction as well. Below is the image for the same:

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to insert a new node at the beginning

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to insert a new node at the end

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to insert a new node after the given node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to insert a new node before the given node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Deleting a Node from a Doubly Linked List

• Case 1: The first node is deleted.
• Case 2: The last node is deleted.
• Case 3: The node after a given node is deleted.
• Case 4: The node before a given node is deleted.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete the first node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete the last node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete a node after a given node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete a node before a given node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

CIRCULAR DOUBLY LINKED LISTS

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to insert a new node at the beginning

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to insert a new node at the end

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete the first node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to delete the last node

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

QUEUES

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Introduction
• Queue is an important data structure which stores its elements in
an ordered manner.
• We can explain the concept of queues using the following analogy:
People moving on an escalator. The people who got on the escalator
first will be the first one to step out of it.
• A queue is a FIFO (First-In, First-Out) data structure in which the
element that is inserted first is the first one to be taken out.
• The elements in a queue are added at one end called the rear and
removed from the other one end called the front.

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

INSERTING AN ELEMENT

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

DELETING A ELEMENT

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Array
Representation
of
Queues

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Array Representation of Queues

• Queues can be easily represented using linear arrays.
• Every queue has front and rear variables that point to the position
from where deletions and insertions can be done, respectively.
• Consider the queue shown in figure

12 9 7 18 14 36

0 1 2 3 4 5 6 7 8 9

• Here, front = 0 and rear = 5.

• If we want to add one more value in the list say with value 45, then
rear would be incremented by 1 and the value would be stored at
the position pointed by rear.

12 9 7 18 14 36 45

0 1 2 3 4 5 6 7 8 9

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Array Representation of Queues

• Now, front = 0 and rear = 6. Every time a new element has to be

added, we will repeat the same procedure.

• Now, if we want to delete an element from the queue, then the

value of front will be incremented. Deletions are done from only
this end of the queue.

9 7 18 14 36 45

0 1 2 3 4 5 6 7 8 9

• Now, front = 1 and rear = 6.

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Array Representation of Queues

• Before inserting an element in the queue we must check for
overflow conditions.
• An overflow occurs when we try to insert an element into a queue
that is already full, i.e. when rear = MAX – 1, where MAX specifies
the maximum number of elements that the queue can hold.
• Similarly, before deleting an element from the queue, we must
check for underflow condition.
• An underflow occurs when we try to delete an element from a
queue that is already empty. If front = -1 and rear = -1, this means
there is no element in the queue.

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm for Insertion Operation

Step 1: IF REAR=MAX-1, then;
Write OVERFLOW
Go to Step 4
[END OF IF]
Step 2: IF FRONT == -1 and REAR = -1, then
SET FRONT = REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = NUM
Step 4: Exit
© Oxford University Press 2014. All rights reserved.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm for Deletion Operation

Step 1: IF FRONT = -1 OR FRONT > REAR, then

Write UNDERFLOW
Goto Step 2
ELSE
SET VAL = QUEUE[FRONT]
SET FRONT = FRONT + 1

[END OF IF]
Step 2: Exit

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

LINKED LIST
Representation
of
Queues

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Linked Representation of Queues

• In a linked queue, every element has two parts: one that stores data
and the other that stores the address of the next element.
• The START pointer of the linked list is used as FRONT.
• We will also use another pointer called REAR which will store the
address of the last element in the queue.
• All insertions will be done at the rear end and all the deletions will
be done at the front end.
• If FRONT = REAR = NULL, then it indicates that the queue is empty.

1 7 3 4 2 6 5 X

FRONT REAR

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Inserting an Element in a Linked Queue

Step 1: Allocate memory for the new node and name it as PTR
Step 2: SET PTR->DATA = VAL
Step 3: IF FRONT = NULL, then
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

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Deleting an Element from a Linked Queue

Step 1: IF FRONT = NULL, then

Write “Underflow”
Go to Step 5
[END OF IF]
Step 2: SET PTR = FRONT
Step 3: FRONT = FRONT->NEXT
Step 4: FREE PTR
Step 5: END

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Circular Queues
7 18 14 36 45 21 99 72

0 1 2 3 4 5 6 7 8 9

• We will explain the concept of circular queues using an example.

• In this queue, front = 2 and rear = 9.
• Now, if you want to insert a new element, it cannot be done
because the space is available only at the left of the queue.
• If rear = MAX – 1, then OVERFLOW condition exists.
• This is the major drawback of a linear queue. Even if space is
available, no insertions can be done once rear is equal to MAX – 1.
• This leads to wastage of space. In order to overcome this problem,
we use circular queues.
• In a circular queue, the first index comes right after the last index.
• A circular queue is full, only when front=0 and rear = Max – 1.
© Oxford University Press 2014. All rights reserved.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Inserting an Element in a Circular Queue

• For insertion we check for three conditions which are as follows:

 If front=0 and rear= MAX – 1, then the circular queue is full.

90 49 7 18 14 36 45 21 99 72

front=0 1 2 3 4 5 6 7 8 rear = 9

 If rear != MAX – 1, then the rear will be incremented and value will
be inserted
90 49 7 18 14 36 45 21 99

front=0 1 2 3 4 5 6 7 rear= 8 9

• If front!=0 and rear=MAX -1, then it means that the queue is

not full. So, set rear = 0 and insert the new element.
49 7 18 14 36 45 21 99 72

front=1 2 3 4 5 6 7 8 rear= 9

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua
Algorithm to Insert an Element in a
Circular Queue
Step 1: IF FRONT = 0 and Rear = MAX – 1, then
Write “OVERFLOW”
Goto Step 4
[END OF IF]
Step 2: IF FRONT = -1 and REAR = -1, then;
SET FRONT = REAR = 0
ELSE IF REAR = MAX – 1 and FRONT != 0
SET REAR = 0
ELSE
SET REAR = REAR + 1
[END OF IF]
Step 3: SET QUEUE[REAR] = VAL
Step 4: Exit
© Oxford University Press 2014. All rights reserved.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Deleting an Element from a Circular Queue

• To delete an element again we will check for three conditions:
 If front = -1, then it means there are no elements in the queue. So
an underflow condition will be reported.

0 1 2 3 4 5 6 7 8 9

 If the queue is not empty and after returning the value on front, if
front = rear, then it means now the queue has become empty and
so front and rear are set to -1.
Delete this element and set
81
rear = front = -1

0 1 2 3 4 5 6 7 8 front=rear= 9

 If the queue is not empty and after returning the value on front, if
front = MAX -1, then front is set to 0.
72 63 9 18 27 39 81

0 1 2 3 4 rear= 5 6 7 8 front= 9

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Algorithm to Delete an Element from a Circular Queue

Step 1: IF FRONT = -1, then

Write “Underflow”
Goto Step 4
[END OF IF]
Step 2: SET VAL = QUEUE[FRONT]
Step 3: IF FRONT = REAR
SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = FRONT + 1
[END OF IF]
[END OF IF]
Step 4: EXIT
© Oxford University Press 2014. All rights reserved.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Deques
• A deque is a list in which elements can be inserted or deleted at
either end.
• It is also known as a head-tail linked list because elements can be
added to or removed from the front (head) or back (tail).
• A deque can be implemented either using a circular array or a
circular doubly linked list.
• In a deque, two pointers are maintained, LEFT and RIGHT which
point to either end of the deque.
• The elements in a deque stretch from LEFT end to the RIGHT and
since it is circular, Dequeue[N-1] is followed by Dequeue[0].

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Deques
• There are two variants of a double-ended queue:
 Input restricted deque: In this dequeue insertions can be done only
at one of the ends while deletions can be done from both the
ends.
 Output restricted deque: In this dequeue deletions can be done
only at one of the ends while insertions can be done on both the
ends.

29 37 45 54 63

0 1 2 LEFT = 3 4 5 6 RIGHT = 7 8 9

63 27 18
42

RIGHT = 0 1 2 3 4 5 6 LEFT = 7 8 9

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Priority Queues
• A priority queue is a queue in which each element is assigned a
priority.
• The priority of elements is used to determine the order in which
these elements will be processed.
• The general rule of processing elements of a priority queue can be
given as:
 An element with higher priority is processed before an element
with lower priority
 Two elements with same priority are processed on a first come
first served (FCFS) basis
• Priority queues are widely used in operating systems to execute the
highest priority process first.
• In computer’s memory priority queues can be represented using
arrays or linked lists.
© Oxford University Press 2014. All rights reserved.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Array Representation of Priority Queues

• When arrays are used to implement a priority queue, then a

separate queue for each priority number is maintained.
• Each of these queues will be implemented using circular arrays
or circular queues. Every individual queue will have its own
FRONT and REAR pointers.
• We can use a two-dimensional array for this purpose where
each queue will be allocated same amount of space.
• Given the front and rear values of each queue, a two
dimensional matrix can be formed.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua

 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Linked Representation of Priority Queues

• When a priority queue is implemented using a linked list, then
every node of the list contains three parts: (1) the information or
data part, (ii) the priority number of the element, (iii) and address
of the next element.
• If we are using a sorted linked list, then element having higher
priority will precede the element with lower priority.

A 1 B 2 C 3 D 3 E 4 X

Priority queue after insertion of a new node

A 1 B 2 C 3 F 4 D 5 E 6 X

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Multiple Queues
• When implementing a queue using an array, the size of the array
must be known in advance.
• If the queue is allocated less space, then frequent OVERFLOW
conditions will be encountered.
• To deal with this problem, the code will have to be modified to
reallocate more space for the array, but this results in sheer wastage
of memory. Thus, there lies a tradeoff between the frequency of
overflows and the space allocated.
• A better solution to deal with this problem is to have multiple
queues or to have more than one queue in the same array.
• One important point to note is that while queue A will grow from left
to right, the queue B on the same time will grow from right to left.
0 1 2 3 4 ………………………………. n-4 n-3 n-2 n-1

Queue A Queue B

© Oxford University Press 2014. All rights reserved.

www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua
 www.android.universityupdates.in | www.universityupdates.in | https://telegram.me/jntua

Applications of Queues
• Queues are widely used as waiting lists for a single shared resource
like printer, disk, CPU.
• Queues are used to transfer data asynchronously e.g., pipes, file IO,
sockets.
• Queues are used as buffers on MP3 players and portable CD players,
iPod playlist.
• Queues are used in Playlist for jukebox to add songs to the end, play
from the front of the list.
• Queues are used in OS for handling interrupts. When programming a
real-time system that can be interrupted, for ex, by a mouse click, it
is necessary to process the interrupts immediately before
proceeding with the current job. If the interrupts have to be handled
in the order of arrival, then a FIFO queue is the appropriate data
structure © Oxford University Press 2014. All rights reserved.
www.android.previousquestionpapers.com | www.previousquestionpapers.com | https://telegram.me/jntua