这是个啥呢？糖葫芦串，一个糖葫芦就是一个Node（节点），这个糖葫芦上又有糖又有山楂，这个Node呢它能储存一个元素值，两个指针，一个指向前，一个指向后
private static class Node<E> {
E item;
Node<E> next;
Node<E> prev;
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
}
为了方便我从前或者从后串糖葫芦，需要两个指针，一个指在最前，一个指在最后
//transient 不参与序列化
transient Node<E> first;
transient Node<E> last;
ADD
这根糖葫芦串，我想从前串一个进去，就可以用addFirst，offerFirst,push
private void linkFirst(E e) {
final Node<E> f = first;
final Node<E> newNode = new Node<>(null, e, f);
first = newNode;
if (f == null)
last = newNode;
else
f.prev = newNode;
size++;
modCount++;
}
public void addFirst(E e) {
linkFirst(e);
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
public void push(E e) {
addFirst(e);
}
我想从后面串一个，就用addLast,add,offer,offerLast
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
l.next = newNode;
size++;
modCount++;
}
public void addLast(E e) {
linkLast(e);
}
public boolean add(E e) {
linkLast(e);
return true;
}
public boolean offerLast(E e) {
addLast(e);
return true;
}
public boolean offer(E e) {
return add(e);
}
呵呵，我还想从中间插一个，真是丧心病狂！想想插之前的准备工作有哪些？index-我要插入的位置，我要检查他的可靠性；由于链表所以我需要获取原先index处的Node；插入后用于重构link联系
private void checkPositionIndex(int index) {
if (!isPositionIndex(index))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
}
private boolean isPositionIndex(int index) {
return index >= 0 && index <= size; //[0, size]
}
Node<E> node(int index) {
// assert isElementIndex(index);
//二分查找
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;
}
}
来看看可调用的方法：add（int index, E element）
void linkBefore(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 void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
想一连串从后面串好几个用：removeAll（Collection）从末尾添加；removeAll（int， Collection）从指定位置开始
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index); //0<=index<=size
Object[] a = c.toArray(); //转化为数组，数组中元素顺序转化后不变
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ; //pred是index-1处Node，succ是index处Node
if (index == size) { //index==size,表示从尾部添加
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
//这插入无非三种情况：1 index=0，也就是将数组元素插入到头部位置，
这时pred=null，succ=first，插入时需要将first指向新的头结点，数组最后一个元素形成的节点
指向succ，succ.pred指回该节点
2 0<index<size pred与succ皆不为null，没有需要特殊处理的地方
3 index = size succ=null，pred=last，last需要重定向到数组末尾处
for (Object o : a) {
@SuppressWarnings("unchecked") E e = (E) o;
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
if (succ == null) {
last = pred;
} else {
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
REMOVE
现在我要吃开始吃了，从前吃一个用：remove，removeFirst，poll，pollFirst，pop
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 removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
//不抛异常，返null
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
public E remove() {
return removeFirst();
}
public E pop() {
return removeFirst();
}
从后吃一个，用removeLast，pollLast
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)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l);
}
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
从中间吃remove(Object), remove(int), removeFirstOccurrence, removeLastOccurrence
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;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}
//删除从前往后第一个出现的o
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
//删除index除的Node，先检查index，保证0<= index < size
public E remove(int index) {
checkElementIndex(index);
return unlink(node(index));
}
//从后往前删除第一个出现的o
public boolean removeLastOccurrence(Object o) {
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}
public boolean removeFirstOccurrence(Object o) {
return remove(o);
}
