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
– the-dumb-programmer

2015-05-08 07:36:41 +00:00
Commented May 8, 2015 at 7:36 — the-dumb-programmer
– the-dumb-programmer, Commented May 8, 2015 at 7:36

Adrian Leonhard · Accepted Answer · 2015-02-04 06:58:39Z

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.

Prashant · Accepted Answer · 2015-02-04 07:13:59Z

0

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.

answered Feb 4, 2015 at 7:13

Prashant

2,6122 gold badges23 silver badges26 bronze badges

Collectives™ on Stack Overflow

addFirst method of ArrayDeque Class

2 Answers 2

Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related