序
首先LinkedList也是非線程安全的，與ArrayList不同的是內(nèi)部實現(xiàn)方式不同紧索， 所以袁辈，兩者在不同的情況下， 效率也可能不同珠漂。本文參考了（http://www.cnblogs.com/xrq730/p/5005347.html）吵瞻。
LinkedList既然是一種雙向鏈表，必然有一個存儲單元甘磨，看一下LinkedList的基本存儲單元橡羞，它是LinkedList中的一個內(nèi)部類：
private static final class Link<ET> {
ET data; // 真正的數(shù)據(jù)
Link<ET> previous; //前一數(shù)據(jù)的引用地址
Link<ET> next; //后一數(shù)據(jù)的引用地址
Link(ET o, Link<ET> p, Link<ET> n) {
data = o;
previous = p;
next = n;
}
}
LinkedList構(gòu)造函數(shù)。
public LinkedList(Collection<? extends E> collection) {
this();
addAll(collection);
}
public LinkedList() {
voidLink = new Link<E>(null, null, null); // 創(chuàng)建空鏈表頭济舆。卿泽。
voidLink.previous = voidLink;
voidLink.next = voidLink;
}
add數(shù)據(jù)時
@Override
public boolean add(E object) {
return addLastImpl(object);
}
private boolean addLastImpl(E object) {
Link<E> oldLast = voidLink.previous; // 空表頭的前一數(shù)據(jù)地址，其實就是最后一個數(shù)據(jù)的地址滋觉。
Link<E> newLink = new Link<E>(object, oldLast（前）, voidLink（后）); // 新Link的后一個數(shù)據(jù)地址永遠為空表頭的地址签夭。
voidLink.previous = newLink; // 重置空表頭的前一數(shù)據(jù)地址為最后添加的數(shù)據(jù)地址。
oldLast.next = newLink;
size++;
modCount++;
return true;
}
add指定位置數(shù)據(jù)時
@Override
public void add(int location, E object) {
if (location >= 0 && location <= size) {
Link<E> link = voidLink;
if (location < (size / 2)) { // 如果為數(shù)據(jù)List的前半部分椎侠。
for (int i = 0; i <= location; i++) {
link = link.next; //找到第 i 個數(shù)據(jù)的下一個數(shù)據(jù) 第租。
}
} else {
for (int i = size; i > location; i--) {
link = link.previous;
}
}
Link<E> previous = link.previous;
Link<E> newLink = new Link<E>(object, previous, link);
previous.next = newLink;
link.previous = newLink;
size++;
modCount++;
} else {
throw new IndexOutOfBoundsException();
}
}
引用例子(原文 ：http://www.cnblogs.com/xrq730/p/5005347.html)
public static void main(String[] args)
{
1 List<String> list = new LinkedList<String>();
2 list.add("111");
3 list.add("222");
}
假設構(gòu)造函數(shù)里new Link() 的地址為0x0000000，那么它的前后地址都為本身地址我纪。
結(jié)合 add()方法慎宾，相信你可以搞懂它們之間的地址賦值。
其它方法大家可自行分析吧浅悉。
小結(jié)():
切勿用普通for循環(huán)遍歷LinkedList
1趟据、順序插入速度ArrayList會比較快术健，因為ArrayList是基于數(shù)組實現(xiàn)的，數(shù)組是事先new好的咳促，只要往指定位置塞一個數(shù)據(jù)就好了勘伺；LinkedList則不同，每次順序插入的時候LinkedList將new一個對象出來尺迂，如果對象比較大，那么new的時間勢必會長一點蹲盘，再加上一些引用賦值的操作膳音，所以順序插入LinkedList必然慢于ArrayList
2、基于上一點苍凛，因為LinkedList里面不僅維護了待插入的元素兵志，還維護了Entry的前置Entry和后繼Entry想罕，如果一個LinkedList中的Entry非常多，那么LinkedList將比ArrayList更耗費一些內(nèi)存
3惭适、數(shù)據(jù)遍歷的速度楼镐，看最后一部分，這里就不細講了凄杯，結(jié)論是：使用各自遍歷效率最高的方式茅信，ArrayList的遍歷效率會比LinkedList的遍歷效率高一些
4、有些說法認為LinkedList做插入和刪除更快，這種說法其實是不準確的：
（1）LinkedList做插入酌摇、刪除的時候，慢在尋址窑多，快在只需要改變前后Entry的引用地址
（2）ArrayList做插入洼滚、刪除的時候，慢在數(shù)組元素的批量copy千康，快在尋址
所以，如果待插入值桩、刪除的元素是在數(shù)據(jù)結(jié)構(gòu)的前半段尤其是非潮挤兀靠前的位置的時候搭盾，LinkedList的效率將大大快過ArrayList，因為ArrayList將批量copy大量的元素鸯隅；越往后滋迈，對于LinkedList來說，因為它是雙向鏈表幕侠，所以在第2個元素后面插入一個數(shù)據(jù)和在倒數(shù)第2個元素后面插入一個元素在效率上基本沒有差別碍彭，但是ArrayList由于要批量copy的元素越來越少，操作速度必然追上乃至超過LinkedList舞箍。
