LinkedList 现在，我们在来看看LinkedList对应Queue的实现部分。在前面一篇文章中，已经讨论过LinkedList里面Node的结构。它本身包含元素值，prev、next两个引用。对链表的增加和删除元素的操作不像数组，不存在要考虑下标的问题，也不需要扩展数组空间，因此就简单了很多。先看查找元素部分：
Java代码 [url=] [/url]
[url=] [/url]
public E getFirst() { final Node<E> f = first; if (f == null) throw new NoSuchElementException(); return f.item; } public E getLast() { final Node<E> l = last; if (l == null) throw new NoSuchElementException(); return l.item; } [url=][/url]
这里唯一值得注意的一点就是last引用是指向队列最末尾和元素，和前面ArrayDeque的情况不一样。
添加元素的方法如下：
[url=][/url]
public boolean add(E e) { linkLast(e); return true; } public boolean offer(E e) { return add(e); } 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++; } [url=][/url]
linkLast的方法在前一篇文章里已经分析过，就不再重复。
删除元素的方法主要有remove():
[url=][/url]
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; } 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; } [url=][/url]
这部分的代码看似比较长，实际上是遍历整个链表，如果找到要删除的元素，则移除该元素。这部分的难点在unlink方法里面。我们分别用要删除元素的前面和后面的引用来判断各种当prev和next为null时的各种情况。虽然不是很复杂，但是很繁琐。 |
