Newbie sees the source code arraydeque

Start with something else ： Today, the wind in Shanghai is not small , Now the wind is still whimpering outside the window , It can't help but remind people of the wind of Shanke .

Analyze today ArrayDeque Source code

ArrayDeque The inheritance diagram of

ArrayDeque Realized Deque Interface , Internally, a resizable array is used to store elements . There is no capacity limit for arrays , The capacity of the array will increase when necessary .ArrayDeque Not thread safe . Not allowed to add Null Elements . When ArrayDeque When used as a stack ,ArrayDeque It might be better than Stack fast . When ArrayDeque As When the queue is used , It might be better than LinkedList Speed up .

to glance at ArrayDeque Several member variables in

// An array of stored elements , The length is always 2 Power of power , Arrays are not allowed to be saturated , In the use of addX Method after adding elements , If the array is saturated , Then it will be immediately expanded to twice the original length 
transient Object[] elements;
// The subscript of the header element of the double ended queue 
transient int head;
// sign ： If a new element is to be added to the end of the double ended queue ( adopt  addLast(E), add(E), or push(E)), Then the subscript of this new element in the double ended queue is tail
transient int tail;
//elements Minimum initial capacity , If the constructor specifies that the lower limit of the initial capacity is less than 8, Then choose 8 As initial capacity 
private static final int MIN_INITIAL_CAPACITY = 8;

Constructors

public ArrayDeque() {
        elements = new Object[16];
    }

// Specify the lower limit of initial capacity , The final initial capacity is greater than or equal to numElements And is 2 A number to the power of , For example, specify numElements=9, Then the initial capacity will eventually be 16
public ArrayDeque(int numElements) {
        allocateElements(numElements);
    }

// Use a collection to initialize the queue 
public ArrayDeque(Collection<? extends E> c) {
        allocateElements(c.size());
        addAll(c);
    }

We specify the initial capacity of the queue as 8, Then let's take a look at the common methods

• addFirst(E e) Insert the element in front of the queue

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

You can see that the element is not allowed to be null Of , In the beginning head and tail All are 0,elements.length=8.

ArrayDeque<Integer> deque = new ArrayDeque<>(7);
for (int i = 0; i < 8; i++) {
            deque.addFirst(i);
        }

Add the first element , expression head = (head - 1) & (elements.length - 1) It is equivalent to (-1&7)=7, therefore elements[7]=0.
Insert a sentence in the middle , About bitwise AND （&） And bitwise OR （|） If the operation is not clear, you can have a look Original code , Inverse code , Complement code Detailed explanation

After inserting head=7, It's not equal to tail, There's no need to expand

Add a second element , expression head = (head - 1) & (elements.length - 1) It is equivalent to (6&7)=6, therefore elements[6]=1. When we finish adding section 8 Element time ,
elements=[7,6,5,4,3,2,1,0], At this time ,head=0,head=tail, At this time, the capacity needs to be expanded
doubleCapacity(), The function of this method is to put elements Double the length , And then use System.arraycopy() Method to reposition elements , We will make a detailed analysis later .

• addLast(E e) Insert the element at the end of the queue

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

ArrayDeque<Integer> deque = new ArrayDeque<>(7);
for (int i = 0; i < 8; i++) {
            deque.addLast(i);
        }

This method and addFirst(E e) Just the opposite , After adding 8 After two elements ,elements=[0,1,2,3,4,5,6,7]

• offerFirst(E e) Internal calls addFirst(e) Method realization , I won't repeat

public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

• offerLast(E e) Internal calls addLast(e) Method realization , I won't repeat

public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

• pollFirst() Query the first element

public E pollFirst() {
        int h = head;
        @SuppressWarnings("unchecked")
        E result = (E) elements[h];
        // Element is null if deque empty
        if (result == null)
            return null;
        elements[h] = null;     // Must null out slot
        head = (h + 1) & (elements.length - 1);
        return result;
    }

When the queue is empty , return null. Isn't empty , Delete and return head Elements on subscripts , And then put head Move back one position .
* pollLast() Query the last element

public E pollLast() {
        int t = (tail - 1) & (elements.length - 1);
        @SuppressWarnings("unchecked")
        E result = (E) elements[t];
        if (result == null)
            return null;
        elements[t] = null;
        tail = t;
        return result;
    }

When the queue is empty , return null. Isn't empty , Delete and return the last element , And then put tail Move forward one position .

• removeFirst() Internal calls pollFirst(), If the element is null, Throw an exception

public E removeFirst() {
        E x = pollFirst();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

• removeLast() Internal calls pollLast(), If the element is null, Throw an exception

public E removeLast() {
        E x = pollLast();
        if (x == null)
            throw new NoSuchElementException();
        return x;
    }

The following methods are simple

// Returns the first element of the queue , But don't delete , If null, How to throw an exception 
public E getFirst() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[head];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }

// Returns the last element of the queue , But don't delete , If null, How to throw an exception 
    public E getLast() {
        @SuppressWarnings("unchecked")
        E result = (E) elements[(tail - 1) & (elements.length - 1)];
        if (result == null)
            throw new NoSuchElementException();
        return result;
    }
// Returns the first element of the queue , But don't delete , The return value can be null
    @SuppressWarnings("unchecked")
    public E peekFirst() {
        // elements[head] is null if deque empty
        return (E) elements[head];
    }
// Returns the last element of the queue , But don't delete , The return value can be null
    @SuppressWarnings("unchecked")
    public E peekLast() {
        return (E) elements[(tail - 1) & (elements.length - 1)];
    }

• removeFirstOccurrence(Object o) Delete the first element in the queue equal to the specified element , from head To tail Traverse . If the specified element is null, Or the deletion fails and returns false, Delete successful return true.

public boolean removeFirstOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = head;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                // call delete Delete ,delete Method by moving elelemts The elements in , To overwrite the element at the position to be deleted , And mobile elements have been optimized , And change accordingly head and tail
                delete(i);
                return true;
            }
            i = (i + 1) & mask;
        }
        return false;
    }

• removeLastOccurrence(Object o) Delete the last element in the queue equal to the specified element

public boolean removeLastOccurrence(Object o) {
        if (o == null)
            return false;
        int mask = elements.length - 1;
        int i = (tail - 1) & mask;
        Object x;
        while ( (x = elements[i]) != null) {
            if (o.equals(x)) {
                delete(i);
                return true;
            }
            i = (i - 1) & mask;
        }
        return false;
    }

* Look at the doubleCapacity() increase elements It's twice the capacity , Repositioning elements

 private void doubleCapacity() {
        assert head == tail;
        int p = head;
        int n = elements.length;
        int r = n - p; // number of elements to the right of p
        int newCapacity = n << 1;
        if (newCapacity < 0)
            throw new IllegalStateException("Sorry, deque too big");
        Object[] a = new Object[newCapacity];
        System.arraycopy(elements, p, a, 0, r);
        System.arraycopy(elements, 0, a, r, p);
        elements = a;
        head = 0;
        tail = n;
    }

Why in this method System.arraycopy() Why should the method be called twice , Let's analyze .
First of all, there are two places where this method is called ,addFirst() and addLast()

Case one ： Use only addFirst() Method add element , When we finish adding the 8 Elements , here elements=[7,6,5,4,3,2,1,0], It needs to be expanded

here
head = tail=0;
p=0;
n=8;
r=8;
First, double the capacity of the array , then
System.arraycopy(elements, p, a, 0, r); Will be able to elements The elements in are subscript p=0 copy to a in , Total copies r=8 Elements ,a From the subscript for 0 Start placing elements

// The second copy is because p=0, So it won't change a.
System.arraycopy(elements, 0, a, r, p);
Finally let elements Point to a. After copying elements=[7,6,5,4,3,2,1,0,null,null,null,null,null,null,null,null],head=0,tail=8;

Reuse addFirst() Method to add an element 8, result elements=[7,6,5,4,3,2,1,0,null,null,null,null,null,null,null,8]

Reuse addFirst() Method to add an element 9, result elements=[7,6,5,4,3,2,1,0,null,null,null,null,null,null,9,8]

As we continue to add elements elements=[7,6,5,4,3,2,1,0,15,14,13,12,11,10,9,8], At this time, the array is full and needs to be expanded
here
head == tail=8;
p=8;
n=16;
r=8;
First, double the capacity of the array , then
System.arraycopy(elements, p, a, 0, r); Will be able to elements The elements in are subscript p=8 copy to a in , Total copies r=8 Elements ,a From the subscript for 0 Start placing elements
After copying a=[15,14,13,12,11,10,9,8,...]
// Second copy p=8, Will be able to elements The elements in are subscript 0 copy to a in , Total copies p=8 Elements ,a From the subscript r=8 Start placing elements
System.arraycopy(elements, 0, a, r, p);
Finally let elements Point to a. After copying a=[15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,...],head=0,tail=16;

Insert a sentence , Here, I vaguely feel that the person who wrote this code is really powerful , admire ！

The second case ： Use only addLast() Method add element , When we finish adding the 8 Elements , here elements=[0,1,2,3,4,5,6,7], It needs to be expanded
here
head = tail=0;
p=0;
n=8;
r=8;
First, double the capacity of the array , then
System.arraycopy(elements, p, a, 0, r); Will be able to elements The elements in are subscript p=0 copy to a in , Total copies r=8 Elements ,a From the subscript for 0 Start placing elements
// The second copy is because p=0, So it won't change a.
System.arraycopy(elements, 0, a, r, p);
Finally let elements Point to a. After copying elements=[0,1,2,3,4,5,6,7,null,null,null,null,null,null,null,null],head=0,tail=8;
Reuse addLast() Method to add an element 8, result elements=[0,1,2,3,4,5,6,7,8,null,null,null,null,null,null,null]
Reuse addLast() Method to add an element 9, result elements=[0,1,2,3,4,5,6,7,8,9,null,null,null,null,null,null]

As we continue to add elements elements=[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15], At this time, the array is full and needs to be expanded
here
head = tail=0;
p=0;
n=16;
r=16;
First, double the capacity of the array , then
System.arraycopy(elements, p, a, 0, r); Will be able to elements The elements in are subscript p=0 copy to a in , Total copies r=16 Elements ,a From the subscript for 0 Start placing elements
// The second copy is because p=0, So it won't change a.
System.arraycopy(elements, 0, a, r, p);
Finally let elements Point to a. After copying elements=[0,1,2,3,4,5,6,7,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,...],head=0,tail=16;

Insert a sentence , Here I deeply feel that the person who wrote this code is really powerful , admire ！

Analyze another situation
Use addFirst() Method add element , When we finish adding the 7 Elements , here elements=[null,6,5,4,3,2,1,0], And then use addLast() Method to add an element 7,
here elements=[7,6,5,4,3,2,1,0] Then the array is full and needs to be expanded
here
head = tail=1;
p=1;
n=8;
r=7;
Double the capacity of the array
System.arraycopy(elements, p, a, 0, r); Will be able to elements The elements in are subscript p=1 copy to a in , Total copies r=7 Elements ,a From the subscript for 0 Start placing elements , Copy
After completion a=[6,5,4,3,2,1,0,...]
Second copy
System.arraycopy(elements, 0, a, r, p); Will be able to elements The elements in are subscript 0 copy to a in , Total copies p=1 Elements ,a From the subscript for r=7 Start placing elements , After copying
a=[6,5,4,3,2,1,0,7,...] here elements=[6,5,4,3,2,1,0,7,...],head = 0``tail=8
If you continue to use it at this time, then use addLast() add to 8 Elements element=[6,5,4,3,2,1,0,7,8,9,10,11,12,13,14,15], At this point, the array is saturated , Capacity expansion
head = tail=0;
p=0;
n=16;
r=16;
Double the capacity of the array
System.arraycopy(elements, p, a, 0, r); Will be able to elements The elements in are subscript p=0 copy to a in , Total copies r=16 Elements ,a From the subscript for 0 Start placing elements , Copy
After completion a=[6,5,4,3,2,1,0,7,8,9,10,11,12,13,14,15,...]
Second copy p=0,a Will not change .
Last elements=[6,5,4,3,2,1,0,7,8,9,10,11,12,13,14,15,...],head = 0``tail=16

ending ： Today is a beautiful day , Tomorrow will also make a beautiful day .