鏈表概述

數(shù)組和鏈表都是線性存儲(chǔ)結(jié)構(gòu)的基礎(chǔ)實(shí)現(xiàn)，棧和隊(duì)列都是線性存儲(chǔ)結(jié)構(gòu)的應(yīng)用

數(shù)組優(yōu)缺點(diǎn)

說(shuō)起鏈表必須說(shuō)一下數(shù)組：數(shù)組是一種連續(xù)存儲(chǔ)線性結(jié)構(gòu)，元素類型相同，大小相等

數(shù)組優(yōu)勢(shì)：存取速度快。

數(shù)組劣勢(shì)：

事先必須知道數(shù)組的長(zhǎng)度
空間通常是有限制的
需要大塊連續(xù)的內(nèi)存塊
插入刪除元素的效率很低

鏈表優(yōu)缺點(diǎn)

鏈表是離散存儲(chǔ)線性結(jié)構(gòu)

n個(gè)節(jié)點(diǎn)離散分配，彼此通過(guò)指針相連，每個(gè)節(jié)點(diǎn)只有一個(gè)前驅(qū)節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)只有一個(gè)后續(xù)節(jié)點(diǎn)，首節(jié)點(diǎn)沒(méi)有前驅(qū)節(jié)點(diǎn)，尾節(jié)點(diǎn)沒(méi)有后續(xù)節(jié)點(diǎn)。

鏈表優(yōu)點(diǎn)：

空間沒(méi)有限制
插入刪除元素很快

鏈表缺點(diǎn)：

節(jié)點(diǎn)的獲取很慢

鏈表分類

對(duì)于鏈表，如果用數(shù)組實(shí)現(xiàn)。那即是靜態(tài)鏈表
鏈表分好幾類：
- 有單向鏈表，
  - 一個(gè)節(jié)點(diǎn)有一個(gè)指針域?qū)傩?，指向其后繼節(jié)點(diǎn)，尾節(jié)點(diǎn)的后繼節(jié)點(diǎn)為NULL。
- 雙向鏈表
  - 一個(gè)節(jié)點(diǎn)兩個(gè)指針域?qū)傩?，分別指向其前驅(qū)，后繼節(jié)點(diǎn)
- 循環(huán)鏈表
  - 相比于單向鏈表，尾節(jié)點(diǎn)的后繼節(jié)點(diǎn)為鏈表的首節(jié)點(diǎn)。
- 雙向循環(huán)鏈表
  - 能通過(guò)任何一個(gè)節(jié)點(diǎn)找到其他所有節(jié)點(diǎn)，相比于雙向鏈表，把最后一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)指向了第一個(gè)節(jié)點(diǎn)，進(jìn)而形成環(huán)式循環(huán)。

鏈表需要注意的點(diǎn)

鏈表需要相同的數(shù)據(jù)類型
鏈表的處理方式都是先取代，后目的。比如刪除鏈?zhǔn)骄€性表的某個(gè)節(jié)點(diǎn)的流程，先取代delete point使它的前驅(qū)節(jié)點(diǎn)指向它的后繼節(jié)點(diǎn)，這樣就完成了取代。然后再free()掉這個(gè)節(jié)點(diǎn)，這樣就達(dá)到了目的。再比如加入某個(gè)節(jié)點(diǎn)，先使add point指向add index要加入處的后繼節(jié)點(diǎn)，這即取代。然后再使add index的前驅(qū)節(jié)點(diǎn)指向add point。
操作一個(gè)鏈表只需要知道它的頭指針就可以做任何操作了

解題步驟：

先考慮特殊情況，邊緣值
進(jìn)入退出循環(huán)時(shí)需要找準(zhǔn)條件，考慮清楚退出循環(huán)時(shí)所需要的變量的終值是多少，方便使用
審視全局，帶正確的值判斷是否AC

控制選擇的節(jié)點(diǎn)

int i = 1;

while (i < index) {
    headNode = headNode.getNextNode();
    i++;
}

這段代碼意義即，從初始化i=0開(kāi)始，如果要插入節(jié)點(diǎn)到第i個(gè)的位置。那么我們就一定需要找到第i-1個(gè)節(jié)點(diǎn)。所以現(xiàn)在我們目標(biāo)明確了，要找第i-1個(gè)節(jié)點(diǎn)。
因?yàn)檠h(huán)的結(jié)束條件是由i控制的，如果我們使變量i原本從0開(kāi)始計(jì)數(shù)++到i-1結(jié)束。跳過(guò)的是i個(gè)元素。這樣就把我們需要的第i-1節(jié)點(diǎn)跳過(guò)了。而我們要想取到它，很明顯我們需要讓循環(huán)少進(jìn)行一次。
為了邏輯清晰，循環(huán)判斷條件不應(yīng)改變。那么我們就需要把i的初始值改為1，而非原先的0。

鏈表操作

遍歷
查找
清空
銷毀
求長(zhǎng)度
排序
刪除節(jié)點(diǎn)
插入節(jié)點(diǎn)

Github - 單鏈表代碼地址 - 歡迎star

添加數(shù)據(jù)到鏈表中

那么無(wú)疑是找到尾節(jié)點(diǎn)插入即可
while(tempNode.getNextNode()!=null)當(dāng)退出循環(huán)時(shí)，那么就定位到了后繼節(jié)點(diǎn)為NULL的節(jié)點(diǎn)即尾節(jié)點(diǎn)。

遍歷鏈表

從頭結(jié)點(diǎn)開(kāi)始輸出，直到尾節(jié)點(diǎn)。
while(tempNode!=null)那么退出循環(huán)時(shí)即所有節(jié)點(diǎn)全部輸出。

給定位置插入節(jié)點(diǎn)到鏈表中

鏈表插入的題要看清題意。是要往第i個(gè)位置插入，還是往索引為i的位置插入。在同樣具有虛擬頭結(jié)點(diǎn)的前提下，兩者直接決定了i的初始值。
因?yàn)橐付ㄎ恢貌迦牍?jié)點(diǎn)。比如2143要往第3個(gè)位置插，那么即插到1,4中間。所以要往哪個(gè)位置插那么必須找到他的前驅(qū)節(jié)點(diǎn)1。這也是我們前面所講的控制選擇的節(jié)點(diǎn)的使用場(chǎng)景。
如下進(jìn)入判斷條件中，如果起始條件是0的時(shí)候，那么需要注意，每進(jìn)入一次循環(huán)+1。那么它總共會(huì)進(jìn)入3次。0,1,2?？墒茄h(huán)中節(jié)點(diǎn)向下遍歷。如果首次進(jìn)入循環(huán)的開(kāi)始節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)而非頭結(jié)點(diǎn)的話即2。往后跳三次，就會(huì)找到3節(jié)點(diǎn)，很明顯不是我們想要的。
所以我們應(yīng)該明白如果要插入到第10個(gè)位置，我們需要找到第九個(gè)節(jié)點(diǎn)，那么循環(huán)起始從第一個(gè)開(kāi)始的話，找到第九個(gè)需要進(jìn)循環(huán)8次退出循環(huán)時(shí)才是第9個(gè)節(jié)點(diǎn)。所以我們可以看出，要插到第10個(gè)位置我們需要循環(huán)得是8次而不是9次。
- 我們知道如果i從0- i<10是10次。即0-9那么我們可以控制i從i = 1開(kāi)始，這樣只使循環(huán)少了一次。那么另一次怎么減呢
- 我們可以再通過(guò)使第一次進(jìn)入循環(huán)的節(jié)點(diǎn)是頭結(jié)點(diǎn)而不是第一個(gè)擁有實(shí)際value的節(jié)點(diǎn)開(kāi)始。這樣我們就可以使無(wú)用節(jié)點(diǎn)也占用一次循環(huán)，也就相當(dāng)于使循環(huán)次數(shù)-1了。

    index = 3;
    ----
    int i = 0;
    temp = headNode.getNextNode();
    while(i < index){
        tempNode = tempNode.getNextNode();
        i++;
    }
    
    int i = 1;
    temp = headNode;
    while(i < index){
        tempNode = tempNode.getNextNode();
        i++;
    }

然后接下承上，即要插入的這個(gè)節(jié)點(diǎn)Node.next = 4然后1.next = Node。切不可亂了順序，否則會(huì)丟失指針

獲取鏈表的長(zhǎng)度

遍歷鏈表，聲明一個(gè)變量，每遍歷一個(gè)節(jié)點(diǎn)變量+1。

int i = 0;
tempNode = headNode.next;
while(tempNode!=null) {
    i++;
    tempNode = tempNode.next;
}

這里需要明白兩點(diǎn)。
- 當(dāng)tempNode等于頭結(jié)點(diǎn)的時(shí)候，我們可以想到這種情況會(huì)使循環(huán)多進(jìn)行一次。
- 當(dāng)循環(huán)判斷條件while()，判斷的不是tempNode!=null即當(dāng)前節(jié)點(diǎn)，而是tempNode.next!=null下一節(jié)點(diǎn)時(shí)。會(huì)使循環(huán)少進(jìn)行一次。
- 這兩點(diǎn)很重要，循環(huán)進(jìn)行多少次的掌控就在這幾點(diǎn)。

刪除給定位置的節(jié)點(diǎn)

和從指點(diǎn)位置插入點(diǎn)一樣。都是要找指定位置的前驅(qū)節(jié)點(diǎn)。
總共4個(gè)節(jié)點(diǎn)，我們要?jiǎng)h除第3個(gè)位置的節(jié)點(diǎn)。即需要找到第2個(gè)節(jié)點(diǎn)，進(jìn)入一次循環(huán)節(jié)點(diǎn)向后移一位，進(jìn)入節(jié)點(diǎn)時(shí)是第一個(gè)節(jié)點(diǎn)。那么我們需要進(jìn)循環(huán)一次即可。那么即

int i = 1；
while(i < 3){
    i++;
    temp = temp.next;
}

對(duì)鏈表進(jìn)行排序

冒泡排序
- 雙層循環(huán)，外層節(jié)點(diǎn)起始位置第一節(jié)點(diǎn)temp = headNode.next，退出條件temp != null。這是索引循環(huán)起始指向第一節(jié)點(diǎn)，最終從末尾節(jié)點(diǎn)跳出。
- 內(nèi)層循環(huán)，起始節(jié)點(diǎn)即第一節(jié)點(diǎn)nextNode = headNode.next，退出條件nextNode.next != null，因?yàn)槊芭菔乔昂笤乇却笮〉?和第2比，第n-1和第n比。所以當(dāng)指到最后節(jié)點(diǎn)的時(shí)候就可以跳出。

找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

這個(gè)起始和正向找節(jié)點(diǎn)是一個(gè)概念，我們只要利用循環(huán)鏈表的思路變換數(shù)字即可。首先我們可以把鏈表看成一個(gè)首尾相連的循環(huán)結(jié)構(gòu)。那么倒數(shù)第k個(gè)，即一個(gè)元素正數(shù)位置的絕對(duì)值加上倒數(shù)位置的絕對(duì)值比總數(shù)多1。比如6個(gè)數(shù)，我們找倒數(shù)第二個(gè)。倒數(shù)第2個(gè)也是正數(shù)第5個(gè)，2+5-1=6。所以我們要找一個(gè)數(shù)，正向找無(wú)疑很方便，只需要(-k+1+總數(shù)) = 元素位置。我們只需要對(duì)鏈表進(jìn)行排序后獲取該元素即可

/**
     * 找鏈表倒數(shù)第index個(gè)節(jié)點(diǎn)
     *
     * @param headNode
     * @param index
     * @return
     */
    public static int findNode(Node headNode, int index) {
        int listLength = listLength(headNode);
        index = -index;
        int trueIndex = (index + listLength + 1) % listLength;
        for (int i = 0; i < trueIndex; i++) {
            headNode = headNode.getNextNode();
        }
        return headNode.getValue();
    }

我們也可以用追隨節(jié)點(diǎn)辦法，設(shè)立兩個(gè)節(jié)點(diǎn)。一個(gè)節(jié)點(diǎn)比另一個(gè)節(jié)點(diǎn)快k步。即先行節(jié)點(diǎn)走了k下，后行節(jié)點(diǎn)出發(fā)走第一下。當(dāng)后行節(jié)點(diǎn)跳出循環(huán)，那么先行節(jié)點(diǎn)必然是倒數(shù)第k個(gè)節(jié)點(diǎn)。我們一般也用這種方法來(lái)找一個(gè)鏈表的幾等分點(diǎn)。如果找一個(gè)鏈表的三等分點(diǎn)，我們給連個(gè)節(jié)點(diǎn)一個(gè)走三步一個(gè)走一步即可。

/**
     * 找倒數(shù)第k個(gè)節(jié)點(diǎn)|追點(diǎn)，簡(jiǎn)潔寫(xiě)法
     *
     * @param headNode
     * @return
     */
    public static int findNode3(Node headNode, int k) {
        Node tempNode = headNode;
        Node nextNode = null;
        int i = 0;
        while (tempNode != null) {
            i++;
            tempNode = tempNode.getNextNode();
            if (tempNode == null) {
                break;
            }
            if (i == k) {
                nextNode = headNode.getNextNode();
            } else if (i > k) {
                nextNode = nextNode.getNextNode();
            }
        }
        return nextNode.getValue();
    }

刪除鏈表重復(fù)數(shù)據(jù)

這里我用while循環(huán)寫(xiě)的，比較簡(jiǎn)單而且簡(jiǎn)潔。其實(shí)本質(zhì)上和冒泡排序的思路一樣，思考的時(shí)候用for循環(huán)的思路思考臨界條件即可。非常簡(jiǎn)單

雙重循環(huán)，第一層循環(huán)是索引節(jié)點(diǎn)循環(huán)，循環(huán)進(jìn)入從第一個(gè)節(jié)點(diǎn)開(kāi)始，到尾節(jié)點(diǎn)跳出。
- 內(nèi)循環(huán)，每進(jìn)入內(nèi)循環(huán)一層循環(huán)的時(shí)候把next節(jié)點(diǎn)賦予最新的外層索引值。然后取該next節(jié)點(diǎn)的next節(jié)點(diǎn)值與索引節(jié)點(diǎn)的值進(jìn)行比較。向后循環(huán)

/**
 * 刪除重復(fù)元素,|參考別人的 O(n2)
 *
 * @param headNode
 */
  public static void removeDumplecateEle(Node headNode) {
        Node temp = headNode.getNextNode();
        Node next;
        while (temp != null) {
            next = temp;
            while (next.getNextNode() != null) {
                if (next.getNextNode().getValue() == temp.getValue()) {
                    next.setNextNode(next.getNextNode().getNextNode());
                } else {
                    next = next.getNextNode();
                }
            }
            temp = temp.getNextNode();
        }
    }

hashtable做法。使鏈表上的每個(gè)節(jié)點(diǎn)插入到hashtable中，插入前進(jìn)行判斷是否在hashtable中存在。
- 需要注意的是，hashtable在存儲(chǔ)的時(shí)候是將該值存到了鍵值的位置。value恒定給值，否則不方便遍歷。

/**
     * 刪除重復(fù)元素 hashtable| 空間開(kāi)銷變大，O(n)
     *
     * @param headNode
     */
    public static void removeDuplecate3(Node headNode) {
        Hashtable<Integer, Integer> hashtable = new Hashtable<Integer, Integer>();
        Node tempNode = headNode.getNextNode();
        while (tempNode != null) {
            if (!hashtable.containsKey(tempNode.getValue())) {
                hashtable.put(tempNode.getValue(), 1);
            }
            tempNode = tempNode.getNextNode();
        }
        // 打印
        for (Map.Entry<Integer, Integer> entryItem : hashtable.entrySet()
                ) {
            System.out.println(entryItem.getKey());
        }
    }

查詢鏈表的中間節(jié)點(diǎn)

兩個(gè)指針，一個(gè)走兩步，一個(gè)走一步。同一起點(diǎn)出發(fā)，拿先行節(jié)點(diǎn)進(jìn)行判斷null值，先行節(jié)點(diǎn)為null那么跳出循環(huán)，此時(shí)后行節(jié)點(diǎn)即為中間節(jié)點(diǎn)。

遞歸從尾到頭輸出單鏈表

很簡(jiǎn)單，因?yàn)殒湵砩蟻?lái)我們只知道頭結(jié)點(diǎn)。而尾遍歷，尾節(jié)點(diǎn)的特點(diǎn)就是next=NULL。所以我們只需要來(lái)個(gè)循環(huán)遞歸的找到遞歸到尾節(jié)點(diǎn)即可。然后方法棧由里到外依次打印即可。

 /**
     * 鏈表逆序遞歸遍歷
     *
     * @param headNode
     */
    public static void traverseByRecursive(Node headNode) {
        if (headNode != null) {
            traverseByRecursive(headNode.getNextNode());
            if (headNode.getValue() != HEAD_POINT_NUMBER) {
                System.out.println(headNode.getValue());
            }
        }
    }

反轉(zhuǎn)鏈表

遞歸和非遞歸的思想差異。遞歸是從鏈表尾開(kāi)始兩兩個(gè)體相互反轉(zhuǎn)。而非遞歸實(shí)現(xiàn)是從鏈表頭開(kāi)始兩兩個(gè)體相互反轉(zhuǎn)。
非遞歸
- 非遞歸實(shí)現(xiàn)需要注意，每一步我們做了什么。比如4,2,3,3。我們第一步拿出了4，第二步成了2,4。第三步3,2,4。這樣。所以我們應(yīng)該做的是，
  - 首先聲明一個(gè)節(jié)點(diǎn)tempNode，讓其根據(jù)鏈表循環(huán)向后遍歷鏈表。直到=null。這樣我們所有元素都反轉(zhuǎn)了。
  - 其次我們發(fā)現(xiàn)第一個(gè)元素抽出的時(shí)候，即新鏈表的頭我們把他進(jìn)行標(biāo)識(shí)firstNode以方便為后續(xù)抽出的節(jié)點(diǎn)的next屬性賦值。比如4，它的next元素是null而后抽出的元素他們的next元素都是在它前一位抽出的元素。因?yàn)檫@個(gè)next元素的賦值操作發(fā)生在循環(huán)中，且只有一次是null其他幾次都為實(shí)際元素，所以我們需要聲明一個(gè)節(jié)點(diǎn)nextNode初始化為null。當(dāng)他第一次進(jìn)入循環(huán)的時(shí)候，即拿出4的時(shí)候?qū)⑵浞湃雝empNode的next屬性中。
  - 然后賦值操作后緊跟著對(duì)該nextNode元素進(jìn)行更改，讓其等于新鏈表的頭firstNode。

while (tempNode != null) {
       firstNode = tempNode;
       tempNode = tempNode.getNextNode();
       firstNode.setNextNode(nextNode);
       nextNode = firstNode;
}

遞歸
- 程序分兩種情況處理，首先做特殊處理，當(dāng)鏈表只有一個(gè)節(jié)點(diǎn)，或者說(shuō)該節(jié)點(diǎn)為null的時(shí)候。那么返回該節(jié)點(diǎn)。
- 當(dāng)鏈表含有多個(gè)元素的時(shí)候，遞歸依次遍歷該鏈表直到當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)(退出條件由第一步控制)。最深層遞歸函數(shù)為次深層遞歸函數(shù)返回當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)。
- 尾元素的next指向他原鏈表的前驅(qū)節(jié)點(diǎn)。前驅(qū)節(jié)點(diǎn)的next指向null。
- 遞歸從最深層返回的頭依次傳遞在遞歸函數(shù)間，從最深層傳到最頂層。供最外層函數(shù)返回。
遞歸需要注意的是：遞歸時(shí)，每次退出一層遞歸函數(shù)，headNode節(jié)點(diǎn)都會(huì)前移一位。因?yàn)樽钌顚拥?code>headNode節(jié)點(diǎn)什么都沒(méi)做，只是找到了表尾節(jié)點(diǎn)進(jìn)行返回。
```
Node temp;
    if (headNode == null || headNode.getNextNode() == null) {
        temp = headNode;
    } else {
        // A B C- D-
        // temp = D;
        // headNode = C;
        // indexNode = D;
        // A -> B -> C          D -> C -> null
        Node indexNode = recursiveReversalLinklist(headNode.getNextNode());
        headNode.getNextNode().setNextNode(headNode);
        headNode.setNextNode(null);
        temp = indexNode;
    }
    // 反回新鏈表的頭，遞歸多層函數(shù)間重復(fù)傳遞，
    return temp;
```

單鏈表的擴(kuò)展

循環(huán)鏈表
雙向鏈表

都很簡(jiǎn)單，不贅述了。

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

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

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

鏈表概述

數(shù)組優(yōu)缺點(diǎn)

鏈表優(yōu)缺點(diǎn)

鏈表分類

鏈表需要注意的點(diǎn)

控制選擇的節(jié)點(diǎn)

鏈表操作

添加數(shù)據(jù)到鏈表中

遍歷鏈表

給定位置插入節(jié)點(diǎn)到鏈表中

獲取鏈表的長(zhǎng)度

刪除給定位置的節(jié)點(diǎn)

對(duì)鏈表進(jìn)行排序

找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

刪除鏈表重復(fù)數(shù)據(jù)

查詢鏈表的中間節(jié)點(diǎn)

遞歸從尾到頭輸出單鏈表

反轉(zhuǎn)鏈表

單鏈表的擴(kuò)展

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

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

鏈表概述

數(shù)組優(yōu)缺點(diǎn)

鏈表優(yōu)缺點(diǎn)

鏈表分類

鏈表需要注意的點(diǎn)

控制選擇的節(jié)點(diǎn)

鏈表操作

添加數(shù)據(jù)到鏈表中

遍歷鏈表

給定位置插入節(jié)點(diǎn)到鏈表中

獲取鏈表的長(zhǎng)度

刪除給定位置的節(jié)點(diǎn)

對(duì)鏈表進(jìn)行排序

找到鏈表中倒數(shù)第k個(gè)節(jié)點(diǎn)

刪除鏈表重復(fù)數(shù)據(jù)

查詢鏈表的中間節(jié)點(diǎn)

遞歸從尾到頭輸出單鏈表

反轉(zhuǎn)鏈表

單鏈表的擴(kuò)展

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av