數據結構（三）–鏈表

文章目錄

• 數據結構（三）--鏈表
• • 介紹
  • 單鏈表
  • • 代碼實現
    • 翻轉鏈表
    • 取出倒數第n個有效節點

介紹

鏈表又分：

• 單鏈表
• 雙鏈表

單鏈表

• 頭節點不存儲數據，所有操作臨時引用指向head；
• 刪除/插入節點：先判斷當前節點是否滿足刪除或插入條件，然后判斷是否可以移動，最后移動（反復）
• 遍歷節點：判斷是否可以移動，移動，打印
• 打印某一節點：判斷是否可以移動，移動，判斷當前節點是否可以打印（反復）

代碼實現

先實現節點

根據需要可以將數據域data的類型改為泛型**< T >**

public class NodeT<T>{private T data;private Node next;public NodeT(){}public NodeT(T data,Node next){this.data = data;this.next = next;}public Node getNext() {return next;}public void setNext(Node next) {this.next = next;}public T getData() {return data;}public void setData(T data) {this.data = data;}@Overridepublic String toString() {return "NodeT{" +"data='" + data + '\''+"}";} }

實現單鏈表

public class LinelistT<T> {private NodeT head ;public LinelistT(){head = new NodeT<T>(null,null);}//打印所有節點public void printNodes(){NodeT tepm = head;while (true){if (tepm.getNext()==null) break;tepm = tepm.getNext();System.out.println(tepm);}}//尾部添加數據public void addNode(T data){NodeT<T> node = new NodeT<T>(data,null);NodeT<T> temp = head;while (true){if (temp.getNext()==null){temp.setNext(node);break;}temp = temp.getNext();}}//插入數據public void insertNode(int index,T data){//判斷越界if (index<=0) throw new RuntimeException("越界");NodeT<T> node = new NodeT<T>(data,null);NodeT temp = head;int i=0;while (true){//添加節點if (i==index-1){node.setNext(temp.getNext());temp.setNext(node);break;}//判斷越界if (temp.getNext()==null) throw new RuntimeException("越界！！！");//移動temp = temp.getNext();i++;}}//刪除節點public NodeT deleteNode(int index) {//判斷越界if (index <=0 )new RuntimeException("越界!!!");NodeT temp = head;int i = 0;while (true) {//刪除節點if (i == index - 1 && temp.getNext() != null) {NodeT temp2 = temp.getNext();temp.setNext(temp2.getNext());temp2.setNext(null);return temp2;}//判斷越界if (temp.getNext()==null)throw new RuntimeException("越界!!!");//移動temp = temp.getNext();i++;}}//打印某一節點public void printNode(int index){//判斷越界if (index<=0) new RuntimeException("越界!!!");NodeT temp = head;int i=0;while (true){//判斷越界if (temp.getNext()==null) {new RuntimeException("越界!!!");}//移動i++;temp = temp.getNext();//打印if (i==index){System.out.println(temp);break;}}}}

主函數

public static void main(String[] args) {LinelistT<String> line = new LinelistT<String>();line.addNode("節點一");line.addNode("節點二");line.addNode("節點三");line.printNodes();System.out.println("-----------------------------");line.deleteNode(2);line.printNodes();System.out.println("-----------------------------");line.insertNode(2,"插入節點");line.printNodes();System.out.println("-----------------------------");}

結果

NodeT{data='節點一'} NodeT{data='節點二'} NodeT{data='節點三'} ----------------------------- NodeT{data='節點一'} NodeT{data='節點三'} ----------------------------- NodeT{data='節點一'} NodeT{data='插入節點'} NodeT{data='節點三'} -----------------------------

翻轉鏈表

在單鏈表中添加以下方法即可，思路如下：

• 創建一個新的臨時鏈表reverseHead
• 取出原鏈表的第一個有效節點
• 將原鏈表的第一個有效節點插入到臨時鏈表的第一個有效位置（head后面）
• 將原鏈表Heda的next指向reverseHead的next即可

public void reverse(){//創建新鏈表LinelistT reverseHead = new LinelistT<T>();NodeT temp = head;while (true){try {NodeT node = this.deleteNode(1);reverseHead.insertNode(1,node.getData());}catch (RuntimeException e) {break;}}head.setNext(reverseHead.head.getNext());}

取出倒數第n個有效節點

獲取有效節點個數

先寫一個統計有效節點個數的函數，當然如果你想優化的話，完全可以在鏈表類中添加一個私有屬性Num，用來記錄個數，因為這里沒寫，所以就多寫一個函數去遍歷。

public int getNodeNum(){NodeT temp = head;int num = 0;while (true){//判斷是否到尾部if (temp.getNext() == null) return num;temp = temp.getNext();num++;}}

獲取倒數有效節點

public NodeT<T> getNodeByreverse(int reverseIndex){int num = this.getNodeNum();if (reverseIndex>num || reverseIndex<=0) throw new RuntimeException("越界");NodeT<T> temp = head;int i = 0;while (true){if (i==num-reverseIndex+1) break;temp = temp.getNext();i++;}return temp;}

總結

以上是生活随笔為你收集整理的数据结构（三）--链表的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。