LinkedList
LinkedList是一种可以在任何位置进行高效地插入和移除操作的有序序列，它是基于双向链表实现的。注意：是双向链表，但不是循环双向链表，不同版本的jdk实现可能不一样。
LinkedList也和ArrayList一样实现了List接口，但是它执行插入和删除操作时比ArrayList更加高效，因为它是基于链表的。基于链表也决定了它在随机访问方面要比ArrayList逊色一点。
除此之外，LinkedList还提供了一些可以使其作为栈、队列、双端队列的方法。这些方法中有些彼此之间只是名称的区别，以使得这些名字在特定的上下文中显得更加的合适。
LinkedList的定义
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList是一个继承于AbstractSequentialList的双向链表。它也可以被当作栈、队列或双端队列进行操作。
LinkedList实现 List 接口，能对它进行队列操作。
LinkedList实现 Deque 接口，即能将LinkedList当作双端队列使用。
LinkedList实现了Cloneable接口，即覆盖了函数clone()，能克隆。
LinkedList实现java.io.Serializable接口，这意味着LinkedList支持序列化，能通过序列化去传输。
LinkedList是非同步的。
LinkedList的属性
transient int size = 0;
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;
size肯定就是LinkedList对象里面存储的元素个数了。LinkedList既然是基于链表实现的，那么这个first肯定就是链表的头节点了，last是链表的尾节点，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;
}
}
Node类只定义了存储的元素、前一个元素、后一个元素，这就是双向链表的节点的定义，每个节点只知道自己的前一个节点和后一个节点。
LinkedList的构造方法
/**
* Constructs an empty list.
*/
public LinkedList() {
}
/**
* Constructs a list containing the elements of the specified
* collection, in the order they are returned by the collection's
* iterator.
*
* @param c the collection whose elements are to be placed into this list
* @throws NullPointerException if the specified collection is null
*/
public LinkedList(Collection<? extends E> c) {
this();
addAll(c);
}
LinkedList提供了两个构造方法。第一个构造方法不接受参数，first节点和last节点均为null，用于表示一个空的链表。第二个构造方法接收一个Collection参数c，调用第一个构造方法构造一个空的链表，之后通过addAll将c中的元素全部添加到链表中。
LinkedList的方法
- boolean addAll(Collection<? extends E> c)
将集合c中所有元素添加到链表的尾部
public boolean addAll(Collection<? extends E> c) {
// size为链表包含的元素个数
return addAll(size, c);
}
- boolean addAll(int index, Collection<? extends E> c)
将集合c中的元素在指定位置插入到链表中
//从指定的位置index开始，将集合c中的元素插入到链表中
public boolean addAll(int index, Collection<? extends E> c) {
//首先判断插入位置的合法性
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
Node<E> pred, succ;
if (index == size) {//说明在链表尾部插入集合元素
succ = null;
pred = last;
}
else { //否则，找到index所在的节点
succ = node(index);
pred = succ.prev;
}
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;
}
- boolean add(E e)
将元素添加到链表的尾部
public boolean add(E e) {
linkLast(e);
return true;
}
从上面的代码可以看出，add(E e)方法只是调用了linkLast(e)方法，并且返回true。
- void linkLast(E 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++;
}
- void addLast(E e)
将元素添加到链表的尾部，该方法等价于add(E e)
public void addLast(E e) {
linkLast(e);
}
- void addFirst(E e)
将元素添加到链表的头部
public void addFirst(E e) {
linkFirst(e);
}
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++;
}
- void clear()
移除链表的所有元素
public void clear() {
// 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++;
}
- boolean contains(Object o)
判断链表是否包含指定的元素
public boolean contains(Object o) {
return indexOf(o) != -1;
}
仅仅只是判断o在链表中的索引。先看indexOf(Object o)方法。
- int indexOf(Object o)
返回指定元素在链表第一次出现的位置，如果链表不包含指定的元素，则返回-1
public int indexOf(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;
}
注意：该方法传入的元素可以为null，也就是说contains方法可以接收null作为方法参数。如果指定的元素不为null，则调用元素的equals方法进行判断.
- node(int index)
返回链表指定位置处的节点
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;
}
}
该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置处的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index<size/2，就只从位置0往后遍历到位置index处，而如果index>size/2，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历。
- E element()
取出但不移除链表的第一个元素
public E element() {
return getFirst();
}
- E getFirst()
返回链表的第一个元素，如果链表为空，则抛出
NoSuchElementException
public E getFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return f.item;
}
element()方法调用了getFirst()返回链表的第一个节点的元素。为什么要提供功能一样的两个方法，像是包装了一下名字？其实这只是为了在不同的上下文“语境”中能通过更贴切的方法名调用罢了。
- E get(int index)
返回链表指定位置处的元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
get(int index)方法用于获得指定索引位置的节点的元素。它通过node(int index)方法获取节点。node(int index)方法遍历链表并获取节点，在上面有说明过，不再陈述。
- E set(int index, E element)
使用指定的元素替换链表指定位置处的元素
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
先获取指定索引的节点，保留原来的元素，然后用element进行替换，之后返回原来的元素。
- E getLast()
返回链表的最后一个元素，如果链表为空，则抛出
NoSuchElementException
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
- lastIndexOf(Object o)
返回指定元素在链表最后一次出现的位置
public int lastIndexOf(Object o) {
int index = size;
if (o == null) {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (x.item == null)
return index;
}
} else {
for (Node<E> x = last; x != null; x = x.prev) {
index--;
if (o.equals(x.item))
return index;
}
}
return -1;
}
因为查找的是last index，即最后一次出现的位置，所以采用由后向前的遍历方式。因为采用了由后向前的遍历，所以index被赋值为size，并且循环体内执行时都进行递减操作。分两种情况判断是否存在，分别是null和不为null。
- boolean offer(E e)
将指定的元素添加到链表尾部
public boolean offer(E e) {
return add(e);
}
- boolean offerFirst(E e)
在链表的头部插入指定元素
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
- boolean offerLast(E e)
在链表的尾部插入指定元素
public boolean offerLast(E e) {
addLast(e);
return true;
}
上面这三个方法都只是调用了相应的add方法，同样只是提供了不同的方法名在不同的语境下使用。
- E peek()
取出但不移除链表的一个元素，如果链表为null，则返回null
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
- E peekFirst()
取出但不移除链表的第一个元素，如果链表为null，则返回null
public E peekFirst() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
- E peekLast()
取出但不移除链表的最后一个元素，如果链表为null，则返回null
public E peekLast() {
final Node<E> l = last;
return (l == null) ? null : l.item;
}
上面的三个方法也很简单，同样只是提供了不同的方法名在不同的语境下使用。
- E poll()
取出并移除链表的第一个元素，如果链表为null，则返回null
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
- E pollFirst()
取出并移除链表的第一个元素，如果链表为null，则返回null
public E pollFirst() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
- E pollLast()
取出并移除链表的最后一个元素，如果链表为null，则返回null
public E pollLast() {
final Node<E> l = last;
return (l == null) ? null : unlinkLast(l);
}
poll相关的方法都是获取并移除某个元素。
- E pop()
移除并返回链表的第一个元素，如果链表为null，则抛出NoSuchElementException
public E pop() {
return removeFirst();
}
- void push(E e)
在链表的头部添加一个元素
public void push(E e) {
addFirst(e);
}
这两个方法对应栈的操作，即弹出一个元素和压入一个元素，仅仅是调用了removeFirst()和addFirst()方法。
- E remove()
取出并移除链表的第一个元素，如果链表为null，则抛出NoSuchElementException
public E remove() {
return removeFirst();
}
- E removeFirst()
移除并返回链表的第一个元素，如果链表为null，则抛出NoSuchElementException
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return 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;
}
- E removeLast()
移除并返回链表的最后一个元素，如果链表为null，则抛出NoSuchElementException
public E removeLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(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)
first = null;
else
prev.next = null;
size--;
modCount++;
return element;
}
- boolean remove(Object 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;
}
- E unlink(Node<E> x)
移除指定的节点，并返回节点包含的元素
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;
}
- boolean removeLastOccurrence(Object 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;
}
- Object clone()
返回链表的浅层拷贝，链表包含的元素不会被拷贝
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone.first = clone.last = null;
clone.size = 0;
clone.modCount = 0;
// Initialize clone with our elements
for (Node<E> x = first; x != null; x = x.next)
clone.add(x.item);
return clone;
}
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e) {
throw new InternalError(e);
}
}
- Object[] toArray()
返回一个包含链表所有元素的数组
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
LinkedList的Iterator
除了Node，LinkedList还有一个内部类：ListItr。
ListItr实现了ListIterator接口，可知它是一个迭代器，通过它可以遍历修改LinkedList。
在LinkedList中提供了获取ListItr对象的方法：listIterator(int index)。
public ListIterator<E> listIterator(int index) {
checkPositionIndex(index);
return new ListItr(index);
}
该方法只是简单的返回了一个ListItr对象。
LinkedList中还有通过继承获得的listIterator()方法，该方法只是调用了listIterator(int index)并且传入0。
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned;
private Node<E> next;
private int nextIndex;
private int expectedModCount = modCount;
ListItr(int index) {
// assert isPositionIndex(index);
next = (index == size) ? null : node(index);
nextIndex = index;
}
public boolean hasNext() {
return nextIndex < size;
}
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
public boolean hasPrevious() {
return nextIndex > 0;
}
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
public int nextIndex() {
return nextIndex;
}
public int previousIndex() {
return nextIndex - 1;
}
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
public void forEachRemaining(Consumer<? super E> action) {
Objects.requireNonNull(action);
while (modCount == expectedModCount && nextIndex < size) {
action.accept(next.item);
lastReturned = next;
next = next.next;
nextIndex++;
}
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}
LinkedList还有一个提供Iterator的方法：descendingIterator()。该方法返回一个DescendingIterator对象。DescendingIterator是LinkedList的一个内部类。
public Iterator<E> descendingIterator() {
return new DescendingIterator();
}
DescendingIterator
private class DescendingIterator implements Iterator<E> {
private final ListItr itr = new ListItr(size());
public boolean hasNext() {
return itr.hasPrevious();
}
public E next() {
return itr.previous();
}
public void remove() {
itr.remove();
}
}
从类名和上面的代码可以看出这是一个反向的Iterator，代码很简单，都是调用的ListItr类中的方法。
关于LinkedList的几点说明
- 注意源码中的 Node<E> node(int index)方法
Node<E> node(int 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;
}
}
该方法返回双向链表中指定位置处的节点，而链表中是没有下标索引的，要指定位置出的元素，就要遍历该链表，从源码的实现中，我们看到这里有一个加速动作。源码中先将index与长度size的一半比较，如果index<size/2，就只从位置0往后遍历到位置index处，而如果index>size/2，就只从位置size往前遍历到位置index处。这样可以减少一部分不必要的遍历。
- LinkedList与ArrayList的区别
LinkedList与ArrayList在性能上各有优缺点，都有各自适用的地方，总结如下：
- ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
- LinkedList不支持高效的随机元素访问。
- ArrayList的空间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间，就存储密度来说，ArrayList是优于LinkedList的。
总之，当操作是在一列数据的后面添加数据而不是在前面或中间，并且需要随机地访问其中的元素时，使用ArrayList会提供比较好的性能，当你的操作是在一列数据的前面或中间添加或删除数据，并且按照顺序访问其中的元素时，就应该使用LinkedList了。
- LinkedList中允许元素为null
优先级链表（来自JBOSS）###
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
public class BasicPriorityLinkedList {
protected LinkedList[] linkedLists;
protected int priorities;
protected int size;
public BasicPriorityLinkedList(int priorities) {
this.priorities = priorities;
initDeques();
}
public void addFirst(Object obj, int priority) {
linkedLists[priority].addFirst(obj);
size++;
}
public void addLast(Object obj, int priority) {
linkedLists[priority].addLast(obj);
size++;
}
public Object removeFirst() {
Object obj = null;
for (int i = priorities - 1; i >= 0; i--) {
LinkedList ll = linkedLists[i];
if (!ll.isEmpty()) {
obj = ll.removeFirst();
break;
}
}
if (obj != null) {
size--;
}
return obj;
}
public Object removeLast() {
Object obj = null;
for (int i = 0; i < priorities; i++) {
LinkedList ll = linkedLists[i];
if (!ll.isEmpty()) {
obj = ll.removeLast();
}
if (obj != null) {
break;
}
}
if (obj != null) {
size--;
}
return obj;
}
public Object peekFirst() {
Object obj = null;
for (int i = priorities - 1; i >= 0; i--) {
LinkedList ll = linkedLists[i];
if (!ll.isEmpty()) {
obj = ll.getFirst();
}
if (obj != null) {
break;
}
}
return obj;
}
public List getAll() {
List all = new ArrayList();
for (int i = priorities - 1; i >= 0; i--) {
LinkedList deque = linkedLists[i];
all.addAll(deque);
}
return all;
}
public void clear() {
initDeques();
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public ListIterator iterator() {
return new PriorityLinkedListIterator(linkedLists);
}
protected void initDeques() {
linkedLists = new LinkedList[priorities];
for (int i = 0; i < priorities; i++) {
linkedLists[i] = new LinkedList();
}
size = 0;
}
class PriorityLinkedListIterator implements ListIterator {
private LinkedList[] lists;
private int index;
private ListIterator currentIter;
PriorityLinkedListIterator(LinkedList[] lists) {
this.lists = lists;
index = lists.length - 1;
currentIter = lists[index].listIterator();
}
public void add(Object arg0) {
throw new UnsupportedOperationException();
}
public boolean hasNext() {
if (currentIter.hasNext()) {
return true;
}
while (index >= 0) {
if (index == 0 || currentIter.hasNext()) {
break;
}
index--;
currentIter = lists[index].listIterator();
}
return currentIter.hasNext();
}
public boolean hasPrevious() {
throw new UnsupportedOperationException();
}
public Object next() {
if (!hasNext()) {
throw new NoSuchElementException();
}
return currentIter.next();
}
public int nextIndex() {
throw new UnsupportedOperationException();
}
public Object previous() {
throw new UnsupportedOperationException();
}
public int previousIndex() {
throw new UnsupportedOperationException();
}
public void remove() {
currentIter.remove();
size--;
}
public void set(Object obj) {
throw new UnsupportedOperationException();
}
}
}
