一. 基本原理和優(yōu)缺點

優(yōu)點:

1.底層基于雙向鏈表，往LinkedList中間插入元素時，不需要移動大量的元素，只需要修改前后節(jié)點的指針，速度快。

2.適合頻繁、大量的插入元素，不會導(dǎo)致頻繁的擴容和拷貝元素。插入元素，只不過就是把新的元素掛到舊元素下面。

缺點:

1.不適合讀取隨機位置的元素，比如list.get(10)，因為需要遍歷鏈表，直到找到這個位置上的元素為止。

二. 源碼分析

2.1 add

默認(rèn)在雙向鏈表的尾部插入一個元素

public boolean add(E e) {
	linkLast(e);
	return true;
}

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

2.2 node

在雙向鏈表中，找到目標(biāo)下標(biāo)對應(yīng)的節(jié)點。這里可以學(xué)習(xí)鏈表的遍歷方式。

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 >> 1)，判斷待尋找的節(jié)點在雙向鏈表的前半部分，還是后半部分。

如果是前半部分，則會從雙向鏈表的頭節(jié)點開始遍歷，通過節(jié)點的next指針，不斷的向后尋找節(jié)點。→

如果是后半部分，則會從雙向鏈表的尾節(jié)點開始遍歷，通過節(jié)點的prev指針，不斷的向前尋找節(jié)點。←

2.3 add(int index, E element)

在指定元素的前面，插入一個元素。比如現(xiàn)在想要在隊尾插入一個元素。

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;
	if (pred == null)
		first = newNode;
	else
		pred.next = newNode;
	size++;
	modCount++;
}

succ指向隊尾元素，succ.prev表示隊尾節(jié)點前面的那個節(jié)點(倒數(shù)第二個節(jié)點)。

首先，創(chuàng)建一個新節(jié)點，讓新節(jié)點的prev指針指向倒數(shù)第二個節(jié)點，新節(jié)點的next指針指向隊尾節(jié)點。

接著，讓隊尾節(jié)點指的prev指向新節(jié)點。

最后，把倒數(shù)第二個節(jié)點的next指針指向新節(jié)點。

2.4 get

獲取一個隨機位置的節(jié)點中的值。

public E get(int index) {
	checkElementIndex(index);
	return node(index).item;
}

隨機讀取是ArrayList的強項， 因為ArrayList底層基于數(shù)組實現(xiàn)，通過下標(biāo)能快速找到對應(yīng)的內(nèi)存地址，接著直接讀取內(nèi)存地址中的值。

隨機讀取是LinkedList弱項，LinkedList底層基于雙向鏈表實現(xiàn)，它沒辦法通過下標(biāo)，直接找到內(nèi)存地址，必須從頭、尾節(jié)點開始，借助節(jié)點的prev和next指針，不斷的向前或向后尋找，直到找到元素為止。

node()方法的代碼之前已經(jīng)學(xué)習(xí)過了，先大致的判斷目標(biāo)節(jié)點距離頭、尾節(jié)點，哪個節(jié)點更近，盡量的減少查詢的次數(shù)，接著就是借助頭尾節(jié)點，不斷的向前或向后找，比如從頭節(jié)點，不斷的向后找。

2.5 getFirst

返回頭節(jié)點的值。如果頭節(jié)點為空，則拋出異常。

public E getFirst() {
	final Node<E> f = first;
	if (f == null)
		throw new NoSuchElementException();
	return f.item;
}

2.6 peek

返回頭節(jié)點的值，頭節(jié)點不需要出隊。

peek與getFirst的區(qū)別：如果不存在頭節(jié)點，peek會返回null，而getFirst會直接報錯。

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

2.7 getLast

返回尾部節(jié)點的值。

public E getLast() {
	final Node<E> l = last;
	if (l == null)
		throw new NoSuchElementException();
	return l.item;
}

2.8 removeLast

刪除隊尾節(jié)點。

public E removeLast() {
	final Node<E> l = last;
	if (l == null)
		throw new NoSuchElementException();
	return unlinkLast(l);
}

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

通過last指針找到隊尾元素，斷開隊尾元素與倒數(shù)第二個元素的指針指向，last指針指向倒數(shù)第二個元素，作為新的隊尾元素。

此時，原隊尾節(jié)點的next指針等于null，item等于null，prev等于null，且沒有被任何節(jié)點指向，接著就靠JVM來進行垃圾回收了。

2.9 removeFirst

刪除隊頭節(jié)點。

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

把隊列的頭節(jié)點與第二個節(jié)點之前的指針指向全部斷開，讓JVM來回收頭節(jié)點。

接著，讓first指針原隊列的第二個節(jié)點，作為隊列新的頭結(jié)點。

2.10 remove(int index)

刪除指定下標(biāo)的節(jié)點。

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

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

首先，通過node方法，遍歷鏈表，找到待刪除的節(jié)點。

接著，解除待刪除節(jié)點，對于左右兩邊節(jié)點的所有指針指向。讓左右兩邊的節(jié)點的next和prev指針互相指向。

最后，由JVM回收這個沒有任何人指向的節(jié)點。

三. 總結(jié)

LinkedList是一個基于雙向鏈表實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，對于隊頭和隊尾節(jié)點來說，無論是插入、刪除還是讀取節(jié)點的值，其實都是很輕松的。并且，默認(rèn)從隊尾插入節(jié)點，從隊頭獲取節(jié)點，所以LinkedList天然就可以作為隊列來使用。

由于基于雙向鏈表實現(xiàn)，所以無論你怎么插入數(shù)據(jù)，LinkedList的性能都很不錯，不用擔(dān)心擴容，移動大量元素等問題，性能上很好。

但是呢，在鏈表的中間插入元素，比在隊頭和隊尾插入元素的性能要差一些，這是因為隊頭和隊尾分別有first和last指針指向著它們，如果要在鏈表的中間指定位置插入元素，首先要遍歷鏈表，找到目標(biāo)元素，然后才能修改左右兩邊節(jié)點的指針，插入節(jié)點。

此外，如果要隨機獲取某個位置的元素，尤其是鏈表內(nèi)節(jié)點的數(shù)量很多的時候，由于需要遍歷鏈表，所以性能比較差。

到此這篇關(guān)于Java中的LinkedList底層源碼分析的文章就介紹到這了,更多相關(guān)LinkedList底層源碼內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論