web數組與鏈表到單鏈表的反轉怎么理解

本篇內容主要講解“web數組與鏈表到單鏈表的反轉怎么理解”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“web數組與鏈表到單鏈表的反轉怎么理解”吧!

數組與鏈表

數組最大的一個特點就是，需要一塊連續的內存空間。假設現在內存空間剩余了 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;     } }

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

初始狀態：

第一次循環結束

第二次循環結束

第三次循環結束

第四次循環結束

第五次循環結束

到此，相信大家對“web數組與鏈表到單鏈表的反轉怎么理解”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！