LinkedList
本文github地址
總體介紹
LinkedList同時(shí)實(shí)現(xiàn)了List接口和Deque接口，也就是說(shuō)它既可以看作一個(gè)順序容器，又可以看作一個(gè)隊(duì)列（Queue），同時(shí)又可以看作一個(gè)棧（Stack）。這樣看來(lái)，LinkedList簡(jiǎn)直就是個(gè)全能冠軍。當(dāng)你需要使用棧或者隊(duì)列時(shí)，可以考慮使用LinkedList，一方面是因?yàn)镴ava官方已經(jīng)聲明不建議使用Stack類，更遺憾的是，Java里根本沒(méi)有一個(gè)叫做Queue的類（它是個(gè)接口名字）。關(guān)于棧或隊(duì)列，現(xiàn)在的首選是ArrayDeque，它有著比LinkedList（當(dāng)作棧或隊(duì)列使用時(shí)）有著更好的性能。
LinkedList底層通過(guò)雙向鏈表實(shí)現(xiàn)，本節(jié)將著重講解插入和刪除元素時(shí)雙向鏈表的維護(hù)過(guò)程，也即是之間解跟List接口相關(guān)的函數(shù)，而將Queue和Stack以及Deque相關(guān)的知識(shí)放在下一節(jié)講。雙向鏈表的每個(gè)節(jié)點(diǎn)用內(nèi)部類Node表示。LinkedList通過(guò)first和last引用分別指向鏈表的第一個(gè)和最后一個(gè)元素。注意這里沒(méi)有所謂的啞元，當(dāng)鏈表為空的時(shí)候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的實(shí)現(xiàn)方式?jīng)Q定了所有跟下標(biāo)相關(guān)的操作都是線性時(shí)間，而在首段或者末尾刪除元素只需要常數(shù)時(shí)間。為追求效率LinkedList沒(méi)有實(shí)現(xiàn)同步（synchronized），如果需要多個(gè)線程并發(fā)訪問(wèn)，可以先采用Collections.synchronizedList()方法對(duì)其進(jìn)行包裝。
方法剖析
add()
add()方法有兩個(gè)版本，一個(gè)是add(E e)，該方法在LinkedList的末尾插入元素，因?yàn)橛?code>last指向鏈表末尾，在末尾插入元素的花費(fèi)是常數(shù)時(shí)間。只需要簡(jiǎn)單修改幾個(gè)相關(guān)引用即可；另一個(gè)是add(int index, E element)，該方法是在指定下表處插入元素，需要先通過(guò)線性查找找到具體位置，然后修改相關(guān)引用完成插入操作。
結(jié)合上圖，可以看出add(E e)的邏輯非常簡(jiǎn)單。
//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;//原來(lái)鏈表為空，這是插入的第一個(gè)元素
else
l.next = newNode;
size++;
return true;
}
add(int index, E element)
//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ù)有一點(diǎn)小小的trick，因?yàn)殒湵黼p向的，可以從開(kāi)始往后找，也可以從結(jié)尾往前找，具體朝那個(gè)方向找取決于條件index < (size >> 1)，也即是index是靠近前端還是后端。
remove()
remove()方法也有兩個(gè)版本，一個(gè)是刪除跟指定元素相等的第一個(gè)元素remove(Object o)，另一個(gè)是刪除指定下標(biāo)處的元素remove(int index)。
兩個(gè)刪除操作都要1.先找到要?jiǎng)h除元素的引用，2.修改相關(guān)引用，完成刪除操作。在尋找被刪元素引用的時(shí)候remove(Object o)調(diào)用的是元素的equals方法，而remove(int index)使用的是下標(biāo)計(jì)數(shù)，兩種方式都是線性時(shí)間復(fù)雜度。在步驟2中，兩個(gè)revome()方法都是通過(guò)unlink(Node<E> x)方法完成的。這里需要考慮刪除元素是第一個(gè)或者最后一個(gè)時(shí)的邊界情況。
//unlink(Node<E> x)，刪除一個(gè)Node
E unlink(Node<E> x) {
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {//刪除的是第一個(gè)元素
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {//刪除的是最后一個(gè)元素
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;//let GC work
size--;
return element;
}
get()
get(int index)得到指定下標(biāo)處元素的引用，通過(guò)調(diào)用上文中提到的node(int index)方法實(shí)現(xiàn)。
public E get(int index) {
checkElementIndex(index);//index >= 0 && index < size;
return node(index).item;
}
set()
set(int index, E element)方法將指定下標(biāo)處的元素修改成指定值，也是先通過(guò)node(int index)找到對(duì)應(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;
}
posted on 2016-05-04 08:35
CarpenterLee 閱讀(1845)
評(píng)論(3) 編輯 收藏