ArrayList Implementation in Java

Question

Can someone please evaluate my code and let me know how I can improve it?

public class ArrayListImplementation {

static class ListNode<T> {
    private T value;

    public ListNode(T val) {
        this.value = val;
    }

    public T getValue() {
        return this.value;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append(this.value);
        return sb.toString();
    }
}

static class List<T> {
    private ListNode<T>[] node;
    private int listSize;
    private int initialCapacity;

    public List(int size) {
        node = new ListNode[size];
        initialCapacity = size;
    }

    public int size() {
        return listSize;
    }

    public boolean isEmpty() {
        return listSize == 0;
    }

    public T get(int index) {
        if(index >= initialCapacity) {
            throw new ArrayIndexOutOfBoundsException();
        }

        return node[index].getValue();
    }

    public void add(T val) {
        if(listSize == initialCapacity) {
            System.out.println("No space to add a new list element");
            return;
        }

        ListNode<T> head = null;
        if(listSize == 0) {
            head = new ListNode<>(val);
            node[0] = head;
            listSize++;
            return;
        }

        ListNode<T> cur = new ListNode<>(val);
        node[listSize++] = cur;
    }

    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("[ ");
        for(int i = 0; i < initialCapacity - 1; ++i) {
            sb.append(node[i].getValue() + ", ");
        }
        sb.append(node[initialCapacity - 1].getValue() + " ]");
        return sb.toString();
    }

    public void clear() {
        node = new ListNode[initialCapacity];
        listSize = 0;
        return;
    }

    public boolean remove(T value) {
        boolean result = false;
        for(int i = 0; i < initialCapacity; ++i) {
            if(node[i].getValue() == value) {
                result =  remove(node[i], i);
                if(result) {
                    listSize--;
                }
            }
        }   
        return result;
    }

    private boolean remove(ListNode<T> toBeRemoved, int index) {
        if(index < 0 || index >= initialCapacity) {
            return false;
        }

        if(initialCapacity > 1) {
            int prevSize = initialCapacity;
            ListNode<T>[] copyNode = node;

            node = new ListNode[--initialCapacity];
            for(int i = 0; i < index; ++i) {
                node[i] = copyNode[i];
            }

            for(int i = index + 1; i < prevSize; ++i) {
                node[i-1] = copyNode[i];
            }
        }
        else {
            this.clear();
        }
        return true;
    }
}

public static void main(String[] args) {
    List<Integer> list = new List<Integer>(5);
    System.out.println(list.isEmpty());
    list.add(5);
    list.add(10);
    list.add(15);
    System.out.println(list.get(0));
    System.out.println(list.get(2));
    System.out.println(list.size());
    list.add(20);
    System.out.println(list.size());
    list.add(25);
    System.out.println(list.get(4));
    System.out.println(list.remove(20));
    System.out.println(list.remove(45));
    System.out.println(list.remove(5));
    System.out.println(list.remove(25));
    System.out.println(list.remove(10));
    System.out.println(list.remove(15));
    //System.out.println(list.get(5)); //ArrayIndexOutOfBoundsException
    list.clear();
    System.out.println(list.size());
}}

Answer 1

1. In your ListNode::toString() the use of StringBuilder is useless overhead as you just append one single string. You could strip it down method to just this:

   public String toString() {
       if (this.value == null) { // beware of null!
           return "null";
       }
       return this.value.toString();
   }
   

2. In your List::add(T) method you should throw an Exception (maybe an ArrayIndexOutOfBoundsException with a proper message) if the list is full (if(listSize == initialCapacity) {) instead of writing a note to System.out. Otherwise the calling code of your implementation wouldn't notice the problem. See Fail Fast Principle.

3. In your add(T) method, why are there two different paths for the first and the other items, when the do exactly the same?

4. Is it by intention, that you reduce the intial/maximum size of your internal array in the remove(ListNode<T> toBeRemoved, int index) method?

   node = new ListNode[--initialCapacity];  // << newSize = initialCapacity -1
   

   It seems a bit strange to me.

   • In your remove methods you use initialCapacity where you rather should use listSize (except from the line mentioned in 4a).

   • Within the remove you could reuse the add method. I would refactor it to something like this:

     public boolean remove(T value) {
         boolean result = false;
         for(int i = 0; i < listSize; ++i) { // note: only check elements added
             if(node[i].getValue() == value) {
                 result =  remove(node[i], i);
                 if(result) {
                     listSize--;
                 }
                 // break; // note: exit loop if you only want to remove first occurence.
             }
         }   
         return result;
     }
     
     private boolean remove(ListNode<T> toBeRemoved, int deleteIdx) {
         if(deleteIdx < 0 || deleteIdx >= listSize) { // note: if no element -> exit
             return false;
         }
     
         if(listSize > 1) { // note: listSize relevant here
             ListNode<T>[] oldNode = node;
     
             node = new ListNode[initialCapacity]; // note: same size here
             int sourceIdx = 0; 
             for(int targetIdx = 0; targetIdx < listSize; targetIdx++) {
                 if (targetIdx == deleteIdx) {
                     sourceIdx++; // skip deleted element
                 }
                 node[targetIdx] = oldNode[sourceIdx++];
             }
         }
         else {
             this.clear();
         }
         return true;
     }