LinkedList
LinkedList是一種可以在任何位置進行高效地插入和移除操作的有序序列略号，它是基于雙向鏈表實現(xiàn)的刑峡。注意：是雙向鏈表，但不是循環(huán)雙向鏈表玄柠，不同版本的jdk實現(xiàn)可能不一樣突梦。
LinkedList也和ArrayList一樣實現(xiàn)了List接口，但是它執(zhí)行插入和刪除操作時比ArrayList更加高效羽利，因為它是基于鏈表的宫患。基于鏈表也決定了它在隨機訪問方面要比ArrayList遜色一點这弧。
除此之外娃闲，LinkedList還提供了一些可以使其作為棧、隊列匾浪、雙端隊列的方法皇帮。這些方法中有些彼此之間只是名稱的區(qū)別，以使得這些名字在特定的上下文中顯得更加的合適户矢。
LinkedList的定義
public class LinkedList<E> extends AbstractSequentialList<E> implements List<E>, Deque<E>, Cloneable, java.io.Serializable
LinkedList是一個繼承于AbstractSequentialList的雙向鏈表玲献。它也可以被當作棧、隊列或雙端隊列進行操作梯浪。
LinkedList實現(xiàn) List 接口，能對它進行隊列操作瓢娜。
LinkedList實現(xiàn) Deque 接口挂洛，即能將LinkedList當作雙端隊列使用。
LinkedList實現(xiàn)了Cloneable接口眠砾，即覆蓋了函數(shù)clone()虏劲，能克隆。
LinkedList實現(xiàn)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對象里面存儲的元素個數(shù)了堡掏。LinkedList既然是基于鏈表實現(xiàn)的，那么這個first肯定就是鏈表的頭節(jié)點了刨疼，last是鏈表的尾節(jié)點泉唁，Node就是節(jié)點對象了鹅龄。
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類只定義了存儲的元素、前一個元素亭畜、后一個元素扮休，這就是雙向鏈表的節(jié)點的定義，每個節(jié)點只知道自己的前一個節(jié)點和后一個節(jié)點拴鸵。
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提供了兩個構造方法玷坠。第一個構造方法不接受參數(shù)，first節(jié)點和last節(jié)點均為null劲藐，用于表示一個空的鏈表侨糟。第二個構造方法接收一個Collection參數(shù)c，調用第一個構造方法構造一個空的鏈表瘩燥，之后通過addAll將c中的元素全部添加到鏈表中秕重。
LinkedList的方法
- boolean addAll(Collection<? extends E> c)
將集合c中所有元素添加到鏈表的尾部
public boolean addAll(Collection<? extends E> c) {
// size為鏈表包含的元素個數(shù)
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所在的節(jié)點
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)
返回指定元素在鏈表第一次出現(xiàn)的位置庐扫，如果鏈表不包含指定的元素，則返回-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作為方法參數(shù)形庭。如果指定的元素不為null，則調用元素的equals方法進行判斷.
- node(int index)
返回鏈表指定位置處的節(jié)點
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;
}
}
該方法返回雙向鏈表中指定位置處的節(jié)點厌漂，而鏈表中是沒有下標索引的萨醒，要指定位置處的元素，就要遍歷該鏈表苇倡，從源碼的實現(xiàn)中富纸，我們看到這里有一個加速動作。源碼中先將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()返回鏈表的第一個節(jié)點的元素埃元。為什么要提供功能一樣的兩個方法，像是包裝了一下名字媚狰？其實這只是為了在不同的上下文“語境”中能通過更貼切的方法名調用罷了岛杀。
- E get(int index)
返回鏈表指定位置處的元素
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
get(int index)方法用于獲得指定索引位置的節(jié)點的元素。它通過node(int index)方法獲取節(jié)點崭孤。node(int index)方法遍歷鏈表并獲取節(jié)點类嗤，在上面有說明過，不再陳述辨宠。
- 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;
}
先獲取指定索引的節(jié)點遗锣，保留原來的元素，然后用element進行替換嗤形，之后返回原來的元素精偿。
- E getLast()
返回鏈表的最后一個元素，如果鏈表為空赋兵，則拋出
NoSuchElementException
public E getLast() {
final Node<E> l = last;
if (l == null)
throw new NoSuchElementException();
return l.item;
}
- lastIndexOf(Object o)
返回指定元素在鏈表最后一次出現(xiàn)的位置
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笔咽，即最后一次出現(xiàn)的位置，所以采用由后向前的遍歷方式霹期。因為采用了由后向前的遍歷叶组，所以index被賦值為size，并且循環(huán)體內執(zhí)行時都進行遞減操作历造。分兩種情況判斷是否存在甩十，分別是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)
移除指定元素在鏈表第一次的出現(xiàn)
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)
移除指定的節(jié)點沥曹，并返回節(jié)點包含的元素
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)
移除指定元素在鏈表的最后一次出現(xiàn)
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()
返回一個包含鏈表所有元素的數(shù)組
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實現(xiàn)了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;
}
}
該方法返回雙向鏈表中指定位置處的節(jié)點奸汇，而鏈表中是沒有下標索引的施符，要指定位置出的元素，就要遍歷該鏈表擂找，從源碼的實現(xiàn)中戳吝，我們看到這里有一個加速動作。源碼中先將index與長度size的一半比較贯涎，如果index<size/2听哭，就只從位置0往后遍歷到位置index處，而如果index>size/2，就只從位置size往前遍歷到位置index處陆盘。這樣可以減少一部分不必要的遍歷普筹。
- LinkedList與ArrayList的區(qū)別
LinkedList與ArrayList在性能上各有優(yōu)缺點，都有各自適用的地方隘马，總結如下：
- ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結構太防，LinkedList基于鏈表的數(shù)據(jù)結構。
- LinkedList不支持高效的隨機元素訪問祟霍。
- ArrayList的空間浪費主要體現(xiàn)在在list列表的結尾預留一定的容量空間杏头，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗相當?shù)目臻g，就存儲密度來說沸呐，ArrayList是優(yōu)于LinkedList的醇王。
總之，當操作是在一列數(shù)據(jù)的后面添加數(shù)據(jù)而不是在前面或中間崭添，并且需要隨機地訪問其中的元素時寓娩，使用ArrayList會提供比較好的性能，當你的操作是在一列數(shù)據(jù)的前面或中間添加或刪除數(shù)據(jù)呼渣，并且按照順序訪問其中的元素時棘伴，就應該使用LinkedList了。
- LinkedList中允許元素為null
優(yōu)先級鏈表（來自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();
}
}
}
