從數組與鏈表到單鏈表的反轉，一文帶你吃透

作者：鴨血粉絲 2020-02-07 11:07:53

開發后端

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

[[314217]]

阿粉發現大家在說鏈表的時候，就會常說另外一個概念：數組。

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

數組與鏈表

數組最大的一個特點就是，需要一塊連續的內存空間。假設現在內存空間剩余了 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) ，所以在開發中它是比較受歡迎的。而在這其中體現的一個最重要的思想就是：空間換時間。

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

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

單鏈表反轉代碼實現

/** 
 * 鏈表反轉 
 */ 
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; 
    } 
}