addFirst method of ArrayDeque Class

Question

The code of addFirst method in java.util.ArrayDeque class is

public void addFirst(E e) {
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();
}

Here, I am not able to understand the meaning of

head = (head - 1) & (elements.length - 1)

Also, Suppose if array size is 10. head is at 0 and tail is at 9(Array is full). In this case, at what index system will do insertion? (My understanding is: if array is full then, first increase its size and then do insertion in the arraySize()-1 index.)

I had the same doubt :) – the-dumb-programmer May 08 '15 at 07:36 — the-dumb-programmer, May 08 '15 at 07:36

score 17 · Accepted Answer · answered Feb 04 '15 at 06:58

The functionality of the following line is basically (head - 1) MODULO (elements.length), so that subtracting 1 from head results in the maximum possible value instead of -1 when head == 0.

head = (head - 1) & (elements.length - 1)

10 is not valid length of elements, according to the implementation, elements.length is always a power of two. If this were not the case the operation would not work.

Understanding why this works requires knowledge of bit operations. Assuming elements.length == 16 == 00010000b and that the length of values are 8 bits instead of the actual 32 for simplicity's sake:

(elements.length - 1) is used to get a bit mask of ones n bits long, where 2^n is the current length of elements. (elements.length - 1) == 15 == 00001111b in this case.

If head > 0 and head < elements.length (which is a given), then (head - 1) & (elements.length - 1) == (head - 1), as ANDing with 1s does nothing.

If head == 0, head - 1 == -1 == 11111111b. (Two's complement signed integer notation, although you can also view it as a simple integer overflow.) ANDing with the mask (head - 1) & 00001111b == 11111111b & 00001111b == 00001111b == 15, which is the wanted value.

score 0 · Answer 2 · answered Feb 04 '15 at 07:13

Here its using & operator means it will perform Binary AND operation in both the integer.

lets assume your case head = 0 then head will become

head = -1

and elements.length = 16 (which is by default and also as @Adrian said it will be of only power of 2)

so performing the operation -1 & 15 (i.e. 11111111 & 00001111) it will become 15 which is the target position to add the element.

addFirst method of ArrayDeque Class

2 Answers2

Linked