上一篇文章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;
今天的分享到這里,謝謝冠骄!