Question

I am implementing a generic List class and not getting the expected output.

My current output is: [0, 1, null]

Expected Output in a separate test class:

List list = new SparseList<>(); 
list.add("0");
list.add("1");
list.add(4, "4");

will result in the following list of size 5: [0, 1, null, null, 4].

list.add(3, "Three");

will result in the following list of size 6: [0, 1, null, Three, null, 4].

list.set(3, "Three");

is going to produce a list of size 5 (unchanged): [0, 1, null, Three, 4].

When removing an element from the list above, via list.remove(1); the result should be the following list of size 4: [0, null, Three, 4]

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class SparseList<E> implements List<E>{
    private int endIndex = 0;
    
    private HashMap<Integer,E> list;
    
    public SparseList() {
        list = new HashMap<>();
    }
    
    public SparseList(E[] arr) {
        list = new HashMap<>();
        for(int i = 0; i <arr.length; i++) {
            list.put(i, arr[i]);
        }
        endIndex = arr.length - 1;
    }
    
    @Override
    public boolean add(E e) {
        list.put(endIndex, e);
        endIndex++;
        return true;
    }
    
    @Override
    public void add(int index, E element) {
        list.put(index, element);
    }
    
    @Override
    public E remove(int index) {
        return list.remove(index);
    }
    
    @Override
    public E get(int index) {
        return list.get(index);
    }
    
    @Override
    public E set(int index, E element) {
        E previous = list.get(index);
        list.put(index, element);
        return previous;
    }
    
    @Override
    public int size() {
        return endIndex + 1;
    }

    @Override
    public void clear() {
        list.clear();
        
    }
    
    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public String toString() {
        String s = "";
        for(int i = 0; i < list.size(); i++) {
            if(list.get(i) == null) {
                s += "null, ";
            }else {
            s += list.get(i).toString() + ", ";
        }
        }
        return "[" + s + "]";
    }

    @Override
    public boolean contains(Object o) {
        throw new UnsupportedOperationException();
    }

    @Override
    public Iterator<E> iterator() {
        throw new UnsupportedOperationException();
    }

    @Override
    public Object[] toArray() {
        throw new UnsupportedOperationException();
    }

    @Override
    public <T> T[] toArray(T[] a) {
        throw new UnsupportedOperationException();
    }


    @Override
    public boolean containsAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean removeAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean retainAll(Collection<?> c) {
        throw new UnsupportedOperationException();
    }

    @Override
    public boolean remove(Object o) {
        throw new UnsupportedOperationException();
    }
    
    @Override
    public int indexOf(Object o) {
        throw new UnsupportedOperationException();
    }

    @Override
    public int lastIndexOf(Object o) {
        throw new UnsupportedOperationException();
    }

    @Override
    public ListIterator<E> listIterator() {
        throw new UnsupportedOperationException();
    }

    @Override
    public ListIterator<E> listIterator(int index) {
        throw new UnsupportedOperationException();
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        throw new UnsupportedOperationException();
    }

}

8.4.3

Answer 1

Raw_code:

import java.util.Collection;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;

public class SparseList<E> implements List<E>{
private int endIndex = 0;

private HashMap<Integer,E> list;

public SparseList() {
list = new HashMap<>();
}

public SparseList(E[] arr) {
list = new HashMap<>();
for(int i = 0; i <arr.length; i++) {
list.put(i, arr[i]);
}
endIndex = arr.length - 1;
}

@Override
public boolean add(E e) {
list.put(endIndex, e);
endIndex++;
return true;
}

@Override
public void add(int index, E element) {
int i, count = 0, temp;
// for loop to add elements into the list until the given key reached
for (i = 0; i<= index; i++){
// if statement to check whether the given key(index) maths the present index of list
if (i == index)
// if true, adding element at the given position
list.put(index, element);
}

// changing endIndex value by comparing the key value with current endIndex
// if endIndex value is smaller than the number of elements in list , i.e. key value
// assigning index(key value) to the endIndex
if (index > endIndex)
endIndex = index;
else{
for(temp =i; i <= endIndex+1; i++){
if(i != temp){
list.put(i, list.get(i-1));
count++;
}
}
list.put(temp, null);
endIndex += count;
}
}

@Override
public E remove(int index) {
return list.remove(index);
}

@Override
public E get(int index) {
return list.get(index);
}

@Override
public E set(int index, E element) {
E previous = list.get(index);
int i, k;
for ( i = 0; i<= index; i++){
if (i == index){
list.put(index, element);
}
}
for (k = i; k < endIndex; k++){
list.put(k, list.get(k+1));
}
list.remove(k);
endIndex--;
return previous;
}

@Override
public int size() {
return endIndex + 1;
}

@Override
public void clear() {
list.clear();

}

@Override
public boolean isEmpty() {
return list.isEmpty();
}

@Override
public String toString() {
String s = "";
for(int i = 0; i < size() ; i++) {
if(list.get(i) == null) {
s += "null, ";
}
else {
s += list.get(i).toString() + ", ";
}
}
return "[" + s + "]";
}
@Override
public boolean contains(Object o) {
throw new UnsupportedOperationException();
}

@Override
public Iterator<E> iterator() {
throw new UnsupportedOperationException();
}

@Override
public Object[] toArray() {
throw new UnsupportedOperationException();
}

@Override
public <T> T[] toArray(T[] a) {
throw new UnsupportedOperationException();
}

@Override
public boolean containsAll(Collection<?> c) {
throw new UnsupportedOperationException();
}

@Override
public boolean addAll(Collection<? extends E> c) {
throw new UnsupportedOperationException();
}

@Override
public boolean addAll(int index, Collection<? extends E> c) {
throw new UnsupportedOperationException();
}

@Override
public boolean removeAll(Collection<?> c) {
throw new UnsupportedOperationException();
}

@Override
public boolean retainAll(Collection<?> c) {
throw new UnsupportedOperationException();
}

@Override
public boolean remove(Object o) {
throw new UnsupportedOperationException();
}

@Override
public int indexOf(Object o) {
throw new UnsupportedOperationException();
}

@Override
public int lastIndexOf(Object o) {
throw new UnsupportedOperationException();
}

@Override
public ListIterator<E> listIterator() {
throw new UnsupportedOperationException();
}

@Override
public ListIterator<E> listIterator(int index) {
throw new UnsupportedOperationException();
}

@Override
public List<E> subList(int fromIndex, int toIndex) {
throw new UnsupportedOperationException();
}
}

Driver.java:
import java.util.List;
public class Driver{
public static void main(String[] args){
List list = new SparseList<>();
list.add("0");
list.add("1");
list.add(4, "4");
list.add(3, "Three");
list.set(3, "Three");
System.out.println(list);
}
}