Khulna University, Khulna

Computer Science and Engineering Discipline

Course No: CSE 2102
Course Title: Data Structure Laboratory
Problem Set: Array-Based Lists

1 Array-Based Lists
Everyday we deal with different types of lists. We might have a list consisting of
employee data, student data, sales data, or a list of rental properties. One thing
common to all lists is that all the elements of a list are of the same type. Because
all the elements of a list are of the same type, an effective and convenient way to
process a list is to store it in an array. Initially, the size of the array holding the list
elements is set to a reasonable number, like 10, or 15, or 20 . . . . When we want to
insert elements beyond that size we may expand the array twice its size. Thus, we
must know how full the array is; that is, we must keep track of the number of list
elements stored in the array. It follows that, to maintain and process the list in an
array, we need the following three variables:

• The array holding the list elements

• A variable to store the length of the list (that is, the number of list elements
currently in the array)

• A variable to store the size of the array (that is, the maximum number of
elements that can be stored in the array)

Suppose that the variable length indicates the number of elements in the list and
maxSize indicates the maximum number of elements that can be stored in the list.
Then length and maxSize are nonnegative integers and, therefore, we can declare
them to be of type int.
What about the type of the array, that is, the data type of the array elements?
If we have a list of numbers, the array elements could be of type int or double. If
we have a list of names, the array elements are of type string. Similarly, if we have
a list of students, the array elements are of type studentType (a data type you can
define). As we can see, there are various types of lists. A list of sales data or a list
of students’ data is empty if its length is zero. To insert an item at the end of a list
of any type would require you to add the element after the current last element and
then increment the length by one. Similarly, it can be seen that, for the most part,
the algorithms to implement operations on a list of names, on a list of sales data, or
on a list of students’ data are the same. We do not want to spend time and efforts to
develop separate code for each type of list we encounter. Instead, we want to develop
a generic code that can be used to implement any type of list in a program.
Following are some of the operations performed on a list:

1. Create the list. The list is initialized to an empty state.

2. Determine whether the list is empty.

3. Determine whether the list is full.

4. Find the size of the list.

5. Destroy, or clear, the list.

6. Determine whether an item is the same as a given list element.

1
 7. Insert an item in the list at the specified location.

8. Remove an item from the list at the specified location.

9. Replace an item at the specified location with another item.

10. Retrieve an item from the list from the specified location.

11. Search the list for a given item.

Now that we know the operations to be performed on a list and how to store the
list into the computer’s memory, next we define the class implementing the list as an
abstract data type (ADT). The following class, ArrayListType, defines the list as an
ADT:
1 import j a v a . u t i l . Arrays ;
2

3 p u b l i c c l a s s ArrayListType <A>
4 {
5 private int length ;
6 p r i v a t e i n t maxSize ;
7 A [ ] data ;
8

9 p u b l i c ArrayListType ( i n t maxSize )
10 {
11 t h i s . maxSize = maxSize ;
12 data = (A [ ] ) new Object [ maxSize ] ;
13 length = 0;
14 }
15
16 // Method t o d e t e r m i n e whether t h e l i s t i s empty
17 // P o s t c o n d i t i o n : Returns t r u e i f t h e l i s t i s empty ;
18 // o t h e r w i s e , r e t u r n s f a l s e .
19 p u b l i c b o o l e a n isEmpty ( )
20 {
21 r e t u r n ( l e n g t h == 0 ) ;
22 }
23
24 // Method t o d e t e r m i n e whether t h e l i s t i s f u l l .
25 // P o s t c o n d i t i o n : Returns t r u e i f t h e l i s t i s f u l l ;
26 // o t h e r w i s e , r e t u r n s f a l s e .
27 public boolean i s F u l l ( )
28 {
29 r e t u r n ( l e n g t h == maxSize ) ;
30 }
31
32 // Method t o d e t e r m i n e t h e number o f e l e m e n t s i n t h e l i s t
33 // P o s t c o n d i t i o n : Returns t h e v a l u e o f l e n g t h .
34 public int l i s t S i z e ( )
35 {
36 return length ;
37 }
38

39 // Method t o output t h e e l e m e n t s o f t h e l i s t
40 // P o s t c o n d i t i o n : Elements o f t h e l i s t a r e output on
41 // t h e s t a n d a r d output d e v i c e .
42 public void p r i n t L i s t ( )
43 {
44 int i ;
45
46 f o r ( i = 0 ; i < l e n g t h ; i++ )
47 System . out . p r i n t ( data [ i ] . t o S t r i n g ( ) + ” ”) ;
48 System . out . p r i n t l n ( ) ;
49 }
50

51 // Method t o i n s e r t an item i n t h e l i s t a t t h e p o s i t i o n
52 // s p e c i f i e d by l o c a t i o n . The item t o be i n s e r t e d i s p a s s e d
53 // a s a parameter .
54 // P o s t c o n d i t i o n : S t a r t i n g a t l o c a t i o n , t h e e l e m e n t s o f t h e
55 // l i s t a r e s h i f t e d down , l i s t [ l o c a t i o n ] = i n s e r t I t e m ; ,
56 // and l e n g t h ++;. I f t h e l i s t i s f u l l t h e l i s t i s expaned .

Page 2
 57 // I f t h e l o c a t i o n i s out o f range , an a p p r o p r i a t e
58 // message i s d i s p l a y e d .
59 public void insertAt ( i n t location , A insertItem )
60 {
61 // System . out . p r i n t l n ( l o c a t i o n +” ”+ i n s e r t I t e m ) ;
62 i f ( l o c a t i o n < 0 | | l o c a t i o n > maxSize )
63 System . out . p r i n t l n ( ”The p o s i t i o n o f t h e item t o be
i n s e r t e d i s out o f r a n g e ” ) ;
64 else
65 {
66 i f ( l e n g t h >= maxSize ) // l i s t i s f u l l
67 expandArray ( 5 ) ;
68
69 f o r ( i n t i=l e n g t h ; i >l o c a t i o n ; i −−)
70 data [ i ] = data [ i − 1 ] ; //move t h e e l e m e n t s down
71 // i n s e r t t h e item a t l o c a t i o n
72 data [ l o c a t i o n ] = i n s e r t I t e m ;
73 l e n g t h ++; // i n c r e m e n t t h e l e n g t h
74 // }// end f o r
75 } // end e l s e
76 } // end i n s e r t A t
77
78 // Method t o i n s e r t an item a t t h e end o f t h e l i s t . The parameter
79 // i n s e r t I t e m s p e c i f i e s t h e item t o be i n s e r t e d .
80 // P o s t c o n d i t i o n : l i s t [ l e n g t h ] = i n s e r t I t e m ; and l e n g t h ++;
81 // I f t h e l i s t i s f u l l t h e l i s t i s expanded .
82 p u b l i c v o i d i n s e r t E n d (A i n s e r t I t e m )
83 {
84 }
85

86 // Method t o remove t h e item from t h e l i s t a t t h e p o s i t i o n

87 // s p e c i f i e d by l o c a t i o n
88 // P o s t c o n d i t i o n : The l i s t e l e m e n t a t l i s t [ l o c a t i o n ] i s removed
89 // and l e n g t h i s decremented by 1 . I f l o c a t i o n i s out o f range ,
90 // an a p p r o p r i a t e message i s d i s p l a y e d .
91 p u b l i c v o i d removeAt ( i n t l o c a t i o n )
92 {
93 }
94
95 // Method t o r e t r i e v e t h e e l e m e n t from t h e l i s t a t t h e
96 // p o s i t i o n s p e c i f i e d by l o c a t i o n .
97 // P o s t c o n d i t i o n : r e t I t e m = l i s t [ l o c a t i o n ] I f l o c a t i o n
98 // i s out o f range , an a p p r o p r i a t e message i s d i s p l a y e d .
99 public A retrieveAt ( int location )
100 {
101 A retItem = null ;
102
103 i f ( l o c a t i o n < maxSize ) {
104 r e t I t e m = data [ l o c a t i o n ] ;
105 }
106 else {
107 System . out . p r i n t l n ( ”The l o c a t i o n i s out o f r a n g e ! ! ! ” ) ;
108 }
109
110 return retItem ;
111 }
112
113 // Method t o r e p l a c e t h e e l e m e n t s i n t h e l i s t a t t h e p o s i t i o n
114 // s p e c i f i e d by l o c a t i o n .
115 //The item t o be r e p l a c e d i s s p e c i f i e d by t h e parameter repItem .
116 // P o s t c o n d i t i o n : l i s t [ l o c a t i o n ]= repItem
117 // I f l o c a t i o n i s out o f range , an a p p r o p r i a t e message i s d i s p l a y e d .
118 p u b l i c v o i d r e p l a c e A t ( i n t l o c a t i o n , A repItem )
119 {
120 }
121
122 // Method t o remove a l l t h e e l e m e n t s from t h e l i s t .
123 // A f t e r t h i s o p e r a t i o n , t h e s i z e o f t h e l i s t i s z e r o .
124 // P o s t c o n d i t i o n : l e n g t h = 0 ;
125 public void c l e a r L i s t ( )
126 {

Page 3
127 }
128
129 // Method t o s e a r c h t h e l i s t f o r a g i v e n item .
130 // P o s t c o n d i t i o n : I f t h e item i s found ,
131 // r e t u r n s t h e l o c a t i o n i n t h e a r r a y where t h e
132 // item i s found ; o t h e r w i s e , r e t u r n s −1.
133 p u b l i c i n t s e q S e a r c h ( A item )
134 {
135 return 0;
136 }
137
138 // Method t o i n s e r t t h e item s p e c i f i e d by t h e parameter i n s e r t I t e m
139 // a t t h e end o f t h e l i s t . However , f i r s t t h e l i s t i s s e a r c h e d
140 // t o s e e whether t h e item t o be i n s e r t e d i s a l r e a d y i n t h e l i s t .
141 // P o s t c o n d i t i o n : l i s t [ l e n g t h ]= i n s e r t I t e m and l e n g t h++
142 // I f t h e item i s a l r e a d y i n t h e l i s t an a p p r o p r i a t e message
143 // i s d i s p l a y e d .
144 // I f t h e l i s t i s f u l l , t h e a r r a y i s expanded
145 public void i n s e r t ( A insertItem )
146 {
147 }
148
149 // Method t o remove an item from t h e l i s t . The parameter removeItem
150 // s p e c i f i e s t h e item t o be removed .
151 // P o s t c o n d i t i o n : I f removeItem i s found i n t h e l i s t , i t i s
152 // removed from t h e l i s t and l e n g t h i s decremented by one .
153 p u b l i c v o i d remove (A removeItem )
154 {
155 }
156

157 // Method t o expand t h e l i s t ( used by i n s e r t methods ) . The parameter

158 // i n c S i z e s p e c i f i e s t h e i n c r e m e n t s i z e o f t h e l i s t .
159 // P o s t c o n d i t i o n : l i s t i s i n c r e m e n t e d by i n c S i z e .
160 p u b l i c v o i d expandArray ( i n t i n c S i z e )
161 {
162 A [ ] temp = data ;
163 maxSize = maxSize + i n c S i z e ;
164 data = (A [ ] ) new Object [ maxSize ] ;
165 data = Arrays . copyOf ( temp , data . l e n g t h ) ;
166 temp = n u l l ;
167 } // end expandArray
168 }

The list is empty if length is zero; it is full if length is equal to maxSize. Therefore,
the definitions of the functions isEmpty and isFull are simple.

1.1 insertAt method

The function insertAt inserts an item at a specific location in the list. The item
to be inserted and the insert location in the array are passed as parameters to this
function. To insert the item somewhere in the middle of the list, we must first make
room for the new item. That is, we need to move certain elements right one array
slot. Of course, special cases such as trying to insert in a full list must be handled
separately. Other member functions can handle some of these cases. The definition
of the function insertAt is as follows:
1 // Method t o i n s e r t an item i n t h e l i s t a t t h e p o s i t i o n s p e c i f i e d by
2 // l o c a t i o n . The item t o be i n s e r t e d i s p a s s e d a s a parameter .
3 // P o s t c o n d i t i o n : S t a r t i n g a t l o c a t i o n , t h e e l e m e n t s o f t h e l i s t
4 // a r e s h i f t e d down , l i s t [ l o c a t i o n ] = i n s e r t I t e m ; , and l e n g t h ++;
5 // I f t h e l i s t i s f u l l t h e l i s t i s expaned .
6 // I f t h e l o c a t i o n i s out o f range , an a p p r o p r i a t e message i s d i s p l a y e d .
7 public void insertAt ( i n t location , A insertItem )
8 {
9 i f ( l o c a t i o n < 0 | | l o c a t i o n > maxSize )
10 System . out . p r i n t l n ( ”The p o s i t i o n o f t h e item t o be i n s e r t e d i s out
o f range ” ) ;
11 else
12 {
13 i f ( l e n g t h >= maxSize ) // l i s t i s f u l l

Page 4
14 expandArray ( 5 ) ;
15 f o r ( i n t i=l e n g t h ; i >l o c a t i o n ; i −−)
16 data [ i ] = data [ i − 1 ] ; //move t h e e l e m e n t s down
17 data [ l o c a t i o n ] = i n s e r t I t e m ; // i n s e r t t h e item a t t h e s p e c i f i e d
position
18 l e n g t h ++; // i n c r e m e n t t h e l e n g t h
19 } // end e l s e
20 } // end i n s e r t A t

Implement all the methods in the program.

1.2 Creating a list of a class

We made the list generic so that we can create any kind of list. For example, say we
have a Student class as follows:
1 public class Student {
2 private S t r i n g name ;
3 private i n t ID ;
4 private double s c o r e ;
5
6 p u b l i c Student ( S t r i n g name , i n t ID , d o u b l e s c o r e )
7 {
8 t h i s . name = name ;
9 t h i s . ID = ID ;
10 this . score = score ;
11 }
12
13 public void print ( )
14 {
15 System . out . p r i n t ( ”Name : ” + name + ” ID : ” + ID + ” S c o r e : ” +
s c o r e +”\n” ) ;
16 }
17 }

To create a list of 10 students, we create a object of ArrayListType:

ArrayListType alStudents = new ArrayListType<Student>(10);
Now remember that the signature of insertAt method, public void insertAt(int
location, A insertItem), where A is the type of our object. alStudents can store
10 Student type objects, so before we store an Student object we need to create it
first. A call to insertAt method would be:
Student st = new Student("AAAA", 2, 98.5);
[Link](0, st); or simply,
[Link](0, new Student("AAAA", 2, 98.5));
The following program tests the various operations on array-based lists.
1 import j a v a . u t i l . Random ;
2 import j a v a . u t i l . Scanner ;
3
4 p u b l i c c l a s s TestArrayListType
5 {
6 p u b l i c s t a t i c v o i d main ( S t r i n g [ ] a r g s )
7 {
8 ArrayListType a l I n t s = new ArrayListType<I n t e g e r >(20) ;
9 Scanner i n = new Scanner ( System . i n ) ;
10
11 // p o p u l a t e t h e l i s t with 20 random numbers
12 Random rand = new Random ( ) ; // a pseudo−random number g e n e r a t o r
13 // u s e c u r r e n t time a s a s e e d
14 rand . s e t S e e d ( System . c u r r e n t T i m e M i l l i s ( ) ) ;
15 // f i l l t h e data a r r a y with pseudo−random numbers from 0 t o 99
16 f o r ( i n t i = 0 ; i < 2 0 ; i ++)
17 a l I n t s . i n s e r t A t ( i , rand . n e x t I n t ( 1 0 0 ) ) ;
18 System . out . p r i n t l n ( ”The s i z e o f t h e l i s t i s ” + a l I n t s .
l i s t S i z e () ) ;
19 alInts . printList () ;
20
21 a l I n t s . i n s e r t A t (0 , 250) ;
22 System . out . p r i n t l n ( ”The s i z e o f t h e l i s t i s ” + a l I n t s .
l i s t S i z e () ) ;

Page 5
23 alInts . printList () ;
24
25 // Enter an i n t t o remove from t h e a l I n t s
26 i n t number ;
27 System . out . p r i n t l n ( ” Enter an item t o be d e l e t e d : ” ) ;
28 number = i n . n e x t I n t ( ) ;
29 a l I n t s . remove ( number ) ;
30 System . out . p r i n t l n ( ” A f t e r removing ” + number + ” , t h e l i s t
is : ”) ;
31 alInts . printList ( ) ;
32
33 ArrayListType a l S t r i n g s = new ArrayListType<S t r i n g >(5) ;
34 String str ;
35
36 System . out . p r i n t l n ( ” Enter 5 s t r i n g s : ” ) ;
37 f o r ( i n t i = 0 ; i < 5 ; i ++)
38 {
39 s t r = in . nextLine ( ) ;
40 alStrings . insertAt ( i , str ) ;
41 }
42 System . out . p r i n t l n ( ”The s i z e o f t h e l i s t i s ” + a l S t r i n g s .
l i s t S i z e () ) ;
43 System . out . p r i n t l n ( ”The l i s t you e n t e r e d i s ” ) ;
44 alStrings . printList () ;
45
46 System . out . p r i n t l n ( ” Enter t h e s t r i n g t o be d e l e t e d : ” ) ;
47 s t r = in . nextLine ( ) ;
48 a l S t r i n g s . remove ( s t r ) ;
49 System . out . p r i n t l n ( ” A f t e r removing ” + s t r + ” , t h e l i s t i s : ”
);
50 alStrings . printList ( ) ;
51
52
53 ArrayListType a l S t u d e n t s = new ArrayListType<Student >(2) ;
54 a l S t u d e n t s . i n s e r t A t ( 0 , new Student ( ”AAAA” , 2 , 9 8 . 5 ) ) ;
55 a l S t u d e n t s . i n s e r t A t ( 1 , new Student ( ”BBBB” , 1 , 8 8 . 5 ) ) ;
56 a l S t u d e n t s . i n s e r t A t ( 0 , new Student ( ”CCCC” , 4 , 7 9 . 0 ) ) ;
57
58 Student s t ;
59 f o r ( i n t i = 0 ; i < a l S t u d e n t s . l i s t S i z e ( ) ; i++ )
60 {
61 s t = ( Student ) a l S t u d e n t s . r e t r i e v e A t ( i ) ;
62 st . print () ;
63 } // end f o r
64
65 }
66 }

Based on the above implementation, solve the problems given next.

Page 6
1. You learned in a college algebra or calculus course that a polynomial, p(x), in
one variable, x, is an expression of the form:
p(x) = a0 + a1 x + · · · + an−1 xn−1 + an xn
where ai are real (or complex) numbers and n is a nonnegative integer. If p(x) =
a0 , p(x) is called a constant polynomial. If p(x) is a nonzero constant polynomial,
the degree of p(x) is defined to be 0. If p(x) is not constant and an 6= 0, n is called
the degree of p(x); that is, the degree of a nonconstant polynomial is defined to
be the exponent of the highest power of x.
The basic operations performed on polynomials are add, subtract, multiply, di-
vide, and evaluate a polynomial at any given point. For example, suppose that
p(x) = 1 + 2x + 3x2 ,
and
q(x) = 4 + x.
The degree of p(x) is 2 and the degree of q(x) is 1. Moreover,
p(2) = 1 + 2.2 + 3.22 = 17
p(x) + q(x) = 5 + 3x + 3x2
p(x) − q(x) = −3 + x + 3x2
p(x) ∗ q(x) = 4 + 9x + 14x2 + 3x3

We will design and implement the class PolynomialType to perform the various
polynomial operations in a program. we will implement the following operations
on polynomials:

1. Evaluate a polynomial at a given value.

2. Add polynomials.
3. Subtract polynomials.
4. Multiply polynomials.

We assume that the coefficients of polynomials are real numbers. To store a

polynomial, we use a dynamic array as follows. Suppose p(x) is a polynomial of
degree n ≥ 0. Let list be an array of size n + 1. The coefficient ai of xi is stored
in list [i].

If p(x) is a polynomial of degree n, we need an array of size n + 1 to store the

coefficients of p(x). Suppose that p(x) = 1 + 8x − 3x2 + 5x4 + 7x8 . Then the
array storing the coefficient of p(x) is given below:

Next, we define the operations addition, subtruction, and multiplication. Sup-

pose that
p(x) = a0 + a1 x + · · · + an−1 xn−1 + an xn and
q(x) = b0 + b1 x + · · · + bm−1 xm−1 + bm xm . Let t = max(n, m). Then
p(x) + q(x) = c0 + c1 x + · · · + ct−1 xt−1 + ct xt , where for i = 0, 1, 2, ..., t


ai + bi , if i ≤ min(n, m)

c i = ai , if i > m (1)

bi , if i > n


Page 7
 The difference, p(x) − q(x), of p(x) and q(x) can be defined similarly. It follows
that the degree of the polynomials is ≤ max(n, m).
The product, p(x) ∗ q(x), of p(x) and q(x) is defined as follows:
p(x) ∗ q(x) = d0 + d1 x + · · · + dn+m xn+m ,
The coefficient dk , for k = 0, 1, 2, · · · , t, is given by the formula
dk = a0 ∗ bk + a1 ∗ bk−1 + · · · + ak b0 ,
where if either ai or bi does not exist, it is assumed to be zero. For example,
d0 = a0 b0
d1 = a0 b1 + a1 b0
...
dn+m = an bm
Based on the above discussion, complete the program.

2. The function removeAt of the class ArrayListType removes an element from the
list by shifting the elements of the list. However, if the element to be removed
is at the beginning of the list and the list is fairly large, it could take a lot of
computer time. Because the list elements are in no particular order, you could
simply remove the element by swapping the last element of the list with the item
to be removed and reducing the length of the list. Rewrite the definition of the
function removeAt using this technique.

3. The function remove of the class ArrayListType removes only the first occur-
rence of an element. Add a function removeAll to the class ArrayListType that
would remove all occurrences of a given element. Also, write the definition of the
function removeAll and a program to test this function.

4. Using classes, design an online address book to keep track of the names, addresses,
phone numbers, and dates of birth of family members, close friends, and certain
business associates. Your program should be able to handle a maximum of 500
entries.

a. Define a class, AddressType, that can store a street address, city, state, and
zip code. Use the appropriate functions to print and store the address. Also,
use constructors to automatically initialize the data members.
b. Define a class PersonType, that can store a person’s last name and first
name. Use the appropriate functions to print and store the name. Also, use
constructors to automatically initialize the data members.
c. Define a class, DateType, to store a person’s date of birth, in three fields
(month, day, and year). The method setDate should check the values for
the month, day, and year before storing the date into the data members.
Add a method, isLeapYear, to check whether a year is a leap year.
d. Define a class ExtPersonType using the class PersonType, the class DateType,
and the class AddressType. Add a data member to this class to classify the
person as a family member, friend, or business associate. Also, add a data
member to store the phone number. Add the functions to print and store
the appropriate information. Use constructors to automatically initialize the
data members.
e. Derive the class AddressBookType from the class ArrayListType, as defined
earlier, so that an object of type AddressBookType can store objects of
type ExtPersonType. An object of type AddressBookType should be able
to process a maximum of 500 entries. Add necessary operations to the
class AddressBookType so that the program should perform the following
operations:
i. Load the data into the address book from a file.
ii. Search for a person by last name.
iii. Print the address, phone number, and date of birth (if it exists) of a
given person.

Page 8
iv. Print the names of the people whose birthdays are in a given month or
between two given dates.
v. Print the names of all the people having the same status, such as family,
friend, or business.
vi. Print the names of all the people between two last names.

Page 9