Queue 队列
这些操作都是在头部进行操作,但队列内的排序则不尽然相同,可以FIFO,也可以LIFO, 队列、栈!
操作 | 抛出异常 | 返回特定值 |
---|---|---|
Insert | add(容量限制) | offer |
Remove | remove(queue为空) | poll |
Examine | element(queue为空) | peek |
Deque 双端队列
方法比较
First Element (Head) | Last Element (Tail) | |||
Throws exception | Special value | Throws exception | Special value | |
Insert | {@link Deque#addFirst addFirst(e)} | {@link Deque#offerFirst offerFirst(e)} | {@link Deque#addLast addLast(e)} | {@link Deque#offerLast offerLast(e)} |
Remove | {@link Deque#removeFirst removeFirst()} | {@link Deque#pollFirst pollFirst()} | {@link Deque#removeLast removeLast()} | {@link Deque#pollLast pollLast()} |
Examine | {@link Deque#getFirst getFirst()} | {@link Deque#peekFirst peekFirst()} | {@link Deque#getLast getLast()} | {@link Deque#peekLast peekLast()} |
作为队列, FIFO
{@code Queue} Method | Equivalent {@code Deque} Method |
{@link java.util.Queue#add add(e)} | {@link #addLast addLast(e)} |
{@link java.util.Queue#offer offer(e)} | {@link #offerLast offerLast(e)} |
{@link java.util.Queue#remove remove()} | {@link #removeFirst removeFirst()} |
{@link java.util.Queue#poll poll()} | {@link #pollFirst pollFirst()} |
{@link java.util.Queue#element element()} | {@link #getFirst getFirst()} |
{@link java.util.Queue#peek peek()} | {@link #peek peekFirst()} |
作为栈 Stack
Stack Method | Equivalent {@code Deque} Method |
{@link #push push(e)} | {@link #addFirst addFirst(e)} |
{@link #pop pop()} | {@link #removeFirst removeFirst()} |
{@link #peek peek()} | {@link #peekFirst peekFirst()} |
双向链表: 链表记录头节点和尾节点,每个节点会持有前驱节点和后驱节点的引用。
public class LinkedList {
Node first;
Node last
class Node {
Node pre;
Object item;
Node next;
}
}
fail-fast机制:在创建Iterator后,只能通过iterator的remove后者add方法修改集合,其他方式都会引起遍历失败。
/**
* Pointer to first node.
* 集合为空时,first和last必定为空
* 集合不为空时,first的前驱为空,first的item不为空
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* 集合为空时,first和last必定为空
* 集合不为空时,last的后驱为空,last的item不为空
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
内部获取指定位置的元素,判断index在前半部分还是后半部分
if( index < size >> 1) {
//从first开始向后遍历
}else {
//从last开始向前遍历
}
修改集合结构时,需操作前后节点的prev和next,同时需考虑是否需要设置头尾节点
记录几个关键方法,其余方法底层均是使用此部分方法实现
/**
* Links e as first element.
* 链接一个元素为头部节点,注意:此并非为替换元素
*/
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
//集合的头节点引用至新节点
first = newNode;
if (f == null)
//代表空集合,空集合的头节点、尾节点相同,节点的prev\next均为null
last = newNode;
else
//否则将原先头节点的prev指向新的头节点
f.prev = newNode;
size++;
modCount++;
}
/**
* Links e as last element.
*/
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
//空集合,首尾节点相同
first = newNode;
else
//设置原尾结点的next
l.next = newNode;
size++;
modCount++;
}
/**
* Inserts element e before non-null Node succ.
* 将元素插入特定节点之前
* 需要做四个链接更新
* 1. 设置新节点的prev和next
* 2. 设置succ的prev为新节点
* 3. 设置succ的原prev节点的next节点为新节点
*/
void linkBefore(E e, Node<E> succ) {
// assert succ != null;
//记录后继者的prev引用
final Node<E> pred = succ.prev;
//构造节点,指定prev为succ的prev,next为succ,
final Node<E> newNode = new Node<>(pred, e, succ);
// 设置succ的prev引用,更新链接关系
succ.prev = newNode;
if (pred == null)
//succ为原来的头节点,相当于此动作为设置新的头节点
//更新first的引用
first = newNode;
else
//更新succ的原prev节点的next链接
pred.next = newNode;
size++;
modCount++;
}
/**
* Unlinks non-null first node f.
* 去掉头节点
*/
private E unlinkFirst(Node<E> f) {
// assert f == first && f != null;
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
//更新集合的头节点引用
first = next;
//空集合
if (next == null)
//空集合,首尾节点相同,同时将last置为null
last = null;
else
//将next的prev置为null,取消引用关系
next.prev = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null last node l.
* 去掉尾结点
*/
private E unlinkLast(Node<E> l) {
// assert l == last && l != null;
final E element = l.item;
final Node<E> prev = l.prev;
l.item = null;
l.prev = null; // help GC
//更新集合尾结点的引用
last = prev;
if (prev == null)
//若集合为空,首尾节点相同,需将头节点设置为null
first = null;
else
//集合尾结点的next为null,更新新的尾部节点的next链接关系
prev.next = null;
size--;
modCount++;
return element;
}
/**
* Unlinks non-null node x.
* 去掉某个节点
* 1. 设置x的item prev next为null, help GC
* 2. 设置x的prev节点的next为x的next节点
* 3. 设置x的next节点的prev为x的prev节点
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
//[prev item next] [prev item next] [prev item next]
if (prev == null) {
//节点的prev引用为空,则可认为是头节点,此时需更新集合的first引用
first = next;
} else {
//设置x的prev节点的next为x的next节点
prev.next = next;
x.prev = null;
}
if (next == null) {
//节点的next引用为空,则可认为是尾节点,此时需更新集合的next引用
last = prev;
} else {
//设置x的next节点的prev为x的prev节点
next.prev = prev;
x.next = null;
}
//help gc
x.item = null;
size--;
modCount++;
return element;
}