摘要：今天來看另一種很基礎的數據結構鏈表。其次是尾結點的指針，它指向了，表示鏈表結束。但是，如果我們要查找鏈表數據怎么辦呢鏈表的內存不是連續的，不能像數組那樣根據下標訪問，所以只能通過遍歷鏈表來查找，時間復雜度為。

1. 概述

前面說到了數組，利用連續的內存空間來存儲相同類型的數據，其最大的特點是支持下標隨機訪問，但是刪除和插入的效率很低。今天來看另一種很基礎的數據結構——鏈表。鏈表不需要使用連續的內存空間，它使用指針將不連續的內存塊連接起來，形成一種鏈式結構。

2. 單鏈表

首先來看看單鏈表，存儲數據的內存塊叫做節點，每個節點保存了一個 next 指針，指向下一個節點的內存地址，結合下圖你就很容易看明白了：

其中有兩個節點指針比較的特殊，首先是鏈表頭節點的指針，它指向了鏈表的第一個節點的地址，利用它我們可以遍歷得到整個鏈表。其次是尾結點的指針，它指向了 null ，表示鏈表結束。

不難看出，單鏈表的最大特點便是使用指針來連接不連續的節點，這樣我們不用擔心擴容的問題了，并且，鏈表的插入和刪除操作也非常的高效，只需要改變指針的指向即可。

結合上圖不難理解，單鏈表能夠在 O(1) 復雜度內刪除和添加元素，這就比數組高效很多。但是，如果我們要查找鏈表數據怎么辦呢？鏈表的內存不是連續的，不能像數組那樣根據下標訪問，所以只能通過遍歷鏈表來查找，時間復雜度為 O(n)。下面是單鏈表的代碼示例：

public class SingleLinkedList {
    private Node head = null;//鏈表的頭節點

    //根據值查找節點
    public Node findByValue(int value) {
        Node p = head;
        while (p != null && p.getData() != value)
            p = p.next;
        return p;
    }

    //根據下標查找節點
    public Node findByIndex(int index) {
        Node p = head;
        int flag = 0;
        while (p != null){
            if (flag == index)
                return p;
            flag ++;
            p = p.next;
        }
        return null;
    }

    //插入節點到鏈表頭部
    public void insertToHead(Node node){
        if (head == null) head = node;
        else {
            node.next = head;
            head = node;
        }
    }
    public void insertToHead(int value){
        this.insertToHead(new Node(value));
    }

    //插入節點到鏈表末尾
    public void insert(Node node){
        if (head == null){
            head = node;
            return;
        }

        Node p = head;
        while (p.next != null) p = p.next;
        p.next = node;
    }
    public void insert(int value){
        this.insert(new Node(value));
    }

    //在某個節點之后插入節點
    public void insertAfter(Node p, Node newNode){
        if (p == null) return;
        newNode.next = p.next;
        p.next = newNode;
    }
    public void insertAfter(Node p, int value){
        this.insertAfter(p, new Node(value));
    }

    //在某個節點之前插入節點
    public void insertBefore(Node p, Node newNode){
        if (p == null) return;
        if (p == head){
            insertToHead(newNode);
            return;
        }
        //尋找節點p前面的節點
        Node pBefore = head;
        while (pBefore != null && pBefore.next != p){
            pBefore = pBefore.next;
        }

        if (pBefore == null) return;
        newNode.next = pBefore.next;
        pBefore.next = newNode;
    }
    public void insertBefore(Node p, int value){
        insertBefore(p, new Node(value));
    }

    //刪除節點
    public void deleteByNode(Node p){
        if (p == null || head == null) return;
        if (p == head){
            head = head.next;
            return;
        }
        Node pBefore = head;
        while (pBefore != null && pBefore.next != p){
            pBefore = pBefore.next;
        }

        if (pBefore == null) return;
        pBefore.next = pBefore.next.next;
    }

    //根據值刪除節點
    public void deleteByValue(int value){
        Node node = this.findByValue(value);
        if (node == null) return;
        this.deleteByNode(node);
    }

    //打印鏈表的所有節點值
    public void print(){
        Node p = head;
        while (p != null){
            System.out.print(p.getData() + "  ");
            p = p.next;
        }
        System.out.println();
    }
        //定義鏈表節點
    public static class Node{
        private int data;
        private Node next;

        public Node(int data) {
            this.data = data;
            this.next = null;
        }

        public int getData() {
            return data;
        }
    }
}

3. 循環鏈表

循環鏈表和單鏈表的唯一區別便是鏈表的尾結點指針并不是指向 null，而是指向了頭節點，這樣便形成了一個環形的鏈表結構：

4. 雙向鏈表

雙向鏈表，顧名思義，就是鏈表不只是存儲了指向下一個節點的 next 指針，還存儲了一個指向前一個節點的 prev 指針，如下圖：

為什么要使用這種具有兩個指針的鏈表呢？主要是為了解決鏈表刪除和插入操作的效率問題。

在單鏈表中，要刪除一個節點，必須找到其前面的節點，這樣就要遍歷鏈表，時間開銷較高。但是在雙向鏈表中，由于每個節點都保存了指向前一個節點的指針，這樣我們能夠在 O(1) 的時間復雜度內刪除節點。

插入操作也類似，比如要在節點 p 之前插入一個節點，那么也必須遍歷單鏈表找到 p 節點前面的那個節點。但是雙向鏈表可以直接利用前驅指針 prev 找到前一個節點，非常的高效。

這也是雙向鏈表在實際開發中用的更多的原因，雖然每個節點存儲了兩個指針，空間開銷更大，這就是一種典型的用空間換時間的思想。

下面是雙向鏈表的代碼示例：

public class DoubleLinkedList {
    private Node head = null;//鏈表的頭節點

    //在某個節點之前插入節點，這里方能體現出雙向鏈表的優勢
    public void insertBefore(Node p, Node newNode) {
        if (p == null) return;
        if(p == head) {
            this.insertToHead(newNode);
            return;
        }
        
        newNode.prev = p.prev;
        p.prev.next = newNode;
        
        newNode.next = p;
        p.prev = newNode;
    }
    public void insertBefore(Node p, int value) {
        this.insertBefore(p, new Node(value));
    }
    
    //刪除某個節點
    public void deleteByNode(Node node) {
        if(node == null || head == null) return;
        if (node == head) {
            head = head.next;
            if(head != null) head.prev = null;
            return;
        }
        Node prev = node.prev;
        Node next = node.next;
        prev.next = next;
        if(next != null) next.prev = prev;
    }
    
    //根據值刪除節點
    public void deleteByValue(int value) {
        Node node = this.findByValue(value);
        if (node == null) return;
        this.deleteByNode(node);
    }
   
    //定義鏈表節點
    public static class Node{
        private int data;
        private Node prev;//鏈表的前驅指針
        private Node next;//鏈表的后繼指針
        
        public Node(int data) {
            this.data = data;
            this.prev = null;
            this.next = null;
        }

        public int getData() {
            return data;
        }
    }
}