手撕數據結構與算法

前言

底層基礎決定上層發展。

點個贊在看，讓我知道你在關注技術。

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

本系列內容預覽：

1. 什么是鏈表？

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

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

1.1 單向鏈表

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

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

頭節點：鏈表中第一個節點，頭節點中可以不存儲數據。

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

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

1.2 單向循環鏈表

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

1.3 雙向鏈表

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

1.4 雙向循環鏈表

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

2. 鏈表VS數組

說了半天鏈表，不知道大家了解了沒有，我自己都感覺很枯燥。可是基礎就是這樣，只有學好了基礎才能更好的向上爬。現在我們來看下鏈表和我們之前講的數組有什么區別。首先它們兩個的存儲結構就不一樣，數組是順序存儲結構，也就是說它在內存中是一塊連續的存儲空間，而鏈表是鏈式存儲結構，也就是非連續的。我們來看下它們在內存中表現：

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

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

3. 鏈表的基本操作

3.1 鏈表的增加

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

• 增加到頭部

  

  增加到頭部一共分為兩步，第一步將新節點的后繼指針指向原頭節點，第二步是將新節點變為頭節點。這樣就完成了頭部添加。

• 增加到中間

  

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

• 增加到尾部

  

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

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

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

    //頭節點
    private static Node headNode = null;
    //尾節點
    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("超出鏈表節點范圍");
        }
        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++;
    }

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

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

}

/**
 * 定義一個節點
 *
 * @param <T>
 */
class Node<T> {
    /**
     * 節點中的數據
     */
    private T date;
    /**
     * 下一個節點的指針
     */
    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 鏈表的刪除

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

• 刪除頭部

  

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

• 刪除中間

  

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

• 刪除尾部

  

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

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

    //頭節點
    private static Node headNode = null;
    //尾節點
    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("超出鏈表節點范圍");
        }
        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--;
    }

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

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

}

3.3 鏈表的修改

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

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

    //頭節點
    private static Node headNode = null;
    //尾節點
    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("超出鏈表節點范圍");
        }
        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);
        }
    }

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

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

}

3.4 鏈表的查詢

說道查詢，不知道大家發現沒有，上邊的代碼中已經有過實現了