2020/04/20 21:56

#### Queue 队列

Remove remove（queue为空） poll
Examine element（queue为空） peek

#### Deque 双端队列

Summary of Deque methods

Comparison of Queue and Deque methods

Comparison of Stack and Deque methods

public class LinkedList {
Node first;
Node last

class Node {
Node pre;
Object item;
Node next;
}
}



    /**
* 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;


if( index < size >> 1) {
//从first开始向后遍历
}else {
//从last开始向前遍历
}



/**
* Links e as first element.
* 链接一个元素为头部节点，注意：此并非为替换元素
*/
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.
*/
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.
* 去掉头节点
*/
// 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.
* 去掉尾结点
*/
// 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;
}

/**
* 去掉某个节点
* 1. 设置x的item prev next为null， help GC
* 2. 设置x的prev节点的next为x的next节点
* 3. 设置x的next节点的prev为x的prev节点
*/
// 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;
}



0
0 收藏

0 评论
0 收藏
0