一、類注釋翻譯
* Doubly -linked list implementation of the {@code List} and {@code Deque}
* interfaces. Implements all optional list operations, and permits all
* elements (including {@code null}).
使用“雙向連結清單”來實作List與Deque接口。 實作了所有List接口中的方法，并且允許存放所有元素，包括Null。
* <p>All of the operations perform as could be expected for a doubly- linked
* list. Operations that index into the list will traverse the list from
* the beginning or the end, whichever is closer to the specified index.
所有的操作都可通過雙向連結清單完成。通過從開頭或者結尾周遊集合，去接近要操作的那個元素。
* <p><strong>Note that this implementation is not synchronized.</strong>
* If multiple threads access a linked list concurrently, and at least
* one of the threads modifies the list structurally, it <i> must</i> be
* synchronized externally. (A structural modification is any operation
* that adds or deletes one or more elements; merely setting the value of
* an element is not a structural modification.) This is typically
* accomplished by synchronizing on some object that naturally
* encapsulates the list.
*
* If no such object exists, the list should be "wrapped" using the
* {@link Collections#synchronizedList Collections.synchronizedList}
* method. This is best done at creation time, to prevent accidental
* unsynchronized access to the list: <pre>
* List list = Collections.synchronizedList(new LinkedList(...));</pre>
*
* <p>The iterators returned by this class's {@code iterator} and
* {@code listIterator} methods are <i> fail- fast </i>: if the list is
* structurally modified at any time after the iterator is created, in
* any way except through the Iterator's own {@code remove} or
* {@code add} methods, the iterator will throw a {@link
* ConcurrentModificationException} . Thus, in the face of concurrent
* modification, the iterator fails quickly and cleanly, rather than
* risking arbitrary, non - deterministic behavior at an undetermined
* time in the future.
*
* <p>Note that the fail - fast behavior of an iterator cannot be guaranteed
* as it is, generally speaking, impossible to make any hard guarantees in the
* presence of unsynchronized concurrent modification. Fail- fast iterators
* throw {@code ConcurrentModificationException} on a best- effort basis.
* Therefore, it would be wrong to write a program that depended on this
* exception for its correctness: <i> the fail- fast behavior of iterators
* should be used only to detect bugs. </i>
這幾段的翻譯與ArrayList相似，請參考：http://blog.csdn.net/disiwei1012/article/details/73947173
二、自己動手實作雙向連結清單
1.定義node節點類
2.實作基本方法
package com.demo4;
public class DoubleLinkList {
int length;
private Node header;
private Node tail;
public DoubleLinkList() {
length = ;
header = null ;
tail = null ;
}
/**
* 列印連結清單所有元素
*/
public void printAll(){
Node currentNode = header ;
while (currentNode != null){
System. out .println(currentNode .obj );
currentNode = currentNode .next ;
}
}
/**
* 删除指定位置元素
* @param index
*/
public void removeByIndex(Integer index ){
checkRangIndex( index);
Node node = this .getNode(index );
if (node .prev == null){
header = node. next;
header. prev = null ;
} else if (node .next == null){
tail = node. prev;
tail. next = null ;
} else {
Node preNode = node. prev;
Node nextNode = node. next;
preNode. next = nextNode;
nextNode. prev = preNode;
}
length--;
node = null ;//等待GC回收
}
/**
* 尾插法插入元素
* @param obj
*/
public void addTail(Object obj ){
this .addTailByIndex(obj , null);
}
/**
* 頭插法插入元素
* @param obj
*/
public void addHeader(Object obj ){
this .addHeaderByIndex(obj , null);
}
/**
* 尾插法插入元素，指定位置
* @param obj
* @param index 指定具體插入位置
*/
public void addTailByIndex(Object obj ,Integer index ){
if (index == null){
if (header == null){
createHeader( new Node(null , null, obj));
} else {
Node node = new Node(tail , null, obj);
tail. next = node;
tail = node;
length++;
}
} else {
checkRangIndex( index);
Node node = this .getNode(index );
node. next = null ;
node. prev = tail;
tail. next = node;
tail = node;
length++;
}
}
/**
* 頭插法插入元素,指定位置
* @param obj
* @param index 指定具體插入位置
*/
public void addHeaderByIndex(Object obj ,Integer index ){
if (index == null){
if (header == null){
createHeader( new Node(null , null, obj));
} else {
Node node = new Node(null ,header ,obj );
header. prev = node;
header = node;
length++;
}
} else {
checkRangIndex( index);
Node node = this .getNode(index );
node. next = header;
node. prev = null ;
header. prev = node;
header = node;
length++;
}
}
/**
* 根據索引擷取節點，如果索引在連結清單的前半部分，則從頭節點開始
* 如果索引在連結清單的後半部分，則從尾節點開始
* @param index
* @return
*/
public Node getNode( int index ){
checkRangIndex( index);
Node currentNode = null ;
if (index < length /){
currentNode = header ;
for (int i = ;i <index ;i ++){
currentNode = currentNode .next ;
}
} else {
currentNode = tail ;
for (int i =length -;i >index ;i --){
currentNode = currentNode .prev ;
}
}
return currentNode ;
}
/**
* 判斷索引位址是否合法
* @param index
*/
public void checkRangIndex( int index){
if (index < || index > length-){
throw new RuntimeException( "索引位址不合法！" );
}
}
/**
* 連結清單無節時建立頭結點，header和tail指向統一節點
* @param node
*/
public void createHeader(Node node ){
header = node;
tail = header;
length++;
}
private static class Node{
Node prev;
Node next;
Object obj;
public Node(Node prev ,Node next ,Object obj ) {
this .prev = prev ;
this .next = next ;
this .obj = obj ;
}
}
}
三、源碼分析
1.我們來看下LinkedList是如果定義雙向節點的：
和我定義的差别不大。
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 ;
}
}
LinkedList繼承關系如下：
LinkedList繼承抽象類AbstractSequentialList，我們知道抽象類可以選擇實作接口中的方法，也可以不實作接口中的方法，
LinkedList隻需實作AbstractSequentialList中未實作的方法、Deque接口中規定的方法、List接口中規定的方法就好了。
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
//存儲元素個數，即連結清單節點的個數
transient int size = ;
/**
* 頭節點
* 滿足這兩個條件
* 1.(first == null && last == null) 2.(first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* 尾節點
* 滿足這兩個條件
* 1. (first == null && last == null) 2.(last.next == null && last.item != null)
*/
transient Node<E> last;
/**
* 空構造函數
*/
public LinkedList() {
}
/**
* 構造一個LinkedList，并将集合c中的元素全部放入
*
* @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);
}
/**
* 頭插法插入元素
* 如果該連結清單沒有頭結點和尾節點，則将該節點為頭尾節點，
* 如果已經有頭結點，則插入頭結點前方
*/
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;
//元素個數+1
size++;
//修改次數+1
modCount++;
}
/**
* 尾插法插入元素
* 如果該連結清單沒有頭結點和尾節點，則将該節點為頭尾節點，
* 如果已經有尾結點，則插入尾節點的後方
*/
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;
//元素個數+1
size++;
//修改次數+1
modCount++;
}
/**
* 在節點succ前插入節點，succ不能為null,否則會抛出空指針
*/
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;
//如果succ無前節點，succ預設為頭結點
if (pred == null)
first = newNode;
else
pred. next = newNode;
size++;
modCount++;
}
/**
* 删除頭結點
*/
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 ; //GC回收
//首節點的後一個節點為新的首節點
first = next;
if (next == null)
last = null ;
else
next. prev = null ;
//元素個數-1
size--;
//修改次數+1
modCount++;
//傳回被删除元素
return element ;
}
/**
* 删除尾節點
*/
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
//尾節點的prev節點作為新的尾節點
last = prev;
if (prev == null)
first = null ;
else
prev. next = null ;
size--;
modCount++;
return element ;
}
/**
* 删除中間節點
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x .item ;
//x的下一個節點
final Node<E> next = x .next ;
//x的前一個節點
final Node<E> prev = x .prev ;
//如果無前節點，則x為頭節點
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 ;
}
/**
* 傳回頭節點中儲存的資料，如果頭節點為null,則抛出NoSuchElementException
* @return the first element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getFirst() {
final Node<E> f = first ;
if (f == null)
throw new NoSuchElementException();
return f .item ;
}
/**
* 傳回尾節點中儲存的資料，如果尾節點為null,則抛出NoSuchElementException
*
* @return the last element in this list
* @throws NoSuchElementException if this list is empty
*/
public E getLast() {
final Node<E> l = last ;
if (l == null)
throw new NoSuchElementException();
return l .item ;
}
/**
* 移除頭節點，并傳回頭節點
* @return the first element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeFirst() {
final Node<E> f = first ;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f );
}
/**
* 移除尾節點，并傳回尾節點
*
* @return the last element from this list
* @throws NoSuchElementException if this list is empty
*/
public E removeLast() {
final Node<E> l = last ;
if (l == null)
throw new NoSuchElementException();
return unlinkLast(l );
}
/**
* 頭插法插入元素
*
* @param e the element to add
*/
public void addFirst(E e ) {
linkFirst( e);
}
/**
* 尾插法插入元素
*
* @param e the element to add
*/
public void addLast(E e ) {
linkLast( e);
}
/**
* 判斷集合中是否至少有一個節點的資料等于o
*
* @param o element whose presence in this list is to be tested
* @return {@code true} if this list contains the specified element
*/
public boolean contains(Object o ) {
return indexOf(o ) != -;
}
/**
* 傳回存儲節點的個數
*
* @return the number of elements in this list
*/
public int size() {
return size ;
}
/**
* 尾插法插入元素
*/
public boolean add(E e ) {
linkLast( e);
return true ;
}
/**
* 移除集合中第一個出現的節點中的資料等于o的節點，如果集合中不包含該元素，則什麼都不做
* 如果o為null,則删除第一個資料為null的節點
*/
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 ;
}
/*
* 将集合c中的元素全部加到連結清單的尾部
*/
public boolean addAll(Collection<? extends E> c) {
return addAll(size , c );
}
/**
* 将集合c插入到雙向連結清單中，插入的位置是index之後
*/
public boolean addAll(int index , Collection<? extends E> c ) {
checkPositionIndex( index);//檢測index是否>=0或者<length
Object[] a = c.toArray();
//新加入節點個數
int numNew = a .length ;
if (numNew == )//如果沒有節點要插入傳回false
return false ;
//如果index等于size,則相當于插入尾部
Node<E> pred, succ;
if (index == size ) {
succ = null ;
pred = last;
} else {
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 ;
}
/**
* 移除集合中全部節點，相當于清空集合，為了確定被GC回收，清空引用
* The list will be empty after this call returns.
*/
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 = ;
modCount++;
}
// Positional Access Operations
/**
* 傳回指定節點的資料
*/
public E get( int index ) {
checkElementIndex( index);
return node(index ).item ;
}
/**
* 替換指定節點的資料
*/
public E set( int index , E element ) {
checkElementIndex( index);
Node<E> x = node( index);
E oldVal = x. item;
x. item = element;
return oldVal ;
}
/**
* 在指定元素前插入節點
*/
public void add(int index , E element ) {
checkPositionIndex( index);
if (index == size )
linkLast( element);
else
linkBefore( element, node( index));
}
/**
* 移除指定位置元素
*/
public E remove( int index ) {
checkElementIndex( index);
return unlink(node(index ));
}
/**
* Tells if the argument is the index of an existing element.
*/
private boolean isElementIndex( int index) {
return index >= && index < size;
}
/**
* 判斷一個索引是否在連結清單允許的範圍内
*/
private boolean isPositionIndex( int index) {
return index >= && index <= size;
}
private String outOfBoundsMsg( int index ) {
return "Index: " +index +", Size: " +size ;
}
private void checkElementIndex( int index) {
if (!isElementIndex(index ))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index ));
}
private void checkPositionIndex( int index) {
if (!isPositionIndex(index ))
throw new IndexOutOfBoundsException(outOfBoundsMsg(index ));
}
/**
* 傳回指定位置的節點，和我寫的差不多
*/
Node<E> node( int index ) {
// 若index < 雙向連結清單長度的1/2,則從前先後查找;
// 否則，從後向前查找。
if (index < (size >> )) {
Node<E> x = first;
for (int i = ; i < index ; i ++)
x = x. next;
return x ;
} else {
Node<E> x = last;
for (int i = size - ; i > index ; i --)
x = x. prev;
return x ;
}
}
// Search Operations
/**
* 查詢對象o在集合中的位置
* 如果對象o為null,傳回第一個節點資料為null的節點的位置，
* 否則，傳回第一個一個比對節點的位置。如果未找到，則傳回-1
*/
public int indexOf(Object o ) {
int index = ;
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 -;
}
/**
* 查詢對象o在集合中的位置
* 如果對象o為null,傳回最後一個節點資料為null的節點的位置，
* 否則，傳回最後一個比對節點的位置。如果未找到，則傳回-1
*/
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 -;
}
// Queue operations.實作隊列接口中的方法
/**
* 傳回頭節點的資料，如果節點為null，則傳回null
* @return the head of this list, or {@code null} if this list is empty
* @since 1.5
*/
public E peek() {
final Node<E> f = first ;
return (f == null) ? null : f. item;
}
/**
* 傳回頭節點
*/
public E element() {
return getFirst();
}
/**
* 傳回頭節點資料，并将頭節點删除
*
*/
public E poll() {
final Node<E> f = first ;
return (f == null) ? null : unlinkFirst( f);
}
/**
* 傳回頭節點，并将頭節點删除
*
*/
public E remove() {
return removeFirst();
}
/**
* 在尾部增加一個元素e
*/
public boolean offer(E e ) {
return add(e );
}
// Deque operations
/**
* 在頭部增加一個元素e
*/
public boolean offerFirst(E e ) {
addFirst( e);
return true ;
}
public boolean offerLast(E e ) {
addLast( e);
return true ;
}
public E peekFirst() {
final Node<E> f = first ;
return (f == null) ? null : f. item;
}
public E peekLast() {
final Node<E> l = last ;
return (l == null) ? null : l. item;
}
public E pollFirst() {
final Node<E> f = first ;
return (f == null) ? null : unlinkFirst( f);
}
public E pollLast() {
final Node<E> l = last ;
return (l == null) ? null : unlinkLast( l);
}
public void push(E e ) {
addFirst( e);
}
public E pop() {
return removeFirst();
}
public boolean removeFirstOccurrence(Object o ) {
return remove(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 ;
}
/**
* 在抽象類AbstractSequentialList中唯一沒有實作的方法
* 傳回該集合ListIterator疊代器
*/
public ListIterator<E> listIterator( int index ) {
checkPositionIndex( index);
return new ListItr( index);
}
private class ListItr implements ListIterator<E> {
private Node<E> lastReturned = null;//最後一個傳回的節點，也就是目前持有的節點
private Node<E> next ;//目前持有節點的下一個節點
private int nextIndex ;//目前持有節點的下一個節點位置
private int expectedModCount = modCount ;//實作fast-fail
ListItr( int index ) {
next = ( index == size) ? null : node(index );
nextIndex = index ;
}
//根據nextIndex是否等于size，判斷時候是否還有下一個節點
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 > ;
}
//擷取前一個節點
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 - ;
}
//移除目前持有節點
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 ++;
}
//替換目前持有節點的值為e
public void set(E e ) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned .item = e ;
}
//在目前持有節點後插入節點e
public void add(E e ) {
checkForComodification();
lastReturned = null ;
if (next == null)
linkLast( e);
else
linkBefore( e, next);
nextIndex ++;
expectedModCount ++;
}
final void checkForComodification() {//fast-fail具體時間
if (modCount != expectedModCount )
throw new ConcurrentModificationException();
}
}
//節點定義
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 ;
}
}
/**
* @since 1.6
*/
public Iterator<E> descendingIterator() {
return new DescendingIterator ();
}
/**
* Adapter to provide descending iterators via ListItr.previou
* 從後周遊集合，通過ListItr
*/
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();
}
}
@SuppressWarnings( "unchecked" )
private LinkedList<E> superClone() {
try {
return (LinkedList<E>) super.clone();
} catch (CloneNotSupportedException e ) {
throw new InternalError();
}
}
/**
*淺拷貝集合，不拷貝元素，自拷貝引用
* @return a shallow copy of this {@code LinkedList} instance
*/
public Object clone() {
LinkedList<E> clone = superClone();
// Put clone into "virgin" state
clone. first = clone. last = null ;
clone. size = ;
clone. modCount = ;
// Initialize clone with our elements
for (Node<E> x = first ; x != null; x = x. next)
clone.add( x. item);
return clone ;
}
/**
* 傳回一個包含該集合所有元素的集合，為了保證集合數組的安全，需要建構一個新數組
* <p> This method acts as bridge between array -based and collection- based
* APIs.
*
* @return an array containing all of the elements in this list
* in proper sequence
*/
public Object[] toArray() {
Object[] result = new Object[size ];
int i = ;
for (Node<E> x = first ; x != null; x = x. next)
result[ i++] = x. item;
return result ;
}
/**
* 給一個數組a,傳回一個數組（數組元素按照集合從前往後的順序排列），該數組包含了集合中的所有元素
* 若數組a的長度不足以裝入所有的集合元素，則使用Array.newInstance()這一方法建立一個size大小，
* 元素類型為數組a的元素類型的數組，并将該數組指派給a
*/
@SuppressWarnings( "unchecked" )
public <T> T[] toArray(T[] a) {
if (a .length < size )
a = (T[])java.lang.reflect.Array. newInstance(
a .getClass().getComponentType(), size );
int i = ;
Object[] result = a;
for (Node<E> x = first ; x != null; x = x. next)
result[ i++] = x. item;
if (a .length > size )
a[ size] = null ;
return a ;
}
}
![PriorityQueue優先隊列源碼解析QueuePriorityQueue[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)