UNIT:1

A data structure is a way of organizing and storing the data in a

computer so that it can be accessed and modified efficiently. The
main idea is to reduce the space and time complexities of different
tasks.

Algorithm is a step-by-step procedure, which defines a set of instructions

to be executed in a certain order to get the desired output. Algorithms are
generally created independent of underlying languages, i.e. an algorithm
can be implemented in more than one programming language.
From the data structure point of view, following are some important
categories of algorithms −
 Search − Algorithm to search an item in a data structure.
 Sort − Algorithm to sort items in a certain order.
 Insert − Algorithm to insert item in a data structure.
 Update − Algorithm to update an existing item in a data structure.
 Delete − Algorithm to delete an existing item from a data structure.

Characteristics of an Algorithm
Not all procedures can be called an algorithm. An algorithm should have
the following characteristics −
 Unambiguous − Algorithm should be clear and unambiguous. Each
of its steps (or phases), and their inputs/outputs should be clear and
must lead to only one meaning.
 Input − An algorithm should have 0 or more well-defined inputs.
 Output − An algorithm should have 1 or more well-defined outputs,
and should match the desired output.
 Finiteness − Algorithms must terminate after a finite number of
steps.
 Feasibility − Should be feasible with the available resources.
 Independent − An algorithm should have step-by-step directions,
which should be independent of any programming code.
How to Write an Algorithm?
There are no well-defined standards for writing algorithms. Rather, it is
problem and resource dependent. Algorithms are never written to support
a particular programming code.
As we know that all programming languages share basic code constructs
like loops (do, for, while), flow-control (if-else), etc. These common
constructs can be used to write an algorithm.
We write algorithms in a step-by-step manner, but it is not always the
case. Algorithm writing is a process and is executed after the problem
domain is well-defined. That is, we should know the problem domain, for
which we are designing a solution.

Example
Let's try to learn algorithm-writing by using an example.
Problem − Design an algorithm to add two numbers and display the
result.
Step 1 − START
Step 2 − declare three integers a, b & c
Step 3 − define values of a & b
Step 4 − add values of a & b
Step 5 − store output of step 4 to c
Step 6 − print c
Step 7 − STOP
Algorithms tell the programmers how to code the program. Alternatively,
the algorithm can be written as −
Step 1 − START ADD
Step 2 − get values of a & b
Step 3 − c ← a + b
Step 4 − display c
Step 5 − STOP

Data Structure Classification

Linear Data Structures: A data structure is called linear if all of
its elements are arranged in the linear order. In linear data
structures, the elements are stored in non-hierarchical way where
each element has the successors and predecessors except the
first and last element.

Types of Linear Data Structures are given below:

Arrays: An array is a collection of similar type of data items and

each data item is called an element of the array. The data type of
the element may be any valid data type like char, int, float or
double.

The elements of array share the same variable name but each
one carries a different index number known as subscript. The
array can be one dimensional, two dimensional or
multidimensional.

The individual elements of the array age are:

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

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

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

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

allowed only at one end, called top.

A stack is an abstract data type (ADT), can be implemented in

most of the programming languages. It is named as stack
because it behaves like a real-world stack, for example: - piles of
plates or deck of cards etc.

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

only at one end called rear and deleted only at the other end
called front.

It is an abstract data structure, similar to stack. Queue is opened

at both end therefore it follows First-In-First-Out (FIFO)
methodology for storing the data items.

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

Types of Non Linear Data Structures are given below:

Trees: Trees are multilevel data structures with a hierarchical

relationship among its elements known as nodes. The
bottommost nodes in the herierchy are called leaf node while
the topmost node is called root node. Each node contains
pointers to point adjacent nodes.

Tree data structure is based on the parent-child relationship

among the nodes. Each node in the tree can have more than one
children except the leaf nodes whereas each node can have
atmost one parent except the root node. Trees can be classfied
into many categories which will be discussed later in this tutorial.

Graphs: Graphs can be defined as the pictorial representation of

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

Operations on data structure

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

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

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

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

the elements to the data structure at any location.

If the size of data structure is n then we can only insert n-1 data
elements into it.

3) Deletion:The process of removing an element from the data

structure is called Deletion. We can delete an element from the
data structure at any random location.

If we try to delete an element from an empty data structure

then underflow occurs.

4) Searching: The process of finding the location of an element

within the data structure is called Searching. There are two
algorithms to perform searching, Linear Search and Binary
Search. We will discuss each one of them later in this tutorial.

5) Sorting: The process of arranging the data structure in a

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

Languages such as C++/Java are developed from 'C'. These

languages are widely used in various technologies. Thus, 'C'
forms a base for many other languages that are currently in use.

C Basic Commands
Following are the basic commands in C programming language:

C Basic commands Explanation

#include <stdio.h> This command

includes
standard input
output header
file(stdio.h)
from the C
library before
compiling a C
program

int main() It is the main

function from
where C
program
execution
begins.
{ Indicates the
beginning of
the main
function.

/*_some_comments_*/ Whatever
written inside
this command
“/* */” inside
a C program, it
will not be
considered for
compilation
and execution.

printf(“Hello_World! “); This command

prints the
output on the
screen.

getch(); This command

is used for any
character input
from keyboard.

return 0; This command

is used to
terminate a C
program (main
function) and it
returns 0.
 } It is used to
indicate the
end of the
main function.

Structure of a C program
After the above discussion, we can formally assess the
structure of a C program. By structure, it is meant that any
program can be written in this structure only. Writing a C
program in any other structure will hence lead to a
Compilation Error.
The structure of a C program is as follows:

1. The components of the above structure are:

1. Header Files Inclusion: The first and foremost
component is the inclusion of the Header files in a C
program.
A header file is a file with extension .h which contains C
function declarations and macro definitions to be shared
between several source files.
Some of C Header files:
 stddef.h – Defines several useful types and macros.
 stdint.h – Defines exact width integer types.
 stdio.h – Defines core input and output functions
 stdlib.h – Defines numeric conversion functions,
pseudo-random network generator, memory allocation
 string.h – Defines string handling functions
 math.h – Defines common mathematical functions
2. Main Method Declaration: The next part of a C program
is to declare the main() function. The syntax to declare
the main function is:
Syntax to Declare the main method:
int main()
{}

1.
2. Variable Declaration: The next part of any C program is the
variable declaration. It refers to the variables that are to be
used in the function. Please note that in the C program, no
variable can be used without being declared. Also in a C
program, the variables are to be declared before any
operation in the function.
Example:

int main()
{

int a;
.
.
1.
2. Body: The body of a function in the C program, refers to the
operations that are performed in the functions. It can be
anything like manipulations, searching, sorting, printing, etc.
Example:

int main()
{
int a;

printf("%d", a);
.
.
1.
2. Return Statement: The last part of any C program is the
return statement. The return statement refers to the returning
of the values from a function. This return statement and
return value depend upon the return type of the function. For
 example, if the return type is void, then there will be no
return statement. In any other case, there will be a return
statement and the return value will be of the type of the
specified return type.
Example:

int main()
{
int a;

printf("%d", a);

return 0;
}
1.
2. Writing first program:
Following is first program in C

#include <stdio.h>

int main(void)

printf("GeeksQuiz");

return 0;

}
1. Let us analyze the program line by line.
Line 1: [ #include <stdio.h> ] In a C program, all lines that
start with # are processed by a preprocessor which is a
program invoked by the compiler. In a very basic term,
the preprocessor takes a C program and produces another C
program. The produced program has no lines starting with #,
all such lines are processed by the preprocessor. In the
above example, the preprocessor copies the preprocessed
code of stdio.h to our file. The .h files are called header files
in C. These header files generally contain declarations of
functions. We need stdio.h for the function printf() used in the
program.
Line 2 [ int main(void) ] There must be a starting point from
where execution of compiled C program begins. In C, the
execution typically begins with the first line of main(). The
void written in brackets indicates that the main doesn’t take
any parameter (See this for more details). main() can be
written to take parameters also. We will be covering that in
future posts.
The int was written before main indicates return type of
main(). The value returned by main indicates the status of
program termination. See this post for more details on the
return type.
Line 3 and 6: [ { and } ] In C language, a pair of curly
brackets define scope and are mainly used in functions and
control statements like if, else, loops. All functions must start
and end with curly brackets.
Line 4 [ printf(“GeeksQuiz”); ] printf() is a standard library
function to print something on standard output. The
semicolon at the end of printf indicates line termination. In C,
a semicolon is always used to indicate end of a statement.
Line 5 [ return 0; ] The return statement returns the value
from main(). The returned value may be used by an
operating system to know the termination status of your
program. The value 0 typically means successful
termination.
 Concept of Array
Definition
o Arrays are defined as the collection of similar type of data
items stored at contiguous memory locations.
o Arrays are the derived data type in C programming language
which can store the primitive type of data such as int, char,
double, float, etc.
o Array is the simplest data structure where each data
element can be randomly accessed by using its index
number.
o For example, if we want to store the marks of a student in 6
subjects, then we don't need to define different variable for
the marks in different subject. instead of that, we can define
an array which can store the marks in each subject at a the
contiguous memory locations.

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

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

Program without array:

1. #include <stdio.h>
2. void main ()
3. {
4. int marks_1 = 56, marks_2 = 78, marks_3 = 88, marks_4 = 76,
marks_5 = 56, marks_6 = 89;
5. float avg = (marks_1 + marks_2 + marks_3 + marks_4 + mark
s_5 +marks_6) / 6 ;
6. printf(“avg”);
7. getch();
8. }

Program by using array:

1. #include <stdio.h>
2. void main ()
3. {
4. int marks[6] = {56,78,88,76,56,89);
5. int i;
6. float avg;
7. for (i=0; i<6; i++ )
8. {
9. avg = avg + marks[i];
10. }
11. printf(avg);
12. }

Array Representation
Arrays can be declared in various ways in different languages. For
illustration, let's take C array declaration.
 Arrays can be declared in various ways in different languages. For
illustration, let's take C array declaration.

Concept Diagram of Arrays

Note:

 Elements are stored at contiguous memory locations.

 An index is always less than the total number of array items.
 In terms of syntax, any variable that is declared as an array
can store multiple values.
 Almost all languages have the same comprehension of
arrays but have different ways of declaring and initializing
them.
 However, three parts will always remain common in all the
initializations, i.e., array name, elements, and the data type
of elements.

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.
 Update − Updates an element at the given index.

Traverse Operation
This operation is to traverse through the elements of an array.

Example
Following program traverses and prints the elements of an array:
#include <stdio.h>
main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");
 for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the
following result −

Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8

Insertion Operation
Insert operation is to insert one or more data elements into an array.
Based on the requirement, a new element can be added at the beginning,
end, or any given index of array.
Here, we see a practical implementation of insertion operation, where we
add data at the end of the array −

Example
Following is the implementation of the above algorithm −
Live Demo

#include <stdio.h>

main() {
int LA[] = {1,3,5,7,8};
int item = 10, k = 3, n = 5;
int i = 0, j = n;
printf("The original array elements are :\n");

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

 printf("LA[%d] = %d \n", i, LA[i]);
}

n = n + 1;
while( j >= k) {
LA[j+1] = LA[j];
j = j - 1;
}

LA[k] = item;

printf("The array elements after insertion :\n");

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

printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the
following result −

Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after insertion :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 10
LA[4] = 7
LA[5] = 8
For other variations of array insertion operation click here
Deletion Operation
Deletion refers to removing an existing element from the array and re-
organizing all elements of an array.

Algorithm
Consider LA is a linear array with N elements and K is a positive integer
such that K<=N. Following is the algorithm to delete an element available
at the Kth position of LA.
1. Start
2. Set J = K
3. Repeat steps 4 and 5 while J < N
4. Set LA[J] = LA[J + 1]
5. Set J = J+1
6. Set N = N-1
7. Stop

Example
Following is the implementation of the above algorithm −
Live Demo

#include <stdio.h>

void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
j = k;
while( j < n) {
LA[j-1] = LA[j];
j = j + 1;
 }
n = n -1;
printf("The array elements after deletion :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the
following result −

Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after deletion :
LA[0] = 1
LA[1] = 3
LA[2] = 7
LA[3] = 8

Search Operation
You can perform a search for an array element based on its value or its
index.

Algorithm
Consider LA is a linear array with N elements and K is a positive integer
such that K<=N. Following is the algorithm to find an element with a value
of ITEM using sequential search.
1. Start
2. Set J = 0
3. Repeat steps 4 and 5 while J < N
4. IF LA[J] is equal ITEM THEN GOTO STEP 6
5. Set J = J +1
6. PRINT J, ITEM
7. Stop

Example
Following is the implementation of the above algorithm −
Live Demo

#include <stdio.h>

void main() {
int LA[] = {1,3,5,7,8};
int item = 5, n = 5;
int i = 0, j = 0;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
while( j < n){
if( LA[j] == item ) {
break;
}
j = j + 1;
}
printf("Found element %d at position %d\n", item,
j+1);
}
When we compile and execute the above program, it produces the
following result −

Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
Found element 5 at position 3

Update Operation
Update operation refers to updating an existing element from the array at a
given index.

Algorithm
Consider LA is a linear array with N elements and K is a positive integer
such that K<=N. Following is the algorithm to update an element available
at the Kth position of LA.
1. Start
2. Set LA[K-1] = ITEM
3. Stop

Example
Following is the implementation of the above algorithm −
Live Demo

#include <stdio.h>

void main() {
int LA[] = {1,3,5,7,8};
int k = 3, n = 5, item = 10;
int i, j;
printf("The original array elements are :\n");
for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
LA[k-1] = item;

printf("The array elements after updation :\n");

 for(i = 0; i<n; i++) {
printf("LA[%d] = %d \n", i, LA[i]);
}
}
When we compile and execute the above program, it produces the
following result −

Output
The original array elements are :
LA[0] = 1
LA[1] = 3
LA[2] = 5
LA[3] = 7
LA[4] = 8
The array elements after updation :
LA[0] = 1
LA[1] = 3
LA[2] = 10
LA[3] = 7
LA[4] = 8

Types of Arrays in C
In c programming language, arrays are classified into two types. They are as
follows...

1. Single Dimensional Array / One Dimensional Array

2. Multi Dimensional Array

Single Dimensional Array

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

Declaration of Single Dimensional Array

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

datatype arrayName [ size ] ;

Example Code
int rollNumbers [60] ;

The above declaration of single dimensional array reserves 60 continuous memory

locations of 2 bytes each with the name rollNumbers and tells the compiler to allow
only integer values into those memory locations.

Initialization of Single Dimensional Array

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

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

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

The above declaration of single dimensional array reserves 6 contiguous memory

locations of 2 bytes each with the name marks and initializes with value 89 in first
memory location, 90 in second memory location, 76 in third memory location, 78 in
fourth memory location, 98 in fifth memory location and 86 in sixth memory location.

We can also use the following general syntax to intialize a single dimensional array
without specifying size and with initial values...
 datatype arrayName [ ] = {value1, value2, ...} ;
The array must be initialized if it is created without specifying any size. In this case,
the size of the array is decided based on the number of values initialized.

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

char studentName [] = "btechsmartclass" ;

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

Accessing Elements of Single Dimensional Array

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

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

dimensional array...

arrayName [ indexValue ]
Example Code
marks [2] = 99 ;
In the above statement, the third element of 'marks' array is assinged with
value '99'.

Multi Dimensional Array

An array of arrays is called as multi dimensional array. In simple words, an array
created with more than one dimension (size) is called as multi dimensional array.
Multi dimensional array can be of two dimensional array or three dimensional
array or four dimensional array or more...

Most popular and commonly used multi dimensional array is two dimensional
array. The 2-D arrays are used to store data in the form of table. We also use 2-D
arrays to create mathematical matrices.

Declaration of Two Dimensional Array

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

datatype arrayName [ rowSize ] [ columnSize ] ;

Example Code
int matrix_A [2][3] ;

The above declaration of two dimensional array reserves 6 continuous memory

locations of 2 bytes each in the form of 2 rows and 3 columns.

Initialization of Two Dimensional Array

We use the following general syntax for declaring and initializing a two dimensional
array with specific number of rows and coloumns with initial values.

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

Example Code
int matrix_A [2][3] = { {1, 2, 3},{4, 5, 6} } ;

The above declaration of two-dimensional array reserves 6 contiguous memory

locations of 2 bytes each in the form of 2 rows and 3 columns. And the first row is
initialized with values 1, 2 & 3 and second row is initialized with values 4, 5 & 6.

We can also initialize as follows...

Example Code
int matrix_A [2][3] = {

{1, 2, 3},

{4, 5, 6}

} ;

Accessing Individual Elements of Two Dimensional

Array
In a c programming language, to access elements of a two-dimensional array we
use array name followed by row index value and column index value of the element
that to be accessed. Here the row and column index values must be enclosed in
separate square braces. In case of the two-dimensional array the compiler assigns
separate index values for rows and columns.

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

arrayName [ rowIndex ] [ columnIndex ]

Example Code
matrix_A [0][1] = 10 ;
In the above statement, the element with row index 0 and column index 1
of matrix_A array is assinged with value 10.

Introduction to Linked Lists

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

Advantages of Linked Lists

 They are a dynamic in nature which allocates

the memory when required.
  Insertion and deletion operations can be easily
implemented.
 Stacks and queues can be easily executed.
 Linked List reduces the access time.

Disadvantages of Linked Lists

 The memory is wasted as pointers require

extra memory for storage.
 No element can be accessed randomly; it has
to access each node sequentially.
 Reverse Traversing is difficult in linked list.

Applications of Linked Lists

 Linked lists are used to implement stacks,

queues, graphs, etc.
 Linked lists let you insert elements at the
beginning and end of the list.
 In Linked Lists we don't need to know the size
in advance.
Types of Linked Lists

There are 3 different implementations of Linked

List available, they are:
1.Singly Linked List
2.Doubly Linked List
3.Circular Linked List
Let's know more about them and how they are
different from each other.

Singly Linked List

Singly linked lists contain nodes which have

a data part as well as an address part i.e. next,
which points to the next node in the sequence of
nodes.
The operations we can perform on singly linked
lists are insertion, deletion and traversal.
Doubly Linked List

In a doubly linked list, each node contains

a data part and two addresses, one for
the previous node and one for the next node.

Circular Linked List

In circular linked list the last node of the list holds

the address of the first node hence forming a
circular chain.
We will learn about all the 3 types of linked list,
one by one, in the next tutorials. So click
on Next button, let's learn more about linked lists.
Difference between Array and Linked List
Both Linked List and Array are used to store linear
data of similar type, but an array consumes
contiguous memory locations allocated at compile
time, i.e. at the time of declaration of array, while
for a linked list, memory is assigned as and when
data is added to it, which means at runtime.
Before we proceed further with the differences
between Array and Linked List, if you are not
familiar with Array or Linked list or both, you can
check these topics first:

This is the basic and the most important difference

between a linked list and an array. In the section
below, we will discuss this in details along with
highlighting other differences.
Linked List vs. Array

Array is a datatype which is widely implemented as

a default type, in almost all the modern
programming languages, and is used to store data
of similar type.
But there are many use cases, like the one where
we don't know the quantity of data to be stored, for
which advanced data structures are required, and
one such data structure is linked list.
Let's understand how array is different from Linked
list.

Array Linked list

An array is a collection of A linked list is a collection of

elements of a similar data type. objects known as a node where
node consists of two parts, i.e.,
data and address.

Array elements store in a Linked list elements can be stored

contiguous memory location. anywhere in the memory or
randomly stored.

Array works with a static The Linked list works with dynamic
memory. Here static memory memory. Here, dynamic memory
means that the memory size is means that the memory size can
fixed and cannot be changed at be changed at the run time
the run time. according to our requirements.
Array elements are independent Linked list elements are dependent
of each other. on each other. As each node
contains the address of the next
node so to access the next node,
we need to access its previous
node.

Array takes more time while Linked list takes less time while
performing any operation like performing any operation like
insertion, deletion, etc. insertion, deletion, etc.

Accessing any element in an Accessing an element in a linked

array is faster as the element in list is slower as it starts traversing
an array can be directly accessed from the first element of the linked
through the index. list.

In the case of an array, memory In the case of a linked list, memory

is allocated at compile-time. is allocated at run time.

Memory utilization is inefficient in Memory utilization is efficient in

the array. For example, if the size the case of a linked list as the
of the array is 6, and array memory can be allocated or
consists of 3 elements only then deallocated at the run time
the rest of the space will be according to our requirement.
unused.
Below we have a pictorial representation showing
how consecutive memory locations are allocated
for array, while in case of linked list random
memory locations are assigned to nodes, but each
node is connected to its next node using pointer.

On the left, we have Array and on the right, we

have Linked List.

Why we need pointers in Linked List? [Deep Dive]

In case of array, memory is allocated in contiguous

manner, hence array elements get stored in
consecutive memory locations. So when you have
to access any array element, all we have to do is
use the array index, for example arr[4] will directly
access the 5th memory location, returning the data
stored there.
But in case of linked list, data elements are
allocated memory at runtime, hence the memory
location can be anywhere. Therefore to be able to
access every node of the linked list, address of
every node is stored in the previous node, hence
forming a link between every node.
We need this additional pointer because without
it, the data stored at random memory locations will
be lost. We need to store somewhere all the
memory locations where elements are getting
stored.
Yes, this requires an additional memory space with
each node, which means an additional space
of O(n) for every n node linked list.

Sparse Matrix and its

representations | (Using Arrays
and Linked Lists)
A matrix is a two-dimensional data object made of
m rows and n columns, therefore having total m x
n values. If most of the elements of the matrix
have 0 value, then it is called a sparse matrix.
Why to use Sparse Matrix instead of simple
matrix ?
 Storage: There are lesser non-zero elements

than zeros and thus lesser memory can be used

to store only those elements.
 Computing time: Computing time can be saved

by logically designing a data structure traversing

only non-zero elements..
Example:
0 0 3 0 4
0 0 5 7 0
0 0 0 0 0
0 2 6 0 0
Representing a sparse matrix by a 2D array leads
to wastage of lots of memory as zeroes in the
matrix are of no use in most of the cases. So,
instead of storing zeroes with non-zero elements,
we only store non-zero elements. This means
storing non-zero elements with triples- (Row,
Column, value).
Sparse Matrix Representations can be done in
many ways following are two common
representations:
1. Array representation
2. Linked list representation
Method 1: Using Arrays:
2D array is used to represent a sparse matrix in which there are
three rows named as

 Row: Index of row, where non-zero element is located

 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index –
(row,column)
// C++ program for Sparse Matrix Representation

// using Array

#include<stdio.h>

int main()

// Assume 4x5 sparse matrix

int sparseMatrix[4][5] =

{0 , 0 , 3 , 0 , 4 },

{0 , 0 , 5 , 7 , 0 },

{0 , 0 , 0 , 0 , 0 },

{0 , 2 , 6 , 0 , 0 }
};

int size = 0;

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

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

if (sparseMatrix[i][j] != 0)

size++;

// number of columns in compactMatrix (size) must be

// equal to number of non - zero elements in

// sparseMatrix

int compactMatrix[3][size];

// Making of new matrix

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

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

if (sparseMatrix[i][j] != 0)

compactMatrix[0][k] = i;

compactMatrix[1][k] = j;

compactMatrix[2][k] = sparseMatrix[i][j];

k++;

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

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

printf("%d ", compactMatrix[i][j]);

 printf("\n");

return 0;

Output:
0 0 1 1 3 3
2 4 2 3 1 2
3 4 5 7 2 6

Method 2: Using Linked Lists

In linked list, each node has four fields. These four fields are defined
as:
 Row: Index of row, where non-zero element is located
 Column: Index of column, where non-zero element is located
 Value: Value of the non zero element located at index –
(row,column)
 Next node: Address of the next node.
// C++ program for sparse matrix representation.
// Using Link list

#include<iostream>

using namespace std;

// Node class to represent link list

class Node

public:

int row;

int col;

int data;

Node *next;

};

// Function to create new node

void create_new_node(Node **p, int row_index,

int col_index, int x)

Node *temp = *p;

Node *r;

// If link list is empty then

// create first node and assign value.

if (temp == NULL)

temp = new Node();

temp->row = row_index;

temp->col = col_index;

temp->data = x;

temp->next = NULL;
 *p = temp;

// If link list is already created

// then append newly created node

else

while (temp->next != NULL)

temp = temp->next;

r = new Node();

r->row = row_index;

r->col = col_index;

r->data = x;

r->next = NULL;
 temp->next = r;

// Function prints contents of linked list

// starting from start

void printList(Node *start)

Node *ptr = start;

cout << "row_position:";

while (ptr != NULL)

cout << ptr->row << " ";

ptr = ptr->next;

}
cout << endl;

cout << "column_position:";

ptr = start;

while (ptr != NULL)

cout << ptr->col << " ";

ptr = ptr->next;

cout << endl;

cout << "Value:";

ptr = start;

while (ptr != NULL)

{
 cout << ptr->data << " ";

ptr = ptr->next;

// Driver Code

int main()

// 4x5 sparse matrix

int sparseMatrix[4][5] = { { 0 , 0 , 3 , 0 , 4 },

{ 0 , 0 , 5 , 7 , 0 },

{ 0 , 0 , 0 , 0 , 0 },

{ 0 , 2 , 6 , 0 , 0 } };
// Creating head/first node of list as NULL

Node *first = NULL;

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

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

// Pass only those values which

// are non - zero

if (sparseMatrix[i][j] != 0)

create_new_node(&first, i, j,

sparseMatrix[i][j]);

printList(first);
 return 0;

// This code is contributed by ronaksuba

Output:
row_position: 0 0 1 1 3 3
column_postion: 2 4 2 3 1 2
Value: 3 4 5 7 2 6
Declaration The declaration varies for The declaration varies for different
different programming programming language:
language:
1. For C++,
1. For C++, datatype variable_name[row]
datatype [column]
 variable_name[row]

2. For Java,
datatype [] 2. For Java,
variable_name= new datatype [][] variable_name=
dataype[row] new dataype[row][column]

Declaration The declaration varies for The declaration varies for different
different programming programming language:
language:
3. For C++,
 3. For C++,
datatype datatype variable_name[row]
variable_name[row] [column]
4. For Java, 4. For Java,
datatype [] datatype [][] variable_name=
variable_name= new new dataype[row][column]
dataype[row]

UNIT-(STACKS)
Stack is a linear data structure which follows a particular order in
which the operations are performed. The order may be LIFO(Last In
First Out) or FILO(First In Last Out).
Mainly the following three basic operations are performed in the
stack:
 Push: Adds an item in the stack. If the stack is full, then it is said
to be an Overflow condition.
 Pop: Removes an item from the stack. The items are popped in
the reversed order in which they are pushed. If the stack is
empty, then it is said to be an Underflow condition.
 Peek or Top: Returns top element of stack.
 isEmpty: Returns true if stack is empty, else false.


How to understand a stack practically?

There are many real-life examples of a stack. Consider the simple
example of plates stacked over one another in a canteen. The plate
which is at the top is the first one to be removed, i.e. the plate which
has been placed at the bottommost position remains in the stack for
the longest period of time. So, it can be simply seen to follow
LIFO/FILO order.
Time Complexities of operations on stack:
push(), pop(), isEmpty() and peek() all take O(1) time. We do not run
any loop in any of these operations.
Implementation:
There are two ways to implement a stack:
 Using array
 Using linked list

What is a Stack?
A Stack is a linear data structure that follows the LIFO (Last-In-
First-Out) principle. Stack has one end, whereas the Queue has
two ends (front and rear). It contains only one pointer top
pointer pointing to the topmost element of the stack. Whenever
an element is added in the stack, it is added on the top of the
stack, and the element can be deleted only from the stack. In
other words, a stack can be defined as a container in which
insertion and deletion can be done from the one end
known as the top of the stack.

Some key points related to stack

o It is called as stack because it behaves like a real-world
stack, piles of books, etc.
o A Stack is an abstract data type with a pre-defined capacity,
which means that it can store the elements of a limited size.
 o It is a data structure that follows some order to insert and
delete the elements, and that order can be LIFO or FILO.

Working of Stack
Stack works on the LIFO pattern. As we can observe in the below
figure there are five memory blocks in the stack; therefore, the
size of the stack is 5.

Suppose we want to store the elements in a stack and let's

assume that stack is empty. We have taken the stack of size 5 as
shown below in which we are pushing the elements one by one
until the stack becomes full.

Since our stack is full as the size of the stack is 5. In the above
cases, we can observe that it goes from the top to the bottom
when we were entering the new element in the stack. The stack
gets filled up from the bottom to the top.

When we perform the delete operation on the stack, there is only

one way for entry and exit as the other end is closed. It follows
the LIFO pattern, which means that the value entered first will be
removed last. In the above case, the value 5 is entered first, so it
will be removed only after the deletion of all the other elements.
Standard Stack Operations
The following are some common operations implemented
on the stack:

o push(): When we insert an element in a stack then the

operation is known as a push. If the stack is full then the
overflow condition occurs.
o pop(): When we delete an element from the stack, the
operation is known as a pop. If the stack is empty means
that no element exists in the stack, this state is known as an
underflow state.
o isEmpty(): It determines whether the stack is empty or not.
o isFull(): It determines whether the stack is full or not.'
o peek(): It returns the element at the given position.
o count(): It returns the total number of elements available in
a stack.
o change(): It changes the element at the given position.
o display(): It prints all the elements available in the stack.

PUSH operation
The steps involved in the PUSH operation is given below:

o Before inserting an element in a stack, we check whether

the stack is full.
o If we try to insert the element in a stack, and the stack is
full, then the overflow condition occurs.
o When we initialize a stack, we set the value of top as -1 to
check that the stack is empty.
 o When the new element is pushed in a stack, first, the value
of the top gets incremented, i.e., top=top+1, and the
element will be placed at the new position of the top.
o The elements will be inserted until we reach the max size of
the stack.

POP operation
The steps involved in the POP operation is given below:

o Before deleting the element from the stack, we check

whether the stack is empty.
o If we try to delete the element from the empty stack, then
the underflow condition occurs.
 o If the stack is not empty, we first access the element which
is pointed by the top
o Once the pop operation is performed, the top is
decremented by 1, i.e., top=top-1.

Applications of Stack
The following are the applications of the stack:

o Balancing of symbols: Stack is used for balancing a

symbol. For example, we have the following program:

1. int main()
2. {
3. cout<<"Hello";
4. cout<<"javaTpoint";
5. }
As we know, each program has an opening and closing braces;
when the opening braces come, we push the braces in a stack,
and when the closing braces appear, we pop the opening braces
from the stack. Therefore, the net value comes out to be zero. If
any symbol is left in the stack, it means that some syntax occurs
in a program.

o String reversal: Stack is also used for reversing a string.

For example, we want to reverse a "adityacollege" string,
so we can achieve this with the help of a stack.
First, we push all the characters of the string in a stack until
we reach the null character.
After pushing all the characters, we start taking out the
character one by one until we reach the bottom of the stack.
o UNDO/REDO: It can also be used for performing
UNDO/REDO operations. For example, we have an editor in
which we write 'a', then 'b', and then 'c'; therefore, the text
written in an editor is abc. So, there are three states, a, ab,
and abc, which are stored in a stack. There would be two
stacks in which one stack shows UNDO state, and the other
shows REDO state.
If we want to perform UNDO operation, and want to achieve
'ab' state, then we implement pop operation.
o Recursion: The recursion means that the function is calling
itself again. To maintain the previous states, the compiler
creates a system stack in which all the previous records of
the function are maintained.

DFS(Depth First Search): This search is implemented on

a Graph, and Graph uses the stack data structure.
 o Backtracking: Suppose we have to create a path to solve a
maze problem. If we are moving in a particular path, and we
realize that we come on the wrong way. In order to come at
the beginning of the path to create a new path, we have to
use the stack data structure.
o Expression conversion: Stack can also be used for
expression conversion. This is one of the most important
applications of stack. The list of the expression conversion is
given below:
o Infix to prefix

o Infix to postfix

o Prefix to infix

o Prefix to postfix

Postfix to infix

o Memory management: The stack manages the memory.

The memory is assigned in the contiguous memory blocks.
The memory is known as stack memory as all the variables
are assigned in a function call stack memory. The memory
size assigned to the program is known to the compiler. When
the function is created, all its variables are assigned in the
stack memory. When the function completed its execution,
all the variables assigned in the stack are released.

Array implementation of Stack

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

Adding an element onto the stack (push operation)

Adding an element into the top of the stack is referred to as push operation. Push
operation involves following two steps.

1. Increment the variable Top so that it can now refere to the next memory
location.
2. Add element at the position of incremented top. This is referred to as
adding new element at the top of the stack.

Stack is overflown when we try to insert an element into a completely filled stack
therefore, our main function must always avoid stack overflow condition.

Algorithm:

 begin
 if top = n then stack full
 top = top + 1
 stack (top) : = item;
 end

implementation of push algorithm in C language

 void push (int val,int n) //n is size of the stack
 {
 if (top == n )
 printf("\n Overflow");
 else
 {
 top = top +1;
 stack[top] = val;
  }
 }

Deletion of an element from a stack (Pop operation)

 Deletion of an element from the top of the stack is called
pop operation. The value of the variable top will be
incremented by 1 whenever an item is deleted from the
stack. The top most element of the stack is stored in an
another variable and then the top is decremented by 1. the
operation returns the deleted value that was stored in
another variable as the result.
 The underflow condition occurs when we try to delete an
element from an already empty stack.
Algorithm :

1. begin
2. if top = 0 then stack empty;
3. item := stack(top);
4. top = top - 1;
5. end;

Time Complexity : o(1)

Implementation of POP algorithm using C language

1. int pop ()
2. {
3. if(top == -1)
4. {
5. printf("Underflow");
6. return 0;
7. }
8. else
9. {
10. return stack[top - - ];
11. }
12. }

Visiting each element of the stack (Peek operation)

Peek operation involves returning the element which is present at the top of the stack without
deleting it. Underflow condition can occur if we try to return the top element in an already empty
stack.

Algorithm :

PEEK (STACK, TOP)

1. Begin
2. if top = -1 then stack empty
3. item = stack[top]
4. return item
5. End

Time complexity: o(n)

Implementation of Peek algorithm in C language

1. int peek()
2. {
3. if (top == -1)
4. {
5. printf("Underflow");
6. return 0;
7. }
8. else
9. {
10. return stack [top];
11. }
12. }

C program

1. #include <stdio.h>
2. int stack[100],i,j,choice=0,n,top=-1;
3. void push();
4. void pop();
5. void show();
6. void main ()
7. {
8.
9. printf("Enter the number of elements in the stack ");
10. scanf("%d",&n);
11. printf("*********Stack operations using array*********");
12.
13. printf("\n----------------------------------------------\n");
14. while(choice != 4)
15. {
16. printf("Chose one from the below options...\n");
17. printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
18. printf("\n Enter your choice \n");
19. scanf("%d",&choice);
20. switch(choice)
21. {
22. case 1:
23. {
24. push();
25. break;
26. }
27. case 2:
28. {
29. pop();
30. break;
31. }
32. case 3:
33. {
34. show();
35. break;
36. }
37. case 4:
38. {
39. printf("Exiting....");
40. break;
41. }
42. default:
43. {
44. printf("Please Enter valid choice ");
45. }
46. };
47. }
48. }
49.
50. void push ()
51. {
52. int val;
53. if (top == n )
54. printf("\n Overflow");
55. else
56. {
57. printf("Enter the value?");
58. scanf("%d",&val);
59. top = top +1;
60. stack[top] = val;
61. }
62. }
63.
64. void pop ()
65. {
66. if(top == -1)
67. printf("Underflow");
68. else
69. top = top -1;
70. }
71. void show()
72. {
73. for (i=top;i>=0;i--)
74. {
75. printf("%d\n",stack[i]);
76. }
77. if(top == -1)
78. {
79. printf("Stack is empty");
80. }
81. }
ADT:-
The definition of ADT only mentions what operations are to be
performed but not how these operations will be implemented. It does
not specify how data will be organized in memory and what
algorithms will be used for implementing the operations. It is called
“abstract” because it gives an implementation-independent view. The
process of providing only the essentials and hiding the details is
known as abstraction.
The user of data type does not need to know how that data type is
implemented, for example, we have been using Primitive values like
int, float, char data types only with the knowledge that these data
type can operate and be performed on without any idea of how they
are implemented. So a user only needs to know what a data type
can do, but not how it will be implemented. Think of ADT as a black
box which hides the inner structure and design of the data type. Now
we’ll define three ADTs namely List ADT, Stack ADT, Queue ADT.
1. List ADT
 The data is generally stored in key sequence in a list which
has a head structure consisting of count, pointers and address
of compare function needed to compare the data in the list.
 The data node contains the pointer to a data structure and
a self-referential pointer which points to the next node in the
list.

1. Stack ADT
 In Stack ADT Implementation instead of data being stored in
each node, the pointer to data is stored.
 The program allocates memory for the data and address is
passed to the stack ADT.
 The head node and the data nodes are encapsulated in the
ADT. The calling function can only see the pointer to the
stack.
 The stack head structure also contains a pointer
to top and count of number of entries currently in stack.

Linked list implementation of stack

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

In linked list implementation of stack, the nodes are maintained

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

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

Adding a node to the stack (Push operation)

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

10.2M
 188

Difference between JDK, JRE, and JVM

1. Create a node first and allocate memory to it.

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

Time Complexity : o(1)

 C implementation :
1. void push ()
2. {
3. int val;
4. struct node *ptr =(struct node*)malloc(sizeof(struct node)
);
5. if(ptr == NULL)
6. {
7. printf("not able to push the element");
8. }
9. else
10. {
11. printf("Enter the value");
12. scanf("%d",&val);
13. if(head==NULL)
14. {
15. ptr->val = val;
16. ptr -> next = NULL;
17. head=ptr;
18. }
19. else
20. {
21. ptr->val = val;
22. ptr->next = head;
23. head=ptr;
24.
25. }
26. printf("Item pushed");
27.
28. }
29. }

Deleting a node from the stack (POP

operation)
Deleting a node from the top of stack is referred to as
 .

//Stack ADT Type Definitions

 typedef struct node

void *DataPtr;

struct node *link;

} StackNode;

typedef struct

int count;

StackNode *top;

} STACK;

2. A Stack contains elements of the same type arranged in

sequential order. All operations take place at a single end that is
top of the stack and following operations can be performed:
 push() – Insert an element at one end of the stack called top.
 pop() – Remove and return the element at the top of the stack,
if it is not empty.
 peek() – Return the element at the top of the stack without
removing it, if the stack is not empty.
 size() – Return the number of elements in the stack.
 isEmpty() – Return true if the stack is empty, otherwise return
false.
 isFull() – Return true if the stack is full, otherwise return false.
 Infix expression: K + L - M*N + (O^P) * W/U/V * T + Q

Input Expression Stack Postfix Expression

K K

+ +

L + KL

- - K L+

M - K L+ M

* -* K L+ M

N -* KL+MN

+ + K L + M N*
K L + M N* -

( +( K L + M N *-

O +( KL+MN*-O

^ +(^ K L + M N* - O

P +(^ K L + M N* - O P

) + K L + M N* - O P ^
* +* K L + M N* - O P ^

W +* K L + M N* - O P ^ W

/ +/ K L + M N* - O P ^ W *

U +/ K L + M N* - O P ^W*U

/ +/ K L + M N* - O P ^W*U/

V +/ KL + MN*-OP^W*U/V

* +* KL+MN*-OP^W*U/V/

T +* KL+MN*-OP^W*U/V/T

+ + KL+MN*-OP^W*U/V/T*
KL+MN*-OP^W*U/V/T*+

Q + KL+MN*-OP^W*U/V/T*Q

KL+MN*-OP^W*U/V/T*+Q+

The final postfix expression of infix expression(K + L - M*N +

(O^P) * W/U/V * T + Q) is KL+MN*-OP^W*U/V/T*+Q+.