Java LinkedList源碼剖析

2019-11-06 07:26:10

字體：大中小

供稿：網(wǎng)友

引用自此博客文章，感謝CarpenterLee

java LinkedList源碼剖析

本文github地址

總體介紹

LinkedList同時實現(xiàn)了List接口和Deque接口，也就是說它既可以看作一個順序容器，又可以看作一個隊列（Queue），同時又可以看作一個棧（Stack）。這樣看來，LinkedList簡直就是個全能冠軍。當你需要使用棧或者隊列時，可以考慮使用LinkedList，一方面是因為Java官方已經(jīng)聲明不建議使用Stack類，更遺憾的是，Java里根本沒有一個叫做Queue的類（它是個接口名字）。關(guān)于棧或隊列，現(xiàn)在的首選是ArrayDeque，它有著比LinkedList（當作棧或隊列使用時）有著更好的性能。

LinkedList

LinkedList底層通過雙向鏈表實現(xiàn)，本節(jié)將著重講解插入和刪除元素時雙向鏈表的維護過程，也即是之間解跟List接口相關(guān)的函數(shù)，而將Queue和Stack以及Deque相關(guān)的知識放在下一節(jié)講。雙向鏈表的每個節(jié)點用內(nèi)部類Node表示。LinkedList通過first和last引用分別指向鏈表的第一個和最后一個元素。注意這里沒有所謂的啞元，當鏈表為空的時候first和last都指向null。

//Node內(nèi)部類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的實現(xiàn)方式?jīng)Q定了所有跟下標相關(guān)的操作都是線性時間，而在首段或者末尾刪除元素只需要常數(shù)時間。為追求效率LinkedList沒有實現(xiàn)同步（synchronized），如果需要多個線程并發(fā)訪問，可以先采用Collections.synchronizedList()方法對其進行包裝。

方法剖析

add()

add()方法有兩個版本，一個是add(E e)，該方法在LinkedList的末尾插入元素，因為有last指向鏈表末尾，在末尾插入元素的花費是常數(shù)時間。只需要簡單修改幾個相關(guān)引用即可；另一個是add(int index, E element)，該方法是在指定下表處插入元素，需要先通過線性查找找到具體位置，然后修改相關(guān)引用完成插入操作。

add()

結(jié)合上圖，可以看出add(E e)的邏輯非常簡單。

//add(E e)public boolean add(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++; return true;}

add(int index, E element)的邏輯稍顯復(fù)雜，可以分成兩部，1.先根據(jù)index找到要插入的位置；2.修改引用，完成插入操作。

//add(int index, E element)public void add(int index, E element) { checkPositionIndex(index);//index >= 0 && index <= size; if (index == size)//插入位置是末尾，包括列表為空的情況 add(element); else{ Node<E> succ = node(index);//1.先根據(jù)index找到要插入的位置 //2.修改引用，完成插入操作。 final Node<E> pred = succ.prev; final Node<E> newNode = new Node<>(pred, e, succ); succ.prev = newNode; if (pred == null)//插入位置為0 first = newNode; else pred.next = newNode; size++; }}

上面代碼中的node(int index)函數(shù)有一點小小的trick，因為鏈表雙向的，可以從開始往后找，也可以從結(jié)尾往前找，具體朝那個方向找取決于條件index < (size >> 1)，也即是index是靠近前端還是后端。

remove()

remove()方法也有兩個版本，一個是刪除跟指定元素相等的第一個元素remove(Object o)，另一個是刪除指定下標處的元素remove(int index)。

remove()

兩個刪除操作都要1.先找到要刪除元素的引用，2.修改相關(guān)引用，完成刪除操作。在尋找被刪元素引用的時候remove(Object o)調(diào)用的是元素的equals方法，而remove(int index)使用的是下標計數(shù)，兩種方式都是線性時間復(fù)雜度。在步驟2中，兩個revome()方法都是通過unlink(Node<E> x)方法完成的。這里需要考慮刪除元素是第一個或者最后一個時的邊界情況。

//unlink(Node<E> x)，刪除一個NodeE unlink(Node<E> x) { 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;//let GC work size--; return element;}

get()

get(int index)得到指定下標處元素的引用，通過調(diào)用上文中提到的node(int index)方法實現(xiàn)。

public E get(int index) { checkElementIndex(index);//index >= 0 && index < size; return node(index).item;}

set()

set(int index, E element)方法將指定下標處的元素修改成指定值，也是先通過node(int index)找到對應(yīng)下表元素的引用，然后修改Node中item的值。

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

上一篇：java static關(guān)鍵字的使用

下一篇：Java 接口——面向?qū)ο蟮木?/a>