LinkedList實現(xiàn)分析(二)——常用操作

上一篇文章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如下圖所示:


myList.png

然后執(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)入下圖所示:


myList.png

當示例代碼執(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)如下圖所示:


myList.png

然后示例代碼執(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)如下圖所示:


myList.png

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)如下圖所示:


myList.png

然后執(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)如下圖所示:


image.png

然后執(zhí)行 succ.prev = newNode紧卒,是把原來succ指向的前驅(qū)節(jié)點改成了newNode侥衬,因為newNode插入了succ節(jié)點前面,因此succ的prev就是newNode跑芳,指向完的myList狀態(tài)如下:


image.png

然后是判斷pred是否為null,在myList的當前狀態(tài)中轴总, succ.prev是null,pred也就是null博个,所以把first指向newNode怀樟,也就是在myList的頭結(jié)點succ之前添加一個新元素newNode,即 first = newNode;然后對size和modCount加一坡倔,執(zhí)行完最后myList的狀態(tài)如下圖:
image.png

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;

今天的分享到這里,謝謝冠骄!

最后編輯于
?著作權歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末伪煤,一起剝皮案震驚了整個濱河市,隨后出現(xiàn)的幾起案子凛辣,更是在濱河造成了極大的恐慌抱既,老刑警劉巖,帶你破解...
    沈念sama閱讀 218,941評論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件扁誓,死亡現(xiàn)場離奇詭異防泵,居然都是意外死亡蚀之,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,397評論 3 395
  • 文/潘曉璐 我一進店門捷泞,熙熙樓的掌柜王于貴愁眉苦臉地迎上來足删,“玉大人,你說我怎么就攤上這事肚邢∫佳撸” “怎么了?”我有些...
    開封第一講書人閱讀 165,345評論 0 356
  • 文/不壞的土叔 我叫張陵骡湖,是天一觀的道長贱纠。 經(jīng)常有香客問我,道長响蕴,這世上最難降的妖魔是什么谆焊? 我笑而不...
    開封第一講書人閱讀 58,851評論 1 295
  • 正文 為了忘掉前任,我火速辦了婚禮浦夷,結(jié)果婚禮上辖试,老公的妹妹穿的比我還像新娘。我一直安慰自己劈狐,他們只是感情好罐孝,可當我...
    茶點故事閱讀 67,868評論 6 392
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著肥缔,像睡著了一般莲兢。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上续膳,一...
    開封第一講書人閱讀 51,688評論 1 305
  • 那天改艇,我揣著相機與錄音,去河邊找鬼坟岔。 笑死谒兄,一個胖子當著我的面吹牛,可吹牛的內(nèi)容都是我干的社付。 我是一名探鬼主播承疲,決...
    沈念sama閱讀 40,414評論 3 418
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼鸥咖!你這毒婦竟也來了纪隙?” 一聲冷哼從身側(cè)響起,我...
    開封第一講書人閱讀 39,319評論 0 276
  • 序言:老撾萬榮一對情侶失蹤扛或,失蹤者是張志新(化名)和其女友劉穎绵咱,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體,經(jīng)...
    沈念sama閱讀 45,775評論 1 315
  • 正文 獨居荒郊野嶺守林人離奇死亡悲伶,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點故事閱讀 37,945評論 3 336
  • 正文 我和宋清朗相戀三年艾恼,在試婚紗的時候發(fā)現(xiàn)自己被綠了。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片麸锉。...
    茶點故事閱讀 40,096評論 1 350
  • 序言:一個原本活蹦亂跳的男人離奇死亡钠绍,死狀恐怖,靈堂內(nèi)的尸體忽然破棺而出花沉,到底是詐尸還是另有隱情柳爽,我是刑警寧澤,帶...
    沈念sama閱讀 35,789評論 5 346
  • 正文 年R本政府宣布碱屁,位于F島的核電站磷脯,受9級特大地震影響,放射性物質(zhì)發(fā)生泄漏娩脾。R本人自食惡果不足惜赵誓,卻給世界環(huán)境...
    茶點故事閱讀 41,437評論 3 331
  • 文/蒙蒙 一、第九天 我趴在偏房一處隱蔽的房頂上張望柿赊。 院中可真熱鬧俩功,春花似錦、人聲如沸碰声。這莊子的主人今日做“春日...
    開封第一講書人閱讀 31,993評論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽胰挑。三九已至蔓罚,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間洽腺,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,107評論 1 271
  • 我被黑心中介騙來泰國打工覆旱, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留蘸朋,地道東北人。 一個月前我還...
    沈念sama閱讀 48,308評論 3 372
  • 正文 我出身青樓扣唱,卻偏偏與公主長得像藕坯,于是被迫代替她去往敵國和親。 傳聞我的和親對象是個殘疾皇子噪沙,可洞房花燭夜當晚...
    茶點故事閱讀 45,037評論 2 355

推薦閱讀更多精彩內(nèi)容