1. 概述
以雙向鏈表實(shí)現(xiàn)审姓。鏈表無容量限制廷雅，但雙向鏈表本身使用了更多空間奏纪，也需要額外的鏈表指針操作。
按下標(biāo)訪問元素—get(i)/set(i,e) 要悲劇的遍歷鏈表將指針移動到位(如果i>數(shù)組大小的一半盛龄，會從末尾移起)饰迹。
插入芳誓、刪除元素時修改前后節(jié)點(diǎn)的指針即可，但還是要遍歷部分鏈表的指針才能移動到下標(biāo)所指的位置啊鸭，只有在鏈表兩頭的操作—add(), addFirst(),removeLast()或用iterator()上的remove()能省掉指針的移動锹淌。
LinkedList是一個簡單的數(shù)據(jù)結(jié)構(gòu)，與ArrayList不同的是赠制，他是基于鏈表實(shí)現(xiàn)的赂摆。
Doubly-linked list implementation of the List and Deque interfaces. Implements all optional list operations, and permits all elements (including null).
LinkedList<String> list = new LinkedList<String>();
list.add("語文: 1");
list.add("數(shù)學(xué): 2");
list.add("英語: 3");
結(jié)構(gòu)也相對簡單一些，如下圖所示：
- 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;
}
這兩個函數(shù)都調(diào)用了node函數(shù)钟些，該函數(shù)會以O(shè)(n/2)的性能去獲取一個節(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è)計篙耗，將節(jié)點(diǎn)訪問的復(fù)雜度由O(n)變?yōu)镺(n/2)迫筑。
