上一篇文章LinkedList實現(xiàn)分析（一）介紹了LinkedList中的一些重要屬性和構造方法，下面我們將詳細介紹一下LinkedList提高的常用方法的實現(xiàn)原理
元素添加
add(E e)方法
往LinkedList添加元素，LinkedList提供了多重方式程储，首先介紹add方法登疗，下面我們使用一個簡單的實例代碼來分析一下add方法的實現(xiàn)原理：
List<String> myList = new LinkedList();//1
myList.add("a"); //2
myList.add("b"); //3
myList.add("c"); //4
執(zhí)行第一行代碼后創(chuàng)建了一個空的myList對象，此時myList如下圖所示：
然后執(zhí)行第2行代碼myList.add("a")娱节，把字符串"a"添加到myList中挠蛉，通過debug方式進入add方法內(nèi)部：
public boolean add(E e) {
linkLast(e);
return true;
}
add又調(diào)用linkLast方法，linkLast方法實現(xiàn)如下：
void linkLast(E e) {
final Node<E> l = last;
final Node<E> newNode = new Node<>(l, e, null);
last = newNode;
if (l == null)
first = newNode;
else
l.next = newNode;
size++;
modCount++;
}
在linkLast內(nèi)部肄满，此時e="a"谴古。首先把last，此時myList是新創(chuàng)建的對象稠歉，last=null掰担，賦值給一個臨時變量 l，這里的做法是用來保存last的值怒炸，然后用元素e創(chuàng)建一個新的Node對象带饱，這里是往myList的尾部添加元素，因此創(chuàng)建的Node節(jié)點的構造方法最后一個參數(shù)是null横媚，而第一個參數(shù)表示的是插入元素e的前一個元素指針纠炮，因此需要傳入l，因為在整個LinkedList中l(wèi)ast屬性表示的最后一個元素灯蝴。當創(chuàng)建好包含e的newNode節(jié)點的時候恢口，此時newNode就應該是myList的最后一個節(jié)點，也是第一個節(jié)點（l==null）穷躁，因此把newNode賦值給last和first耕肩，然后把表示myList大學的size進行加一因妇，最后對modCount加一，記錄了修改次數(shù)猿诸。執(zhí)行完第2行代碼后婚被，myList的狀態(tài)入下圖所示:
當示例代碼執(zhí)行第3行代碼的時,同樣會執(zhí)行l(wèi)inkLast，此時e=“b”梳虽。在進入linkLast方法的時候址芯，last的值已經(jīng)不在是null，而是剛剛創(chuàng)建的包含了“a”的Node節(jié)點對象窜觉，同樣把last先用一個臨時變量l保存起來谷炸，然后創(chuàng)建一個包含“b”的Node節(jié)點，這個時候該node節(jié)點的前一個節(jié)點是“a”所在的節(jié)點禀挫，因此構造函數(shù) new Node<>(l, e, null)旬陡，把新創(chuàng)建的newNode作為整個myList的最后一個節(jié)點： last = newNode，而由于l不為null语婴，也就是last不為null描孟，所以需要把新創(chuàng)建的節(jié)點放到myList中最后一個節(jié)點的后面： l.next = newNode，最后修改size和modCount的值砰左，完成“b”元素的添加匿醒。此時myList的狀態(tài)如下圖所示：
然后示例代碼執(zhí)行到第4行，此時myList已經(jīng)有2個node菜职，根據(jù)上圖可知last指向了“b”node青抛，然創(chuàng)建“c”的node對象，讓“c”的prev執(zhí)行“b”酬核，然后myList中的last指向“c”蜜另，“b”的next執(zhí)行“c”，執(zhí)行完后myList的狀態(tài)如下圖所示:
add(int index, E element)
該方法是在指定的索引的位置插入一個元素嫡意，index值指定的索引位置举瑰，element是需要插入的元素信息。這里還是以一個示例為基礎進行對 add(int index, E element) 源碼的分析蔬螟，示例代碼如下：
List<String> myList = new LinkedList();//1
myList.add("a"); //2
myList.add(0,"b")//3
當示例代碼執(zhí)行完第2部的時候此迅，myList的狀態(tài)如下圖所示：
然后執(zhí)行第3行代碼，具體 add(int index, E element) 的源碼如下：
public void add(int index, E element) {
checkPositionIndex(index);//index校驗
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
首先是對傳入的index進行位置校驗旧巾，具體實現(xiàn)是要求index不能小于0耸序，不能大于myList當前的大小。根據(jù)示例代碼鲁猩，執(zhí)行到第3行的時候坎怪，此時size=1，index=0廓握，因此程序執(zhí)行l(wèi)inkBefore方法搅窿，linkBefore是第一參數(shù)是新添加的元素element嘁酿，第二個參數(shù)表示element需要被添加到myList中哪個元素的后面。這里傳入是位置索引男应，因此需要調(diào)用node(index)方法找到mylist中index對應的node對象闹司，node方法實現(xiàn)如下：
Node<E> node(int 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與整個list的大小(size)的1/2進行比較沐飘，如果index<size/2游桩，那么對myList進行正序遍歷，如果index>=size/2耐朴，那么對myList進行倒序遍歷众弓。這里需要大家注意的是源碼中使用<font color=red>右移操作獲取size的1/2</font>，這個技巧希望大家可以掌握：
在java中隔箍，數(shù)字左移表示乘2，數(shù)字右移除2
由于當前myList的size=1脚乡，右移之后是0蜒滩，index=0，因此執(zhí)行else的語句奶稠，從last指向的node開始倒序遍歷俯艰，此時myList只有一個index=0所指向的元素就是last的值，因此把last返回锌订。node方法執(zhí)行完之后竹握，開始執(zhí)行l(wèi)inkBefore方法：
void linkBefore(E e, Node<E> succ) {
final Node<E> pred = succ.prev;
final Node<E> newNode = new Node<>(pred, e, succ);
succ.prev = newNode;
if (pred == null)
first = newNode;
else
pred.next = newNode;
size++;
modCount++;
}
linkBefore方法就是一個雙向列表的插入操作，首先把succ的前驅(qū)節(jié)點prev保存到臨時變量pred辆飘，使用傳入的e（根據(jù)示例代碼啦辐，此時e=“b”）創(chuàng)建一個新的Node對象：newNode，由于是在succ節(jié)點的前面插入新元素"b"蜈项，因此newNode的前驅(qū)點是之前succ節(jié)點的前驅(qū)節(jié)點芹关，newNode的后節(jié)點就是succ節(jié)點本身：final Node<E> newNode = new Node<>(pred, e, succ)，此時myList的狀態(tài)如下圖所示：
然后執(zhí)行 succ.prev = newNode紧卒，是把原來succ指向的前驅(qū)節(jié)點改成了newNode侥衬，因為newNode插入了succ節(jié)點前面，因此succ的prev就是newNode跑芳，指向完的myList狀態(tài)如下：
然后是判斷pred是否為null,在myList的當前狀態(tài)中轴总， succ.prev是null，pred也就是null博个，所以把first指向newNode怀樟，也就是在myList的頭結(jié)點succ之前添加一個新元素newNode，即 first = newNode;然后對size和modCount加一坡倔，執(zhí)行完最后myList的狀態(tài)如下圖:
addAll(Collection<? extends E> c)
下面介紹一下使用集合對象給LinkedList添加元素漂佩，addAll有兩個重載方法：
public boolean addAll(Collection<? extends E> c)
public boolean addAll(int index, Collection<? extends E> c)
在源碼中脖含，addAll(Collection<? extends E> c)實際是調(diào)用了addAll(int index, Collection<? extends E> c) :
public boolean addAll(Collection<? extends E> c) {
return addAll(size, c);
}
因此這里只介紹后面一個addAll的實現(xiàn):
public boolean addAll(int index, Collection<? extends E> c) {
checkPositionIndex(index);
Object[] a = c.toArray();
int numNew = a.length;
if (numNew == 0)
return false;
//下面的代碼是查詢需要插入位置的前驅(qū)和后繼節(jié)點
Node<E> pred, succ;
if (index == size) {
succ = null;
pred = last;
} else {
succ = node(index);
pred = succ.prev;
}
//把a中的元素創(chuàng)建為一個列表
//并且讓pred指向a的最后一個節(jié)點
for (Object o : a) {
Node<E> newNode = new Node<>(pred, e, null);
if (pred == null)
first = newNode;
else
pred.next = newNode;
pred = newNode;
}
//如果沒有后繼節(jié)點，那么c集合中最后一個節(jié)點就是
//整個list的最后節(jié)點
if (succ == null) {
last = pred;
} else {
//如果在list找到插入的前驅(qū)和后繼節(jié)點
//把c中的最后一個節(jié)點的后繼節(jié)點指向succ
//把后繼節(jié)點的前驅(qū)節(jié)點指向c中的最后一個節(jié)點
pred.next = succ;
succ.prev = pred;
}
size += numNew;
modCount++;
return true;
}
addAll方法內(nèi)部投蝉，首先還是判斷index的值是否合法养葵，然后對傳入的Collection對象c進行驗證， 接著在源碼中定義了兩個變量：
Node<E> pred, succ;
pred表示需要插入c的前驅(qū)節(jié)點瘩缆，succ表示c的后繼節(jié)點关拒。當index=size表示是把c添加到LinkedList的尾部，因此執(zhí)行succ=null和pred=last;否則調(diào)用 node(index)方法庸娱，找到后繼節(jié)點succ着绊，然后把當前后繼節(jié)點的前驅(qū)節(jié)點賦值給pred。
找到所插入前驅(qū)和后繼節(jié)點之后熟尉，開始循環(huán)遍歷c归露，把c中的每一個元素創(chuàng)建一個Node對象，c中的前一個元素都是后一個元素的前驅(qū)節(jié)點斤儿，把c建立為一個鏈表剧包。然后把c的鏈表插入的LinkedList中，具體見上面源碼的注釋往果，完成鏈表的連接操作只會疆液，對size和modCount進行加1操作。
其他添加元素的方法
下面介紹一個往list頭插入元素的方法：
public void addFirst(E e) {
linkFirst(e);
}
private void linkFirst(E e) {
//保存第一個元素
final Node<E> f = first;
//頭插法陕贮，因此newNode的前驅(qū)節(jié)點是null堕油，后繼節(jié)點是f
final Node<E> newNode = new Node<>(null, e, f);
//讓新創(chuàng)建節(jié)點當整個list的頭節(jié)點
first = newNode;
if (f == null)
//如果f=null，表示當前l(fā)ist沒有一個元素肮之，因此需要給last=newNode
last = newNode;
else
//把之前的first接的前驅(qū)節(jié)點換成新創(chuàng)建的newNode
f.prev = newNode;
size++;
modCount++;
}
頭插入的原理就是在整個list中掉缺，找到一個元素first，把first的前驅(qū)節(jié)點換成新插入的元素戈擒，然后把新傳入元素的后繼節(jié)點指向之前的頭節(jié)點攀圈，具體實現(xiàn)見上面源碼和注釋
LinkedList提供了offer(E e)，offerFirst(E e)峦甩， offerLast(E e)赘来，addFirst(E e) ，addLast(E e)凯傲，push(E e) 往list中添加一個元素的方法犬辰，這些方法的底層都是基于上面介紹的原理實現(xiàn)的：頭插和尾插。這里就不多做說明冰单。
獲取元素
LinkedList獲取元素提供多種方法：
//根據(jù)索引獲取元素
public E get(int index)
//獲取頭元素
public E peek()
//獲取頭元素幌缝，并且把頭元素從list中刪除
public E poll()
//獲取頭元素，并且把頭元素從list中刪除
public E pop()
下面追個介紹這些方法的具體實現(xiàn)：
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
由上面源碼可知诫欠，get操作底層是調(diào)用的node方法涵卵，node方法參考上面的介紹浴栽。
下面是peek，peek操作是獲取頭元素轿偎，因此只需要獲取到LinkedList的first所執(zhí)行的元素就可以了典鸡。
public E peek() {
final Node<E> f = first;
return (f == null) ? null : f.item;
}
下面介紹poll():
public E poll() {
final Node<E> f = first;
return (f == null) ? null : unlinkFirst(f);
}
private E unlinkFirst(Node<E> f) {
//保存f的具體值
final E element = f.item;
final Node<E> next = f.next;
f.item = null;
f.next = null; // help GC
//f的后繼節(jié)點賦值給LinkedList的first
first = next;
//next==null表示要刪除的節(jié)點是list的最后一個節(jié)點
if (next == null)
last = null;
else
//表示刪除f之后的list列表中，頭結(jié)點的prev應該為null坏晦，而之前
//prev是執(zhí)行f的
next.prev = null;
size--;
modCount++;
return element;
}
由上面源碼可知萝玷，當調(diào)用poll的時候，會把LinkedList的頭元素返回昆婿，然后把頭元素從LinkedList中刪除球碉。
下面看一下pop方法：
public E removeFirst() {
final Node<E> f = first;
if (f == null)
throw new NoSuchElementException();
return unlinkFirst(f);
}
pop方法的底層也是調(diào)用unlinkFirst方法完成頭結(jié)點的刪除操作。
To Array的操作
LinkedList提供了兩種方法完成list到數(shù)組的轉(zhuǎn)換：
public Object[] toArray()
public <T> T[] toArray(T[] a)
第一個方法仓蛆，是把list轉(zhuǎn)為Object類型的數(shù)組睁冬，具體是實現(xiàn)如下：
public Object[] toArray() {
Object[] result = new Object[size];
int i = 0;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
return result;
}
該方法的實現(xiàn)原理比較簡單，首先創(chuàng)建一個大小與list相同的object類型數(shù)組看疙，然后從頭到尾遍歷list的元素痴突，把每個元素放到創(chuàng)建的數(shù)組中，因為數(shù)組對象是Object類型狼荞，因此list中的任何元素都可以直接放入到數(shù)組中，最后把數(shù)組返回帮碰。
在T[] toArray(T[] a) 方法中相味，需要傳遞一個T類型的數(shù)組對象，這樣可以按照T類型返回T類型數(shù)組：
public <T> T[] toArray(T[] a) {
if (a.length < size)
a = (T[])java.lang.reflect.Array.newInstance(
a.getClass().getComponentType(), size);
int i = 0;
Object[] result = a;
for (Node<E> x = first; x != null; x = x.next)
result[i++] = x.item;
if (a.length > size)
a[size] = null;
return a;
}
首先是判斷傳入的數(shù)組a的大小是否大于或者等于list的大小殉挽，如果小于丰涉，那么利用反射機制重新創(chuàng)建一個數(shù)組，此時參數(shù)a和toArray的數(shù)組就不是同一個數(shù)組了斯碌，如果a的大小大于size的值一死，假設數(shù)組a={"1","2","3","4"},LinkedList的值是:{"a","b"}，那么調(diào)用toArray方法之后傻唾，a的值變?yōu)椋簕"a","b",null,"4"}投慈。"3"變?yōu)閚ull是因為
if (a.length > size)
a[size] = null;
今天的分享到這里，謝謝冠骄！
