HW 1: The Fixed List Data Structure

SOLUTION

Solution

Overview

In this homework, there are two goals: (1) refresh your experience with Java and Generics and (2) implement your first data structure. The data structure you will program is called a FixedList which will implement a List interface using a fixed size array back end. Unlike an ArrayList, the FixedList specifies a maximal size that is declared at construction.

Due Date

This homework is due Sunday, August 28th at 2359

Grading

This assignment is graded out of 100 points.

15 points: Proper use of Java Generics
60 points : add(), get(), set(), remove()
25 points : Proper shifting of data

Submission and Starter Code

All starter code for this homework can be obtained via the ~aviv/bin/ic312-up and submission will occur via ~aviv/bin/ic312-submit.

You must submit the following file(s):

FixedList.java
README : containing any attribution or notes for grading.
Any testing files you'd like us to look at and consider during grading.

Description

The `List` Interface

Recall that interfaces in Java provide a way for a programmer to describe how a class of objects should be interacted with without actually describing the implementation directly. For example, the List interface specifies the general method of a List but not the specifics of the implementation, which could be a LinkedList, an ArrayList, or, in this case, a FixedList.

For this assignment, and throughout this class, we will use the following List interface. Note that this is slightly different then Java's built in list inteface in java.util, and you should avoid mixing the two. To help, we've placed the List interface in the ic312 package, and we will add interfaces and implementations to this package throughout the semester.

package ic312;

public interface List<T>{

    /**
    Return the element at index i in the list.

    @param i the index to get at
    @return the value of the elemnt at the inde
    **/
    public T get(int i) throws IndexOutOfBoundsException;


    /**
    Set the value of the element at index i to e

    @param i the index to set at
    @param e the value to set 
    @return the value of the element set
    **/
    public T set(int i, T e) throws IndexOutOfBoundsException;

    /**
    Add an element e to the list at the index i

    @param i the index to add to
    @param e the value to add
    **/
    public void add(int i, T e) throws IndexOutOfBoundsException;

    /**
    Remove an element from the list at index i and return it

    @param i the index to be removed
    @return the element removed
    **/
    public T remove(int i)   throws IndexOutOfBoundsException;


    /**
    Returns the number of elements in the list

    @return the number of elements in the list
    **/
    public int size();
}

Here's some sample code of how one might use this interface.

List<Integer> l = /*some implementation of a List*/

for(int i=0;i<10;i++){
    //add elements to the front of list
    l.add(0,new Integer(i));
}

for(int i=0;i<l.size();i++){
   //double all elements
   l.set(i,l.get(i)*2);
}

while(l.size(){
   //remove all elements and print them out
   System.out.println(""+l.remove(0) +" ");
}

Java Generics

You should notice that the List interface uses generic types to describe the elements it stores. Only once a List is instantiated, should the class be described, for example, in the sample code above, the specific element type is named as an Integer and then Integer's are added, set, gotten, and removed from the list.

We encourage you to read the Java documentation of generics for additional details.

https://docs.oracle.com/javase/tutorial/java/generics/index.html

And, if you have questions, please ask your instructor or MGSP leader.

The FixedList

The FixedList implementation of the List interface is one where the user must define how large the list can be in the constructor and the list can never grow bigger or smaller.

List<Integer> l = new FixedList<Integer>(10); //size 5 list

The elements of the list are stored in the object as an array.

private T elements[]; //array of elements of type generic T
private int numElem; //how many elements currently stored

You must implement your FixedList such that the elements array always arranges items in the lower indexes of the list. To do this, consider how you must shift elements in the array as items are added and removed.

All methods must also check bounds to ensure that the user only accesses appropriate indexes. For example, consider the following sequence of operations, the current array arrangement, and the error conditions.

List<Integer> l = new FixedList<Integer>(5); // [ ] -- empty list

l.add(0, new Integer(1));  // [ 1 ] 
l.get(0) // -> 1
l.get(1) //IndexOutOfBoundsException -- cant' get value outside the current size
l.set(1, new Integer(2));  //IndexOutOfBoundsException -- can't set value before it's added

l.add(0, new Integer(2));  // [ 2 1 ] 
l.add(1, new Integer(3));  // [ 2 3 1 ]
l.add(4, new Integer(4));  // IndexOutOfBoundsException -- adding more than +1 the current size
l.add(5, new Integer(5));  // IndexOutOfBoundsException -- outside the bounds of the fixedList at size 5
l.add(-1, new Integer(-1));  // IndexOutOfBoundsException -- negative index

l.add(3, new Integer(4));  // [ 2 3 1 4 ]
l.add(0, new Integer(5));  // [ 5 2 3 1 4 ]
l.add(0, new Integer(6));  //  IndexOutOfBoundsException -- list is full

l.set(0, new Integer(20)); // [ 20 2 3 1 4]
l.set(2, new Integer(10)); // [ 20 2 10 1 4]
l.set(5, new Integer(10)); // IndexOutOfBoundsException -- access out of bounds
l.set(-1, new Integer(10)); // IndexOutOfBoundsException -- negative index

System.out.println(""+l.get(0).toString()); // -> 20
System.out.println(""+l.get(1).toString()); // -> 2
System.out.println(""+l.get(2).toString()); // -> 1
System.out.println(""+l.get(5).toString()); //IndexOutOfBoundException -- getting out of bounds
System.out.println(""+l.get(-1).toString()); //IndexOutOfBoundException -- negative index

System.out.println("size: "+list.size()); //-> 5 

//Current list: [ 20 2 10 1 4]

l.remove(0); // [ 2 10 1 4 ] -- removed first element

System.out.println("size: "+lihhst.size()); //-> 4


System.out.println(""+l.get(4).toString()); //IndexOutOfBoundEception
                                            //-- getting out of bounds of the size of the list
l.set(4, new Integer(100)); //IndexOutOfBoundException
                            //-- setting out of bounds of the size of the list


l.remove(1); // [ 2 1 4 ] -- removed second element
l.remove(0); // [ 1 4 ]
l.remove(0); // [ 4 ]
l.remove(1); // IndexOutOfBoundsException -- removing out of bounds
l.remove(0); // [ ]
l.remove(0); // IndexOutOfBoundsException -- removing from an empty list

To help your development and grading, a toString() method is provided. Note that in grading, we will test on a wide variety of input and settings.

IC312: Data Structures (FA17)