Sparse Vector Using Linked List

Implement the linked list sparse vector class (LLSparseVec.java) so that LLMainClass can be executed.

Nodes in the linked list are nonzero elements of the vector, sorted according to their indices. The length of a vector is specified at construction.

When an element is set to zero, the corresponding node should be removed!

Implement the constructor, accessor methods, getElement, setElement, clearElement, getAllIndices, getAllValues. In otherwords, when LLMainClass is called using VEC argument and with a single input file, the program should be able to run correctly and give the same output as ArrayMainClass.

Implement both the addition, subtraction and multiplication methods in LLSparseVec. The method subtraction(otherV) means the current vector minus otherV.

The algorithm has to be O(m), in which m is the maximum number of nonzero elements in a vector (length of the list). To achieve this, you cannot simply use get and set in Problem 1. Only algorithms with O(m) complexity will get credits. The smart-merge method in HW1 is a good place to start. But note the difference here.

All operations return a new sparse vector object, storing the result.

If the two vectors length do not match, return a null object.

When LLMainClass is called using VEC argument and with multiple input files, the program should be able to run correctly and give the same output as ArrayMainClass.

//code given to implement

public class LLSparseVec implements SparseVec {

public LLSparseVec(int len){

return;

}

@Override

public int getLength() {

// TODO Auto-generated method stub

return 0;

}

@Override

public int numElements() {

// TODO Auto-generated method stub

return 0;

}

@Override

public int getElement(int idx) {

// TODO Auto-generated method stub

return 0;

}

@Override

public void clearElement(int idx) {

// TODO Auto-generated method stub

}

@Override

public void setElement(int idx, int val) {

// TODO Auto-generated method stub

}

@Override

public int[] getAllIndices() {

// TODO Auto-generated method stub

return null;

}

@Override

public int[] getAllValues() {

// TODO Auto-generated method stub

return null;

}

@Override

public SparseVec addition(SparseVec otherV) {

// TODO Auto-generated method stub

return null;

}

@Override

public SparseVec subtraction(SparseVec otherV) {

// TODO Auto-generated method stub

return null;

}

@Override

public SparseVec multiplication(SparseVec otherV) {

// TODO Auto-generated method stub

return null;

}

}

Examples: idx = 3 val = 7 idx = 6 val 9 idx = 9 val = 3 val =-2 idx 4 val 2 idx = 9 idx 7 val =-7 val = 2 idx 3 val = 7 idx 6 val- idx = 7 val =-7 idx = 9 idx = 3 val 7 val val 3 val =- 0 idx = 7 val =-7 idx = 4 val = val = 2 idx = 9 val=-4 Page 2 of 4