數組與鏈表

數組最大的一個特點就是，需要一塊連續的內存空間。假設現在內存空間剩餘了 1MB ，但是它不是連續的，這個時候申請一個大小為 1MB 的數組，會告訴你申請失敗，因為這個內存空間不連續。

鏈表最大的一個特點是，不需要一塊連續的內存空間。還是上面那個例子，如果申請的不是大小為 1MB 的數組，而是鏈表，就會申請成功。

如果只是理解到了這個層面，你是不是會覺得，我以後一直用鏈表這種數據結構就可以了？不不不，數組也有它自己的優勢。

阿粉在查閱相關資料時，發現數組簡單易用，又因為它使用的是連續內存空間，就可以藉助 CPU 的緩存機制，預讀數組中的數據，因而訪問效率更高，所以在插入，刪除操作比較少，而查詢比較多的情況下，使用數組是比較有優勢的。

鏈表在內存中不是連續存儲，對 CPU 緩存機制不夠友好，也就沒辦法進行有效預讀。所以鏈表適用於在插入，刪除操作比較多的情況下使用。

鏈表

鏈表分為單鏈表，循環鏈表，和雙向鏈表。

對於單鏈表來說，它的第一個節點也就是頭結點記錄著鏈表的基地址，而最後一個節點也就是尾節點則指向一個空地址 NULL ，循環鏈表也可以理解成特殊的單鏈表，只不過尾節點由原來指向一個空地址 NULL 改為了指向頭結點。

單鏈表是這樣的：

循環鏈表是這樣的：

但是在實際開發中，更加常用的鏈表結構是：雙向鏈表。

它的結構是這樣的：

我們能夠看到它的特點是：佔用內存較多，支持雙向遍歷。因為它有兩個指針，所以相對單鏈表，一個數據就會多佔用一些內存。

既然它佔用內存較多，為什麼在實際開發中還比較常用呢，這裡面有一個思想在裡面，咱們具體來講講。

我們知道，單鏈表，雙鏈表在刪除的時候，時間複雜度為 O(1) ，但是在實際開發中它的時間複雜度並不是這樣，為什麼呢?

這樣想，一般在做數據刪除的時候，你的操作是怎樣的?

首先，查找在節點中「值等於給定某個值」的節點，找到之後再做刪除對吧?也就是說在刪除之前，是需要做查找這個工作的。而單向鏈表和雙向鏈表在查找的時候時間複雜度為 O(n) ，因為它為了找到這個要刪除的元素，需要將所有的元素都遍歷一遍。將上面過程梳理一下就是，查找時間複雜度為 O(n) ，刪除時間複雜度為 O(1) ，總的時間複雜度為 O(n) 。

以上過程在雙鏈表中是怎樣的呢?因為雙鏈表支持雙向遍歷，所以查找這個操作對它來說時間複雜度為 O(1) ，因為它是雙向遍歷，所以在查找元素時，不需要將所有的元素進行遍歷，刪除時時間複雜度為 O(1) ，總的時間複雜度為 O(1) 。

因為雙向鏈表的時間複雜度為 O(1) ，所以在開發中它是比較受歡迎的。而在這其中體現的一個最重要的思想就是：空間換時間。

當內存空間相對時間來說不是那麼重要的話，那我們是不是就可以忽略次要的因素，著重解決主要矛盾?

光說不做不符合阿粉的風格啊。阿粉今天實現了一個比較常見的單鏈表操作---單鏈表反轉

單鏈表反轉代碼實現

<code>/** * 鏈表反轉 */public class ReverseList {    public static class Node{        private int data;        private Node next;        public Node(int data , Node next){            this.data=data;            this.next=next;        }        public int getData(){            return data;        }    }    public static void main(String[] args){        // 初始化單鏈表        Node node5=new Node(5,null);        Node node4=new Node(4,node5);        Node node3=new Node(3,node4);        Node node2=new Node(2,node3);        Node node1=new Node(1,node2);        // 調用反轉方法        Node reverse=reverse(node1);        System.out.println(reverse);    }    /**     *單鏈表反轉     * @param list 為傳入的單鏈表     */    public static Node reverse(Node list){        Node current=list, // 定義 current 為當前鏈表                afterReverse=null;   // 定義 afterReverse 為轉換之後的新鏈表,初始為 null        // 當前鏈表不為空,進行反轉操作        while (current!=null){            // 1. 保存當前節點的 next 指針指向的鏈表            Node next=current.next;            // 2. 將當前節點的 next 指針指向反轉之後的新鏈表            current.next=afterReverse;            // 3. 保存當前的鏈表狀態到新鏈表中            afterReverse=current;            // 4. 將當前節點指針後移一位,進行下一次循環            current=next;        }        return afterReverse;    }}/<code>

接下來咱們斷點調試，看看每次結果：

初始狀態：

第一次循環結束

第二次循環結束

第三次循環結束

第四次循環結束

第五次循環結束

閱讀更多 Java高級架構師 的文章

關鍵字: 中央處理器 鏈表 阿粉