Module 1

Introduction to Data Structure

Compiled by : Mrs. Foram Shah (Assistant Professor - Department of Computer Engineering, TCET)
This document is only meant for Academic Purpose and Internal Circulation only. 1
Content
• Introduction to Java:
• Data Types
• Operators
• Control structure
• Array
• String & vectors
• classes & objects, Methods.
• Introduction to Data Structure :
• Types of data Structures
• Abstract data type
• Importance of ADT
• Operations on data structures.

Compiled by : Mrs. Foram Shah 2

Introduction to Java
• It is a programming language created in 1991. James Gosling, Mike
Sheridan, and Patrick Naughton, a team of Sun engineers known as
the Green team
• Sun Microsystems released its first public implementation in 1996
as Java 1.0.
• The latest version of Java is Java 20 or JDK 20 released on March, 21st
2023

Compiled by : Mrs. Foram Shah 3

Applications of Java in real world
• Desktop GUI Applications
• Mobile Applications
• Artificial intelligence
• Web applications
• Big Data technology
• Gaming applications
• Business applications
• Embedded systems
• Cloud applications
• Scientific applications

Compiled by : Mrs. Foram Shah 4

Data Types
Data types are divided into two groups:
•Primitive data types - includes byte, short, int, long, float, double, boolean and char
•Non-primitive data types - such as String, Arrays and Classes
Data Type Size Description
byte 1 byte Stores whole numbers from -128 to 127
short 2 bytes Stores whole numbers from -32,768 to 32,767
int 4 bytes Stores whole numbers from -2,147,483,648 to
2,147,483,647
long 8 bytes Stores whole numbers from -9,223,372,036,854,775,808
to 9,223,372,036,854,775,807

float 4 bytes Stores fractional numbers. Sufficient for storing 6 to 7

decimal digits
double 8 bytes Stores fractional numbers. Sufficient for storing 15
decimal digits
boolean 1 bit Stores true or false values
char 2 bytes Stores a single character/letter or ASCII values
Compiled by : Mrs. Foram Shah 5
Data types Example:
public class Main
{
public static void main (String [] args)
{
int myNum = 5; // integer (whole number)
float myFloatNum = 5.99f; // floating point number
char myLetter = 'D'; // character
boolean myBool = true; // boolean
String myText = "Hello"; // String
[Link](myNum);
[Link](myFloatNum);
[Link](myLetter);
[Link](myBool);
[Link](myText);
}
Compiled by : Mrs. Foram Shah 6
}
Operators
• Operator in Java is a symbol that is used to perform operations. For
example: +, -, *, / etc.
• There are many types of operators in Java which are given below:
• Unary Operator
• Arithmetic Operator
• Shift Operator
• Relational Operator
• Bitwise Operator
• Logical Operator
• Ternary Operator
• Assignment Operator

Compiled by : Mrs. Foram Shah 7

 Java Operator Precedence
Operator Type Category Precedence
Unary postfix expr++ expr--
prefix ++expr --expr +expr -expr ~ !

Arithmetic multiplicative */%

additive +-
Shift shift << >> >>>
Relational comparison < > <= >= instanceof
equality == !
Bitwise bitwise AND &
bitwise exclusive OR ^
bitwise inclusive OR |
Logical logical AND &&
logical OR ||
Ternary ternary ?:
Assignment assignment = += -= *= /= % & ^= | <<= >>= >>>=

Compiled by : Mrs. Foram Shah 8

Operators Example:
import [Link]. *;
class GFG {
public static void main (String [] args) {

// Arithmetic operators
int a = 10;
int b = 3;
int c = 5;
int Result;
[Link]("a + b = " + (a + b));
[Link]("a - b = " + (a - b));
[Link]("a * b = " + (a * b));
[Link]("a / b = " + (a / b));
[Link]("a % b = " + (a % b));
// Using unary operators
[Link]("Post increment: " + (a++));
[Link]("Pre increment: " + (++a));

[Link]("Post decrement: " + (b--));

[Link]("Pre decrement: " + (--b));

Compiled by : Mrs. Foram Shah 9

 // Logical operators
// Assignment operators boolean x = true;
int f = 7; boolean y = false;
[Link]("x && y: " + (x && y));
[Link]("f += 3: " + (f += 3));
[Link]("x || y: " + (x || y));
[Link]("f -= 2: " + (f -= 2)); [Link](“! x: " + (!x));
[Link]("f *= 4: " + (f *= 4));
[Link]("f /= 3: " + (f /= 3)); // ternary operator.
[Link]("f %= 2: " + (f %= 2)); Result = ((a > b)? (a > c)? a : c : (b > c) ? b : c);
[Link]("f &= 0b1010: " + (f &= [Link]("Max of three numbers = "+ result);
0b1010));
// Bitwise operators
[Link]("f |= 0b1100: " + (f |= 0b1100));
int d = 0b1010;
[Link]("f ^= 0b1010: " + (f ^= 0b1010)); int e = 0b1100;
[Link]("f <<= 2: " + (f <<= 2)); [Link]("d & e: " + (d & e));
[Link]("f >>= 1: " + (f >>= 1)); [Link]("d | e: " + (d | e));
[Link]("f >>>= 1: " + (f >>>= 1)); [Link]("d ^ e: " + (d ^ e));
[Link]("~d: " + (~d));
// Comparison operators [Link]("d << 2: " + (d << 2));
[Link]("a > b: " + (a > b)); [Link]("e >> 1: " + (e >> 1));
[Link]("e >>> 1: " + (e >>> 1));
[Link]("a < b: " + (a < b));
[Link]("a >= b: " + (a >= b)); // shift operators
[Link]("a <= b: " + (a <= b)); // using left shift
[Link]("a == c: " + (a == c)); [Link]("a<<1: " + (a << 1));
[Link]("a!= c: " + (a != c)); // using right shift
[Link]("a>>1: " + (a >> 1));
}
Compiled by : Mrs. Foram Shah } 10
Control structures
• Java compiler executes the code from top to bottom. The statements in the code are executed
according to the order in which they appear. However, Java provides statements that can be used
to control the flow of Java code. Such statements are called control flow statements. It is one of
the fundamental features of Java, which provides a smooth flow of program.
• Java provides three types of control flow statements.
• Decision Making statements
• if statements
• switch statement
• Loop statements
• do while loop
• while loop
• for loop
• for-each loop
• Jump statements
• break statement
• continue statement

Compiled by : Mrs. Foram Shah 11

Simple if statement:
• It is the most basic statement among all control flow statements in
Java. It evaluates a Boolean expression and enables the program to
enter a block of code if the expression evaluates to true.
• Syntax of if statement is given below.
if(condition)
{
statement 1; //executes when condition is true
}

Compiled by : Mrs. Foram Shah 12

Example
public class Student
{
public static void main(String[] args)
{
int x = 10;
int y = 12;
if(x+y > 20)
{
[Link]("x + y is greater than 20");
}
}
}

Compiled by : Mrs. Foram Shah 13

if-else statement
• The if-else statement is an extension to the if-statement, which uses
another block of code, i.e., else block. The else block is executed if the
condition of the if-block is evaluated as false.
• Syntax:
if(condition)
{
statement 1; //executes when condition is true
}
else{
statement 2; //executes when condition is false
}

Compiled by : Mrs. Foram Shah 14

Example:
public class Student {
public static void main(String[] args) {
int x = 10;
int y = 12;
if(x+y < 10) {
[Link]("x + y is less than 10");
} else {
[Link]("x + y is greater than 20");
}
}
}

Compiled by : Mrs. Foram Shah 15

if-else-if ladder
• The if-else-if statement contains the if-statement followed by multiple else-if
statements. In other words, we can say that it is the chain of if-else statements
that create a decision tree where the program may enter in the block of code
where the condition is true. We can also define an else statement at the end of
the chain.
• Syntax of if-else-if statement is given below.
if(condition 1) {
statement 1; //executes when condition 1 is true
}
else if(condition 2) {
statement 2; //executes when condition 2 is true
}
else {
statement 2; //executes when all the conditions are false
}

Compiled by : Mrs. Foram Shah 16

Example:
public class Student {
public static void main(String[] args) {
String city = "Delhi";
if(city == "Meerut") {
[Link]("city is meerut");
}else if (city == "Noida") {
[Link]("city is noida");
}else if(city == "Agra") {
[Link]("city is agra");
}else {
[Link](city);
}
}
}
Compiled by : Mrs. Foram Shah 17
Nested if-statement
• In nested if-statements, the if statement can contain
a if or if-else statement inside another if or else-if statement.
• Syntax
if(condition 1) {
statement 1; //executes when condition 1 is true
if(condition 2) {
statement 2; //executes when condition 2 is true
}
else{
statement 2; //executes when condition 2 is false
}
}
Compiled by : Mrs. Foram Shah 18
Example
public class Student {
public static void main(String[] args) {
String address = "Delhi, India";

if([Link]("India")) {
if([Link]("Meerut")) {
[Link]("Your city is Meerut");
}else if([Link]("Noida")) {
[Link]("Your city is Noida");
}else {
[Link]([Link](",")[0]);
}
}else {
[Link]("You are not living in India");
}
}
}
Compiled by : Mrs. Foram Shah 19
Switch Statement:
• In Java, Switch statements are similar to if-else-if statements. The switch
statement contains multiple blocks of code called cases and a single case is
executed based on the variable which is being switched. The switch statement is
easier to use instead of if-else-if statements. It also enhances the readability of
the program.
• Points to be noted about switch statement:
• The case variables can be int, short, byte, char, or enumeration. String type is also
supported since version 7 of Java
• Cases cannot be duplicate
• Default statement is executed when any of the case doesn't match the value of
expression. It is optional.
• Break statement terminates the switch block when the condition is satisfied.
It is optional, if not used, next case is executed.
• While using switch statements, we must notice that the case expression will be of
the same type as the variable. However, it will also be a constant value.

Compiled by : Mrs. Foram Shah 20

Syntax
switch (expression){
case value1:
statement1;
break;
.
.
.
case valueN:
statementN;
break;
default:
default statement;
} Compiled by : Mrs. Foram Shah 21
 Example
public class Student implements Cloneable {
public static void main(String[] args) {
int num = 2;
switch (num){
case 0:
[Link]("number is 0");
break;
case 1:
[Link]("number is 1");
break;
default:
[Link](num);
}
}
} Compiled by : Mrs. Foram Shah 22
Loop Statements
• In programming, sometimes we need to execute the block of code repeatedly
while some condition evaluates to true. However, loop statements are used to
execute the set of instructions in a repeated order. The execution of the set of
instructions depends upon a particular condition.
• In Java, we have three types of loops that execute similarly. However, there are
differences in their syntax and condition checking time.
• for loop
• while loop
• do-while loop

Compiled by : Mrs. Foram Shah 23

for loop
• It enables us to initialize the loop variable, check the condition, and
increment/decrement in a single line of code. We use the for loop
only when we exactly know the number of times, we want to execute
the block of code.
• Syntax
for(initialization, condition, increment/decrement) {
//block of statements
}

Compiled by : Mrs. Foram Shah 24

Example
public class Calculattion {
public static void main(String[] args) {
// TODO Auto-generated method stub
int sum = 0;
for(int j = 1; j<=10; j++) {
sum = sum + j;
}
[Link]("The sum of first 10 natural numbers is " + sum);
}
}

Compiled by : Mrs. Foram Shah 25

for-each loop
• Java provides an enhanced for loop to traverse the data structures like
array or collection. In the for-each loop, we don't need to update the
loop variable. The syntax to use the for-each loop in java is given
below.
• Syntax
for(data_type var : array_name/collection_name){
//statements
}

Compiled by : Mrs. Foram Shah 26

Example:
public class Calculation {
public static void main(String[] args) {
// TODO Auto-generated method stub
String[] names = {"Java","C","C++","Python","JavaScript"};
[Link]("Printing the content of the array names:\n");
for(String name:names) {
[Link](name);
}
}
}

Compiled by : Mrs. Foram Shah 27

while loop
• The while loop is also used to iterate over the number of statements multiple
times. However, if we don't know the number of iterations in advance, it is
recommended to use a while loop. Unlike for loop, the initialization and
increment/decrement doesn't take place inside the loop statement in while loop.
• It is also known as the entry-controlled loop since the condition is checked at the
start of the loop. If the condition is true, then the loop body will be executed;
otherwise, the statements after the loop will be executed.
• Syntax:
while(condition){
//looping statements
}

Compiled by : Mrs. Foram Shah 28

 public class Calculation {
public static void main(String[] args) {
// TODO Auto-generated method stub
int i = 0;
[Link]("Printing the list of first
10 even numbers \n");
while(i<=10) {
[Link](i);
i = i + 2;
}
}
}

Compiled by : Mrs. Foram Shah 29

do-while loop
• The do-while loop checks the condition at the end of the loop after
executing the loop statements. When the number of iteration is not known
and we have to execute the loop at least once, we can use do-while loop.
• It is also known as the exit-controlled loop since the condition is not
checked in advance.
• Syntax:
do
{
//statements
} while (condition);

Compiled by : Mrs. Foram Shah 30

public class Calculation {
public static void main(String[] args) {
// TODO Auto-generated method stub
int i = 0;
[Link]("Printing the list of first 10 even numbers \n");
do {
[Link](i);
i = i + 2;
}while(i<=10);
}
}
Compiled by : Mrs. Foram Shah 31
Jump Statements
• Jump statements are used to transfer the control of the program to
the specific statements. In other words, jump statements transfer the
execution control to the other part of the program. There are two
types of jump statements in Java, i.e., break and continue.
• Java break statement
• As the name suggests, the break statement is used to break the
current flow of the program and transfer the control to the next
statement outside a loop or switch statement. However, it breaks only
the inner loop in the case of the nested loop.
• The break statement cannot be used independently in the Java
program, i.e., it can only be written inside the loop or switch
statement.
Compiled by : Mrs. Foram Shah 32
The break statement example with for loop
public class BreakExample {

public static void main(String[] args) {

// TODO Auto-generated method stub
for(int i = 0; i<= 10; i++) {
[Link](i);
if(i==6) {
break;
}
}
}
}

Compiled by : Mrs. Foram Shah 33

break statement example with labeled for loop
public class Calculation {
public static void main(String[] args) {
// TODO Auto-generated method stub
a:
for(int i = 0; i<= 10; i++) {
b:
for(int j = 0; j<=15;j++) {
c:
for (int k = 0; k<=20; k++) {
[Link](k);
if(k==5) {
break a;
}
}
}
}
}
Compiled by : Mrs. Foram Shah 34
}
continue statement
• Unlike break statement, the continue statement doesn't break the loop,
whereas, it skips the specific part of the loop and jumps to the next iteration
of the loop immediately.
public class ContinueExample {
public static void main(String[] args) {
// TODO Auto-generated method stub
for(int i = 0; i<= 2; i++) {
for (int j = i; j<=5; j++) {
if(j == 4) {
continue;
}
[Link](j);
}
}
}
}
Compiled by : Mrs. Foram Shah 35
 Array
● Normally, an array is a collection of similar type of elements which has contiguous
memory location.
● Java array is an object which contains elements of a similar data type.
● Additionally, The elements of an array are stored in a contiguous memory location.
● It is a data structure where we store similar elements.
● We can store only a fixed set of elements in a Java array.
● Array in Java is index-based, the first element of the array is stored at the 0th index,
2nd element is stored on 1st index and so on.

Compiled by : Mrs. Foram Shah 36

Array -Indicing
● In Java, array is an object of a dynamically generated class.
● Java array inherits the Object class, and implements the Serializable as well
as Cloneable interfaces.
● We can store primitive values or objects in an array in Java.
● Like C/C++, we can also create single dimensional or multidimensional arrays
in Java.

37
Advantages and disadvantages
Advantages:
○ Code Optimization: It makes the code optimized, we can retrieve or sort the data
efficiently.
○ Random access: We can get any data located at an index position.

Disadvantages

○ Size Limit: We can store only the fixed size of elements in the array. It doesn't grow its size
at runtime. To solve this problem, collection framework is used in Java which grows
automatically.

38
Types of Array in java
There are two types of array.

○ Single Dimensional Array

○ Multidimensional Array

Single Dimensional Array in Java

Syntax to Declare an Array in Java
1. dataType[] arr; (or)
2. dataType []arr; (or)
3. dataType arr[];

Instantiation of an Array in Java

1. arrayRefVar=new datatype[size];

Example of Java Array

Let's see the simple example of java array, where we are going to declare, instantiate, initialize and traverse an
array.
39
 declare, instantiate, initialize and traverse an array

1. class Testarray{
2. public static void main(String args[]){
3. int a[]=new int[5];//declaration and instantiation
4. a[0]=10;//initialization
5. a[1]=20;
6. a[2]=70;
7. a[3]=40;
8. a[4]=50;
9. //traversing array
10. for(int i=0;i<[Link];i++)//length is the property of array
11. [Link](a[i]);
12. }}
40
Passing Array to a Method in Java
1. class Testarray2{
2. //creating a method which receives an array as a parameter
3. void minimum(int arr[])
4. {
int min=arr[0];
for(int i=1;i<[Link];i++)
if(min>arr[i])
min=arr[i];
[Link](min);
1. }
2.
3. public static void main(String args[]){
4. int a[]={33,3,4,5};//declaring and initializing an array
5. minimum(a);//passing array to method
6. }} 41
2D Array

Declaring 2-D array in Java:

Any 2-dimensional array can be declared as follows:
Syntax:
data_type array_name[][]; (OR) data_type[][] array_name;
42
Program
import [Link].*;
class GFG {
public static void main(String[] args)
{
int[][] integer2DArray; // 2D integer array
String[][] string2DArray; // 2D String array
double[][] double2DArray; // 2D double array
boolean[][] boolean2DArray; // 2D boolean array
float[][] float2DArray; // 2D float array
double[][] double2DArray; // 2D double array
}
}
43
Programs:
1) Write a program that inputs a 2D array and displays how the
array elements will look in row major form and column major
form.
2) Write a program to sort the given array using bubble sort
technique. Give the array-status after every iteration.

44
Strings
Character functions
[Link]

String functions
[Link]

45
String Programs

46
Vectors
[Link]

47
Class and objects, Methods

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

Compiled by : Mrs. Foram Shah 50

Types of Data structure
 Linear Data Structure
• A Linear data structure have data elements arranged in sequential manner and
each member element is connected to its previous and next element.
• This connection helps to traverse a linear data structure in a single level and in
single run.
• Such data structures are easy to implement as computer memory is also
sequential.
• Examples of linear data structures are List, Queue, Stack, Array etc.
Array
• 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.
• Example:
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
• 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 Structure
• A non-linear data structure has no set sequence of connecting all its
elements and each element can have multiple paths to connect to other
elements.
• Such data structures supports multi-level storage and often cannot be
traversed in single run.
• Such data structures are not easy to implement but are more efficient in
utilizing computer memory.
• Examples of non-linear data structures are Tree, BST, Graphs etc.
Tree
• Trees are multilevel data structures with a
hierarchical relationship among its elements
known as nodes.
• The bottom most nodes in the hierarchy are
called leaf node while the topmost node is
called root node.
• Each node contains pointers to point
adjacent nodes.
• Tree data structure is based on the
parent-child relationship among the nodes.
• Each node in the tree can have more than
one children except the leaf nodes whereas
each node can have at most one parent
except the root node
Graph
• Graphs can be defined as the pictorial representation of the set of elements
(represented by vertices) connected by the links known as edges.
• A graph is different from tree in the sense that a graph can have cycle while
the tree cannot have the one.
Abstract Data type
• The Data Type is basically a type of data that can be used in different computer
program.
• It signifies the type like integer, float etc, the space like integer will take 4-bytes,
character will take 1-byte of space etc.
• The abstract data type is special kind of datatype, whose behaviour is defined by
a set of values and set of operations.
• The keyword “Abstract” is used as we can use these data types, we can perform
different operations. But how those operations are working that is totally hidden
from the user.
• The ADT is made of with primitive data types, but operation logics are hidden.
• Some examples of ADT are Stack, Queue, List etc.
 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 divide 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.
 Operations on Data Structure
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
Compiled by : Mrs. Foram Shah 63