java源碼學習-LinkedList

java.util.LinkedList

• 介紹
• 類圖
• 屬性
• 類
• • 内部類-Node
  • 内部類-ListItr
  • • 屬性
    • 方法
    • • 構造方法
      • 添加新節點元素
      • 下一個節點相關方法
      • 前一個節點相關方法
      • 移除節點
      • 替換節點
  • 内部類-DescendingIterator
  • LLSpliterator類(待完善)
• 方法
• • 構造方法
  • 方法
  • 添加新節點元素相關方法
  • • List接口的添加操作
    • Deque接口的添加操作
    • 總結(待完善)
  • 擷取節點相關方法
  • • 擷取指定位置節點方法
    • 擷取首節點相關方法
    • 擷取尾節點相關方法
    • 總結(待完善)
  • 移除節點相關方法
  • • 删除指定對象方法
    • 删除指定位置節點方法
    • 删除頭節點相關方法
    • 删除尾節點相關方法
    • 總結(待完善)
  • 包含節點相關方法
  • 替換節點
  • 清空清單
  • 克隆
  • 轉換成數組
  • 其他方法(待完善)
• 總結

介紹

• Linked(鍊)List(清單)：節點之間 以 鍊的形式 進行關聯，形成的清單
• 實作了清單接口List(能對它進行隊列操作)、雙向隊列接口Deque(能将LinkedList當作雙端隊列使用)
• 繼承了 有序清單抽象類-AbstractSequentialList

類圖

屬性

// 首節點
transient Node<E> first;

// 尾節點
transient Node<E> last;

// 節點個數
transient int size = 0;
           

類

内部類-Node

LinkedList中，每一個節點 都是一個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;
	}
}
           

内部類-ListItr

實作了 清單疊代器接口ListIterator

屬性

// 最近一次傳回的節點
private Node<E> lastReturned;
// 下一個節點
private Node<E> next;
// 下一個節點的index
private int nextIndex;
private int expectedModCount = modCount;
           

方法

構造方法

ListItr(int index) {
	// 如果指定位置index = size，也就是說指定位置index是清單末尾， 則下一個節點next是null
	// 否則，next 就是 以index為索引的下一個節點，其中node(index)是方法
	// assert isPositionIndex(index);
	next = (index == size) ? null : node(index);
	// 下一個節點的index = 入參index
	nextIndex = index;
}
           

添加新節點元素

@Override
public void add(E e) {
	// 如果多個線程在同時操作，就抛出異常
	checkForComodification();
	// 最近一次傳回的節點為空(特别注意這塊!!!)
	lastReturned = null;
	// 如果下一個節點為空，則在清單末尾添加新節點
	if (next == null) {
		linkLast(e);
	} else {
		// 如果下一個節點不為空，則在 next節點 之前添加新節點
		linkBefore(e, next);
	}
	// 下一個節點的index自增
	nextIndex++;
	expectedModCount++;
}

final void checkForComodification() {
	if (modCount != expectedModCount) {
		throw new ConcurrentModificationException();
	}
}
           

下一個節點相關方法

// 根據判斷 下一個節點索引 是否小于 清單節點個數 得出 是否有下一個節點
@Override
public boolean hasNext() {
	return nextIndex < size;
}

@Override
public E next() {
	checkForComodification();
	// 如果沒有下一個節點，就抛出異常
	// 第1次調用，nextIndex = 0
	// 第2次調用，nextIndex = 1
	// 第3次調用，nextIndex = 2
	// 第4次調用，nextIndex = 3，不再小于size，會抛出異常
	if (!hasNext()) {
		throw new NoSuchElementException();
	}

	// 假設清單是三個節點内容是a、b、c，從a開始，根據構造方法，next = 節點a對應的節點，nextIndex = 0
	// 第1次調用next方法，根據構造方法，lastReturned = a
	// 第2次調用next方法，由于上次調用之後next變成了b，是以 lastReturned = b
	// 第3次調用next方法，由于上次調用之後next變成了c，是以 lastReturned = c
	lastReturned = next;
	// 第1次調用， next 變成 a.next，也就是b
	// 第2次調用， next 變成 b.next，也就是c
	// 第3次調用， next 變成 c.next，也就是null
	next = next.next;
	// 下一個節點索引自增1
	// 第1次調用後， nextIndex = 1
	// 第2次調用後， nextIndex = 2
	// 第3次調用後， nextIndex = 3
	nextIndex++;
	// 傳回 最近一次傳回的節點的内容，也就是item
	return lastReturned.item;
}
           

前一個節點相關方法

注意：在調用完previous之後，next 和 lastReturned 指向的是同一個節點，而在調用完next方法之後，next 和 lastReturned 指向的不是同一個節點

@Override
public boolean hasPrevious() {
	return nextIndex > 0;
}

@Override
public E previous() {
	checkForComodification();
	// 如果是在沒有調用過next方法的時候，此時nextIndex = 0，會抛出異常
	// 在第四次調用的時候，nextIndex = 0，也會抛出異常
	if (!hasPrevious()) {
		throw new NoSuchElementException();
	}

	// 假設此時已經調用過3次next方法了，nextIndex = 3、next = null、lastReturned = c
	// 第1次調用previous方法，由于next == null，是以 next = last(最後一個節點) ，也就是next = c，此時lastReturned 也=c
	// 第2次調用previous方法，由于next(=c) != null，是以 next = next.prev(也就是c.prev=b) ，此時lastReturned 也=b
	// 第3次調用previous方法，由于next(=b) != null，是以 next = next.prev(也就是b.prev=a) ，此時lastReturned 也=a
	lastReturned = next = (next == null) ? last : next.prev;
	// 第1次調用，nextIndex從3變成2
	// 第2次調用，nextIndex從2變成1
	// 第3次調用，nextIndex從1變成0
	nextIndex--;
	// 傳回 最近一次傳回的節點的内容，也就是item
	return lastReturned.item;
}
           

移除節點

移除 目前位置的 節點

@Override
public void remove() {
	checkForComodification();
	// 如果lastReturned = null，說明沒有調用過next方法，也就不知道該移除哪個節點，抛出異常
	if (lastReturned == null) {
		throw new IllegalStateException();
	}

	// 得到 目前節點lastReturned 的 下一個節點lastNext
	// 假如說，此時 lastReturned = b，則lastNext = c
	Node<E> lastNext = lastReturned.next;
	// 移除 目前節點lastReturned(b)
	unlink(lastReturned);
	// 如果 下一個節點next = 目前節點lastReturned，說明剛執行過previous方法(特别要注意這塊!!!)
	// 如果 next 也等于 b，說明剛執行過previous方法，此時nextIndex=1
	if (next == lastReturned) {
		// 那就把 next節點 變成 c
		next = lastNext;
	} else {
		// 如果 下一個節點next != 目前節點lastReturned，說明剛執行過next方法，把下一個節點的索引自減少-1
		// 如果 下一個節點next 不等于 b，說明剛執行過next方法，此時nextIndex=2，把nextIndex變成1
		nextIndex--;
	}
	// 把 目前節點 置為null，友善垃圾回收(特别要注意這塊!!!)
	lastReturned = null;
	expectedModCount++;
}
           

替換節點

@Override
public void set(E e) {
	// 如果lastReturned = null，說明沒有調用過next方法，也就不知道該替換哪個節點，抛出異常
	if (lastReturned == null) {
		throw new IllegalStateException();
	}
	checkForComodification();
	// 把 目前節點的item替換為元素e
	lastReturned.item = e;
}
           

内部類-DescendingIterator

• 實作了 Iterator接口
• 提供 清單的 降序疊代
• 依賴ListItr類，使用的都是ListItr中的方法

private class DescendingIterator implements Iterator<E> {
	private final ListItr itr = new ListItr(size());
	
	@Override
	public boolean hasNext() {
		return itr.hasPrevious();
	}
	
	@Override
	public E next() {
		return itr.previous();
	}
        
	@Override
	public void remove() {
		itr.remove();
	}
}
           

LLSpliterator類(待完善)

實作了 Spliterator接口

方法

構造方法

public LinkedList() {
}

public LinkedList(Collection<? extends E> c) {
	this();
	addAll(c);
}
           

方法

添加新節點元素相關方法

List接口的添加操作

// 繼承的是AbstraceList
@Override
public boolean add(E e) {
	linkLast(e);
	return true;
}

// 繼承的是AbstraceList
@Override
public void add(int index, E element) {
	checkPositionIndex(index);
	// 如果指定位置 = 清單大小，相當于在清單末尾添加指定元素element
	if (index == size) {
		linkLast(element);
	} else {
		linkBefore(element, node(index));
	}
}

private void checkPositionIndex(int index) {
	if (!isPositionIndex(index)) {
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}
}

private boolean isPositionIndex(int index) {
	return index >= 0 && index <= size;
}

@Override
public boolean addAll(Collection<? extends E> c) {
	return addAll(size, c);
}

@Override
public boolean addAll(int index, Collection<? extends E> c) {
	checkPositionIndex(index);

	// 把參數集合轉換成數組
	Object[] a = c.toArray();
	int numNew = a.length;
	// 如果參數集合大小=0，則傳回添加失敗
	if (numNew == 0) {
		return false;
	}

	Node<E> pred, succ;
	// 如果 指定位置index = 清單大小size，則 指定位置=null，前一個節點為清單最後一個節點last
	if (index == size) {
		succ = null;
		pred = last;
	} else {
		// 如果 指定位置index != 清單大小size，則根據index擷取指定位置節點 和 其前一個節點
		succ = node(index);
		pred = succ.prev;
	}
	// 上面這裡，如果index=0，size=0，則succ=null，pred=null
	// 上面這裡，如果index=0，size!=0，則succ=是首節點，pred=null
	// 上面這裡，如果index!=0，size!=0，則succ=index位置的節點，pred=index位置的節點 的 前置節點

	// 循環數組
	for (Object o : a) {
		@SuppressWarnings("unchecked") E e = (E) o;
		// 建立節點，建立節點 的 前置節點 = pred，後驅節點 暫時 為null
		Node<E> newNode = new Node<>(pred, e, null);
		// 如果 前置節點pred = null，說明指定位置index=0，把 建立節點 當作是 清單的 首節點
		if (pred == null) {
			first = newNode;
		} else {
			// 如果 前置節點pred 不為null，則把 前置節點pred 的 後驅節點 改為 目前建立的節點
			pred.next = newNode;
		}
		// 把 建立節點 替換為 前置節點，為的是下一次循環
		pred = newNode;
	}

	// 循環結束，如果succ=null，意味着 循環之前 index=0、size=0
	// 則把最後一次循環結束之後的pred節點 當作 清單尾節點
	if (succ == null) {
		last = pred;
	} else {
		// 循環結束，如果succ!=null，意味着 循環之前 index!=0、size!=0
		// 則把最後一次循環結束之後的pred節點 的後繼節點 設定為 之前擷取到的 index位置的節點(succ)
		// 把 index位置的節點(succ) 的 前置節點 設定為 最後一次循環結束之後的pred節點
		pred.next = succ;
		succ.prev = pred;
	}

	size += numNew;
	modCount++;
	return true;
}
           

下面來看linkFirst和linkLast

private void linkFirst(E e) {
	// 首節點f
	final Node<E> f = first;
	// 建立一個新節點newNode，newNode的前置節點為null、後繼節點為 首節點f
	final Node<E> newNode = new Node<>(null, e, f);
	// 把newNode設定為首節點
	first = newNode;
	// 如果 首節點f 為空，則代表 清單也是空的，把newNode也設定為尾節點
	if (f == null) {
		last = newNode;
	} else {
		// 如果 首節點f 不為空，則把 首節點f 的 前置節點 設定為 建立節點newNode
		f.prev = newNode;
	}
	size++;
	modCount++;
}

void linkLast(E e) {
	// 尾節點l
	final Node<E> l = last;
	// 建立一個新節點newNode，newNode的前置節點為l、後繼節點為null
	final Node<E> newNode = new Node<>(l, e, null);
	// 把newNode設定為尾節點
	last = newNode;
	// 如果 尾節點l 為空，則代表 清單也是空的，把newNode也設定為首節點
	if (l == null) {
		first = newNode;
	} else {
		// 如果 尾節點l 不為空，則把 尾節點l 的 後置節點 設定為 建立節點newNode
		l.next = newNode;
	}
	size++;
	modCount++;
}
           

Deque接口的添加操作

實際上用到的都是add相關方法

public void push(E e) {
	addFirst(e);
}

// 繼承的是Deque
@Override
public void addFirst(E e) {
	linkFirst(e);
}

// 繼承的是Deque
@Override
public void addLast(E e) {
	linkLast(e);
}

// 繼承的是Deque
@Override
public boolean offer(E e) {
	return add(e);
}

// 繼承的是Deque
@Override
public boolean offerFirst(E e) {
	addFirst(e);
	return true;
}

@Override
public boolean offerLast(E e) {
	addLast(e);
	return true;
}
           

總結(待完善)

擷取節點相關方法

擷取指定位置節點方法

// 繼承的是AbstractSequentialList
@Override
public E get(int index) {
	checkElementIndex(index);
	return node(index).item;
}

private void checkElementIndex(int index) {
	if (!isElementIndex(index)) {
		throw new IndexOutOfBoundsException(outOfBoundsMsg(index));
	}
}

private boolean isElementIndex(int index) {
	return index >= 0 && index < size;
}
           

擷取首節點相關方法

// 1.element、getFirst
// 繼承的是Deque
@Override
public E element() {
	return getFirst();
}

// 繼承的是Deque
// 注意 如果首節點為空 則抛出異常
@Override
public E getFirst() {
	final Node<E> f = first;
	if (f == null) {
		throw new NoSuchElementException();
	}
	return f.item;
}

// 2.peek、peekFirst
// 如果首節點為空 則傳回null
// 注意，不删除首節點
public E peek() {
	final Node<E> f = first;
	return (f == null) ? null : f.item;
}

public E peekFirst() {
	final Node<E> f = first;
	return (f == null) ? null : f.item;
}

// 3.poll、pollFirst
// 移除首節點并傳回
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);
}
           

下面來看unlinkFirst方法

private E unlinkFirst(Node<E> f) {
	// assert f == first && f != null;
	// 得到首節點的元素内容
	final E element = f.item;
	// 得到首節點的下一個節點
	final Node<E> next = f.next;
	// 把上面2個都置為null
	f.item = null;
	f.next = null; // help GC
	// 把首節點的下一個節點 作為 新的首節點
	first = next;
	// 如果新的首節點為null，則尾節點也為null
	if (next == null)
		last = null;
	else
		// 如果新的首節點不為null，則新的首節點的 前置節點 置為null
		next.prev = null;
	size--;
	modCount++;
	return element;
}
           

擷取尾節點相關方法

// 繼承的是Deque
// 注意如果 尾節點為空 則抛出異常
@Override
public E getLast() {
	final Node<E> l = last;
	if (l == null) {
		throw new NoSuchElementException();
	}
	return l.item;
}

// 如果尾節點為空 則傳回null
// 注意，不删除尾節點
public E peekLast() {
	final Node<E> l = last;
	return (l == null) ? null : l.item;
}

// 移除尾節點并傳回
public E pollLast() {
	final Node<E> l = last;
	return (l == null) ? null : unlinkLast(l);
}
           

下面來看unlinkLast方法

private E unlinkLast(Node<E> l) {
	// assert l == last && l != null;
	final E element = l.item;
	final Node<E> prev = l.prev;
	// 把尾節點的元素内容 和 尾節點的前置節點 置為null
	l.item = null;
	l.prev = null; // help GC
	// 把 尾節點 的 前置節點 作為新的尾節點
	last = prev;
	if (prev == null)
		first = null;
	else
		// 把新的尾節點的 後驅節點置為null
		prev.next = null;
	size--;
	modCount++;
	return element;
}
           

總結(待完善)

移除節點相關方法

删除指定對象方法

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) {
		// 如果要删除的對象 的 前置節點為Null，說明要删除的對象是首節點，把要删除的對象 的 後置節點 作為 新的首節點
		first = next;
	} else {
		// 如果要删除的對象 的 前置節點不為Null
		// 把 要删除的對象 的 (前置節點的後置節點) 設定為 (要删除的對象 的 後置節點)
		prev.next = next;
		x.prev = null;
	}

	if (next == null) {
		// 如果要删除的對象 的 後置節點為Null，說明要删除的對象是尾節點，把要删除的對象 的 前置節點 作為 新的尾節點
		last = prev;
	} else {
		// 如果要删除的對象 的 後置節點不為Null
		// 把 要删除的對象 的 (後置節點的前置節點) 設定為 (要删除的對象 的 前置節點)
		next.prev = prev;
		x.next = null;
	}

	x.item = null;
	size--;
	modCount++;
	return element;
}
           

删除指定位置節點方法

public E remove(int index) {
	checkElementIndex(index);
	return unlink(node(index));
}
           

删除頭節點相關方法

public E pop() {
	return removeFirst();
}

public E remove() {
	return removeFirst();
}

// 删除頭結點，如果頭節點為空，則抛出異常
public E removeFirst() {
	final Node<E> f = first;
	if (f == null)
		throw new NoSuchElementException();
	return unlinkFirst(f);
}

// removeFirstOccurrence
           

另外 poll、pollFirst 也可以用于删除頭節點

删除尾節點相關方法

// 删除尾結點，如果尾節點為空，則抛出異常
public E removeLast() {
	final Node<E> l = last;
	if (l == null)
		throw new NoSuchElementException();
	return unlinkLast(l);
}

// removeLastOccurrence
           

另外 pollLast 也可以用于删除頭節點

總結(待完善)

包含節點相關方法

// 繼承的是AbstractCollection
@Override
public boolean contains(Object o) {
	return indexOf(o) != -1;
}

// 繼承的是AbstractList
@Override
public int indexOf(Object o) {
	// 從0開始循環
	int index = 0;
	if (o == null) {
		for (Node<E> x = first; x != null; x = x.next) {
			if (x.item == null) {
				// 找到第一個内容為null的節點之後就傳回
				return index;
			}
			index++;
		}
	} else {
		for (Node<E> x = first; x != null; x = x.next) {
			if (o.equals(x.item)) {
				// 找到第一個内容=指定對象o的節點之後就傳回
				return index;
			}
			index++;
		}
	}
	return -1;
}

@Override
public int lastIndexOf(Object o) {
	// 從清單末尾開始往前循環
	int index = size;
	if (o == null) {
		for (Node<E> x = last; x != null; x = x.prev) {
			index--;
			// 找到最後一個内容為null的節點之後就傳回
			if (x.item == null){
				return index;
			}
		}
	} else {
		for (Node<E> x = last; x != null; x = x.prev) {
			index--;
			// 找到最後一個内容=指定對象o的節點之後就傳回
			if (o.equals(x.item)) {
				return index;
			}
		}
	}
	return -1;
}
           

替換節點

public E set(int index, E element) {
	checkElementIndex(index);
	Node<E> x = node(index);
	E oldVal = x.item;
	x.item = element;
	return oldVal;
}
           

清空清單

// 繼承的是AbstractList
@Override
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; ) {
		// 清單的首節點開始循環，隻要節點不為空，就一直循環
		// 擷取 循環到的節點x 的 下一個節點next
		Node<E> next = x.next;
		// 把節點x的内容、前置、後置都設定為null
		x.item = null;
		x.next = null;
		x.prev = null;
		// 用 下一個節點next 作為 目前節點x，繼續循環
		x = next;
	}
	// 把首尾節點都置為null
	first = last = null;
	// 把清單大小設定尾0
	size = 0;
	modCount++;
}
           

克隆

基本比較好閱讀

@Override
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);
	}
}
           

轉換成數組

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;
}

public <T> T[] toArray(T[] a) {
	if (a.length < size)
		a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
	int i = 0;
	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;
}
           

其他方法(待完善)

總結

• 為什麼first和last用transient修飾？