集合类库（二）：LinkedList

(4) 奇怪的链表随机访问方法——get()

我们都知道，数据结构中的链表是不支持快速随机访问的。如果要查找链表的第n个元素，必须从头开始迭代n-1次。尽管如此，JDK还是给我们提供了一个get()方法，我们可以看看get的源代码:

Java代码　　　

//LinkedList随机访问第index号元素　
public　E　get(int　index)　{　
　　　　return　entry(index).element;　
}　
private　Entry<E>　entry(int　index)　{　
　　　　if　(index　<　0　||　index　>=　size)　
　　　　　　throw　new　IndexOutOfBoundsException("Index:　"+index+",　Size:　"+size);　
　　　　Entry<E>　e　=　header;　
　　　　if　(index　<　(size　>>　1))　{//折半查找，提高效率　
　　　　　　for　(int　i　=　0;　i　<=　index;　i++)　
　　　　　　　　e　=　e.next;　
　　　　}　else　{　
　　　　　　for　(int　i　=　size;　i　>　index;　i--)　
　　　　　　　　e　=　e.previous;　
　　　　}　
　　　　return　e;　
}

注意：由于LinkedList是双重循环链表，其get随机查找方法利用了折半查找 算法(size>>1就是size/2)。 即便如此，虽然一定程度上降低了查找的代价，但是迭代是不可避免的。所以说，当你的LinkedList不得不需要大量使用get方法时（如下面的代码），考虑一下，你可能正在使用一个错误的数据结构来解决问题。

Java代码　　

//效率底下的使用get　
LinkedList<String>　list=new　LinkedList<String>();　
for(int　i=0;i<list.size;i++)　
　　　　System.out.println(list.get(i));