Data Structure Lab
Lab number (4)
Subject: Using different data structures at implementation level
Lab Objectives:
Solve a given problem using different data structures
a. Using List implementation using fixed-size array
b. Using List implementation using dynamic array
Part I:
Use list DS to solve the following problem on the
implementation level:
1. Create a list interface of the List ADT named ListInterface that
contains signatures and specification of the following methods:
a. add(Object newEntry)
b. isEmpty()
c. isFull()
d. display()
e. contains(Object anEntry)
2. Create a class named AList that implements the ADT list using
fixed size array implementation considering the following:
Add to the end method has one Object parameter, returns
Boolean, and works as follows:
Check whether list is full or not:
a. if list is not full, then:
i. add the newEntry at the end of the list
ii. length++
iii. return true
b. else return false
isEmpty method has no parameters, returns Boolean, and
checks whether length (i.e. number of list entries) equals 0
or not as follows:
if length==0
then return true
else return false
isFull method has no parameters, returns Boolean, and
checks whether number of list entries equals list size as
follows:
if length== array size
then return true
else return false
display method has no parameters or return type and
prints all list entries from index 0 to <length.
contains method has one Object parameter, returns
Boolean, and checks whether the list contains anEntry as
follows:
for index 0 to <length
if array[index] equals anEntry
then return true
else return false
3. Test the list by creating a testing class (with the main method)
to:
a. Create a list of size 3.
b. Create three objects and add them to the created list
c. Display all entries in the list
d. Create a fourth object and add it to the list
e. Display all entries in the list again
4. On the implementation level, update add() method, so that you
can overcome the size limitation (i.e. Dynamic array instead of
fixed size array implementation), as follows:
Check whether array is full or not:
a. if array is not full, then:
i. add the newEntry at the end of the array
ii. length++
iii. return true
b. else double the array size as follows:
i. create new array of size= old array size *2
ii. copy array entries to the new array
c. add the newEntry at the end of the new array
i. length++
ii. return true
5. Modify isFull() method so it always returns false.
6. Return to your application class (i.e. testing class) and do the
following:
a. Create a fifth object and add it to the array as a new entry.
b. Display all entries in the array again
7. What do you notice about the array entries in both cases (fixed
size array and dynamic array implementation)?
Part II :
1. Declare a new method called next() that retrieves the next entry
of index (predefined) in the list implemented using array with
dynamic expansion. A variable named index should be declared
in the List class, and initialized by -1. The method increases the
index by 1 and retrieves the entry after index position in the list.
The method next() is activated if the list is not empty and
index is greater than or equals 0 and less than length, then a
reference to the list entry comes after the indicated one is
returned, otherwise, null is returned.
Notes: Remember to add the method signature to the interface and
add integer index variable in the DList class (initialized by -1)
2. Test both next() method.
3. Declare a new method called duplicate () that retrieves a given
position in the list implemented using array with dynamic
expansion. The method receives as argument an integer
(givenPosition). The method duplicate() is activated if the list
is not empty and givenPosition is greater or equals 0 and less
than length. The method will copy the entry at the givenPosition
and add it to the end of the list. A Boolean (true/false) is then
returned whether the operation is succeeded or not.
4. Test duplicate() method.
