web數(shù)組與鏈表到單鏈表的反轉怎么理解

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

讓客戶滿意是我們工作的目標，不斷超越客戶的期望值來自于我們對這個行業(yè)的熱愛。我們立志把好的技術通過有效、簡單的方式提供給客戶，將通過不懈努力成為客戶在信息化領域值得信任、有價值的長期合作伙伴，公司提供的服務項目有：主機域名、網頁空間、營銷軟件、網站建設、赤峰網站維護、網站推廣。

數(shù)組與鏈表

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

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

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

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

鏈表

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

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

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

單鏈表是這樣的：

web數(shù)組與鏈表到單鏈表的反轉怎么理解

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

web數(shù)組與鏈表到單鏈表的反轉怎么理解

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

它的結構是這樣的：

web數(shù)組與鏈表到單鏈表的反轉怎么理解

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

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

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

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

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

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

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

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

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

單鏈表反轉代碼實現(xià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);         // 調用反轉方法         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. 保存當前節(jié)點的 next 指針指向的鏈表             Node next=current.next;             // 2. 將當前節(jié)點的 next 指針指向反轉之后的新鏈表             current.next=afterReverse;             // 3. 保存當前的鏈表狀態(tài)到新鏈表中             afterReverse=current;             // 4. 將當前節(jié)點指針后移一位,進行下一次循環(huán)             current=next;         }         return afterReverse;     } }

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

初始狀態(tài)：

web數(shù)組與鏈表到單鏈表的反轉怎么理解