Based on JDK1.8 in Java ArrayDeque set of source code for in-depth analysis, including a variety of methods of the underlying implementation, at the end of the ArrayDeque and LinkedList comparison case and use recommendations.
1 Overview of ArrayDeque
public class ArrayDeque< E > extends AbstractCollection< E > implements Deque< E >, Cloneable, Serializable
ArrayDeque, from JDK1.6, is a dual-ended queue that uses a variable capacity circular array. The internal elements are ordered (stored in order), and null elements are not supported (LinkedList is supported).
AbstractCollection inherits from AbstractCollection and is a member of the Java Collection system. It has the common methods of the Collection system, such as getting iterator methods from iterator().
There is no implementation of the List interface, no method to get more advanced Listiterator iterators through Listiterator (), and no set of methods to manipulate elements by index, such as add(int index, E element), get(int index), Remove (int index), set(int index, E element), etc.
The Deque interface is implemented, that is, “double Ended queue, double ended queue”, so there is a method to access elements at both ends of the double-ended queue, and can simulate the “first-in, first-out FIFO” queue, and can simulate the “first-in, last-out FILO” stack.
Cloneable and Serializable interface are implemented to support cloning and serialization operations.
ArrayDeque implementation is not synchronized, but you can use the Collections. SynchronizedCollection () to convert a thread-safe Collection!
Learning ArrayDequed is often accompanied by comparing it to a LinkedList, which you can read about in this article:Java LinkedList set source depth analysis and application introduction.
2 ArrayDeque API methods
Like LinkedList, ArrayDeque implements the Deque interface and has several methods that operate at the top and bottom of the list, such as insert, fetch, and remove. Some methods also throw exceptions, and some return a special value such as null:
| behavior | The first element (header) | The last element (tail) | ||
| The results of | An exception is thrown | Special values | An exception is thrown | Special values |
| insert | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| remove | removeFirst() | pollFirst() | removeLast() | pollLast() |
| To obtain | getFirst() | peekFirst() | getLast() | peekLast() |
Because the Deque interface inherits from the Queue interface. When using a dual-ended queue as a queue, you get FIFO (first-in, first-out) behavior. Removes the element from the beginning of the dual-end queue by adding it to the end of the dual-end queue.
The methods inherited from the Queue interface are completely equivalent to Deque methods, as shown in the following table:
| The Queue method | Equivalent Deque method |
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
A double-ended queue Deque can also be used as a LIFO (last in, first out) Stack, and this interface should be used first over the legacy Stack class. When a dual-ended queue is used as a stack, elements are pushed to the beginning of the dual-ended queue and ejected from the beginning of the dual-ended queue. The stack method is completely equivalent to the Deque method, as shown in the following table:
| The stack method | Equivalent Deque method |
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
Both the queue and the stack extract elements from the beginning of the two-endian queue.
3 ArrayDeque source parsing
3.1 Main class attributes
ArrayDeque: ArrayDeque: ArrayDeque: ArrayDeque: ArrayDeque: ArrayDeque: ArrayDeque: ArrayDeque: ArrayDeque
transient Object[] elements;
/** * The index of the head node of the dual-end queue */
transient int head;
/** * The index of the next bit of the end node of the double-ended queue, i.e. the index of the next element to be added to the end. * /
transient int tail;
/** * The minimum size used by the newly created collection. The capacity, it must be a power of 2 */
private static final int MIN_INITIAL_CAPACITY = 8;
Copy the codeAs you can see from these main properties, ArrayDeque uses arrays to implement dual-endian queues, with the array index as either the head or the next bit at the end of the queue, and with a minimum capacity of 8, which must be a power of 2.
3.2 Constructor and initial capacity
3.2.1 ArrayDeque ()
public ArrayDeque()
Construct an empty array double – ended queue with an initial capacity of 16.
public ArrayDeque(a) {
// Create an empty array of length 16
elements = new Object[16];
}
Copy the code3.2.2 ArrayDeque (int numElements)
public ArrayDeque(int numElements)
Constructs an empty array double – ended queue with the specified initial capacity.
private void allocateElements(int numElements) {
// Get a fixed minimum capacity
int initialCapacity = MIN_INITIAL_CAPACITY;
// If the specified capacity is greater than or equal to the fixed minimum capacity
// Then try to find the smallest power of 2 larger than the specified capacity by using the following algorithm
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
// If the specified capacity is less than the fixed minimum capacity, then the initial capacity is the fixed minimum capacity 8
// Create an array based on the final capacity
elements = new Object[initialCapacity];
}
Copy the codeLet’s focus on the algorithm to find the actual initial capacity!
The first line is initialCapacity = numElements, which assigns the specified capacity value to the initialCapacity.
And then the next six lines:
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
Copy the codeThis is a very clever algorithms for incoming any less than 2 ^ ^ 30 (greater than or equal to 8) type int initialCapacity is an integer value, after five times the unsigned right shift and bit or after operation, will get a 2 ^ ^ k – 1 value, and then from 1-6, get ^ ^ 2 k, This 2^k^ is the smallest power of 2 greater than initialCapacity.
| = is the ligatures, “or” a | = b, meaning that a = a | b. Here | is an or operator, when calculating first converts a decimal number to a binary complement, digits alignment, two digits as long as there is a 1, the result is 1, otherwise the result is 0.
>>> indicates the unsigned right shift, and a>>> N indicates the number A moves n bits to the right, including the sign bit. That is, the decimal number A is converted to binary complement first, and then moved n bits to the right with the sign bit, and the left space is filled with 0, where the unsigned right shift a>>>n can be expressed as a= A /2^n
This might be a little abstract, but let’s take an example, let’s say the initialCapacity is 8.
8The binary complement of:0000 0000 0000 0000 0000 0000 0000 1000
>>>1Then it becomes:0000 0000 0000 0000 0000 0000 0000 0100| become after operation:0000 0000 0000 0000 0000 0000 0000 1100
>>>2Then it becomes:0000 0000 0000 0000 0000 0000 0000 0011| become after operation:0000 0000 0000 0000 0000 0000 0000 1111
>>>4Then it becomes:0000 0000 0000 0000 0000 0000 0000 0000| become after operation:0000 0000 0000 0000 0000 0000 0000 1111
>>>8Then it becomes:0000 0000 0000 0000 0000 0000 0000 0000| become after operation:0000 0000 0000 0000 0000 0000 0000 1111
>>>16Then it becomes:0000 0000 0000 0000 0000 0000 0000 0000| become after operation:0000 0000 0000 0000 0000 0000 0000 1111Since the increase1Then it becomes:0000 0000 0000 0000 0000 0000 0001 0000
Copy the codeThe final result of the right shift operation and the bit or operation is converted to decimal 15, and then incremented by 1 to 16, which is the smallest power of 2 greater than 8.
In fact, the core of the algorithm is to convert all the lower order bits of the number to 1 by right shift and or operation. Since integers are fixed to 32 bits in Java, we can see that five right moves have a total of 32 bits shifted to the right, so that all the lower bits of the highest bit 1 can be changed to 1 for all positive integers in the int range.
And then you add one, and the binary carries the one forward, and all the lower orders are zeros, and you get the smallest power of two greater than n.
The following code takes into account the special case:
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
Copy the codeIf the specified initial value is a particularly large (greater than or equal to 2^30^) int value, then its binary complement is “01…” In this way, after the above algorithm, the value must be 0111 1111 1111 1111 1111 1111 1111 1111. Then add 1, so it becomes 1, 0000, 0000, 0000, 0000, 0000, 0000, 0000.
As you can see, the end result is that the highest sign bit becomes 1, which makes it a negative number. This error is actually caused by exceeding the maximum limit for int values. In this case, ArrayDeque moves the initialCapacity unsigned one bit to the right, so that it becomes 0100 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 0000 This is actually the maximum power of 2 in the range of int (Java int range is -2^31^ ~ 2^31^-1).
Conclusion:
For a constructor with a specified capacity, its actual capacity is not necessarily the specified capacity. There are three cases:
- If num_initial_capacity is smaller than MIN_INITIAL_CAPACITY, the actual initialized capacity is MIN_INITIAL_CAPACITY.
- If numElements is greater than or equal to MIN_INITIAL_CAPACITY and less than 2^30^, the actual initialized capacity is the least quadratic power greater than numElements.
- If numElements is greater than or equal to 2^30^, the actual initialized capacity is 2^30^.
Bonus: In fact, the Hashmap source code uses a similar algorithm for specifying the initial capacity. Also, why does the initial capacity have to be a power of two? There will be a solution below!
3.2.3 ArrayDeque (Collection <? extends E> c)
public ArrayDeque(Collection<? extends E> c)
Constructs a double-ended queue containing the elements of the specified collection in the order returned by the iterators of the collection.
public ArrayDeque(Collection<? extends E> c) {
// Allocate an empty array of sufficient capacity
allocateElements(c.size());
// Batch add
addAll(c);
}
public boolean addAll(Collection<? extends E> c) {
boolean modified = false;
// Inside is the circular call to the add method
for (E e : c)
if (add(e))
modified = true;
return modified;
}
Copy the code3.3 Adding Methods
3.3.1 Adding methods to the Tail
public void addLast(E e)
Inserts the specified element at the end of this two-endian queue.
/** * adds the specified element to the end of the double-ended queue. * *@paramE The element to be added */
public void addLast(E e) {
// If the added element is NULL, a NullPointerException is thrown
if (e == null)
throw new NullPointerException();
// Store the element at tail, the empty node next to the original tail node
elements[tail] = e;
/* Calculate the new index of the next tail node */
if ((tail = (tail + 1) & (elements.length - 1)) == head)
// Expansion method
doubleCapacity();
}
Copy the codeFirst, if the added element is NULL, a NullPointerException is thrown. Then insert the element; The new index of the next tail node is calculated and the capacity expansion is determined.
The main calculation of the next tail node index algorithm and capacity expansion mechanism!
3.3.1.1 Calculating a New index
First, I’ll explain one of the drawbacks of the traditional approach to implementing queues using arrays, namely “false overflow.” For traditional array implementations of queues, the head and tail nodes are generally located at the beginning and end of the array. If the tail node reaches the end of the array, directly adding the index of the tail node will cause the array length to overflow, so expansion is often considered. However, there is still space left in the first half of the array, such as deleting some of the head nodes while inserting the tail nodes). This phenomenon is called “false overflow” because the real array space is not used up, resulting in a waste of space. On this in the Java queue data structure in detail and the implementation of the case demo in a more detailed explanation!
To optimize this “false overflow” disadvantage. We can cancel the head and tail node relative location, for example, if the end node to reach at the end of the array, array expansion and not in a hurry, at this time will be the next end node index set to 0 index, namely the beginning of the array, and then the index at head and a tail node index whether overlap, if there is no overlap, so that the array and can make use of the space, If it overlaps then you can expand it, so you can take advantage of the free space in the first half.
This solution results in the index of the queue’s head and tail, which are not related to the index of the array’s head and tail. The index of the head node may be larger than the index of the tail node.
In an ArrayDeque, the operation of finding the next tail node implements the above solution algorithm. The implementation is also very clever. A small amount of code can be used to calculate the index of the next tail node and handle the case when the head and tail indexes reach both ends of the array. The final tail value will be fixed between [0, elements.length-1]. Its algorithm implementation is as follows:
tail = (tail + 1) & (elements.length - 1)
Copy the code&represents the bit and operation that converts a decimal number to a binary complement, then the result is 1 if both the bits are 1, and the result is 0 otherwise. For example, if elements. Length =8 and tail=7, then the index of the next tail node will be 8, and the calculated value should be 0, 8&7:
0000 1000 -->8
0000 0111 -->7-- -- -- -- -0000 0000 -->0
Copy the codeI also need to explain why the initial capacity of an array must be a power of two.
If a positive integer is raised to the power of 2, then the binary number must be of the form “the highest bit is 1, the lowest bit is all zeros”; If the number is subtracted by 1 and its binary is of the form “the highest bit is reduced by one and all the lower bits are 1s”, the binary of 8 and 7 above is 1000, and the binary of 7 is 0111.
If our elements. Length is raised to a power of 2, then elements. Length -1 will be the same as the ones mentioned above. For example, if elements. Length is 8 and tail is 3 at some point, then the next tail should be 4, after & :
0000 0100 -->4
0000 0111 -->7-- -- -- --0000 0100 -->4
Copy the codeWe can find that for the first operand tail+1 (1~ elements. Length), (tail +1) & (elements. Length -1) can get all the results of 0~ elements.
If our elements. Length is not a power of 2, then the elements. Length -1 binary will be of the form “the highest bit is reduced by one, and all the lower bits are 1”.
For example, if elements. Length is 9 and tail is 3 at some point, then the next tail should be 4, after & :
0000 0100 -->4
0000 1000 -->8-- -- -- -- --0000 0000 -->0
Copy the codeWe can find that for the first operand tail+1 (1~ elements. Length), (tail +1) & (elements. Length -1) cannot get all the results of 0~ elements. This will cause problems in calculating the index of the next tail node.
There’s actually a rule of calculation here. For a positive integer m, n:
- If n=m, then m&n=n;
- If n is a power of two, and m is less than n, then M&n is equal to zero;
- If n is not a power of two, and m is less than n, then M&n =m;
- If n is a power of two, then n plus 1&n is equal to n;
- If n is not a power of 2, then n plus 1&n is equal to 0;
If elements. Length is a power of 2, then elements. Length -1 is not a power of 2. According to the above calculation rules, “array capacity (length) must be a power of 2” this requirement is to ensure the correctness of the calculation of the next tail node index and the first node index, that is, to ensure that the calculated index can be taken to [0~elements. Length -1] between all the values!
3.3.1.2 Capacity Expansion Mechanism
After calculating the next index of the new tail node using the above algorithm, we see that the value will be compared with head. If the value is equal, that is, the next tail node and the index of the head node overlap, which means that the group capacity is really used up and needs to be expanded.
The doubleCapacity method is used to increase the capacity of the system. It is used to increase the capacity of the system by twice as much as the original capacity.
/** * Try to double the original capacity, but it's not that easy */
private void doubleCapacity(a) {
// The predicate starts and ends coincide
assert head == tail;
// Save the header index
int p = head;
// Save the size of the original array
int n = elements.length;
// Get the number of elements to the right of the header node
int r = n - p; // number of elements to the right of p
NewCapacity =n*(2^1) newCapacity=n*(2^1)
int newCapacity = n << 1;
// If the new capacity is greater than or equal to 2^30, the new capacity will be less than 0
if (newCapacity < 0)
// Throw an exception directly
throw new IllegalStateException("Sorry, deque too big");
// If newCapacity is greater than 0, create an array
Object[] a = new Object[newCapacity];
/* Copy the original array data to the new array */
}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}
System.arraycopy(elements, p, a, 0, r);
// Copy the data from the left of the original head node with index [0,p-1] to the new array with index [r,p-1]
System.arraycopy(elements, 0, a, r, p);
// Change the index of the first node back to 0 and the index of the next last node back to n(that is, the size of the original array, because the array can hold the index)
/* Change the reference */
elements = a;
// Re-assign the header index
head = 0;
// Re-assign the index of the next tail node
tail = n;
}
Copy the codeLet’s summarize the main steps of expansion:
- First calculate the new capacity, use
<<Calculate that the theoretical new capacity should be twice the original capacity or negative, and then go to step 2; In fact, if the original capacity is greater than or equal to 2^30^, the expanded capacity will be less than 0. That is, the maximum capacity of ArrayDeque is 2^30^. - Then check whether the new capacity is less than 0. If the value is less than 0, the new capacity exceeds the upper limit of the int value, and an exception is thrown. The program ends.
- Create an empty array of new size and copy the data from the original array to the new array. After two copies, the index of the head node is changed to 0 again, and the index of the next tail node is changed to the length of the original array. Then change the array references and associated values, and the expansion is over!
3.3.1.3 Other methods
public boolean add(E e)
Adds the specified element to the end of the double-ended queue.
public boolean add(E e) {
// Call the addLast method internally
addLast(e);
return true;
}
Copy the codepublic boolean offerLast(E e)
Adds the specified element to the end of the double-ended queue.
public boolean offerLast(E e) {
// Call the addLast method internally
addLast(e);
return true;
}
Copy the codepublic boolean offer(E e)
Adds the specified element to the end of the double-ended queue.
public boolean offer(E e) {
// Call the offerLast method internally
return offerLast(e);
}
Copy the code3.3.2 Methods to add to the header
public void addFirst(E e)
Inserts the specified element into the beginning of this two-endian queue.
public void addFirst(E e) {
/ / found empty
if (e == null)
throw new NullPointerException();
// Calculate the new header index and insert the element
// The index of the next tail node is calculated in the same way
elements[head = (head - 1) & (elements.length - 1)] = e;
// If the index of the head node is equal to the index of the next tail node, then try expanding
if (head == tail)
doubleCapacity();
}
Copy the codeLet’s look at how the header index is calculated:
head = (head - 1) & (elements.length - 1)
Copy the codeThis method is similar to the next tail index, except that the first operand is head-1. Since the initial head is 0, when the first head node is added, it is -1&(elements.length -1). The first node index starts at the end of the array and then decreases successively. The first operand is tail+1. The last index starts at the head of the array and increases incrementing. This is also an interesting result!
3.3.2.1 Other methods
public boolean offerFirst(E e)
Inserts the specified element into the beginning of this two-endian queue.
public boolean offerFirst(E e) {
// Call the addFirst method internally
addFirst(e);
return true;
}
Copy the codepublic void push(E e)
Pushes the element onto the stack represented by this double-ended queue. In other words, insert the element at the beginning of this double-ended queue.
public void push(E e) {
// Call the addFirst method internally
addFirst(e);
}
Copy the code3.4 Removing Methods
3.4.1 Method for Removing the Tail
public E pollLast()
Get and remove the last element of this double-enqueued; If this dual-end queue is empty, null is returned.
public E pollLast(a) {
// Since tail represents the index of the next node of the tail node, we get the index of the real tail node
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked")
// Get the node element result at the index
E result = (E) elements[t];
// Return null if result is null
if (result == null)
return null;
// Empty the space at the index
elements[t] = null;
//tail is assigned to the index
tail = t;
// Return the element value
return result;
}
Copy the code3.4.1.1 Other methods
public E removeLast()
Get and remove the last element of this double-enqueued; If this double-ended queue is empty, it throws a NoSuchElementException exception.
public E removeLast(a) {
// Call the pollLast method internally
E x = pollLast();
// Throw an exception if the return value is NULL
if (x == null)
throw new NoSuchElementException();
return x;
}
Copy the code3.4.2 Method for Removing the Header
public E pollFirst()
Get and remove the first element of this double-enqueued; If this dual-end queue is empty, null is returned.
public E pollFirst(a) {
// Get the index of the head nodules
int h = head;
@SuppressWarnings("unchecked")
// Get the element at the index
E result = (E) elements[h];
// If the element is null, null is returned
if (result == null)
return null;
// Set the index space to empty
elements[h] = null;
// Calculate the next new header index
head = (h + 1) & (elements.length - 1);
// Return the element node
return result;
}
Copy the code3.4.2.1 Other methods
public E removeFirst()
Gets and removes the first element of this double-enqueued. If this double-ended queue is empty, it throws a NoSuchElementException exception.
public E removeFirst(a) {
// Call the pollFirst method internally
E x = pollFirst();
// Throw an exception if null is returned
if (x == null)
throw new NoSuchElementException();
return x;
}
Copy the codepublic E remove()
Gets and removes the first element of this double-enqueued. If this double-ended queue is empty, it throws a NoSuchElementException exception.
public E remove(a) {
// Call the removeFirst method internally
return removeFirst();
}
Copy the codepublic E poll()
Gets and moves the head of the queue (in other words, the first element of the dual-enqueued) represented by this dual-enqueued; If this dual-end queue is empty, null is returned.
public E poll(a) {
// Call the pollFirst method internally
return pollFirst();
}
Copy the code3.4.3 Removing a Specified element
3.4.3.1 Removing elements that appear for the first time
public boolean removeFirstOccurrence(Object o)
Removes the first occurrence of the specified element from this two-endian queue. If the double-ended queue does not contain the element, no changes are made. More specifically, remove the first one that satisfies (o == null? E == null: O. quals(e)), if such an element exists. Returns true if the double-ended queue contains the specified element (or if the double-ended queue has changed as a result of the call).
public boolean removeFirstOccurrence(Object o) {
/ / null checks
if (o == null)
// Return false if o is null
return false;
// Get the maximum index
int mask = elements.length - 1;
// Get the index of the header node
int i = head;
Object x;
// Start the lookup loop from the starting node
while( (x = elements[i]) ! =null) {
// If the node is not null
// If the node is equal to o, use equals to compare
if (o.equals(x)) {
/* Call delete to delete the element at that position and adjust the position of subsequent elements */
delete(i);
/ / return true
return true;
}
// The value of index I is similar to the process of retrieving the index of the next node when adding a node, i.e. circular lookup
i = (i + 1) & mask;
}
// Return false if the loop is complete and no equal elements are found
return false;
}
Copy the codeLet’s look at the delete method source code:
/** * delete the element with the specified index, and adjust the position of other elements **@paramThe I index *@returnReturn false if I is close to the head node; Return true if I is close to the tail node. The return value is used in the iterator with */
private boolean delete(int i) {
// A series of assertions to ensure that the data structure is correct
checkInvariants();
// Save a reference to the original array
final Object[] elements = this.elements;
// Get the largest index, the second operand of the & operation
final int mask = elements.length - 1;
final int h = head;
final int t = tail;
// Get the distance from I to the top node index
final int front = (i - h) & mask;
// Get the distance from I to the index of the tail node
final int back = (t - i) & mask;
If front is greater than or equal to the distance from the tail node to the head node, then a "concurrent modification" has occurred and an exception is thrown
if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
If I is close to the head node, then the elements between that position and the head are moved. If I is close to the tail node, then the elements between that position and the tail are moved to minimize the number of elements moved */
/*1 If the end node of I is near */
if (front < back) {
if (h <= i) {
[h+1, I] = [h+1, I] = [h+1, I] [h+1, I] = [h+1, I
System.arraycopy(elements, h, elements, h + 1, front);
} else {
[h,elements.length-1] and [0,i-1] need to be arrayCopy twice
// First move element [0,i-1] to position [1, I]
System.arraycopy(elements, 0, elements, 1, i);
// Then move the last element of the array (at the index of elements.length-1) to the beginning (at the index of 0)
elements[0] = elements[mask];
// Finally move [h,elements.length-1-1] element to [h+1,elements.length-1]
System.arraycopy(elements, h, elements, h + 1, mask - h);
}
// Set the original head node to null
elements[h] = null;
// Calculate the new head index
head = (h + 1) & mask;
/ / returns false
return false;
}
/*2 If I is closer to the tail node */
else {
if (i < t) {
[I +1,t] = [I +1,t] = [I +1,t] = [I +1,t]
System.arraycopy(elements, i + 1, elements, i, back);
// Calculate the index of the next node of the new tail node by reducing it by 1, so t must be greater than 0, and subtracting 1 will not be negative; There is also no need to manually empty the position of t, because when you move above, the last element is null
tail = t - 1;
} else {
// If I is greater than or equal to the next node index t of the tail node, then it is a little more complicated, because there are two discontinuous elements, namely [I +1,elements.length-1] and [0,t], and arrayCopy is required twice
[I +1,elements. Length-1] = [I,elements. Length-1-1] = [I +1,elements
System.arraycopy(elements, i + 1, elements, i, mask - i);
// Then move the first element (index 0) to the end (index 0) of the array (elements.length-1)
elements[mask] = elements[0];
// Finally move element [1,t] to position [0, t-1]
System.arraycopy(elements, 1, elements, 0, t);
// Calculate the next node index of the new tail node; There is also no need to manually empty the position of t, because when you move above, the last element is null
tail = (t - 1) & mask;
}
/ / return true
return true; }}Copy the codeThis may seem like a lot, but it’s not too difficult. One of the main optimizations to note is to first calculate the distance between the head and tail nodes of the index that you want to delete, and then take the smaller distance to move the elements. This reduces the number of elements that need to be moved.
public boolean remove(Object o)
Removes the first occurrence of the specified element from this two-endian queue.
public boolean remove(Object o) {
// Calls the removeFirstOccurrence method internally
return removeFirstOccurrence(o);
}
Copy the code3.4.3.1 Removing the last Element
public boolean removeFirstOccurrence(Object o)
Removes the last occurrence of the specified element from this two-endian queue. If the double-ended queue does not contain the element, no changes are made. More specifically, remove the last one that satisfies (o == null? E == null: O. quals(e)), if such an element exists. Returns true if the double-ended queue contains the specified element (or if the double-ended queue has changed as a result of the call).
public boolean removeLastOccurrence(Object o) {
/ / null checks
if (o == null)
// Return false if o is null
return false;
// Get the maximum index
int mask = elements.length - 1;
// Get the index of the tail node
int i = (tail - 1) & mask;
Object x;
// Start the lookup loop from the last node
while( (x = elements[i]) ! =null) {
// If the node is not null
// If the node is equal to o, use equals to compare
if (o.equals(x)) {
/* Call delete to delete the element at that position and adjust the position of subsequent elements */
delete(i);
return true;
}
// The value of index I is similar to the process of retrieving the index of the next node when a node is added
i = (i - 1) & mask;
}
// Return false if the loop is complete and no equal elements are found
return false;
}
Copy the code3.5 Obtaining Methods
3.5.1 Method for Obtaining the Header
public E getFirst()
Gets, but does not remove, the last element of this double-enqueued. If this double-ended queue is empty, it throws a NoSuchElementException exception.
public E getFirst(a) {
// Get the header node
@SuppressWarnings("unchecked")
E result = (E) elements[head];
// If the header is null, an exception is thrown
if (result == null)
throw new NoSuchElementException();
return result;
}
Copy the codepublic E peekFirst()
Gets, but does not remove, the last element of this double-ended queue; If this dual-end queue is empty, null is returned.
public E peekFirst(a) {
// elements[head] is null if deque empty
return (E) elements[head];
}
Copy the codepubilc E element()
Gets, but does not remove the head of this queue. If this queue is empty, it throws a NoSuchElementException exception.
public E element(a) {
// Call the getFirst method internally
return getFirst();
}
Copy the codepublic E peek()
Gets, but does not remove, the first element of this double-ended queue; If this dual-end queue is empty, null is returned.
public E peek(a) {
// Call the peekFirst method internally
return peekFirst();
}
Copy the code3.5.2 Method of Obtaining the Tail
public E getLast()
Gets, but does not remove, the last element of this double-enqueued. If this double-ended queue is empty, it throws a NoSuchElementException exception.
public E getLast(a) {
// Get the tail element
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
// If the tail node is null, an exception is thrown
if (result == null)
throw new NoSuchElementException();
return result;
}
Copy the codepublic E peekLast()
Gets, but does not remove, the last element of this double-ended queue; If this dual-end queue is empty, null is returned.
public E peekLast(a) {
return (E) elements[(tail - 1) & (elements.length - 1)];
}
Copy the code3.6 Other Methods
public boolean contains(Object o)
Returns true if the double-enqueued contains the specified element. More specifically, return true if and only if the double-enqueued contains at least one element E that satisfies O.equals (e).
public boolean contains(Object o) {
/ / found empty
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
Object x;
// Use equals () internally to determine whether or not it is equal
while( (x = elements[i]) ! =null) {
if (o.equals(x))
return true;
i = (i + 1) & mask;
}
return false;
}
Copy the codepublic void clear()
Removes all elements from this two-endian queue. After this call returns, the double-ended queue will be empty.
public void clear(a) {
int h = head;
int t = tail;
if(h ! = t) {// clear all cells
head = tail = 0;
int i = h;
int mask = elements.length - 1;
do {
// Loop to empty each node
elements[i] = null;
i = (i + 1) & mask;
} while (i != t);
}
}
Copy the code4 The difference between ArrayDeque and LinkedList
Similarities:
- Both ArrayDeque and LinkedList implement the Deque interface. Both are dual-ended queue implementations, and both have a set of methods that operate on the head and tail of the queue.
- Are non-thread-safe collections.
Difference:
ArrayDeque comes from JDK1.6. The bottom layer is a dual-end queue implemented by an array, while the bottom layer is a dual-end queue implemented by a LinkedList implemented by JDK1.2.
- ArrayDeque does not allow null elements, while LinkedList does.
- ArrayDeque is generally more efficient than LinkedList if you only use the Deque method, which is to manipulate elements from both ends of the queue to be used as a queue or stack, and if you have a large amount of data. This may be because ArrayDeque does not need to create node objects. The added element is directly treated as a Node object, while the LinkedList needs to wrap the added element as a Node Node and has assignment operations for other references.
- LinkedList also implements the List interface, with a way to manipulate the queue data by “indexing,” although the “index” here is only a self-maintained index, not an index of an array, a feature that ArrayDeque does not have. If you want to add, delete, or change elements in the middle of the queue, you can only use LinkedList, so the application (or method) of LinkedList is more extensive.
5 Performance Comparison
ArrayDeque: ArrayDeque: LinkedList: ArrayDeque: LinkedList
/ * * *@author lx
*/
public class ArrayDequeTest2 {
static ArrayDeque<Integer> arrayDeque = new ArrayDeque<Integer>();
static LinkedList<Integer> linkedList = new LinkedList<Integer>();
public static long arrayDequeAdd(a) {
// Start time
long startTime = System.currentTimeMillis();
for (int i = 1; i <= 5000000; i++) {
arrayDeque.addLast(i);
arrayDeque.addFirst(i);
}
// End time
long endTime = System.currentTimeMillis();
// Return the elapsed time
return endTime - startTime;
}
public static long arrayDequeDel(a) {
// Start time
long startTime = System.currentTimeMillis();
for (int i = 1; i <= 5000000; i++) {
arrayDeque.pollFirst();
arrayDeque.pollLast();
}
// End time
long endTime = System.currentTimeMillis();
// Return the elapsed time
return endTime - startTime;
}
public static long linkedListAdd(a) {
// Start time
long startTime = System.currentTimeMillis();
for (int i = 1; i <= 5000000; i++) {
linkedList.addLast(i);
linkedList.addFirst(i);
}
// End time
long endTime = System.currentTimeMillis();
// Return the elapsed time
return endTime - startTime;
}
public static long linkedListDel(a) {
// Start time
long startTime = System.currentTimeMillis();
for (int i = 1; i <= 5000000; i++) {
linkedList.pollFirst();
linkedList.pollLast();
}
// End time
long endTime = System.currentTimeMillis();
// Return the elapsed time
return endTime - startTime;
}
public static void main(String[] args) throws InterruptedException {
Thread.sleep(100);
long time1 = arrayDequeAdd();
long time3 = arrayDequeDel();
System.out.println("ArrayDeque adds elements in time ====>" + time1);
System.out.println("ArrayDeque removes elements in time ====>" + time3);
System.gc();
Thread.sleep(100);
long time2 = linkedListAdd();
long time4 = linkedListDel();
System.out.println("How long it took to add elements to linkedList ====>" + time2);
System.out.println("How long did linkedList remove elements ====>"+ time4); }}Copy the codeIf you don’t understand or need to communicate, you can leave a message. Also hope to like, collect, follow, I will continue to update a variety of Java learning blog!