Java – addfirst method of arraydeque class

java. util. The code for the addfirst method in the 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 can't understand its meaning

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

In addition, assume that the array size is 10 Head is 0 and tail is 9 (the array is full) In this case, what indexing system inserts? (my understanding is: if the array is full, first increase its size, and then insert it in the arraysize() – 1 index.)

Solution

The downstream function is basically (head-1) modulo (elements. Length). Therefore, when head = = 0, subtracting 1 from head will result in the maximum possible value instead of - 1

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

10 is the effective length of the element. According to the implementation, elements Length is always a power of 2 If this is not the case, the operation is invalid

Understanding its working principle requires understanding bit operation Suppose elements Length = = 16 = = 00010000b and for simplicity, the length of the value is 8 bits instead of the actual 32:

(elements. Length – 1) used to obtain a bitmask of N bits, where 2 ^ n is the current length of the element (elements. Length – 1) = = 15 = = 00001111b in this case

If head > 0 and head < elements Length (given), then (head-1) & (elements. Length - 1) = = (head - 1), because the and operation with 1s does not work If head = = 0, head – 1 = = - 1 = = 11111111b (binary complement signed integer representation, although you can also think of it as a simple integer overflow.) And mask (head-1) & 00001111b = = 11111111b & 00001111b = = 00001111b = = 15, this is the desired value