Deque last element insert.

Question

Datastructure Degue.

Method to insert value in front:

Work fine.

 public void insertLeft(Item item) {       
       if (size == deque.length){
          resize(2 * deque.length);
      }
      deque[start] = item;
      start++;
      size++;
}

Method to insert value in tail - overwrite last element because of this line //end = deque.length - 1;

public void insertRight(Item item) {
    if (size == deque.length){
        resize(2 * deque.length);
    }
    end = deque.length - 1;
    deque[end++] = item;
    end %= deque.length;
    size++;
}

How can I fix it?

Answer 1

Say the array is size 10 and currently has 3 values:

_ _ _ 1 2 3 _ _ _ _
      ^     ^
  start     end

As you can see, your insertLeft method is wrong:

• It would replace an existing value
• It moves the index in the wrong direction
• It doesn't handle wrap-around

And your insertRight method is wrong:

• It throws away the end value

Re-think what you're doing, e.g. does the resize() method handle the condition where the array has wrapped?

Example:

3 4 5 _ _ _ _ _ 1 2
      ^         ^
    end         start

If you call insertRight() 5 times, you get:

3 4 5 X X X X X 1 2
                ^
                start
                end

A 6th call to insertRight() would trigger resize(), but would it correct handle it? E.g. resulting in:

3 4 5 X X X X X Y _ _ _ _ _ _ _ _ _ 1 2
                  ^                 ^
                  end               start