Adding to the front of an ArrayDeque in Java

Question

I am tasked with creating a method that adds to the front (left) of an ArrayDeque without using the Deque library. I have come up with a method though its not adding to the que, it is coming out with an empty que. Here is my addLeft method:

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

Here is the test code iv been using:

public class DequeueTest {

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

Any idea where i have gone wrong ?

Where does arr come from? However, you are calling addLeft on the Dequeue but the outcome of addLeft just alters the arr but not the dequeue itself. — lschuetze
– lschuetze, Commented Jan 26, 2016 at 13:37
arr is the array first initialized in the constructor which should hold all the values — Volken
– Volken, Commented Jan 26, 2016 at 13:39
Code is quite horrible ot be honest. If you planned to create a circular buffer approach to deque, there is certainly not enough index arithmetic going on (as you need to handle wrapping around). No idea how decreasing frontPos can work after few times. When copying it should be probably copyArr[i] = arr[i-1]. Or rather corresponding System.arraycopy. Or rather proper index manipulating version of it. Look at ArrayDeque inspiration, you will need a lot of things like "elements[(tail - 1) & (elements.length - 1)]" or corresponding modulo operations. — Artur Biesiadowski
– Artur Biesiadowski, Commented Jan 26, 2016 at 14:11

penguineer · Accepted Answer · 2016-01-26 14:48:46Z

Can you clarify "ArrayDeque without using the Deque library"? Does it mean you do not want to use the ArrayDeque from the JDK?

You've gone wrong at the array copy statement, which should be

copyarr[i] = arr[i-1]

(note how the index is shifted)

Your implementation has serious runtime costs for adding elements in front, as you are copying the array every time. (From the computer science class: ArrayLists gain their runtime behaviour from doubling the array size, when needed, thus balancing the re-sizing costs over all append operations.)

Also, as already mentioned in the comments, have a look at the ArrayDeque implementation for inspiration. Maybe offerFirst is really just what you need.

Addition based on the comment by Ferrybig:

You may want to track the array size in an extra variable, so that the storage array can be larger than the actual deque. This way you can double the storage array size when it is too small, sparing you from creating a copy every time. Still, you have to move the elements (from higher to lower indexes) and finally put in the new element on the first place.

Second optimization step: save the first position and, if you expect multiple inserts at front, reserve some space, so that you don't have to move the elements on every insertion. (Again, you are trading spacial for runtime compexity.)

Collectives™ on Stack Overflow

Adding to the front of an ArrayDeque in Java

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related