復(fù)制一時(shí)爽沪悲，一直復(fù)制一直爽。
github地址：android_interview
雖然從github復(fù)制的，但自己再寫(xiě)一遍能更好的理解和加深記憶尉辑。此文章僅作為個(gè)人學(xué)習(xí)的知識(shí)點(diǎn)小結(jié)，不做任何其他用途较屿。
1隧魄、概括
與ArrayList不同的是，LinkedList是基于鏈表實(shí)現(xiàn)的隘蝎，并且是以雙向鏈表實(shí)現(xiàn)的购啄。鏈表無(wú)容量限制，但雙向鏈表本身使用了更多空間嘱么，也需要額外的鏈表指針操作狮含。
按下標(biāo)訪問(wèn)元素—get(i)/set(i,e) 要悲劇的遍歷鏈表將指針移動(dòng)到位（如果i>數(shù)組大小的一半，會(huì)從末尾移起曼振，否則從頭開(kāi)始移動(dòng)）几迄。
插入、刪除元素時(shí)修改前后節(jié)點(diǎn)的指針即可冰评，但還是要遍歷部分鏈表的指針才能移動(dòng)到下標(biāo)所指的位置映胁，只有在鏈表兩頭的操作—add()，addFirst()集索，removeLast()或用iterator()上的remove()能省掉指針的移動(dòng)嘱丢。
2敲才、set和get函數(shù)
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
這兩個(gè)函數(shù)都調(diào)用了 node 函數(shù)承粤，該函數(shù)會(huì)以O(shè)(n/2)的性能去獲取一個(gè)節(jié)點(diǎn)，具體
實(shí)現(xiàn)如下所示：
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是在前半?yún)^(qū)間還是后半?yún)^(qū)間穷遂，如果在前半?yún)^(qū)間就從head搜索，而在
后半?yún)^(qū)間就從tail搜索娱据。而不是一直從頭到尾的搜索蚪黑。如此設(shè)計(jì)，將節(jié)點(diǎn)訪問(wèn)的復(fù)雜
度由O(n)變?yōu)镺(n/2)中剩。
