Добавление в начало ArrayDeque в Java

Question

Мне поручено создать метод, который добавляет в начало (слева) ArrayDeque без использования библиотеки Deque. Я придумал метод, хотя он не добавляет в очередь, он выходит с пустой очередью. Вот мой метод addLeft:

public T[] addLeft(T item){
    T[] copyarr = (T[]) new Object[arr.length+1];

    if(isEmpty()){
        copyarr[frontPos] = item;

    }else{
        copyarr[frontPos] = item;
        frontPos--;
        for(int i = 1; i<copyarr.length; i++){
            copyarr[i] = arr[i];
        }
    }
    arr = copyarr;
    return arr;
}

Вот тестовый код, который я использовал:

public class DequeueTest {

public static void main(String[] args) {
    Dequeue test = new Dequeue();
    test.addLeft(3);
    test.addLeft(4);
    System.out.println(test.toString());
}
}

Есть идеи, где я ошибся?

Answer 1

Можете ли вы уточнить "ArrayDeque без использования библиотеки Deque"? Означает ли это, что вы не хотите использовать ArrayDeque из JDK?

Вы ошиблись в операторе копирования массива, который должен быть

copyarr[i] = arr[i-1]

(обратите внимание, как смещается индекс)

Ваша реализация имеет серьезные затраты времени выполнения для добавления элементов вперед, так как вы копируете массив каждый раз. (Из урока информатики: ArrayLists получают свое поведение во время выполнения от удвоения размера массива, когда это необходимо, таким образом, балансируя затраты на изменение размера по всем операциям добавления.)

Также, как уже упоминалось в комментариях, посмотрите на реализацию ArrayDeque для вдохновения. Может быть offerFirst это действительно то, что вам нужно.

Дополнение на основе комментария Ferrybig:

Возможно, вы захотите отследить размер массива в дополнительной переменной, чтобы массив хранения мог быть больше, чем фактическая deque. Таким образом, вы можете удвоить размер массива хранения, когда он слишком мал, избавляя вас от необходимости каждый раз создавать копию. Тем не менее, вам нужно переместить элементы (с более высоких на более низкие индексы) и, наконец, поставить новый элемент на первое место.

Второй шаг оптимизации: сохраните первую позицию и, если вы ожидаете несколько вставок спереди, зарезервируйте некоторое пространство, чтобы вам не приходилось перемещать элементы при каждой вставке. (Опять же, вы торгуете пространственно ради сложности во время выполнения.)