[[314217]]

 

阿粉發(fā)現(xiàn)大家在說鏈表的時候，就會常說另外一個概念：數(shù)組。

既然數(shù)組和鏈表，常常會拿到一起做比較。那咱們今天就先來說說數(shù)組和鏈表。

數(shù)組與鏈表

數(shù)組最大的一個特點就是，需要一塊連續(xù)的內(nèi)存空間。假設(shè)現(xiàn)在內(nèi)存空間剩余了 1MB ，但是它不是連續(xù)的，這個時候申請一個大小為 1MB 的數(shù)組，會告訴你申請失敗，因為這個內(nèi)存空間不連續(xù)。

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

如果只是理解到了這個層面，你是不是會覺得，我以后一直用鏈表這種數(shù)據(jù)結(jié)構(gòu)就可以了?不不不，數(shù)組也有它自己的優(yōu)勢。

阿粉在查閱相關(guān)資料時，發(fā)現(xiàn)數(shù)組簡單易用，又因為它使用的是連續(xù)內(nèi)存空間，就可以借助 CPU 的緩存機制，預(yù)讀數(shù)組中的數(shù)據(jù)，因而訪問效率更高，所以在插入，刪除操作比較少，而查詢比較多的情況下，使用數(shù)組是比較有優(yōu)勢的。

鏈表

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

鏈表鏈表分為單鏈表，循環(huán)鏈表，和雙向鏈表。

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

單鏈表是這樣的：

 

 

 

 

循環(huán)鏈表是這樣的：

 

 

 

 

但是在實際開發(fā)中，更加常用的鏈表結(jié)構(gòu)是：雙向鏈表。

它的結(jié)構(gòu)是這樣的：

 

 

 

 

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

既然它占用內(nèi)存較多，為什么在實際開發(fā)中還比較常用呢，這里面有一個思想在里面，咱們具體來講講。

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

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

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

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

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

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

光說不做不符合阿粉的風(fēng)格啊。阿粉今天實現(xiàn)了一個比較常見的單鏈表操作---單鏈表反轉(zhuǎn)

單鏈表反轉(zhuǎn)代碼實現(xiàn)

 

/** 
 * 鏈表反轉(zhuǎn) 
 */ 
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); 
        // 調(diào)用反轉(zhuǎn)方法 
        Node reverse=reverse(node1); 
        System.out.println(reverse); 
    } 
     
    /** 
     *單鏈表反轉(zhuǎn) 
     * @param list 為傳入的單鏈表 
     */ 
    public static Node reverse(Node list){ 
        Node current=list, // 定義 current 為當前鏈表 
                afterReverse=null;   // 定義 afterReverse 為轉(zhuǎn)換之后的新鏈表,初始為 null 
        // 當前鏈表不為空,進行反轉(zhuǎn)操作 
        while (current!=null){ 
            // 1. 保存當前節(jié)點的 next 指針指向的鏈表 
            Node next=current.next; 
            // 2. 將當前節(jié)點的 next 指針指向反轉(zhuǎn)之后的新鏈表 
            current.next=afterReverse; 
            // 3. 保存當前的鏈表狀態(tài)到新鏈表中 
            afterReverse=current; 
            // 4. 將當前節(jié)點指針后移一位,進行下一次循環(huán) 
            current=next; 
        } 
        return afterReverse; 
    } 
} 

接下來咱們斷點調(diào)試，看看每次結(jié)果：

初始狀態(tài)：

 

 

 

 

第一次循環(huán)結(jié)束

 

 

 

 

第二次循環(huán)結(jié)束

 

 

 

 

第三次循環(huán)結(jié)束

 

 

 

第四次循環(huán)結(jié)束

 

 

 

 

第五次循環(huán)結(jié)束

 

 

 

在寫這篇文章的時候，特別是單鏈表反轉(zhuǎn)那一塊，考慮了很久，借鑒網(wǎng)上思路做出來，有的思路真的是很巧妙。

在阿粉的一步步斷點調(diào)試 + 手寫代碼下，終于拿下了單鏈表反轉(zhuǎn)。你掌握了嘛?

參考《極客時間》算法面試通關(guān)40講