腳本之家服務器常用軟件

快捷導航

Java中的LinkedList底層源碼分析

更新時間：2023年12月15日 09:19:37 作者：愛喝咖啡的程序員

這篇文章主要介紹了Java中的LinkedList底層源碼分析,底層基于雙向鏈表,往LinkedList中間插入元素時,不需要移動大量的元素,只需要修改前后節(jié)點的指針,速度快,需要的朋友可以參考下

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

優(yōu)點:

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

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

缺點:

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

二. 源碼分析

2.1 add

默認在雙向鏈表的尾部插入一個元素

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

在雙向鏈表中，找到目標下標對應的節(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;
	}
}

首先，通過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)，通過下標能快速找到對應的內存地址，接著直接讀取內存地址中的值。

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

node()方法的代碼之前已經(jīng)學習過了，先大致的判斷目標節(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é)點，作為隊列新的頭結點。

2.10 remove(int index)

刪除指定下標的節(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é)點。