自寫鏈表極其反轉

來自專欄 java入門到精通1 人贊了文章

上一篇我們說到，數組是在內存中開闢一塊連續的內存空間，而且開闢完就無法改變大小，那麼如果我想充分利用內存以及使用一種可變的數據結構，上一次我們介紹了隊列，這次我們介紹下鏈表。

相對於隊列本質上通過數組來實現，依然是使用連續的內存空間，鏈表就是完全不需要使用連續空間了。它在內存中會呈現不規則的存儲，今天我們就來試著寫一個簡單的單向鏈表。

接下來我們來手寫一個單向鏈表：

首先，要寫個結點Node，結點裡面應該存儲數據和提供下一個結點的位置信息。因此我們設計一個結點Node類，它有儲存的數據和下一個結點的屬性，有獲得和設置它們的方法，為了方便我們再寫一個構造方法來在構造時給它賦數據，代碼如下：

public class Node { Object data; Node next;// 構造方法 public Node() {} public Node(Object data) { this.data = data; }// 設置數據的方法 public boolean setData(Object data) { this.data = data; return true; }// 設置下一個結點的方法 public boolean setNext(Node next) { this.next = next; return true; }// 獲得下一個結點的方法 public Node getNext() { return next; }// 獲得數據的方法 public Object get() { return data; }}

這樣我們就寫了一個節點Node，然後我們要寫一個鏈表利用這些結點連接一串。這樣的一個鏈表需要有數據結構的基本方法——增、刪、查、改。另外，為了更好的管理鏈表實現增刪查改，我們需要一個root根結點的輔助，於是

Node root;//root結點 int size;//已經存儲的結點數 Node flag ;//代表指向的最後一個結點，因為我們要從尾巴往單向鏈表裡加數據。public 鏈表類名(){ root = new Node(); }

我們直接在鏈表構造方法里new上root結點，當然也可以在添加方法里new，下面是鏈表的添加方法

public boolean add(Object data){ if (size == 0) {//如果是第一個添加的話 Node start = new Node(data);//一個start結點對象 root.setNext(start); flag = start;//flag指向鏈表的最後一個結點 size++; return true; }else{ Node new_node = new Node(data); flag.setNext(new_node); flag = new_node;//讓flag始終指向末端結點 size++; return true; } }

有了增加方法肯定還有刪除方法，刪除方法其實就是把鏈表中指向要刪除結點的結點直接跳過要刪除的結點指向下一個節點，把要刪除的結點的指向置空。這樣這個孤立的結點就會自動被GC了。

public Object remove(int index){ check(index); Node a = root; for(int i=0;i<index;i++){ a = a.getNext(); }//遍歷到a為要刪除結點的上一個結點 Node b = a.getNext(); b.setNext(null); a.setNext(a.getNext().getNext()); size--; return b.get(); }

接下來是修改方法

public boolean set(int index,Object data){ check(index);//檢查index是否合法 Node a = root.getNext(); for(int i=0;i<index;i++){ a=a.getNext(); } a.setData(data); return true; }

查方法

public Node get(int index){ check(index); Node a = root.getNext(); for(int i=0;i<index;i++){ a=a.getNext(); }//得到的a就是我們要找的結點，index從0開始 return a; }

接下來我來寫一個最常用的鏈表反轉的方法，先看代碼

public void reverse(){ if(size==0||size==1){ return ;} Node tem1 = this.get(0); Node tem2 = this.get(1); while(tem2.getNext() != null){ Node tem = tem2.getNext(); tem2.setNext(tem1); tem1 = tem2; tem2 = tem; } tem2.setNext(tem1); this.root.setNext(tem2); }

然後來看我的思路。

tem1初始位置為1，tem2初始位置為2，臨時的tem指向tem2的下一個,然後我們一一對其進行反向改指，直到tem2到末尾，最後將root指向最後一個結點，於是所有結點都反指了，而且時間只用了O(N)。這也是最常用的單向鏈表反向的方法！

最後，歡迎加我微信A1395349613，一起討論數據結構問題！

推薦閱讀：