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();
    }

}

Answer 1

I assume there is a typo in the problem statement where it says this: [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].

There is no logical way that the set will remove the null just before 4. With that in mind, here is the fixed code:

The add, remove and toString functions have been fixed and some comments added.

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) {
if (endIndex <= index) { // there is no element yet at index
list.put(index, element);
endIndex = index + 1;
}
else { // there is already an element, need to push to higher indexes
for (int i = endIndex - 1; i >= index; i--)
if (list.get(i) != null) {
list.put(i+1, list.get(i));
list.remove(i);
}
list.put(index, element);
endIndex++;
}
}
  
@Override
public E remove(int index) {
E previous = list.remove (index);
for (int i = index; i < endIndex; i++) { // pull in any remaining items
if (list.get (i+1) != null) {
list.put (i, list.get (i + 1) );
list.remove (i + 1);
}
}
endIndex--;
return previous;
}
  
@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 < endIndex; i++) { // not list.size ()
if(list.get(i) == null) {
s += "null, ";
}else {
s += list.get(i).toString() + ", ";
}
}
// Remove the last unnecessary comma
if (s.length() > 0)
s = s.substring (0, s.length() - 2);
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();
}

}

// Below is the main program used to test:

import java.util.List;
import java.util.ListIterator;

public class Main
{
   public static void main(String[] args) {
String s;
       List list = new SparseList<>();
list.add("0");
list.add("1");
list.add(4, "4");
       s = list.toString (); System.out.println (s);
list.add(3, "Three");
       s = list.toString (); System.out.println (s);
list.set(4, "Four");
       s = list.toString (); System.out.println (s);
list.remove(1);
       s = list.toString (); System.out.println (s);
   }
}
// Below is the output:

[0, 1, null, null, 4]                                                                                                         

[0, 1, null, Three, null, 4]                                                                                                  

[0, 1, null, Three, Four, 4]                                                                                                  

[0, null, Three, Four, 4]