Use Java language to complete sparse array program

In this homework, you will be implementing a data structure called a sparse array. A sparse array is a data structure that allows the user the illusion that they have a large array, most of which are filled with zeroes, which they can use to write to and read from. You will implement this is two different ways: one with an array strategy and one with a linked list strategy.

The sparse array data structure will be specified as follows: Its okay to not use generics for this assignment:

import java.util.*;

public interface SparseArray{

public int size();

public boolean isEmpty();

public int get(int index);

public int set(int index, int value);

}

Lets describe the two implementations:

A. Array based approach:

public class ArraySparseArray implements SparseArray { private static class Pair {

}

private int index;

private int value;

//whatever constructors, getters, and setters necessary.

private Pair[ ] arr; //will reference the array that will store the data items. private int numElements;

public SparseArrayArr(int initSize) //creates the array behind the scenes to hold initSize elements

public int size() // returns how many (meaningful) elements are being held by the array

public boolean isEmpty()

public int get(int index) //return 0 if index isnt there and the associated value if it is there.

public int set(int index, int value) //if index is in the array, then change the associated value and return the old value. If it isnt there, add it in sorted order by index into the array.

public int remove(int index) //remove the index from the array. public String toString() //create a representation for the SparseArray.

}

B. Linked list based approach

public class LinkedSparseArray { private static class SListNode {

private int index;

private int value;

private SListNode next;

//whatever constructors, getters, setters necessary.

}

private static class Pair {

//same as above }

private SListNode head;

public int size()

public boolean isEmpty()

public int get(int index) //return 0 if index isnt there. If it is there return the associated value.

public int set(int index, int value) //if index is there, change the associated value and return the old value. If index isnt there, create a new node and attach it to the list at the beginning of the list.