Добавление к фронту ArrayDeque в Java

Question

Мне поручено создать метод, который добавляет к фронту (слева) ArrayDeque без использования библиотеки Deque. Я придумал метод, хотя он не добавляет в очередь, он выходит с пустым que. Вот мой метод 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; 
} 

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

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:

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

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