voidlinkLast(E e){ final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
if (index < (size >> 1)) { Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
voidlinkBefore(E e, Node<E> succ){ // assert succ != null; final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
public E remove(int index){ checkElementIndex(index); return unlink(node(index)); }
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;
publicbooleanremove(Object o){ if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) { unlink(x); returntrue; } } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) { unlink(x); returntrue; } } } returnfalse; }
publicintindexOf(Object o){ int index = 0; if (o == null) { for (Node<E> x = first; x != null; x = x.next) { if (x.item == null) return index; index++; } } else { for (Node<E> x = first; x != null; x = x.next) { if (o.equals(x.item)) return index; index++; } } return -1; }
publicvoidclear(){ // Clearing all of the links between nodes is "unnecessary", but: // - helps a generational GC if the discarded nodes inhabit // more than one generation // - is sure to free memory even if there is a reachable Iterator for (Node<E> x = first; x != null; ) { Node<E> next = x.next; x.item = null; x.next = null; x.prev = null; x = next; } first = last = null; size = 0; modCount++; }
public E poll(){ // 获取第一个元素,并将第一个删除 final Node<E> f = first; return (f == null) ? null : unlinkFirst(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; else next.prev = null; size--; modCount++; return element; }
public E peek(){ // 只获取不删除 final Node<E> f = first; return (f == null) ? null : f.item; }