Implementation of Bag using only a Java Array-CodePudding

I have pretty much the whole Bag class implemented correctly and it has been proven to work, except for this remove method. The overall time complexity should be O(length). I'm trying to accomplish this by moving the element to be removed to the end of the array and swapping it with the last element. Then, I use Arrays.copyOf() to truncate the array.

public void remove(String s)
    {
        for (int i = 0; i < length; i  ) {
            if(bag[i].equals(s)){

                // Adding bag[i] to end of array: 
                if (length == SIZE){
                    SIZE *= 2;
                    bag = Arrays.copyOf(bag, SIZE);
                }
                bag[length] = bag[i];

                // Moving last element to bag[i]:
                bag[i] = bag[length-1];

                bag = Arrays.copyOf(bag, length-1);
                length--;
            }
        }
    }

If you look at my output, the removal is successful with the removal of 'Cucumber', but when I go to remove the first element in the list, 'Cabbage', it results in an index out of bounds error.

Output:

ADD Guava
Bag: {Cabbage, Cucumber, Broccoli, Banana, Broccoli, Guava}

REMOVE Cucumber
Bag: {Cabbage, Guava, Broccoli, Banana, Broccoli}

REMOVE Cucumber
Bag: {Cabbage, Guava, Broccoli, Banana, Broccoli}

REMOVE Cabbage
Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 5 out of bounds for length 5
    at ArrayBag.remove(ArrayBag.java:84)
    at Main.<init>(Main.java:53)
    at Main.main(Main.java:15)

Process finished with exit code 1

I would really appreciate any help in understanding why I'm getting this error. Thank you!

CodePudding user response：

A bag is an unordered collection of things. The quickest way to remove an item in the bag is to replace it with the last item in the array and decrementing the count. Below is how you would remove an item. I remove the void add(String item) and String toString() method, only showing just the remove method. O(n) because of the linear search for the item in the array.

class Bag {
   private String[] items = new String[100];
   private int size = 0;
   
   void remove(String item){
      int index = indexOf(item);
      if (index >= 0)
        items[index] = items[--size];
   }
   private int indexOf(String item){
      for(int i=0; i<size; i  )
        if (items[i].equals(item))
          return i;
      return -1;
   }
}

Example usage:

public class Main{
    public static void main(String[] args) {
        Bag b = new Bag();
        b.add("apple");
        b.add("banana");
        b.add("orange");
        System.out.println(b);
        b.remove("banana");
        System.out.println(b);
        b.remove("apple");
        System.out.println(b);
    }
}

Output

Bag [apple, banana, orange]
Bag [apple, orange]
Bag [orange]