上一篇看了ArrayDeque的添加元素，这篇我们来看删除元素是怎样实现的。
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeFirst() {
E e = pollFirst();
if (e == null)
throw new NoSuchElementException();
return e;
}
原来removeFirst调用了pollFirst，我们来看看pollFirst：
public E pollFirst() {
final Object[] es;
final int h;
E e = elementAt(es = elements, h = head);
if (e != null) {
es[h] = null;
head = inc(h, es.length);
}
return e;
}
调用了elementAt从elements获取了head位置的元素：
static final <E> E elementAt(Object[] es, int i) {
return (E) es[i];
}
因为是数组，所以直接通过下标访问即可，时间复杂度O(1)。
然后将head元素置空，通过head = inc(h, es.length);将head位置加一。如果超过数组长度，根据循环数组的特点，变为数组第0个下标。
而pollLast实现也是差不多的，就不多啰嗦了。
而peekFirst、peekLast就更简单了，直接通过elementAt通过数组下标快速访问元素即可：
public E peekFirst() {
return elementAt(elements, head);
}
public E peekLast() {
final Object[] es;
return elementAt(es = elements, dec(tail, es.length));
}
由于是数组，所以极度不推荐删除元素的，所以removeFirstOccurrence和removeLastOccurrence这2个极度浪费性能操作能不用尽量不用。
/**
* Removes the first occurrence of the specified element in this
* deque (when traversing the deque from head to tail).
* If the deque does not contain the element, it is unchanged.
* More formally, removes the first element {@code e} such that
* {@code o.equals(e)} (if such an element exists).
* Returns {@code true} if this deque contained the specified element
* (or equivalently, if this deque changed as a result of the call).
*
* @param o element to be removed from this deque, if present
* @return {@code true} if the deque contained the specified element
*/
public boolean removeFirstOccurrence(Object o) {
if (o != null) {
final Object[] es = elements;
for (int i = head, end = tail, to = (i <= end) ? end : es.length;
; i = 0, to = end) {
for (; i < to; i++)
if (o.equals(es[i])) {
delete(i);
return true;
}
if (to == end) break;
}
}
return false;
}
这个removeFirstOccurrence就是删除第一个找到的元素。如果双端队列不包含某个元素，那么就不会变。如果该元素被删除，就会使得数组的元素向前或向后运动。 delete函数作者已经优化了算法，使得每次挪动最少的元素。
/**
* Removes the element at the specified position in the elements array.
* This can result in forward or backwards motion of array elements.
* We optimize for least element motion.
*
* <p>This method is called delete rather than remove to emphasize
* that its semantics differ from those of {@link List#remove(int)}.
*
* @return true if elements near tail moved backwards
*/
boolean delete(int i) {
final Object[] es = elements;
final int capacity = es.length;
final int h, t;
// number of elements before to-be-deleted elt
final int front = sub(i, h = head, capacity);
// number of elements after to-be-deleted elt
final int back = sub(t = tail, i, capacity) - 1;
if (front < back) {
// move front elements forwards
if (h <= i) {
System.arraycopy(es, h, es, h + 1, front);
} else { // Wrap around
System.arraycopy(es, 0, es, 1, i);
es[0] = es[capacity - 1];
System.arraycopy(es, h, es, h + 1, front - (i + 1));
}
es[h] = null;
head = inc(h, capacity);
return false;
} else {
// move back elements backwards
tail = dec(t, capacity);
if (i <= tail) {
System.arraycopy(es, i + 1, es, i, back);
} else { // Wrap around
System.arraycopy(es, i + 1, es, i, capacity - (i + 1));
es[capacity - 1] = es[0];
System.arraycopy(es, 1, es, 0, t - 1);
}
es[tail] = null;
return true;
}
}
每删除一个元素，都要挪动其他元素，非常划不来。那如果用了ArrayDeque，但是迫不得已要删除元素，怎么办？我建议在保存的元素Object里面添加一个叫isDelete的boolean属性。使用前先判断isDelete即可。这就像居委大妈跟普通大妈区别，就是袖子上多一个红袖标，大大写着“居委”两字。
网友评论