Data Structures Throw Java M.tech Lab

      Data Structures throw Java Lab Programs

                                    Meerja Maqbul Baig
                                     M.tech Computer science
                                     www.mtechnotesall.blogspot.com
----------------------------------------------------------------------------------------------------                        

Contents
Prg Program Statement Page
1 Write a Java program that prints all real solutions to the quadratic equation
ax2
 + bx + c = 0. Read in a, b, c and use the quadratic formula. If the
discriminant (b2
– 4ac) is negative; display a message stating that there are no
real solutions.
1
2 The Fibonacci sequence is defined by the following rule: The first two values
in the sequence are 0 and 1. Every subsequent value is the sum of the two
values preceding it. Write a Java program that uses both recursive and nonrecursive
functions to print the nth value in the Fibonacci sequence.
3
3 Write a Java program that prompts the user for an integer and then prints out
all prime numbers up to that integer.
4
4 Write a Java program that checks whether a given string is a palindrome or
not. For example, “MADAM” is a palindrome.
6
5 Write a Java program for sorting a given list of names in ascending order. 7
6 Write a Java program to multiply two given matrices. 8
7 Write a Java Program that reads a line of integers, and then displays each
integer, and the sum of all the integers (use StringTokenizer class).
9
8 Write a Java program that reads a file name from the user then displays
information about whether the file exists, whether the file is readable, whether
the file is writable, the type of file and the length of the file in bytes.
11
9 Write a Java program that reads a file and displays the contents of the file on
the screen, with a line number before each line.
12
10 Write a Java program that displays the number of characters, lines and words
in a text file.
13
11 Write a Java program for creating multiple threads.
(a) Using Thread class
(b) Using Runnable interface
14
12 Write a Java program that illustrates how run time polymorphism is achieved. 16
13 Write a java program that illustrates the following:
(a) Creation of simple package.
(b) Accessing a package.
(c) Implementing interfaces.
17
14 Write a java program that illustrates the following
(a) Handling predefined exceptions
(b) Handling user defined exceptions
19
15 Write Java programs that use both recursive and non-recursive functions for
implementing the following searching methods:
(a) Linear search
(b) Binary search
22
16 Write Java programs to implement the List ADT using arrays and linked lists. 25
17 Write Java programs to implement the following using an array.
(a) Stack ADT
(b) Queue ADT
32
18 Write a java program that reads an infix expression, converts the expression
to postfix form and then evaluates the postfix expression (use stack ADT).
37
19 Write a java program that determines whether parenthetic symbols ( ), { } and
[ ] are nested correctly in a string of characters(use stack ADT).
40
20 Write a java program that uses both stack and queue to test whether the given
string is a palindrome.
41
21 Write Java programs to implement the following using a singly linked list.
(a) Stack ADT
(b) Queue ADT
43
22 Write Java programs to implement the deque (double ended queue) ADT
using
(a) Array
(b) Doubly linked list.
47
23 Write a Java program to implement priority queue ADT. 53
24 Write Java programs that use recursive and non-recursive functions to
traverse the given binary tree in
(a) Preorder
(b) Inorder and
(c) Postorder.
56
25 Write a Java program that displays node values in a level order traversal
(Traverse the tree one level at a time, starting at the root node) for a binary
tree.
60 26 Write a Java program that uses recursive functions.
(a) To create a binary search tree.
(b) To count the number of leaf nodes.
(c) To copy the above binary search tree.
63
27 Write a Java program to perform the following operations:
(a) Insert an element into a binary search tree.
(b) Delete an element from a binary search tree.
(c) Search for a key element in a binary search tree.
 63
28 Write a Java program to perform the following operations
(a) Insertion into an AVL-tree
(b) Deletion from an AVL-tree
66
29 Write a Java program to perform the following operations:
(a) Insertion into a B-tree
(b) Deletion from a B-tree
71
30 Write a Java program to implement all the functions of a dictionary (ADT)
using Hashing.
 76
31 Write Java programs for the implementation of bfs and dfs for a given graph. 81
32 Write Java programs for implementing the following sorting methods:
(a) Bubble sort
(b) Selection sort
(c) Insertion sort
(d) Quick sort
(e) Merge sort
(f) Heap sort
(g) Radix sort
(h) Binary tree sort
 85
33 Write a Java program for implementing KMP pattern matching algorithm. 98 Overview of Java
This section introduces the students to elementary Java. Java is a vast computer language and programming
environment, it is not possible to touch upon all Java-related issues. This section introduces only those
aspects of Java that are necessary for understanding the Java code offered in this book. Java program
examples presented in this section give you to implement data structures.
Quadratic equation
1. Write a Java program that prints all real solutions to the quadratic equation ax2
 + bx + c = 0.
Read in a, b, c and use the quadratic formula. If the discriminant (b2
– 4ac) is negative; display
a message stating that there are no real solutions.
The roots of the quadratic equation, ax2
 + bx + c = 0 are given by:
x = [–b ± √(b2
 – 4ac) ]/2a
The discriminant, d = (b2
 – 4ac)
Case (1): When d is greater than zero, the two roots are real.
x1 = (–b + √d )/2a and x2 = (–b – √d )/2a
Case (2): When d is equal to zero, the two roots are equal.
x1 = x2 = – b /2a
Case (3): When d is less than zero, the two roots are imaginary. Each of the two roots has two
 parts: real-part-1, imaginary-part-1 and real-part-2, imaginary-part-2.
real-part-1, xr1 = –b/2a imaginary-part-1, xi1 = +√d /2a
 real-part-2, xr2 = –b/2a imaginary-part-2, xi2 = –√d /2a
Program 1: Roots of a quadratic equation
import java.lang.Math;
import java.util.Scanner;
class QuadraticEquation
{
 double a, b, c; // coefficients

 QuadraticEquation( double a, double b, double c)
 {
 this.a = a;
 this.b = b;
 this.c = c;
 }
 public void roots()
 {
 if( a == 0.0 )
 { System.out.println("One root = " + (-c/b));
 return;
 }
 double d = b*b - 4.0*a*c; 2 Lab Manual Data Structures through Java
 if(d < 0) // Roots are imaginary
 {
 System.out.println("There are no real solutions.");
 return;
 }

 if(d == 0) // Roots are equal
 {
 System.out.println("Two roots are equal: " + (-b /(2.0*a)));
 return;
 }
 // Roots are real
 double x1 = (-b + Math.sqrt(d))/(2.0*a);
 double x2 = (-b - Math.sqrt(d))/(2.0*a);
 System.out.println("Roots are: " + x1 + ", " + x2);
 }
}
//////////////////// QuadraticEquationDemo.java /////////////////
class QuadraticEquationDemo
{
 public static void main(String[] args)
 {
 Scanner scr = new Scanner(System.in);

 System.out.print(" a = ");
 double a = scr.nextDouble();
 System.out.print(" b = ");
 double b = scr.nextDouble();
 System.out.print(" c = ");
 double c = scr.nextDouble();
 QuadraticEquation qe = new QuadraticEquation(a, b, c);
 qe.roots();
 }
}
Output of this program is as follows (for different values of a, b, and c):
a = 0
b = 4
 c = 1
One root = -0.25
a = 1
b = 4
c = 4
Two roots are equal: -2.0
a = 1
b = 4
c = 8
There are no real solutions
a = 1
b = 4
c = 3  1. Overview of Java

3
Roots are: -1.0, -3.0
Fibonacci sequence
2. The Fibonacci sequence is defined by the following rule: The first two values in the sequence
are 0 and 1. Every subsequent value is the sum of the two values preceding it. Write a Java
program that uses both recursive and non-recursive functions to print the nth value in the
Fibonacci sequence.
The Fibonacci sequence (denoted by f0, f1, f2 …) is as follows:
 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 …
That is, f0 = 0 and f1 = 1 and each succeeding term is the sum of the two preceding terms. For example,
the next two terms of the sequence are
 34 + 55 = 89 and 55 + 89 = 144
Many algorithms have both iterative and recursive formulations. Typically, recursion is more elegant
and requires fewer variables to make the same calculations. Recursion takes care of its book-keeping
by stacking arguments and variables for each method call. This stacking of arguments, while invisible
to the user, is still costly in time and space.

Fibonacci sequence is recursively defined by
f0 = 0, f1 = 1, fi+1 = fi + fi-1 for i = 1, 2 …
Fibonacci class is implemented in Program 2, with iterative and recursive methods, and tested by
main() driver.
Program 2: Fibonacci sequence

import java.io.*;
class Fibonacci
{
public int fibonacciSeq(int n) // Iterative method
 {
 int term1 = 0, term2 = 1, nextTerm = 0;

 if( n == 0 || n == 1) return n;
 int count = 2;
 while( count <= n )
 {
 nextTerm = term1 + term2;
 term1 = term2;
 term2 = nextTerm;
 count++;
 }
 return nextTerm;
 }
 public int recFibonacciSeq(int n) // Recursive method4 Lab Manual Data Structures through Java
{
 if( n == 0 || n == 1) return n;
 else
 return( recFibonacciSeq(n-1) + recFibonacciSeq(n-2) );
 }
}
/////////////////// FibonacciDemo.java ////////////////////////
class FibonacciDemo
{
 public static void main(String[] args) throws IOException
 {
 Fibonacci fib = new Fibonacci();

 BufferedReader kb = new
 BufferedReader(new InputStreamReader(System.in));
 // nth value in the Fibonacci sequence System.out.print("Enter n: ");
 int n = Integer.parseInt(kb.readLine());

 System.out.println("Iterative method: Fibonacci number "
+ n + " is " + fib.fibonacciSeq(n) );
 System.out.println("Recursive method: Fibonacci number "
+ n + " is " + fib.recFibonacciSeq(n) );
 }
 }
Output of this program is:
Enter n: 12
 Iterative method: Fibonacci number 12 is 144
 Recursive method: Fibonacci number 12 is 144
Prime numbers
3. Write a Java program that prompts the user for an integer and then prints out all prime
numbers up to that integer.
A prime number is a positive integer that is exactly divisible only by 1 and itself. The first few prime
numbers are:
 2 3 5 7 11 13 17 23 29 31 37 …
All primes apart from 2 are odd.
As a starting point in developing the prime number generator let us explore how we can establish
whether or not a particular number is a prime. To do this, let us consider a number 13. The definition
of prime number suggests that to determine whether or not 13 is prime, we need to divide it in turn by
the set of numbers 2, 3, 4, 5 …12. If any of these numbers divide into 13 without remainder we will
know it cannot be prime number. Therefore, to test an integer n for prime, n-2 calls to the mod
operation are required. As our n is 13, we need 11 calls. As n grows, the cost of making these divisions
and tests is going to get very expensive. We must therefore look for ways of improving the efficiency
of the algorithm. Firstly, we can try to keep to a minimum the number of numbers that we have to test
for primes, and secondly we can try to improve the efficiency of testing a number for prime.  1. Overview of Java

5
Following up these suggestions, we know that apart from 2, we do not need to examine any of the
even numbers, and only first half of the numbers is enough for testing prime. That is, we can test for
mod operation with numbers, from 3 to n/2. Hence, the following set of numbers is sufficient to test 13
for prime.
 3 4 5 6
Program 3: Prime numbers
import java.io.*;
class PrimeNumber
{
 public void primes(int n)
 {
 int k, m;
 System.out.print("Prime numbers up to " + n + ": 2 3");
 for(m=3; m <= n; m = m+2)
 {
 boolean isPrime = false;
 for(k=2; k <= m/2; k++)
 {
 if(m % k == 0) { isPrime = false; break; }
 else isPrime = true;
 }
 if(isPrime) System.out.print(" " + m);
 }
 }
}
////////////////////////// PrimeNumberDemo.java /////////////////
class PrimeNumberDemo
{
 public static void main(String[] args) throws IOException
 {
 PrimeNumber pn = new PrimeNumber();
 BufferedReader kb = new
 BufferedReader(new InputStreamReader(System.in));
 System.out.print("Enter n: ");
 int n = Integer.parseInt(kb.readLine());
 pn.primes(n);
 }
}
Output:
Enter n: 50
Prime numbers up to 50: 2 3 5 7 11 13 17 19 23 29 31 37
41 43 476 Lab Manual Data Structures through Java
Palindrome
4. Write a Java program that checks whether a given string is a palindrome or not. For example,
“MADAM” is a palindrome.
A string is an array of characters. For example, the string “MADAM” is stored as follows:
[0] [1] [2] [3] [4]
M A D A M
Java supports the manipulation of character data through the primitive data type char and the
associated operations for the input, output, assignment, and comparison of characters. Most
applications of character data require character sequences - or strings - rather than individual
characters. In Java a string is represented by the built-in class String. However, manipulating a
String data type in Java is quite different from manipulating a set (or array) of characters. In the
Java, strings are objects. The Java platform provides the String class to create and manipulate
strings. The most direct way to create a string is to write:
String str = "MADAM";
In this case, "MADAM" is a string literal - a series of characters that is enclosed in double quotes. The
String class provides the method length(), which returns as an int value the number of
characters in the String object. The method of the String class
char charAt(int n)
returns the nth character in a string (where n must be less than string length);
 If the first character is equal to the last character of the string, second character is equal to the
second one from the last character of the string, and so on, then the string is a palindrome.
Program 4: Palindrome
class Palindrome
{
 public boolean isPalindrome(String str)
 {
 System.out.print("Given string: " + str);
 int n = str.length();
 boolean flag = true;
 for( int i=0; i < n/2; i++ )
 if( str.charAt(i) != str.charAt(n-i-1) ) flag = false;
 return flag;

 }
}
////////////////////////// PalindromeDemo.java ////////////////////
class PalindromeDemo
{
 public static void main(String[] args)
 {  1. Overview of Java

7
 Palindrome pal = new Palindrome();
 String str = "MADAM";
 if( pal.isPalindrome(str))
 System.out.print(" is a palindrome.");
 else
 System.out.print(" is not a palindrome.");

 }
 }
Output of this program is: (Note: You may test the program for different character strings).
Given string: MADAM is a palindrome.
Sorting names
5. Write a Java program for sorting a given list of names in ascending order.
Bubble sort algorithm is used to sort the names.
Program 5: Sorting strings
class SortNames
{
 public void sort(String[] a)
 {
 int i, pass, n = a.length;
 String tmp;

 for( pass = 0; pass < n; pass++ )
 {
 for( i = 0; i < n-pass-1; i++ )
 if( ((Comparable)a[i]).compareTo(a[i+1]) > 0)
 {
 tmp = a[i]; // Swap a[i], a[i+1]
 a[i] = a[i+1];
 a[i+1] = tmp;
 }
 }
 }
}
////////////////////////// SortNamesDemo.java ////////////////////
class SortNamesDemo
{
 public static void main(String[] args)
 {
 SortNames sn = new SortNames();
 String[] names =
 {"Ramu", "John", "Anu", "Priya", "Basha", "Prem"};

 int i;
 System.out.println("Unsorted names:"); 8 Lab Manual Data Structures through Java
 for(i=0; i < names.length; i++)
 System.out.println(names[i]);
 sn.sort(names);
 System.out.println("Sorted names:");
 for(i=0; i < names.length; i++)
 System.out.println(names[i]);
 }
 }
Output of this program is:
Unsorted names:
Ramu
John
Anu
Priya
Basha
Prem
Sorted names:
Anu
Basha
John
Prem
Priya
 Ramu
Matrix multiplication
6. Write a Java program to multiply two given matrices.
If the order of matrix A is m x n and of matrix B is n x p (number of columns of A = number of rows
of B = n), then the order of matrix C is m x p, where C = A x B.
 k=n-1
cij = ∑aikbkj for i = 0 to m, and j = 0 to p
 k=0

Example: The following two matrices A and B are used in the program to multiply A by B.
 3 2 0
A = 1 5 1
2 3 4
 2 0 1 1
B = 1 3 0 3
2 2 2 1
Program 6: Matrix multiplication
class MatrixMultiplication
{
 public void matrixMult( int[][] a, int[][] b, int[][] c)
 {
 int i, j, k;  1. Overview of Java

9
 for ( i = 0; i < 3; i++ )
 for ( j = 0; j < 4; j++ )
 { c[i][j] = 0;
 for ( k = 0; k < 3; k++ )
 c[i][j] = c[i][j] + a[i][k] * b[k][j];
 }
 }
}
////////////////////////// MatrixMultiplicationDemo.java //////////
class MatrixMultiplicationDemo
{
 public static void main(String[] args)
 {
 int[][] a = { {3, 2, 0}, {1, 5, 1}, {2, 3, 4} };
 int[][] b = { {2, 0, 1, 1}, {1, 3, 0, 3}, {2, 2, 2, 1} };
 int[][] c;
 c = new int[3][4];
 int i, j;
 MatrixMultiplication mm = new MatrixMultiplication();
 mm.matrixMult(a,b,c);
 System.out.println("matrix C (3 x 4)= A x B :");
 for( i = 0; i < 3; i++ )
 { System.out.println();
 for( j = 0; j < 4; j++ )
 System.out.print( c[i][j] + "\t" );
 }
 }
 }
This program generated the following output:
matrix C (3 x 4)= A x B :
 8 6 3 9
 9 17 3 17
 15 17 10 15

StringTokenizer

7. Write a Java Program that reads a line of integers, and then displays each integer, and the
sum of all the integers (use StringTokenizer class).
The processing of data often consists of parsing a formatted input data (or string). The string
tokenizer class allows an application to break a string into tokens. The discrete parts of a string are
called tokens. The StringTokenizer methods do not distinguish among identifiers, numbers, and
quoted strings, nor do they recognize and skip comments. The set of delimiters (the characters that
separate tokens) may be specified either at creation time or on a per-token basis. StringTokenizer
implements the Enumeration interface. Therefore, given an input string, we can enumerate the
individual tokens contained in it using StringTokenizer. The default delimiters are whitespace 10 Lab Manual Data Structures through Java
characters: space, tab, newline, and carriage return. Other than default delimiters, each character in the
delimiters string is considered a valid delimiter.
A StringTokenizer object internally maintains a current position within the string to be
tokenized. Some operations advance this current position past the characters processed. A token is
returned by taking a substring of the string that was used to create the StringTokenizer object. The
following is one example of the use of the tokenizer. The code:
 StringTokenizer st = new StringTokenizer("this is a test");
 while (st.hasMoreTokens())
{
 System.out.println(st.nextToken());
 }

prints the following output: (Here, space is the default delimiter)
 this
 is
 a
 test

StringTokenizer is a legacy class that is retained for compatibility reasons although its use is
discouraged in new code.
StringTokenizer constructors are:
StringTokenizer(String str)
StringTokenizer(String str, String delimiters)
Program 7: StringTokenizer
import java.util.StringTokenizer;
import java.io.*;
class StringTokenizerDemo
{
 public static void main(String[] args) throws IOException
 {
 BufferedReader kb = new
 BufferedReader(new InputStreamReader(System.in));
 System.out.print("Enter a string of digits: ");
 String str = kb.readLine();
 StringTokenizer st = new StringTokenizer(str);
 int a, sum = 0;
 String s;
 while (st.hasMoreTokens())
 {
 s = st.nextToken();
 a = Integer.parseInt(s);
 sum = sum + a;
 System.out.println(a);
 }
 System.out.println("Sum of these integers = " + sum);  1. Overview of Java

11
 }
}
This program prints the following output:
Enter a string of digits: 45 100 750 5
 45
100
750
 5
Sum of these integers = 900
File class
8. Write a Java program that reads a file name from the user then displays information about
whether the file exists, whether the file is readable, whether the file is writable, the type of file
and the length of the file in bytes.
Most of the classes defined by java.io operate on streams. The File class deals directly with
files and the file system. That is, the File class does not specify how data is retrieved from or stored
in files; it describes the properties of a file itself. A File object is used to get information or
manipulate the information associated with a disk file; such as the permissions, time, date, directory
path, is it readable or writable, file size, and so on.
Files are a primary source and destination for data within many programs. Files are central
resource for storing persistent and shared information.
The following two constructors can be used to create File objects (we have two more
constructors):
File(String directoryPath)
File(String directoryPath, String fileName)
 Here, directoryPath is the path name of the file, fileName is the name of the file.
File class defines many methods that obtain the standard properties of a File object. For
example, getName() returns the file name, and exists() returns true if the file exists, false if it
does not. The File class has many methods that allow us to examine the properties of a sample file
object. Program 8 illustrates some of the File methods. In this example program, an existing
“HashSetDemo.java” file is used.
Many times a program will be developed that requires the user to enter a small amount of
information at the terminal keyboard. The information may consist of number of data elements to be
used in an array. Rather than having the program request this type of data from the user, we can supply
the information to the program at the time of program execution. This capability is provided by what is
known as command line arguments.
The main(String[] args) is a method that has arguments. The parameter args stands for
argument vector. It is an array of strings. The successive elements of the array refer to successive
words in the command line. We can pass arguments to main() method. Java provides a connection to
the arguments on the command line. We illustrate “passing command line arguments to main()”
through the following example. 12 Lab Manual Data Structures through Java
D:\Java>java FileDemo HashSetDemo.java
The string “HashSetDemo.java” is stored in args[0]. If we supply second string on command line,
it will be stored in args[1], and so on.
Program 8: Demonstration of File class
import java.io.File;
class FileDemo
{
 public static void main(String[] args)
 {
 File f = new File(args[0]);
 System.out.println("File name: " + f.getName());
 System.out.println(f.exists() ? "exists" : "does not exist");
 System.out.println(f.canWrite() ? "is writable" : "is not writable");
 System.out.println(f.canRead() ? "is readable" : "is not readable");
 System.out.println(f.isFile()? "is normal file" : "might be a pipe");
 System.out.println("File size (in bytes): " + f.length());
 }
}
This program, FileDemo is executed as follows:
D:\Java>java FileDemo HashSetDemo.java
Output of this program is:
File name: HashSetDemo.java
exists
is writable
is readable
is normal file
File size (in bytes): 258
Note: Most of the File methods are self-explanatory.
FileInputStream class
9. Write a Java program that reads a file and displays the contents of the file on the screen, with
a line number before each line.
The FileInputStream class creates an InputStream that we can use to read bytes from a file. The
most common constructors are:
FileInputStream(String filePath)
FileInputStream(String fileObject)
Here, filePath is the full path name of a file, and fileObject is a File object that describes the file.
When a FileInputStream is created, it is opened for reading. For example,  1. Overview of Java

13
InputStream f = new FileInputStream("HashSetDemo.java");
creates a File object, f for reading. This object refers to the file: "HashSetDemo.java". The
following program demonstrates the FileInputStream.
Program 9: FileInputStream
import java.io.*;
class FileInputStreamDemo
{
 public static void main(String[] args) throws IOException
 {
 InputStream f = new FileInputStream("HashSetDemo.java");
 int size = f.available(); // file size in bytes
 int lineNo = 0;
 char ch;

 System.out.print(++lineNo + ": "); // print line 1:
 ch = (char)f.read(); // read first character of line 1
 System.out.print(ch); // print first character of line 1
 for(int i=1; i < size; i++) // read next character & print
 {
 if( ch == '\n' ) // if it is a newline,
 System.out.print(++lineNo + ": "); // print line number

 ch = (char)f.read(); // read next character
 System.out.print(ch); // print next character
 }
 }
}
Output of this program is:
1: import java.util.*;
2: public class HashSetDemo
3: { public static void main(String[] args)
4: {
5: HashSet<Integer> hs = new HashSet<Integer>();
6:
7: for( int k = 1; k <= 5; k++ )
8: hs.add(11*k);
9:
10: System.out.println("HashSet: " + hs);
11: }
12: }
Counting characters, words, and lines in a text file
10. Write a Java program that displays the number of characters, lines and words in a text file. 14 Lab Manual Data Structures through Java
Program 10: Number of characters, lines and words in a text file
import java.io.*;
class TextFileDemo
{
 public static void main(String[] args) throws IOException
 {
 InputStream f = new FileInputStream("MYDATA.TXT");
 int size = f.available();
 int nLines = 0;
 int nWords = 0;
 char ch;
 System.out.println("Data file: MYDATA.TXT
contains the following text:\n");
 for(int i=0; i < size; i++)
 {
 ch = (char)f.read();
 System.out.print(ch);
 if( ch == ' ' ) nWords++;
 if( ch == '\n' ) nLines++;
 }
 nWords++; // to count the last word in the text file
 System.out.println("\nNo: of characters = " + size);
 System.out.println("No: of words = " + nWords);
 System.out.println("No: of lines = " + nLines);
 }
}
The following output is generated by this program:
Data file: MYDATA.TXT contains the following text:
Real-life applications require that the data be written to or read
from secondary storage devices. The secondary storage devices are
also called auxiliary storage devices such as hard disk, compact disk,
floppy, and magnetic tape. The data is permanently stored on these
devices in the form of data files. Once data is available on these
devices, we can access and change it whenever required.
No: of characters = 405
No: of words = 64
No: of lines = 6
Multiple Threads
11. Write a Java program for creating multiple threads.
(a) Using Thread class
(b) Using Runnable interface  1. Overview of Java

15
Refer Chapter 6: Multi-Threading to understand thread class, Runnable interface and multiple
threads.
Program 11: Multiple threads using Runnable interface
// create multiple threads
class AThread implements Runnable
{ String name;
 Thread th;
 AThread( String threadName)
 { name = threadName;
 th = new Thread(this, name);
 System.out.println("A Thread: " + th);
 th.start();
 }
 public void run() // entry point for the thread
 { try
 { for(int k = 3; k > 0; k--)
 { System.out.println(name + ":" + k);
 Thread.sleep(1000);
 }
 } catch(InterruptedException e)
 { System.out.println(name + "Interrupted"); }
 System.out.println(name + " exiting");
 }
}
/////////////////// MultiThreadDemo.java ////////////////////
class MultiThreadDemo
{ public static void main(String[] args)
 { new AThread("One"); // start threads
 new AThread("Two");
 new AThread("Three");
 try
 { Thread.sleep(10000); // wait for others to end
 } catch(InterruptedException e)
 { System.out.println("Main thread Interrupted"); }
 System.out.println("Main thread exiting");
 }
}
Output:
A Thread: Thread[One,5,main]
A Thread: Thread[Two,5,main]
One:3
Two:3
A Thread: Thread[Three,5,main]
Three:3
One:2
Two:2
Three:2
One:1
Two:1
Three:1
One exiting
Two exiting
Three exiting
Main thread exiting 16 Lab Manual Data Structures through Java
Run-time Polymorphism
12. Write a Java program that illustrates how run time polymorphism is achieved.
In a class hierarchy, when a method in a subclass has the same name and type signature as a method in
its superclass, then the method in the subclass is said to override the method in the superclass. When
an overridden method is called from within a subclass, it will always refer to the version of that
method defined by the subclass. The version of the method defined by the superclass will be hidden.
Method overriding forms the basis for one of Java’s most powerful concepts: dynamic method
dispatch. Dynamic method dispatch is the mechanism by which a call to an overridden method is
resolved at run-time, rather than compile-time. Dynamic method dispatch is important because this is
how Java implements run-time polymorphism.
A superclass reference variable can refer to a subclass object. Java uses this fact to resolve calls to
overridden methods at run-time. When an overridden method is called through a superclass reference,
Java determines which version of that method to execute based upon the type of object being referred
to at run-time the call occurs. When different types of objects are referred to, different versions of an
overridden method will be called. Here is an example that illustrates dynamic method dispatch:
Program 12: Run-time polymorphism through dynamic dispatch
class Animal
{ void callme()
 { System.out.println("It is an Animal."); }
}
class Cat extends Animal
{ void callme()
 { System.out.println("It is a Cat."); }
}
class Dog extends Animal
{ void callme()
 { System.out.println("It is a Dog."); }
}
class DynamicDispatch
{
public static void main(String[] args)
 {
 Animal a = new Animal(); // create Animal object, a
 Cat c = new Cat(); // create Cat object, c
 Dog d = new Dog(); // create Dog object, d
 Animal ref; // obtain a reference of type Animal
 ref = a; // “ref” refers to Animal object
ref.callme(); // calls Animal’s version of callme()
 ref = c; // “ref” refers to Cat object
ref.callme(); // calls Cat’s version of callme()
 ref = d; // “ref” refers to Dog object
ref.callme(); // calls Dog’s version of callme()
 }
}
Output of this program is:  1. Overview of Java

17
It is an Animal.
It is a Cat.
 It is a Dog.
Packages and Interfaces
13. Write a java program that illustrates the following:
(a) Creation of simple package.
(b) Accessing a package.
(c) Implementing interfaces.
Packages are a feature of Java that helps you to organize and structure your classes and their
relationships to one another. A package is a grouping of related types providing access protection and
name space management. Note that types refer to classes, interfaces and others. The types that are part
of the Java platform are members of various packages that bundle classes by function: fundamental
classes are in java.lang, classes for reading and writing (input and output) are in java.io, and so
on. You can put your types in packages too.
 For example, consider the following package specification:
 package MyPack;
 In order for a program to find MyPack, we use one of the two alternatives:
1. Program is executed from a directory immediately above MyPack, or
2. CLASSPATH must be set to include the path to MyPack.
 SET CLASSPATH =C:\MyPack\
 We create a directory, MyPack below the current development directory, put the .class files into
the MyPack directory, and then execute the program from the development directory.
Program 13(a): A simple package example
package MyPack; // A simple package
class Balance
{
 String name;
 double bal;
 Balance(String s, double b) // constructor
 { name = s;
 bal = b;
 }
 void show() // method
 { if(bal < 0)
 System.out.print("-->> ");
 System.out.println(name + ": Rs" + bal);
 }
}
class AccountBalance
{
 public static void main(String args[])
 { Balance current[] = new Balance[3]; 18 Lab Manual Data Structures through Java
 current[0] = new Balance("R. Lepakshi", 15230.50);
 current[1] = new Balance("K. Siva Kumar", 350.75);
 current[2] = new Balance("Michael Jackson", -120.30);
 for(int i = 0; i < 3; i++) current[i].show();
 }
 }
Let the current development directory be C:\java
Create (make directory: md) MyPack directory as follows:
C:\java>md MyPack
Edit the AccountBalance.java program and compile it from current development directory as
follows:
C:\java>edit AccountBalance.java
 C:\java>javac AccountBalance.java
Then, copy Balance.class and AccountBalance.class files from the directory C:\java to
the directory C:\java\MyPack
Execute the AccountBalance class, using the following command line:
C:\java>java MyPack.AccountBalance
AccountBalance is now part of the package MyPack. This means that it cannot be executed by itself.
That is, we cannot use this command line:
C:\java>java AccountBalance
AccountBalance must be qualified with its package name.
In Java, an interface is a reference type, similar to a class that can contain only constants, method
signatures, and nested types. There are no method bodies. Interfaces cannot be instantiated - they can
only be implemented by classes or extended by other interfaces.
Here is an example of an interface definition (defining an interface is similar to creating a new
class). Program 13(b) declares an interface called Items which contains four methods. Note that the
method signatures have no braces and are terminated with a semicolon.
Program 13(b): Defining an interface Items
interface Items
{ boolean equal(); // test whether two numbers are equal
 int add(); // sum of two numbers
 int max(); // maximum of two numbers
 void display(); // print two numbers
}
To declare a class that implements an interface, you include an implements clause in the class
declaration. Your class can implement more than one interface, so the implements keyword is
followed by a comma-separated list of the interfaces implemented by the class. When an instantiable
class implements an interface, it provides a method body for each of the methods declared in the
interface. Here is an example class Client that implements the Items interface.
Program 13(c): Implementing an interface Items
class Client implements Items
{
 int a, b;  1. Overview of Java

19
 Client( int i, int j) // constructor
 { a = i; b = j; }
 public boolean equal()
 { return (a == b); }
 public int add()
 { return(a + b); }
 public int max()
 { if( a > b ) return a;
 else return b;
 }
 public void display()
 { System.out.println(a + " " + b); }

 public int multiply() // non-interface method
 { return(a * b); }
}
Program 13(d): Testing a class which implements an interface
class ClientDemo
{ public static void main(String[] srgs)
 {
Client ob = new Client(5, 7);
 ob.display();
 if( ob.equal())
 System.out.println("Two numbers are equal");
 else
 System.out.println("Two numbers are not equal");
 System.out.println("Sum of two numbers is " + ob.add());
 System.out.println("Max of two numbers is " + ob.max());
 System.out.println("Product of two numbers is " + ob.multiply());
 }
}
Output of this program is:
5 7
Two numbers are not equal
Sum of two numbers is 12
Max of two numbers is 7
Product of two numbers is 35
Exception Handling
14. Write a java program that illustrates the following
(a) Handling predefined exceptions
(b) Handling user defined exceptions
(a) Java uses exceptions to handle errors and other exceptional events. An exception (error) is an
event, which occurs during the execution of a program, which disrupts the normal flow of the program
instructions. When an error occurs within a method, the method creates an object and hands it off to 20 Lab Manual Data Structures through Java
the runtime system. The object, called an exception object, contains information about the error,
including its type and the state of the program when the error occurred. Creating an exception object
and handing it to the runtime system is called throwing an exception.
The first step in constructing an exception handler is to enclose the code that might throw an
exception within a try block. To illustrate how this can be done, the following program includes a
try block and a catch clause which processes the ArithmeticException generated by “divisionby-zero”
error. This is a RuntimeException, predefined in java.lang.
Program 14(a): Handling predefined exceptions
class ExceptionDemo
{
 public static void main(String args[])
 {
 int a = 25, c = 3, d = 0;
 try
 {
 a = 25 / d;
 System.out.println(a);
 } catch(ArithmeticException ae)
 {
 System.out.println(ae);
 }
 System.out.println(a*c);
 }
 }
This program generates the following output:
java.lang.ArithmeticException: / by zero
 75
Notice that the call to println(a) inside the try block is never executed. Once an exception is
thrown, program control transfers out of the try block into the catch block. After displaying error
message, it executes the println(a*c).
(b) Although there are a number of exceptions in the Java class library that you can use in your own
methods; but you might need to create your own exceptions to handle the different kinds of errors in
your program. Creating new exceptions is easy.
 Your new exception should inherit from some other exception in the Java hierarchy. All usercreated
exceptions should be part of the Exception hierarchy. Look for an exception that is close to
the one you are creating. For example, an exception for a bad file format would logically be an
IOException. If you cannot find a closely related exception for your new exception, consider
inheriting from Exception, which forms the top of exception hierarchy.
 The Exception class does not define any methods of its own. It inherits those methods provided
by Throwable. One such method is the toString() which returns a String object containing a
description of the exception (notice the MyException class in the following program).
 The following program illustrates the user-defined exception.
Program 14(b): Handling user defined exceptions
class MyException extends Exception
{
 public String toString()  1. Overview of Java

21
 {
 String str = "MyException (a/d): division by zero";
 return str;
 }
}
class MyExceptionDemo
{
 public static void main(String args[]) throws MyException
 {
 int a = 20, b = 3, d = 2;
 System.out.println("a = " + a + ", b = " + b + ", d = " + d);
 try
 {
 if( d != 0)
 System.out.println( "a/d = " + a/d );
 else
 throw new MyException();
 System.out.println("Normal exit");
 } catch (MyException e)
 { System.out.println(e); }
 System.out.println( "a*b = " + a*b );
 }
 }
Output of this is as follows,
when d = 0:
a = 20, b = 3, d = 0
MyException (a/d): division by zero
a*b = 60
when d = 2:
a = 20, b = 3, d = 2
a/d = 10
Normal exit
a*b = 60 Searching
15. Write Java programs that use both recursive and non-recursive functions for implementing
the following searching methods:
(a) Linear search
(b) Binary search
Linear search
(a) The simplest form of a search is the linear search. This technique is meant for searching a
particular item in an unsorted data set in a sequential manner until the desired data item is found.
Linear search is easy to write and efficient for short lists, but inefficient for long ones. To find any
element in a long array (list), there are far more efficient methods, provided that the array is sorted. A
program for linear search is as follows.
Program 15(a): Iterative Linear search
class LinearSearchDemo
{
 static Object[] a = { 89, 45, 175, 7, 50, 43, 126, 90 };
 static Object key = 126;
 public static void main(String args[])
 {
 if( linearSearch() )
 System.out.println(key + " found in the list");
 else
 System.out.println(key + " not found in the list");
 }
 static boolean linearSearch()
 {
 for( int i=0; i<a.length; i++)
 if(key == a[i]) return true;
 return false;
 }
}
Program 15(b): Recursive Linear search
class RecursiveLinearSearchDemo
{
 static Object[] a = { 89, 45, 175, 7, 50, 43, 126, 90 };
 static Object key = 43;
 public static void main(String args[])
 {
 if( linearSearch(a.length-1) )
 System.out.println(key + " found in the list");
 else
 System.out.println(key + " not found in the list");
 }
 static boolean linearSearch(int n)
 {
 if( n < 0 ) return false;  2. Searching

23
 if(key == a[n])
return true;
 else
return linearSearch(n-1);
 }
}
Binary search
(b) Binary search is a simple method of accessing a particular item in a sorted (ordered) data set. A
search for a particular item with a certain key value resembles the search for a name in telephone
directory or a word in a dictionary. The approximate middle item of the data set is located, and its key
value is examined. If its value is too high, then the key of the middle element of the first half of the set
is examined and procedure is repeated on the first half until the required item is found. If the value is
too low, then the key of the middle entry of the second half of the data set is tried and the procedure is
repeated on the second half. This process continues until the desired key is found or search interval
becomes empty. The binary search algorithm is based on binary search tree.
Program 15(c): Iterative Binary search
class BinarySearchDemo
{
static Object[] a = { "AP", "KA", "MH", "MP", "OR", "TN", "UP", "WB"};
 static Object key = "UP";
 public static void main(String args[])
 {
 if( binarySearch() )
 System.out.println(key + " found in the list");
 else
 System.out.println(key + " not found in the list");
 }
 static boolean binarySearch()
 {
 int c, mid, low = 0, high = a.length-1;
 while( low <= high)
 {
 mid = (low + high)/2;
 c = ((Comparable)key).compareTo(a[mid]);
 if( c < 0) high = mid-1;
 else if( c > 0) low = mid+1;
 else return true;
 }
 return false;
 }
} 24 Lab Manual Data Structures through Java
Program 15(d): Recursive Binary search
class RecursiveBinarySearchDemo
{
 static Object[] a = { "AP", "KA", "MH", "MP", "OR", "TN", "UP", "WB"};
 static Object key = "XP";
 public static void main(String args[])
 {
 if( binarySearch(0, a.length-1) )
 System.out.println(key + " found in the list");
 else
 System.out.println(key + " not found in the list");
 }
 static boolean binarySearch(int low, int high)
 {
 if( low > high ) return false;
int mid = (low + high)/2;
 int c = ((Comparable)key).compareTo(a[mid]);
 if( c < 0) return binarySearch(low, mid-1);
 else if( c > 0) return binarySearch(mid+1, high);
 else return true;
 }
} Linked Lists
16. Write Java programs to implement the List ADT using arrays and linked lists.
List ADT
The elements in a list are of generic type Object. The elements form a linear structure in which list
elements follow one after the other, from the beginning of the list to its end. The list ADT supports the
following operations:
createList(int n): Creates (initially) a list with n nodes.
 Input: integer; Output: None
insertFirst(obj): Inserts object obj at the beginning of a list.
 Input: Object; Output: None
insertAfter(obj, obj p): Inserts object obj after the obj p in a list.
 Input: Object and position; Output: None
 obj deleteFirst(): Deletes the object at the beginning of a list.
 Input: None; Output: Deleted object obj.
obj deleteAfter(obj p): Deletes the object after the obj p in a list.
 Input: Position; Output: Deleted object obj.
boolean isEmpty(): Returns a boolean indicating if the list is empty.
 Input: None; Output: boolean (true or false).
 int size(): Returns the number of items in the list.
 Input: None; Output: integer.
Type Object may be any type that can be stored in the list. The actual type of the object will be
provided by the user. The ADT is translated into a Java interface in the following program.
Program 16(a): A List Interface
public interface List
{
 public void createList(int n);
 public void insertFirst(Object ob);
 public void insertAfter(Object ob, Object pos);
 public Object deleteFirst();
 public Object deleteAfter(Object pos);
 public boolean isEmpty();
 public int size();
 }
Array Implementation of List
Program 16(b): An ArrayList Class
class ArrayList implements List
{
 class Node
 { Object data;
 int next; 26 Lab Manual Data Structures through Java
 Node(Object ob, int i) // constructor
 { data = ob;
 next = i;
 }
 }
 int MAXSIZE; // max number of nodes in the list
 Node list[]; // create list array
 int head, count; // count: current number of nodes in the list
 ArrayList( int s) // constructor
 { MAXSIZE = s;
 list = new Node[MAXSIZE];
 }
 public void initializeList()
 { for( int p = 0; p < MAXSIZE-1; p++ )
 list[p] = new Node(null, p+1);
 list[MAXSIZE-1] = new Node(null, -1);
 }
 public void createList(int n) // create ‘n’ nodes
 { int p;
 for( p = 0; p < n; p++ )
 {
 list[p] = new Node(11+11*p, p+1);
 count++;
 }
 list[p-1].next = -1; // end of the list
 }
 public void insertFirst(Object item)
 {
 if( count == MAXSIZE )
 { System.out.println("***List is FULL");
 return;
 }
 int p = getNode();
 if( p != -1 )
 {
 list[p].data = item;
 if( isEmpty() ) list[p].next = -1;
 else list[p].next = head;
 head = p;
 count++;
 }
 }
 public void insertAfter(Object item, Object x)
 {
 if( count == MAXSIZE )
 { System.out.println("***List is FULL");
 return;
 }
 int q = getNode(); // get the available position to insert new node
 int p = find(x); // get the index (position) of the Object x
 if( q != -1 )
 { list[q].data = item;
 list[q].next = list[p].next;
 list[p].next = q;  3. Linked Lists

27
 count++;
 }
 }
 public int getNode() // returns available node index
 { for( int p = 0; p < MAXSIZE; p++ )
 if(list[p].data == null) return p;
 return -1;
 }
 public int find(Object ob) // find the index (position) of the Object ob
 { int p = head;
 while( p != -1)
 { if( list[p].data == ob ) return p;
 p = list[p].next; // advance to next node
 }
 return -1;
 }
 public Object deleteFirst()
 { if( isEmpty() )
 { System.out.println("List is empty: no deletion");
 return null;
 }
 Object tmp = list[head].data;
 if( list[head].next == -1 ) // if the list contains one node,
 head = -1; // make list empty.
 else
 head = list[head].next;

 count--; // update count
 return tmp;
 }
 public Object deleteAfter(Object x)
 { int p = find(x);
 if( p == -1 || list[p].next == -1 )
 { System.out.println("No deletion");
 return null;
 }
 int q = list[p].next;
 Object tmp = list[q].data;
 list[p].next = list[q].next;
 count--;
 return tmp;
 }
 public void display()
 { int p = head;
 System.out.print("\nList: [ " );
 while( p != -1)
 { System.out.print(list[p].data + " "); // print data
 p = list[p].next; // advance to next node
 }
 System.out.println("]\n");//
 }
 public boolean isEmpty()
 { if(count == 0) return true;
 else return false;
 } 28 Lab Manual Data Structures through Java
 public int size()
 { return count; }
}
Program 16(c): Testing ArrayList Class
class ArrayListDemo
{
public static void main(String[] args)
 {
 ArrayList linkedList = new ArrayList(10);
 linkedList.initializeList();
 linkedList.createList(4); // create 4 nodes
 linkedList.display(); // print the list
 System.out.print("InsertFirst 55:");
 linkedList.insertFirst(55);
 linkedList.display();
 System.out.print("Insert 66 after 33:");
 linkedList.insertAfter(66, 33); // insert 66 after 33
 linkedList.display();
 Object item = linkedList.deleteFirst();
 System.out.println("Deleted node: " + item);
 linkedList.display();
 System.out.print("InsertFirst 77:");
 linkedList.insertFirst(77);
 linkedList.display();
 item = linkedList.deleteAfter(22); // delete node after node 22
 System.out.println("Deleted node: " + item);
 linkedList.display();
 System.out.println("size(): " + linkedList.size());
 }
}
The following output is generated by this program:
List: [ 11 22 33 44 ]
InsertFirst 55:
List: [ 55 11 22 33 44 ]
Insert 66 after 33:
List: [ 55 11 22 33 66 44 ]
Deleted node: 55
List: [ 11 22 33 66 44 ]
InsertFirst 77:
List: [ 77 11 22 33 66 44 ]
Deleted node: 33
List: [ 77 11 22 66 44 ]
size(): 5
  3. Linked Lists

29
Linked Implementation of List
LinkedList class implemented by List interface is given Program 16(d) and it is tested in Program
16(e).
Program 16(d): A LinkedList Class
class LinkedList implements List
{
 class Node
{ Object data; // data item
 Node next; // refers to next node in the list
 Node( Object d ) // constructor
 { data = d; } // ‘next’ is automatically set to null
}
 Node head; // head refers to first node
 Node p; // p refers to current node
 int count; // current number of nodes
 public void createList(int n) // create 'n' nodes
 {
 p = new Node(11); // create first node
 head = p; // assign mem. address of 'p' to 'head'
 for( int i = 1; i < n; i++ ) // create 'n-1' nodes
 p = p.next = new Node(11 + 11*i);
 count = n;
 }
 public void insertFirst(Object item) // insert at the beginning of list
 {
 p = new Node(item); // create new node
 p.next = head; // new node refers to old head
 head = p; // new head refers to new node
 count++;
 }
 public void insertAfter(Object item,Object key)
 {
 p = find(key); // get “location of key item”
 if( p == null )
 System.out.println(key + " key is not found");
 else
 { Node q = new Node(item); // create new node
 q.next = p.next; // new node next refers to p.next
 p.next = q; // p.next refers to new node
count++;
 }
 }
 public Node find(Object key)
 {
 p = head;
 while( p != null ) // start at beginning of list until end of list
 {
 if( p.data == key ) return p; // if found, return key address30 Lab Manual Data Structures through Java
 p = p.next; // move to next node
 }
 return null; // if key search is unsuccessful, return null
 }
 public Object deleteFirst() // delete first node
 {
 if( isEmpty() )
 { System.out.println("List is empty: no deletion");
 return null;
 }
 Node tmp = head; // tmp saves reference to head
 head = tmp.next;
count--;
 return tmp.data;
 }
 public Object deleteAfter(Object key) // delete node after key item
 { p = find(key); // p = “location of key node”
 if( p == null )
 { System.out.println(key + " key is not found");
 return null;
 }
 if( p.next == null ) // if(there is no node after key node)
 { System.out.println("No deletion");
 return null;
 }
 else
 { Node tmp = p.next; // save node after key node
 p.next = tmp.next; // point to next of node deleted
 count--;
 return tmp.data; // return deleted node
 }
 }
 public void displayList()
 { p = head; // assign mem. address of 'head' to 'p'
 System.out.print("\nLinked List: ");
 while( p != null ) // start at beginning of list until end of list
 { System.out.print(p.data + " -> "); // print data
 p = p.next; // move to next node
 }
 System.out.println(p); // prints 'null'
 }
public boolean isEmpty() // true if list is empty
 { return (head == null); }
public int size()
 { return count; }
} // end of LinkeList class  3. Linked Lists

31
Program 16(e): Testing LinkedList Class
 class LinkedListDemo
{ public static void main(String[] args)
 { LinkedList list = new LinkedList(); // create list object
 list.createList(4); // create 4 nodes
 list.displayList();
 list.insertFirst(55); // insert 55 as first node
 list.displayList();
 list.insertAfter(66, 33); // insert 66 after 33
 list.displayList();
 Object item = list.deleteFirst(); // delete first node
 if( item != null )
 { System.out.println("deleteFirst(): " + item);
 list.displayList();
 }
 item = list.deleteAfter(22); // delete a node after node(22)
 if( item != null )
 { System.out.println("deleteAfter(22): " + item);
 list.displayList();
 }
 System.out.println("size(): " + list.size());
 }
}
Here is the output from LinkedListDemo.java:
Linked List: 11 -> 22 -> 33 -> 44 -> null
Linked List: 55 -> 11 -> 22 -> 33 -> 44 -> null
Linked List: 55 -> 11 -> 22 -> 33 -> 66 -> 44 -> null
deleteFirst(): 55
Linked List: 11 -> 22 -> 33 -> 66 -> 44 -> null
deleteAfter(22): 33
Linked List: 11 -> 22 -> 66 -> 44 -> null
size(): 4 Stacks and Queues


No comments: