手撕數(shù)據(jù)結(jié)構(gòu)與算法

前言

底層基礎(chǔ)決定上層發(fā)展。

點個贊在看，讓我知道你在關(guān)注技術(shù)。

本系列文章Github 后端進階指南 已收錄，此項目正在完善中，歡迎star。

本系列內(nèi)容預覽：

1. 什么是鏈表？

鏈表也是線性表中的一種，數(shù)組是線性表中的順序結(jié)構(gòu)，而這次說的鏈表是線性表的鏈式存儲結(jié)構(gòu)，它在內(nèi)存中是非連續(xù)、非順序性的數(shù)據(jù)結(jié)構(gòu)，由若干個節(jié)點組成。它每個節(jié)點中都會存儲數(shù)據(jù)和下一個節(jié)點的地址，存儲數(shù)據(jù)的叫做數(shù)據(jù)域，存儲地址的叫做指針域。指針分為前驅(qū)指針、后繼指針，分別用來記錄前一個節(jié)點和后一個節(jié)點的位置。

指針：將某個變量賦值給指針，實際上就是將變量的地址值賦值給指針，可以看做Java當中的引用。

1.1 單向鏈表

單向鏈表，顧名思義就是只有一個方向的鏈表，從上圖中來看，一個單向鏈表由若干個節(jié)點組成，每個節(jié)點又分為兩個部分，一部分存放數(shù)據(jù)，一部分存放下一個節(jié)點的位置。用圖來說話就是橘色的方塊叫做數(shù)據(jù)域，里面用來存放數(shù)據(jù)data。而黃色的方塊叫做指針域，用來存放下一個節(jié)點的位置next（注意是下一個節(jié)點的位置，不是下一個指針的位置），這個next又被稱為后繼指針。

大家觀察上面的圖，有兩個地方比較特殊，那就是第一個節(jié)點和最后一個節(jié)點。我們還可以稱作頭結(jié)點、尾結(jié)點。這兩個節(jié)點有什么特別之處呢？那就是頭結(jié)點可以不存數(shù)據(jù)，作為鏈表的開始，而尾結(jié)點的后繼指針指向null，代表這是鏈表的最后一個節(jié)點。

頭節(jié)點：鏈表中第一個節(jié)點，頭節(jié)點中可以不存儲數(shù)據(jù)。

頭指針：鏈表中第一個節(jié)點的指針，用來存儲鏈表的基地址，是整個鏈表的開始。

尾節(jié)點：鏈表中最后一個節(jié)點，指向一個空null，代表這是鏈表的最后一個節(jié)點。

1.2 單向循環(huán)鏈表

單向循環(huán)鏈表是從單向鏈表衍生出來的，它和單向鏈表的唯一區(qū)別就是單向鏈表的尾結(jié)點的后繼指針指向了null，而單向循環(huán)鏈表的尾結(jié)點后繼指針指向了頭節(jié)點。這種首尾相連的單鏈表稱單向循環(huán)鏈表。循環(huán)鏈表的優(yōu)點就是從鏈尾到鏈頭比較方便，處理環(huán)形結(jié)構(gòu)問題時比較適用，比如著名的約瑟夫問題。

1.3 雙向鏈表

雙向鏈表稍微復雜一些，它和單向鏈表相比除了后繼指針以外還多了個前驅(qū)指針。如果存儲同樣多的數(shù)據(jù)，雙向鏈表比單向鏈表占用更多的空間，雖然雙向鏈表中的兩個指針很浪費空間，但可以支持雙向遍歷，也給鏈表本身帶來了更多的靈活性。

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

了解了循環(huán)鏈表和雙向鏈表之后，把這兩個組合在一起就是雙向循環(huán)鏈表，大家看圖就知道了，頭節(jié)點的前驅(qū)指針指向尾節(jié)點，尾節(jié)點的后繼指針指向頭節(jié)點。這里就不做過多介紹了，大家知道鏈表都有哪幾種就可以了。

2. 鏈表VS數(shù)組

說了半天鏈表，不知道大家了解了沒有，我自己都感覺很枯燥?？墒腔A(chǔ)就是這樣，只有學好了基礎(chǔ)才能更好的向上爬?，F(xiàn)在我們來看下鏈表和我們之前講的數(shù)組有什么區(qū)別。首先它們兩個的存儲結(jié)構(gòu)就不一樣，數(shù)組是順序存儲結(jié)構(gòu)，也就是說它在內(nèi)存中是一塊連續(xù)的存儲空間，而鏈表是鏈式存儲結(jié)構(gòu)，也就是非連續(xù)的。我們來看下它們在內(nèi)存中表現(xiàn)：

通過圖片，相信大家已經(jīng)看出來區(qū)別了，由于數(shù)組是連續(xù)的存儲結(jié)構(gòu)，可以借助 CPU 的緩存機制，預讀數(shù)組中的數(shù)據(jù)，所以訪問效率更高。而鏈表在內(nèi)存中并不是連續(xù)存儲，所以對 CPU 緩存不友好，沒辦法有效預讀。由于數(shù)據(jù)結(jié)構(gòu)的不同，導致數(shù)組和鏈表的插入、刪除、隨機訪問等操作的時間復雜度正好相反。

鏈表天然的支持動態(tài)擴容，因為它不是預先生成內(nèi)存空間，只有真正使用的時候才會去開辟一塊內(nèi)存空間。而數(shù)組就不行，數(shù)組的缺點就是大小固定，申請多了浪費，申請少了還得頻繁的擴容、搬移數(shù)組，如果數(shù)據(jù)量大了很耗時。所以大家在使用List的時候也是，如果能夠事先預估數(shù)據(jù)量的大小，那么在初始化的時候最好指定下大小，避免擴容時搬移數(shù)據(jù)帶來影響。

3. 鏈表的基本操作

3.1 鏈表的增加

鏈表的增加操作，一共有三種情況：

• 增加到頭部

  

  增加到頭部一共分為兩步，第一步將新節(jié)點的后繼指針指向原頭節(jié)點，第二步是將新節(jié)點變?yōu)轭^節(jié)點。這樣就完成了頭部添加。

• 增加到中間

  

  中間插入也分為兩步，第一步將插入位置的前邊節(jié)點的后繼指針指向新節(jié)點，第二步是將新節(jié)點后繼指針指向插入位置的原節(jié)點。

• 增加到尾部

  

  鏈表的尾部插入最簡單，只需要將最后一個節(jié)點的后繼指針指向新節(jié)點就可以了。

我們來看下代碼，如果大家時間充沛，建議自己手動敲一遍，這樣會理解的更深刻。

/**
 * @author: lixiaoshuang
 * @create: 2019-12-08 23:11
 **/
public class LinkedListAddDemo {

    //頭節(jié)點
    private static Node headNode = null;
    //尾節(jié)點
    private static Node lastNode = null;
    //鏈表的長度
    private static int size;

    public static void main(String[] args) {
        //初始化一個鏈表
        addByIndex(1, 0);
        addByIndex(2, 1);
        addByIndex(3, 2);
        addByIndex(4, 3);

        //頭部插入
        addByIndex(5, 0);
        printNode();   //輸出 5、1、2、3、4
        //中間插入
        addByIndex(5, 2);
        printNode();   //輸出 1、2、5、3、4
        //尾部插入
        addByIndex(5, 4);
        printNode();   //輸出 1、2、3、4、5
    }

    private static void addByIndex(int data, int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出鏈表節(jié)點范圍");
        }
        Node node = new Node(data);
        if (index == 0) {
            //插入到頭部
            node.setNext(headNode);
            headNode = node;
            if (size == 0) {
                lastNode = node;
            }
        } else if (index == size) {
            //插入到尾部
            lastNode.setNext(node);
            lastNode = node;
        } else {
            //插入到中間
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.getNext();
            prevNode.setNext(node);
            node.setNext(nextNode);
        }
        size++;
    }

    /**
     * 通過位置查找鏈表節(jié)點
     *
     * @param index
     * @return
     */
    private static Node get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出鏈表節(jié)點范圍");
        }
        Node temp = headNode;
        for (int i = 0; i < index; i++) {
            temp = temp.getNext();
        }
        return temp;
    }

    /**
     * 打印節(jié)點
     */
    private static void printNode() {
        while (headNode != null) {
            System.out.println(headNode.getDate());
            headNode = headNode.getNext();
        }
    }

}

/**
 * 定義一個節(jié)點
 *
 * @param <T>
 */
class Node<T> {
    /**
     * 節(jié)點中的數(shù)據(jù)
     */
    private T date;
    /**
     * 下一個節(jié)點的指針
     */
    private Node next;

    public Node(T date) {
        this.date = date;
    }

    public Node getNext() {
        return next;
    }

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

    public T getDate() {
        return date;
    }

    public void setDate(T date) {
        this.date = date;
    }
}

3.2 鏈表的刪除

鏈表刪除和增加一樣，也有三種情況：

• 刪除頭部

  

  刪除頭部操作只需要將頭部節(jié)點設(shè)置為當前頭部節(jié)點的下一個節(jié)點就可以了。

• 刪除中間

  

  刪除中間操作只需要將被刪除節(jié)點的前一個節(jié)點的后繼指針指向被刪除節(jié)點的下一個節(jié)點就可以了。

• 刪除尾部

  

  尾部刪除只需要將倒數(shù)第二個節(jié)點的后繼指針指向null就可以。

/**
 * @author: lixiaoshuang
 * @create: 2019-12-08 23:11
 **/
public class LinkedListAddDemo {

    //頭節(jié)點
    private static Node headNode = null;
    //尾節(jié)點
    private static Node lastNode = null;
    //鏈表的長度
    private static int size;

    public static void main(String[] args) {
        //初始化一個鏈表
        addByIndex(1, 0);
        addByIndex(2, 1);
        addByIndex(3, 2);
        addByIndex(4, 3);

        //頭部刪除
        delete(0);
        printNode();   //輸出 2、3、4
        //尾部刪除
        delete(3);
        printNode();   //輸出 1、2、3
        //中間刪除
        delete(2);
        printNode();   //輸出 1、2、4
    }

    /**
     * 鏈表刪除操作
     *
     * @param index
     */
    private static void delete(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出鏈表節(jié)點范圍");
        }
        if (index == 0) {
            //刪除頭部
            headNode = headNode.getNext();
        } else if (index == size - 1) {
            //刪除尾部
            Node prevNode = get(index - 1);
            prevNode.setNext(null);
            lastNode = prevNode;
        } else {
            //刪除中間
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.getNext().getNext();
            prevNode.setNext(nextNode);
        }
        size--;
    }

    /**
     * 通過位置查找鏈表節(jié)點
     *
     * @param index
     * @return
     */
    private static Node get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出鏈表節(jié)點范圍");
        }
        Node temp = headNode;
        for (int i = 0; i < index; i++) {
            temp = temp.getNext();
        }
        return temp;
    }

    /**
     * 打印節(jié)點
     */
    private static void printNode() {
        while (headNode != null) {
            System.out.println(headNode.getDate());
            headNode = headNode.getNext();
        }
    }

}

3.3 鏈表的修改

修改鏈表節(jié)點就直接將要修改的節(jié)點替換為新節(jié)點，第一步先將被修改的節(jié)點的前一個節(jié)點的后繼指針指向新節(jié)點，然后將新節(jié)點的后繼指針指向被修改節(jié)點的下一個節(jié)點，這里講的是如何修改一個節(jié)點，邏輯和上邊的增加刪除差不多，這里就舉一個中間修改的圖例吧。如果想不替換節(jié)點修改節(jié)點中的數(shù)據(jù)，這個比較簡單，大家可以自己實現(xiàn)下。

/**
 * @author: lixiaoshuang
 * @create: 2019-12-08 23:11
 **/
public class LinkedListOperationDemo {

    //頭節(jié)點
    private static Node headNode = null;
    //尾節(jié)點
    private static Node lastNode = null;
    //鏈表的長度
    private static int size;

    public static void main(String[] args) {
        //初始化一個鏈表
        addByIndex(1, 0);
        addByIndex(2, 1);
        addByIndex(3, 2);
        addByIndex(4, 3);

        //修改頭部
        update(5, 0);
        printNode();   //輸出 5、2、3、4
        //修改尾部
        update(5, 3);
        printNode();   //輸出 1、2、3、5
        //修改中間
        update(5, 1);
        printNode();   //輸出 1、5、3、4
    }

    /**
     * 鏈表的修改
     *
     * @param data
     * @param index
     */
    private static void update(int data, int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("超出鏈表節(jié)點范圍");
        }
        Node newNode = new Node(data);
        if (index == 0) {
            //修改頭部
            Node next = headNode.getNext();
            newNode.setNext(next);
            headNode = newNode;
        } else if (index == size) {
            //修改尾部
            Node prevNode = get(index - 1);
            prevNode.setNext(newNode);
            lastNode = newNode;
        } else {
            //修改中間
            Node prevNode = get(index - 1);
            Node nextNode = prevNode.getNext().getNext();
            prevNode.setNext(newNode);
            newNode.setNext(nextNode);
        }
    }

    /**
     * 通過位置查找鏈表節(jié)點
     *
     * @param index
     * @return
     */
    private static Node get(int index) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("超出鏈表節(jié)點范圍");
        }
        Node temp = headNode;
        for (int i = 0; i < index; i++) {
            temp = temp.getNext();
        }
        return temp;
    }

    /**
     * 打印節(jié)點
     */
    private static void printNode() {
        while (headNode != null) {
            System.out.println(headNode.getDate());
            headNode = headNode.getNext();
        }
    }

}

3.4 鏈表的查詢

說道查詢，不知道大家發(fā)現(xiàn)沒有，上邊的代碼中已經(jīng)有過實現(xiàn)了