數(shù)據(jù)結(jié)構(gòu)——鏈表

正文

1缨该、屬性

①：相鄰元素之間通過指針連接。
②：最后一個(gè)元素的后繼指針為NULL茄蚯。
③：鏈表的空間能夠按需分配压彭。
④：沒有內(nèi)存空間的浪費(fèi)。

圖1-1 鏈表示意圖

2渗常、鏈表和數(shù)組的區(qū)別

鏈表和數(shù)組都可以用于存儲(chǔ)數(shù)據(jù)集合壮不，由于兩者的用途相同，所以需要對(duì)它們的用法進(jìn)行區(qū)分皱碘。

2.1询一、數(shù)組概述

整個(gè)數(shù)組所有元素存儲(chǔ)在操作系統(tǒng)分配的一個(gè)內(nèi)存塊中，通過使用特定元素的索引作為數(shù)組下標(biāo)癌椿，可以在常數(shù)時(shí)間內(nèi)訪問數(shù)組元素健蕊。

圖2-1 數(shù)組示意圖

2.2、數(shù)組和鏈表優(yōu)缺點(diǎn)

數(shù)組的優(yōu)點(diǎn)：
1踢俄、簡單且易用缩功。
2、訪問元素為常數(shù)時(shí)間都办。
數(shù)組的缺點(diǎn)：
1嫡锌、大小固定，在使用數(shù)組前需要指定數(shù)組大小琳钉。
2势木、需要分配一個(gè)連續(xù)空間塊，當(dāng)數(shù)組規(guī)模過大時(shí)歌懒，就無法分配存儲(chǔ)整個(gè)數(shù)組的內(nèi)存空間啦桌。
3、如果要在數(shù)組中插入元素及皂，可能需要移動(dòng)存儲(chǔ)在數(shù)組中的其他元素甫男，這樣才能騰出指定的位置來放插入的元素且改。
鏈表的優(yōu)點(diǎn)：
1、鏈表可以在常數(shù)時(shí)間內(nèi)擴(kuò)展查剖。
2钾虐、容易添加新元素。
鏈表的缺點(diǎn)：
1笋庄、訪問單個(gè)元素的時(shí)間開銷問題過大。
2倔监、有時(shí)很難對(duì)鏈表操作直砂，如果要?jiǎng)h除最后一項(xiàng)，倒數(shù)第二項(xiàng)必須更改后繼指針為NULL浩习。這需要從頭遍歷鏈表静暂，找到倒數(shù)第二個(gè)結(jié)點(diǎn)的鏈接，并設(shè)置其后置指針為NULL谱秽。
3洽蛀、鏈表中的額外指針引用需要浪費(fèi)內(nèi)存。

2.3疟赊、鏈表和數(shù)組的比較

參數(shù)	鏈表	數(shù)組
索引	O(n)	O(1)
在最前端插入/刪除	O(1)	O(n)郊供，如果數(shù)組空間沒有填滿(需要移動(dòng)元素)
在最末端插入	O(n)	O(1)，如果數(shù)組空間沒有填滿
在最末端刪除	O(n)	O(1)
在中間插入	O(n)	O(n)近哟，如果數(shù)組空間沒有填滿(需要移動(dòng)元素)
在中間刪除	O(n)	O(n) 驮审，如果數(shù)組空間沒有填滿(需要移動(dòng)元素)
空間浪費(fèi)	O(n)	0

3、單向鏈表

鏈表通常是指單向鏈表吉执，它包含多個(gè)結(jié)點(diǎn)疯淫，每個(gè)結(jié)點(diǎn)都有一個(gè)指向后繼元素的next（下一個(gè)）指針。表中最后一個(gè)結(jié)點(diǎn)的next值為NULL戳玫，表示鏈表的結(jié)束熙掺。

圖3-1 單向鏈表

下面是單向鏈表的類型聲明：

public class ListNode {
    private int data;
    private ListNode next;

    public ListNode(int data){
        this.data=data;
    }

    public void setData(int data){
        this.data=data;
    }

    public int getData(){
        return data;
    }

    public void setNext(ListNode next){
        this.next=next;
    }

    public ListNode getNext() {
        return next;
    }
}

3.1、單向鏈表的基本操作

遍歷鏈表咕宿。
在鏈表中插入一個(gè)元素币绩。
從鏈表中刪除一個(gè)元素。
刪除鏈表荠列。

3.1.1类浪、鏈表的遍歷

假設(shè)表頭結(jié)點(diǎn)的指針指向鏈表中的第一個(gè)結(jié)點(diǎn)。遍歷鏈表需要完成以下步驟：

沿指針遍歷肌似。
遍歷時(shí)顯示結(jié)點(diǎn)的內(nèi)容费就。
當(dāng)next指針為NULL時(shí)結(jié)束遍歷。

下面是遍歷函數(shù)的聲明：

    public int ListLength(ListNode headNode){
        int length=0;
        ListNode currentNode=headNode;
        while (currentNode!=null){
            length++;
            System.out.print(currentNode.getData());
            currentNode=currentNode.getNext();
        }
        return length;
    }

3.1.2川队、鏈表的插入

3.1.2.1力细、在單向鏈表的開頭插入結(jié)點(diǎn)

若要在當(dāng)前表頭結(jié)點(diǎn)前插入一個(gè)新結(jié)點(diǎn)睬澡，只需要修改一個(gè)next指針（新結(jié)點(diǎn)的next指針），如下步驟：

更新新結(jié)點(diǎn)的next指針眠蚂，使其指向當(dāng)前的表頭結(jié)點(diǎn)煞聪。

圖3-2 更新新結(jié)點(diǎn)
更新表頭指針的值，使其指向新結(jié)點(diǎn)逝慧。

圖3-3 更新表頭指針

3.1.2.2昔脯、在單向鏈表的結(jié)尾插入結(jié)點(diǎn)

若要在表尾后插入一個(gè)新結(jié)點(diǎn)，則需要修改兩個(gè)next指針（最后一個(gè)結(jié)點(diǎn)的next指針和新結(jié)點(diǎn)的next指針）笛臣，如下步驟：

新結(jié)點(diǎn)的next指針指向NULL云稚。

圖3-4 更新新結(jié)點(diǎn)
最后一個(gè)結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)。

圖3-5 更新表尾結(jié)點(diǎn)

3.1.2.3沈堡、在單向鏈表的中間插入結(jié)點(diǎn)

假設(shè)在這種情況下插入新結(jié)點(diǎn)静陈，則需要修改兩個(gè)next指針，如下步驟：

如果要在位置3增加一個(gè)元素诞丽，則首先要將指針定位在鏈表的位置2鲸拥。即需要從表頭開始經(jīng)過兩個(gè)結(jié)點(diǎn)，然后插入新結(jié)點(diǎn)僧免。為了簡單起見刑赶，假設(shè)第二個(gè)結(jié)點(diǎn)為位置結(jié)點(diǎn)，新結(jié)點(diǎn)的next指針指向位置結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)猬膨。

圖3-6 更新新結(jié)點(diǎn)
位置結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)角撞。

圖3-7 更新位置結(jié)點(diǎn)

3.1.2.4、函數(shù)實(shí)現(xiàn)

    ListNode InsertInLinkedList(ListNode headNode,ListNode nodeToInsert,int position){
        if(headNode==null){
            return headNode;
        }
        //求鏈表長度
        int size=ListLength(headNode);
        if(position>size+1||position<1){
            System.out.print("position 的范圍在1-(size+1)");
            return headNode;
        }
        if(position==1){
            //在鏈表開頭插入
            nodeToInsert.setNext(headNode);
            return nodeToInsert;
        }
        else {
            //在鏈表中間或者末尾插入
            //位置結(jié)點(diǎn)
            ListNode previousNode=headNode;
            int count=1;
            while (count<position-1){
                previousNode=headNode.getNext();
                count++;
            }
            //位置結(jié)點(diǎn)的下一結(jié)點(diǎn)
            ListNode currentNode=previousNode.getNext();
            //更新新結(jié)點(diǎn)
            nodeToInsert.setNext(currentNode);
            //更新位置結(jié)點(diǎn)
            previousNode.setNext(nodeToInsert);
        }
        return headNode;
    }

3.1.3勃痴、鏈表的刪除

3.1.3.1谒所、刪除鏈表的表頭

創(chuàng)建一個(gè)臨時(shí)結(jié)點(diǎn)，它指向表頭指針?biāo)赶虻慕Y(jié)點(diǎn)沛申。

圖3-8 創(chuàng)建臨時(shí)結(jié)點(diǎn)
修改表頭指針的值劣领，使其指向下一個(gè)結(jié)點(diǎn)，并移除臨時(shí)結(jié)點(diǎn)铁材。

圖3-9 修改表頭并移除臨時(shí)結(jié)點(diǎn)

3.1.3.2尖淘、刪除鏈表的表尾

該操作比刪除鏈表的第一個(gè)結(jié)點(diǎn)要稍微復(fù)雜一些，因?yàn)樗惴ㄐ枰业奖砦步Y(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)著觉。分三步實(shí)現(xiàn)：

遍歷鏈表村生，在遍歷時(shí)還要保存前驅(qū)結(jié)點(diǎn)的地址，當(dāng)遍歷到鏈表的表尾時(shí)饼丘，將有兩個(gè)指針趁桃，分別是表尾結(jié)點(diǎn)的指針和指向表尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針。

圖3-10 表尾及前驅(qū)結(jié)點(diǎn)
將表尾的前驅(qū)結(jié)點(diǎn)的next指針更新為NULL。

圖3-11 更新前驅(qū)結(jié)點(diǎn)
移除表尾結(jié)點(diǎn)

圖3-12 移除表尾

3.1.3.3卫病、刪除鏈表中間的結(jié)點(diǎn)

這種情況下油啤，被刪除的結(jié)點(diǎn)總是位于兩個(gè)結(jié)點(diǎn)之間，因此不需要更新表頭和表尾的指針蟀苛。分兩步實(shí)現(xiàn)：

遍歷鏈表益咬，在遍歷時(shí)保存前驅(qū)結(jié)點(diǎn)的地址，一旦找到被刪除的結(jié)點(diǎn)帜平，將前驅(qū)結(jié)點(diǎn)的next指針的值更新為被刪除的結(jié)點(diǎn)的next指針的值幽告。

圖3-13 更新前驅(qū)結(jié)點(diǎn)
移除需刪除的當(dāng)前結(jié)點(diǎn)

圖3-14 移除結(jié)點(diǎn)

3.1.3.4、函數(shù)實(shí)現(xiàn)

ListNode DeleteNodeFromLinkedList(ListNode headNode,int position){
        //求鏈表長度
        int size=ListLength(headNode);
        if(position>size||position<1){
            System.out.print("position 的范圍在1-size");
            return headNode;
        }
        if(position==1){
            //刪除表頭
            ListNode currentNode=headNode.getNext();
            headNode=null;
            return currentNode;
        }else {
            //刪除中間或表尾
            //前驅(qū)結(jié)點(diǎn)
            ListNode previousNode=headNode;
            int count=1;
            while(count<position-1){
                previousNode=previousNode.getNext();
                count++;
            }
            //要?jiǎng)h除的結(jié)點(diǎn)
            ListNode currentNode=previousNode.getNext();
            //更新前驅(qū)結(jié)點(diǎn)
            previousNode.setNext(currentNode.getNext());
            //刪除當(dāng)前結(jié)點(diǎn)
            currentNode=null;
        }
        return headNode;
    }

3.1.4裆甩、鏈表的釋放

這個(gè)操作通過將當(dāng)前結(jié)點(diǎn)存儲(chǔ)在臨時(shí)變量中评腺，然后釋放當(dāng)前結(jié)點(diǎn)。當(dāng)釋放完當(dāng)前結(jié)點(diǎn)后淑掌，移動(dòng)到下一個(gè)結(jié)點(diǎn)并將其存儲(chǔ)在臨時(shí)變量中，然后不斷重復(fù)該過程直至釋放所有結(jié)點(diǎn)蝶念。代碼如下：

    void DeleteLinkedList(ListNode headNode){
        //臨時(shí)變量 和 迭代器
        ListNode tempNode,iterator=headNode;
        while (iterator!=null){
            tempNode=iterator.getNext();
            iterator=null;
            iterator=tempNode;
        }
    }

4抛腕、雙向鏈表

雙向鏈表的優(yōu)點(diǎn)：對(duì)于鏈表中一個(gè)給定的結(jié)點(diǎn)，可以從兩個(gè)方向進(jìn)行操作媒殉。
雙向鏈表的缺點(diǎn)：每個(gè)結(jié)點(diǎn)需要一個(gè)額外的指針担敌，因此需要更多的開銷，插入和刪除時(shí)更費(fèi)時(shí)廷蓉。

下面給出雙向鏈表的類型聲明：

public class DLLNode {
    private int data;
    private  DLLNode previous;
    private  DLLNode next;

    public DLLNode(int data){
        this.data=data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setPrevious(DLLNode previous) {
        this.previous = previous;
    }

    public DLLNode getPrevious() {
        return previous;
    }

    public void setNext(DLLNode next) {
        this.next = next;
    }

    public DLLNode getNext() {
        return next;
    }
}

4.1全封、雙向鏈表的插入

分為以下三種情況：

在鏈表的開頭前插入一個(gè)新結(jié)點(diǎn)。
在鏈表的末尾后插入一個(gè)新結(jié)點(diǎn)桃犬。
在鏈表的中間插入一個(gè)新結(jié)點(diǎn)刹悴。

4.1.1、在雙向鏈表的開頭插入結(jié)點(diǎn)

將新結(jié)點(diǎn)的后繼指針更新為指向當(dāng)前的表頭結(jié)點(diǎn)攒暇，將前驅(qū)指針賦值為NULL土匀。

圖4-1 更新新結(jié)點(diǎn)
將表頭結(jié)點(diǎn)的前驅(qū)指針更新為指向新結(jié)點(diǎn)，然后將新結(jié)點(diǎn)作為表頭形用。

圖4-2 更新表頭

4.1.2就轧、在雙向鏈表的末尾插入結(jié)點(diǎn)

這種情況下需要遍歷到鏈表的最后，然后插入新結(jié)點(diǎn)田度。

將新結(jié)點(diǎn)的后繼指針賦值為NULL妒御，前驅(qū)指針指向表尾結(jié)點(diǎn)。

圖4-3 更新新結(jié)點(diǎn)
將表尾結(jié)點(diǎn)的后繼指針更新為指向新結(jié)點(diǎn)镇饺。

圖4-4 更新表尾結(jié)點(diǎn)

4.1.3乎莉、在雙向鏈表的中間插入一個(gè)結(jié)點(diǎn)

將新結(jié)點(diǎn)的后繼指針賦值為位置結(jié)點(diǎn)的后繼結(jié)點(diǎn)，前驅(qū)指針指向位置結(jié)點(diǎn)。

圖4-5 更新新結(jié)點(diǎn)
將位置結(jié)點(diǎn)的后繼結(jié)點(diǎn)的前驅(qū)指針賦值為新結(jié)點(diǎn)梦鉴，將位置結(jié)點(diǎn)的后繼指針賦值為新結(jié)點(diǎn)李茫。

圖4-6 更新位置結(jié)點(diǎn)、后繼結(jié)點(diǎn)

4.1.4肥橙、函數(shù)實(shí)現(xiàn)

public DLLNode DLLInsert(DLLNode headNode,DLLNode nodeToInsert,int position){
        if(headNode==null){
            return nodeToInsert;
        }
        //求鏈表長度
        int size=ListLength(headNode);
        if(position<1||position>size+1){
            System.out.print("position 的范圍在1-(size+1)");
            return headNode;
        }
        if(position==1){
            //在鏈表開頭插入
            nodeToInsert.setNext(headNode);
            headNode.setPrevious(nodeToInsert);
            return nodeToInsert;
        }else {
            //在鏈表中間或者表尾插入
            //位置結(jié)點(diǎn)
            DLLNode previousNode=headNode;
            int count=1;
            while (count<position-1){
                previousNode=previousNode.getNext();
                count++;
            }
            //位置結(jié)點(diǎn)的后繼結(jié)點(diǎn)
            DLLNode currentNode=previousNode.getNext();
            //更新新結(jié)點(diǎn)
            nodeToInsert.setNext(currentNode);
            nodeToInsert.setPrevious(previousNode);
            //更新位置結(jié)點(diǎn)
            previousNode.setNext(nodeToInsert);
            //更新位置結(jié)點(diǎn)的后繼結(jié)點(diǎn)
            if(currentNode!=null){
                currentNode.setPrevious(nodeToInsert);
            }
        }
        return headNode;
    }

4.2魄宏、雙向鏈表的刪除

分為以下三種情況：

刪除鏈表的表頭。
刪除鏈表的表尾存筏。
刪除鏈表中間的一個(gè)結(jié)點(diǎn)宠互。

4.2.1、刪除雙向鏈表的第一個(gè)結(jié)點(diǎn)

創(chuàng)建一個(gè)臨時(shí)結(jié)點(diǎn)椭坚，它與表頭指向同一個(gè)結(jié)點(diǎn)予跌。

圖4-7 臨時(shí)結(jié)點(diǎn)
修改表頭指針，使其指向下一個(gè)結(jié)點(diǎn)善茎，將表頭指針的前驅(qū)指針賦值為NULL券册，然后移除臨時(shí)結(jié)點(diǎn)。

圖4-8 更新表頭垂涯、移除臨時(shí)結(jié)點(diǎn)

4.2.2烁焙、刪除雙向鏈表的最后一個(gè)結(jié)點(diǎn)

需要找到表尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，分以下三步進(jìn)行：

遍歷鏈表耕赘，同時(shí)保存前驅(qū)結(jié)點(diǎn)的地址骄蝇。當(dāng)遍歷到表尾時(shí)，有兩個(gè)指針分別是指向表尾結(jié)點(diǎn)的指針和指向表尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的指針操骡。

圖4-9 表尾結(jié)點(diǎn)九火、表尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
更新表尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的后繼指針的值為NULL。

圖4-10 更新表尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
移除表尾結(jié)點(diǎn)册招。

圖4-11 移除表尾結(jié)點(diǎn)

4.2.3岔激、刪除雙向鏈表中間的一個(gè)結(jié)點(diǎn)

與一種刪除情況類似，在遍歷鏈表時(shí)保存前驅(qū)結(jié)點(diǎn)跨细。一旦找到要?jiǎng)h除的結(jié)點(diǎn)鹦倚，更改前驅(qū)結(jié)點(diǎn)的后繼指針使其指向被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)，更改被刪除結(jié)點(diǎn)的后繼結(jié)點(diǎn)的前驅(qū)指針指向被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)冀惭。

圖4-12 更新刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)
移除被刪除的當(dāng)前結(jié)點(diǎn)震叙。

圖4-13 刪除結(jié)點(diǎn)

4.2.4、代碼實(shí)現(xiàn)

public DLLNode DLLDelete(DLLNode headNode,int position){
        int size=ListLength(headNode);
        if(position<1||position>size){
            System.out.print("position 的范圍在1-size");
            return headNode;
        }
        if(position==1){
            //刪除鏈表的第一個(gè)結(jié)點(diǎn)
            DLLNode currentNode=headNode.getNext();
            currentNode.setPrevious(null);
            headNode=null;
            return currentNode;
        }else {
            //刪除鏈表的中間結(jié)點(diǎn)或者最后一個(gè)結(jié)點(diǎn)
            //前驅(qū)結(jié)點(diǎn)
            DLLNode previousNode=headNode;
            int count=1;
            while(count<position-1){
                previousNode=previousNode.getNext();
                count++;
            }
            //刪除結(jié)點(diǎn)
            DLLNode currentNode=previousNode.getNext();
            //后繼結(jié)點(diǎn)
            DLLNode laterNode=currentNode.getNext();
            //更新前驅(qū)結(jié)點(diǎn)
            previousNode.setNext(laterNode);
            //更新后繼結(jié)點(diǎn)
            if(laterNode!=null){
                laterNode.setPrevious(previousNode);
            }
            currentNode=null;
        }
        return headNode;
    }

5散休、循環(huán)鏈表

在單向鏈表和雙向鏈表中媒楼，都采用NULL值作為鏈表的結(jié)束。然而循環(huán)鏈表沒有結(jié)束標(biāo)志戚丸。下面給出循環(huán)鏈表的類型聲明：

public class CLLNode {
    private int data;
    private CLLNode next;
    public CLLNode(int data){
        this.data=data;
    }

    public void setData(int data) {
        this.data = data;
    }

    public int getData() {
        return data;
    }

    public void setNext(CLLNode next) {
        this.next = next;
    }

    public CLLNode getNext() {
        return next;
    }
}

5.1划址、遍歷循環(huán)鏈表

循環(huán)鏈表可以通過標(biāo)記為表頭的結(jié)點(diǎn)進(jìn)行訪問扔嵌，從標(biāo)記為表頭的結(jié)點(diǎn)開始遍歷，利用虛擬結(jié)點(diǎn)——當(dāng)前結(jié)點(diǎn)夺颤，當(dāng)當(dāng)前結(jié)點(diǎn)再次達(dá)到開始結(jié)點(diǎn)時(shí)結(jié)束遍歷痢缎。代碼實(shí)現(xiàn)如下：

 public int CircularListLength(CLLNode headNode){
        int length=0;
        CLLNode currentNode=headNode;
        while (currentNode!=null){
            length++;
            currentNode=currentNode.getNext();
            if(currentNode==headNode){
                break;
            }
        }
        return length;
    }

5.2、在循環(huán)鏈表的表尾插入結(jié)點(diǎn)

在由表頭開始的循環(huán)鏈表的表尾后插入一個(gè)新結(jié)點(diǎn)世澜，也就是在表尾結(jié)點(diǎn)和第一個(gè)結(jié)點(diǎn)之間插入該新結(jié)點(diǎn)独旷。

創(chuàng)建一個(gè)新結(jié)點(diǎn)，并且初始化其next指針指向該結(jié)點(diǎn)自身寥裂。

圖5-1 創(chuàng)建新結(jié)點(diǎn)
更新新結(jié)點(diǎn)的next指針為表頭結(jié)點(diǎn)嵌洼，然后循環(huán)遍歷鏈表直至表尾。即插入位置應(yīng)為循環(huán)鏈表中下一個(gè)結(jié)點(diǎn)是表頭結(jié)點(diǎn)的結(jié)點(diǎn)位置封恰。

圖5-2 更新新結(jié)點(diǎn)
更新表頭結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)麻养。

圖5-3 更新表頭的前驅(qū)結(jié)點(diǎn)
代碼實(shí)現(xiàn)：

 public void InsertAtEndInCLL(CLLNode headNode,CLLNode nodeToInsert){
        CLLNode currentNode=headNode;
        while (currentNode.getNext()!=headNode){
            currentNode=currentNode.getNext();
        }
        //初始化
        nodeToInsert.setNext(nodeToInsert);
        if(headNode==null){
            headNode=nodeToInsert;
        }
        else {
            //更新新結(jié)點(diǎn)
            nodeToInsert.setNext(headNode);
            //更新表頭的前驅(qū)結(jié)點(diǎn)
            currentNode.setNext(nodeToInsert);
        }
    }

5.3、在循環(huán)鏈表的表頭插入結(jié)點(diǎn)

與上述表尾后插入結(jié)點(diǎn)的唯一區(qū)別是诺舔，在插入新結(jié)點(diǎn)后鳖昌，還需要更新指針。

創(chuàng)建一個(gè)新結(jié)點(diǎn)低飒，并且初始化其next指針指向該結(jié)點(diǎn)自身遗遵。

圖5-4 創(chuàng)建新結(jié)點(diǎn)
更新新結(jié)點(diǎn)的next指針為表頭結(jié)點(diǎn)，然后循環(huán)遍歷鏈表直至表尾逸嘀。即插入位置應(yīng)為循環(huán)鏈表中下一個(gè)結(jié)點(diǎn)是表頭結(jié)點(diǎn)的結(jié)點(diǎn)位置。

圖5-5 更新新結(jié)點(diǎn)
更新表頭結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的next指針指向新結(jié)點(diǎn)允粤。

圖5-6 更新表頭的前驅(qū)結(jié)點(diǎn)
設(shè)置新結(jié)點(diǎn)為表頭結(jié)點(diǎn)崭倘。

圖5-7 設(shè)置新結(jié)點(diǎn)為表頭
代碼實(shí)現(xiàn)：

 public void InsertAtBeginInCLL(CLLNode headNode,CLLNode nodeToInsert){
        CLLNode currentNode=headNode;
        while (currentNode.getNext()!=headNode){
            currentNode=currentNode.getNext();
        }
        //初始化
        nodeToInsert.setNext(nodeToInsert);
        if(headNode==null){
            headNode=nodeToInsert;
        }
        else {
            //更新新結(jié)點(diǎn)
            nodeToInsert.setNext(headNode);
            //更新表頭的前驅(qū)結(jié)點(diǎn)
            currentNode.setNext(nodeToInsert);
            //設(shè)置新結(jié)點(diǎn)為表頭
            headNode=nodeToInsert;
        }
    }

5.4、刪除循環(huán)鏈表中的最后一個(gè)結(jié)點(diǎn)

為了刪除最后一個(gè)結(jié)點(diǎn)类垫，需要遍歷循環(huán)鏈表找到倒數(shù)第二個(gè)結(jié)點(diǎn)司光。該結(jié)點(diǎn)成為了新的表尾結(jié)點(diǎn)，其next指針指向第一個(gè)結(jié)點(diǎn)悉患。

遍歷循環(huán)鏈表残家，找到表尾結(jié)點(diǎn)及其前驅(qū)結(jié)點(diǎn)。

圖5-8 遍歷循環(huán)鏈表
更新表尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)的next指針售躁，使其指向表頭結(jié)點(diǎn)坞淮。

圖5-9 更新表尾結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)
移除表尾結(jié)點(diǎn)。

圖5-10 移除表尾結(jié)點(diǎn)
代碼實(shí)現(xiàn)：

public void DeleteLastNodeFromCLL(CLLNode headNode){
        //表尾的前驅(qū)結(jié)點(diǎn)
        CLLNode temp=headNode;
        //表尾
        CLLNode currentNode=headNode;
        if(headNode==null){
            System.out.print("List is empty");
            return;
        }
        while (currentNode.getNext()!=headNode){
            temp=currentNode;
            currentNode=currentNode.getNext();
        }
        //更新表尾的前驅(qū)結(jié)點(diǎn)
        temp.setNext(headNode);
        //移除表尾
        currentNode=null;
        return;
    }

5.5陪捷、刪除循環(huán)鏈表中的第一個(gè)結(jié)點(diǎn)

只需要將表尾結(jié)點(diǎn)的next指針指向第一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)回窘。

遍歷循環(huán)鏈表找到表尾結(jié)點(diǎn)，就是要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)市袖。

圖5-11 遍歷循環(huán)鏈表
創(chuàng)建一個(gè)指向表頭結(jié)點(diǎn)的臨時(shí)結(jié)點(diǎn)啡直，更新表尾結(jié)點(diǎn)的next指針，使其指向第一個(gè)結(jié)點(diǎn)的后繼結(jié)點(diǎn)。

圖5-12 更新表尾結(jié)點(diǎn)
修改表頭指針的值酒觅，使其指向其后繼結(jié)點(diǎn)撮执，移除臨時(shí)結(jié)點(diǎn)。

圖5-13 更新表頭并移除臨時(shí)結(jié)點(diǎn)
代碼實(shí)現(xiàn)：

public void DeleteFrontNodeFromCLL(CLLNode headNode){
        //臨時(shí)結(jié)點(diǎn)
        CLLNode temp=headNode;
        //表尾結(jié)點(diǎn)
        CLLNode currentNode=headNode;
        if(headNode==null){
            System.out.print("List Empty");
            return;
        }
        while (currentNode.getNext()!=headNode){
            currentNode=currentNode.getNext();
        }
        //更新表尾結(jié)點(diǎn)
        currentNode.setNext(headNode.getNext());
        //更新表頭
        headNode=headNode.getNext();
        //移除臨時(shí)結(jié)點(diǎn)
        temp=null;
        return;
    }

6舷丹、松散鏈表

與數(shù)組相比抒钱，鏈表的最大優(yōu)勢(shì)在于，在任何位置插入元素的時(shí)間開銷僅為O(1)掂榔。然而在鏈表中查找某元素的時(shí)間開銷則是O(n)继效。下面介紹單向鏈表的簡單變種，稱為松散鏈表装获。
松散鏈表中的每個(gè)結(jié)點(diǎn)存儲(chǔ)多個(gè)元素（簡稱為塊）瑞信。而每一塊中的所有結(jié)點(diǎn)由循環(huán)鏈表鏈接在一起。

圖6-1 松散鏈表

假設(shè)在任何時(shí)候松散鏈表的元素個(gè)數(shù)不超過n穴豫，為了進(jìn)一步簡化問題凡简，假設(shè)除了最后一塊外，其它塊恰好有? √n?（表示不小于根號(hào)n的最小整數(shù)）精肃，所以在任何時(shí)候秤涩，松散鏈表中的個(gè)數(shù)不會(huì)超過?√n?（表示不大于根號(hào)n的最大整數(shù)）。舉個(gè)例子司抱，n為10的時(shí)候筐眷，? √n?=4，?√n?=2习柠。

6.1匀谣、在松散鏈表查找一個(gè)元素

在松散鏈表中查找第k個(gè)元素，時(shí)間復(fù)雜度為O(√n)资溃。具體描述如下：

遍歷鏈表找到包含第k個(gè)結(jié)點(diǎn)的塊武翎，已知每塊? √n?個(gè)結(jié)點(diǎn)，所以在第? k/? √n??塊溶锭。舉個(gè)例子宝恶，n為10的時(shí)候，? √n?=4趴捅，假設(shè)此時(shí)k=9垫毙。那么? 9/4?=3，即不小于9/4的最小整數(shù)拱绑。因?yàn)閗<=n露久，所以最多遍歷√n個(gè)塊，那么時(shí)間復(fù)雜度也就是O(√n)欺栗。
接著在這個(gè)塊的循環(huán)鏈表找到第（k mod ? √n?）個(gè)結(jié)點(diǎn)毫痕。這個(gè)過程的時(shí)間復(fù)雜度同樣也是O(√n)征峦，原因是每塊中的結(jié)點(diǎn)個(gè)數(shù)最多為? √n?。

6.2消请、在松散鏈表中插入一個(gè)元素

當(dāng)插入結(jié)點(diǎn)的時(shí)候钉答，可能需要調(diào)整松散鏈表中的結(jié)點(diǎn)以保證前面提到的鏈表屬性豫缨，也就是除了最后一塊外，其它塊恰好有? √n?個(gè)結(jié)點(diǎn)。舉個(gè)例子蝴乔，如下圖：

圖6-2 插入元素22

6.3径荔、在松散鏈表中執(zhí)行移動(dòng)操作

上述插入過程中會(huì)對(duì)一些元素進(jìn)行移動(dòng)少辣，使其滿足松散鏈表的相關(guān)性質(zhì)耐齐。其實(shí)每次移動(dòng)操作包括從塊中的循環(huán)鏈表的表尾移除一個(gè)結(jié)點(diǎn)，并在下一塊中的循環(huán)鏈表的表頭插入一個(gè)結(jié)點(diǎn)需频，時(shí)間復(fù)雜度為O(1)丁眼。那么可以推出在松散鏈表中插入一個(gè)元素的時(shí)間復(fù)雜度為O(√n)，因?yàn)樽疃鄨?zhí)行√n次移動(dòng)操作昭殉。

最后編輯于：2018.06.25 21:18:43

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者

人面猴
序言：七十年代末苞七，一起剝皮案震驚了整個(gè)濱河市，隨后出現(xiàn)的幾起案子挪丢，更是在濱河造成了極大的恐慌蹂风，老刑警劉巖，帶你破解...
沈念sama閱讀 216,402評(píng)論 6贊 499
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件乾蓬，死亡現(xiàn)場離奇詭異惠啄，居然都是意外死亡，警方通過查閱死者的電腦和手機(jī)任内，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 92,377評(píng)論 3贊 392
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進(jìn)店門礁阁，熙熙樓的掌柜王于貴愁眉苦臉地迎上來，“玉大人族奢，你說我怎么就攤上這事〉ず瑁” “怎么了越走？”我有些...
開封第一講書人閱讀 162,483評(píng)論 0贊 353
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長靠欢。經(jīng)常有香客問我廊敌，道長，這世上最難降的妖魔是什么门怪？我笑而不...
開封第一講書人閱讀 58,165評(píng)論 1贊 292
?港島之戀（遺憾婚禮）
正文為了忘掉前任骡澈，我火速辦了婚禮，結(jié)果婚禮上掷空，老公的妹妹穿的比我還像新娘肋殴。我一直安慰自己囤锉，他們只是感情好，可當(dāng)我...
茶點(diǎn)故事閱讀 67,176評(píng)論 6贊 388
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布护锤。她就那樣靜靜地躺著官地，像睡著了一般。火紅的嫁衣襯著肌膚如雪烙懦。梳的紋絲不亂的頭發(fā)上驱入，一...
開封第一講書人閱讀 51,146評(píng)論 1贊 297
城市分裂傳說
那天，我揣著相機(jī)與錄音氯析，去河邊找鬼亏较。笑死，一個(gè)胖子當(dāng)著我的面吹牛掩缓，可吹牛的內(nèi)容都是我干的雪情。我是一名探鬼主播，決...
沈念sama閱讀 40,032評(píng)論 3贊 417
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼拾因，長吁一口氣：“原來是場噩夢(mèng)啊……” “哼旺罢！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起绢记，我...
開封第一講書人閱讀 38,896評(píng)論 0贊 274
萬榮殺人案實(shí)錄
序言：老撾萬榮一對(duì)情侶失蹤扁达，失蹤者是張志新（化名）和其女友劉穎，沒想到半個(gè)月后蠢熄，有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體跪解，經(jīng)...
沈念sama閱讀 45,311評(píng)論 1贊 310
?護(hù)林員之死
正文獨(dú)居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點(diǎn)故事閱讀 37,536評(píng)論 2贊 332
?白月光啟示錄
正文我和宋清朗相戀三年签孔，在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了叉讥。大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點(diǎn)故事閱讀 39,696評(píng)論 1贊 348
活死人
序言：一個(gè)原本活蹦亂跳的男人離奇死亡饥追，死狀恐怖图仓，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情但绕，我是刑警寧澤救崔，帶...
沈念sama閱讀 35,413評(píng)論 5贊 343
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站捏顺，受9級(jí)特大地震影響六孵，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜幅骄，卻給世界環(huán)境...
茶點(diǎn)故事閱讀 41,008評(píng)論 3贊 325
男人毒藥：我在死后第九天來索命
文/蒙蒙一劫窒、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧拆座，春花似錦主巍、人聲如沸冠息。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,659評(píng)論 0贊 22
一樁弒父案煤禽，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽铐达。三九已至，卻和暖如春檬果，著一層夾襖步出監(jiān)牢的瞬間瓮孙，已是汗流浹背。一陣腳步聲響...
開封第一講書人閱讀 32,815評(píng)論 1贊 269
情欲美人皮
我被黑心中介騙來泰國打工选脊，沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留杭抠，地道東北人。一個(gè)月前我還...
沈念sama閱讀 47,698評(píng)論 2贊 368
代替公主和親
正文我出身青樓恳啥，卻偏偏與公主長得像偏灿，于是被迫代替她去往敵國和親。傳聞我的和親對(duì)象是個(gè)殘疾皇子钝的，可洞房花燭夜當(dāng)晚...
茶點(diǎn)故事閱讀 44,592評(píng)論 2贊 353

數(shù)據(jù)結(jié)構(gòu)——鏈表

目錄

1、屬性

2瘪松、鏈表和數(shù)組的區(qū)別

2.1、數(shù)組概述

2.2、數(shù)組和鏈表優(yōu)缺點(diǎn)

2.3诬辈、鏈表和數(shù)組的比較

3样屠、單向鏈表

3.1悦穿、單向鏈表的基本操作

3.1.1、鏈表的遍歷

3.1.2、鏈表的插入

3.1.2.1、在單向鏈表的開頭插入結(jié)點(diǎn)

3.1.2.2、在單向鏈表的結(jié)尾插入結(jié)點(diǎn)

3.1.2.3边坤、在單向鏈表的中間插入結(jié)點(diǎn)

3.1.2.4踢故、函數(shù)實(shí)現(xiàn)

3.1.3耸峭、鏈表的刪除

3.1.3.1洽瞬、刪除鏈表的表頭

3.1.3.2菩颖、刪除鏈表的表尾

3.1.3.3、刪除鏈表中間的結(jié)點(diǎn)

3.1.3.4、函數(shù)實(shí)現(xiàn)

3.1.4、鏈表的釋放

4落塑、雙向鏈表

4.1伴逸、雙向鏈表的插入

4.1.1错蝴、在雙向鏈表的開頭插入結(jié)點(diǎn)

4.1.2洲愤、在雙向鏈表的末尾插入結(jié)點(diǎn)

4.1.3、在雙向鏈表的中間插入一個(gè)結(jié)點(diǎn)

4.1.4顷锰、函數(shù)實(shí)現(xiàn)

4.2柬赐、雙向鏈表的刪除

4.2.1官紫、刪除雙向鏈表的第一個(gè)結(jié)點(diǎn)

4.2.2肛宋、刪除雙向鏈表的最后一個(gè)結(jié)點(diǎn)

4.2.3州藕、刪除雙向鏈表中間的一個(gè)結(jié)點(diǎn)

4.2.4、代碼實(shí)現(xiàn)

5酝陈、循環(huán)鏈表

5.1床玻、遍歷循環(huán)鏈表

5.2、在循環(huán)鏈表的表尾插入結(jié)點(diǎn)

5.3沉帮、在循環(huán)鏈表的表頭插入結(jié)點(diǎn)

5.4锈死、刪除循環(huán)鏈表中的最后一個(gè)結(jié)點(diǎn)

5.5、刪除循環(huán)鏈表中的第一個(gè)結(jié)點(diǎn)

6穆壕、松散鏈表

6.1待牵、在松散鏈表查找一個(gè)元素

6.2、在松散鏈表中插入一個(gè)元素

6.3喇勋、在松散鏈表中執(zhí)行移動(dòng)操作

正文

1缨该、屬性

2渗常、鏈表和數(shù)組的區(qū)別

2.1询一、數(shù)組概述

2.2、數(shù)組和鏈表優(yōu)缺點(diǎn)

2.3疟赊、鏈表和數(shù)組的比較

3、單向鏈表

3.1、單向鏈表的基本操作

3.1.1类浪、鏈表的遍歷

3.1.2川队、鏈表的插入

3.1.2.1力细、在單向鏈表的開頭插入結(jié)點(diǎn)

3.1.2.2昔脯、在單向鏈表的結(jié)尾插入結(jié)點(diǎn)

3.1.2.3沈堡、在單向鏈表的中間插入結(jié)點(diǎn)

3.1.2.4、函數(shù)實(shí)現(xiàn)

3.1.3勃痴、鏈表的刪除

3.1.3.1谒所、刪除鏈表的表頭

3.1.3.2尖淘、刪除鏈表的表尾

3.1.3.3卫病、刪除鏈表中間的結(jié)點(diǎn)

3.1.3.4、函數(shù)實(shí)現(xiàn)

3.1.4裆甩、鏈表的釋放

4抛腕、雙向鏈表

4.1全封、雙向鏈表的插入

4.1.1、在雙向鏈表的開頭插入結(jié)點(diǎn)

4.1.2就轧、在雙向鏈表的末尾插入結(jié)點(diǎn)

4.1.3乎莉、在雙向鏈表的中間插入一個(gè)結(jié)點(diǎn)

4.1.4肥橙、函數(shù)實(shí)現(xiàn)

4.2魄宏、雙向鏈表的刪除

4.2.1、刪除雙向鏈表的第一個(gè)結(jié)點(diǎn)

4.2.2烁焙、刪除雙向鏈表的最后一個(gè)結(jié)點(diǎn)

4.2.3岔激、刪除雙向鏈表中間的一個(gè)結(jié)點(diǎn)

4.2.4、代碼實(shí)現(xiàn)

5散休、循環(huán)鏈表

5.1划址、遍歷循環(huán)鏈表

5.2、在循環(huán)鏈表的表尾插入結(jié)點(diǎn)

5.3、在循環(huán)鏈表的表頭插入結(jié)點(diǎn)

5.4、刪除循環(huán)鏈表中的最后一個(gè)結(jié)點(diǎn)

5.5陪捷、刪除循環(huán)鏈表中的第一個(gè)結(jié)點(diǎn)

6舷丹、松散鏈表