Java描述數據結構之鏈表的增刪改查

来源:https://www.cnblogs.com/tosser/archive/2018/05/20/9064671.html
-Advertisement-
Play Games

鏈表是一種常見的基礎數據結構，它是一種線性表，但在記憶體中它並不是順序存儲的，它是以鏈式進行存儲的，每一個節點里存放的是下一個節點的“指針”。在Java中的數據分為引用數據類型和基礎數據類型，在Java中不存在指針的概念，但是對於鏈表而言的指針，指的就是引用數據類型的地址。 鏈表和數組都是線性的數據結 ...


　　鏈表是一種常見的基礎數據結構，它是一種線性表，但在記憶體中它並不是順序存儲的，它是以鏈式進行存儲的，每一個節點里存放的是下一個節點的“指針”。在Java中的數據分為引用數據類型和基礎數據類型，在Java中不存在指針的概念，但是對於鏈表而言的指針，指的就是引用數據類型的地址。

 

　　鏈表和數組都是線性的數據結構，對於數組而言其長度是固定的，由於在記憶體中其是連續的，因此更適合做查找與遍歷，而鏈表在記憶體中是並不是順序存儲的，但是由於其是通過“指針”構成的，因此在插入、刪除時比較數組更為的方便。

 

　　下麵的代碼通過內部類並結合遞歸的方式來實現了一個簡單的用Java語言描述的鏈表的數據結構。

 

　　首先來看一下，鏈表數據結構的定義，代碼如下：

 1 class NodeManager {
 2     private Node root;      // 根節點
 3     private int currentIndex = 0;   // 節點的序號，每次操作從0開始
 4     
 5     public void add(int data) {}
 6     public void delNode(int data) {}
 7     
 8     public void print() {}
 9     
10     public boolean findNode(int data) {}
11     
12     public boolean updateNode(int oldData, int newData) {}
13     
14     // 向索引之前插入
15     public void insert(int index, int data) {}
16     
17     // 誰擁有數據，誰提供方法
18     class Node {
19         private int data;
20         private Node next;  // 把當前類型作為屬性
21         
22         public Node(int data) {
23             this.data = data;
24         }
25         
26         public void setData(int data) {
27             this.data = data;
28         }
29         
30         public int getData() {
31             return data;
32         }
33         
34         // 添加節點
35         public void addNode(int data) {}
36         
37         // 刪除節點
38         public void delNode(int data) {}
39         
40         // 輸出所有節點
41         public void printNode() {}
42         
43         // 查找節點是否存在
44         public boolean findNode(int data) {}
45         
46         // 修改節點
47         public boolean updateNode(int oldData, int newData) {}
48         
49         // 插入節點
50         public void insertNode(int index, int data) {}
51     }
52 }

　　對於鏈表的定義來說，NodeManager類是用來管理鏈表操作的，而成員內部類Node是用於提供鏈表數據與鏈式結構的。對於類的使用者來說，並不直接訪問數據，因此操作的是NodeManager類，而內部類Node提供了真正的數據管理，因此Node類需要提供真正的數據操作方法，對於NodeManager類中也需要提供一套由外部來操作鏈表的方法。因此，在NodeManager類和Node類中都提供了看似相同的方法，但實際的意義並不相同。

　　下麵來查看NodeManager類和Node類中的add()方法，代碼如下：

 1 public void add(int data) {
 2     if ( root == null ) {
 3         root = new Node(data);
 4     } else {
 5         root.addNode(data);
 6     }
 7 }
 8 
 9 // 添加節點
10 public void addNode(int data) {
11     if ( this.next == null ) {
12         this.next = new Node(data);
13     } else {
14         this.next.addNode(data);
15     }
16 }

　　代碼中上面的方法是NodeManager類中的方法，而下麵的方法是Node類中的方法。

　　在Manager類中提供了一個root的成員變數，它用於管理鏈表的頭節點，因此在添加節點時，會先判斷root是否為空，如果為空則直接將節點由root來進行保存，如果root不為空，則通過Node類中的addNode()方法來進行添加，添加到思路是找到當前鏈表的最後一個節點，並將新添加到節點賦值給最後一個節點的next成員變數中。

　　對於鏈表的其他操作也是相同的思路，關於鏈表增刪改查和輸出的完整代碼如下：

  1 class NodeManager {
  2     private Node root;      // 根節點
  3     private int currentIndex = 0;   // 節點的序號，每次操作從0開始
  4     
  5     public void add(int data) {
  6         if ( root == null ) {
  7             root = new Node(data);
  8         } else {
  9             root.addNode(data);
 10         }
 11     }
 12     public void delNode(int data) {
 13         if ( root == null ) return ;
 14         if ( root.getData() == data ) {
 15             Node tmp = root;
 16             root = root.next;
 17             tmp = null;
 18         } else {
 19             root.delNode(data);
 20         }
 21     }
 22     
 23     public void print() {
 24         if ( root != null ) {
 25             System.out.print(root.getData() + " ");
 26             root.printNode();
 27             System.out.println();
 28         }
 29     }
 30     
 31     public boolean findNode(int data) {
 32         if ( root == null ) return false;
 33         if ( root.getData() == data ) {
 34             return true;
 35         } else {
 36             return root.findNode(data);
 37         }        
 38     }
 39     
 40     public boolean updateNode(int oldData, int newData) {
 41         if ( root == null ) return false;
 42         if ( root.getData() == oldData ) {
 43             root.setData(newData);
 44             return true;
 45         } else {
 46             return root.updateNode(oldData, newData);
 47         }
 48     }
 49     
 50     // 向索引之前插入
 51     public void insert(int index, int data) {
 52         if ( index < 0 ) return ;
 53         currentIndex = 0;
 54         if ( index == currentIndex ) {
 55             Node newNode = new Node(data);
 56             newNode.next = root;
 57             root = newNode;
 58         } else {
 59             root.insertNode(index, data);
 60         }
 61     }
 62     
 63     // 誰擁有數據，誰提供方法
 64     class Node {
 65         private int data;
 66         private Node next;  // 把當前類型作為屬性
 67         
 68         public Node(int data) {
 69             this.data = data;
 70         }
 71         
 72         public void setData(int data) {
 73             this.data = data;
 74         }
 75         
 76         public int getData() {
 77             return data;
 78         }
 79         
 80         // 添加節點
 81         public void addNode(int data) {
 82             if ( this.next == null ) {
 83                 this.next = new Node(data);
 84             } else {
 85                 this.next.addNode(data);
 86             }
 87         }
 88         
 89         // 刪除節點
 90         public void delNode(int data) {
 91             if ( this.next != null ) {
 92                 if ( this.next.getData() == data ) {
 93                     Node tmp = this.next;
 94                     this.next = this.next.next;
 95                     tmp = null;
 96                 } else {
 97                     this.next.delNode(data);
 98                 }
 99             }
100         }
101         
102         // 輸出所有節點
103         public void printNode() {
104             if ( this.next != null ) {
105                 System.out.print(this.next.getData() + " ");
106                 this.next.printNode();
107             }
108         }
109         
110         // 查找節點是否存在
111         public boolean findNode(int data) {
112             if ( this.next != null ) {
113                 if ( this.next.getData() == data ) {
114                     return true;
115                 } else {
116                     return this.next.findNode(data);
117                 }
118             }
119             
120             return false;
121         }
122         
123         // 修改節點
124         public boolean updateNode(int oldData, int newData) {
125             if ( this.next != null ) {
126                 if ( this.next.getData() == oldData ) {
127                     this.next.setData(newData);
128                     return true;
129                 } else {
130                     return this.next.updateNode(oldData, newData);
131                 }
132             }
133             return false;
134         }
135         
136         // 插入節點
137         public void insertNode(int index, int data) {
138             currentIndex ++;
139             if ( index == currentIndex ) {
140                 Node newNode = new Node(data);
141                 newNode.next = this.next;
142                 this.next = newNode;
143             } else {
144                 this.next.insertNode(index, data);
145             }
146         }
147     }
148 }

　　以上就是鏈表基本操作的完整代碼，下麵寫一個調用的代碼進行測試，代碼如下：

 1 public class LinkList {
 2     public static void main(String[] args) {
 3         NodeManager nm = new NodeManager();
 4         System.out.println("鏈表的添加（添加5、4、3、2、1）");
 5         nm.add(5);
 6         nm.add(4);
 7         nm.add(3);
 8         nm.add(2);
 9         nm.add(1);
10         nm.print();
11         System.out.println("鏈表的刪除（刪除3）");
12         nm.delNode(3);
13         nm.print();
14         System.out.println("鏈表的查找（查找1）");
15         System.out.println(nm.findNode(1));
16         System.out.println("鏈表的查找（查找10）");
17         System.out.println(nm.findNode(10));
18         System.out.println("鏈表的更新（把1更新為10）");
19         nm.updateNode(1, 10);
20         nm.print();
21         System.out.println("鏈表的插入（在第1個位置插入20）");
22         nm.insert(1, 20);
23         nm.print();
24         System.out.println("鏈表的插入（在第0個位置插入30）");
25         nm.insert(0, 30);
26         nm.print();
27     }
28 }

　　將代碼編譯、運行，結果如下圖：

 

　　對於Java中的集合類中用到了不少的數據結構的知識，等自己狀態好的時候學習學習Java集合類的源碼。我會努力做一個初級程式員！


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 中介者模式-Mediator Pattern(Java實現)
    中介者模式, Mediator Pattern, Java實現 ...
  • Spring MVC 的 Java Config ( 非 XML ) 配置方式
    索引： 開源Spring解決方案--lm.solution 參看代碼 GitHub： solution/pom.xml web/pom.xml web.xml WebInitializer.java WebConfig.java RootConfig.java 一、引入必要類庫 spring-con ...
  • ACM
    ACM 2000 輸入三個字元後，按各個字元的ASCⅡ碼從小打到的順序輸出這三個字元。 import java.util.Scanner; public class Lengxc {public static void main(String[] args) {Scanner scanner = n ...
  • 門面模式-Facade Pattern(Java實現)
    門面模式-Facade Pattern 為一個複雜的模塊或子系統提供一個簡單的供外界訪問的介面 本文中代碼的例子如下: 一個礦場有很多礦工, 礦工的職責也都不一樣. 但一樣的是什麼呢? 一樣的就是每個礦工每天都在重覆一樣的事情....起床, 上班, 工作, 下班, 睡覺...... 要想管理這麼多礦 ...
  • 實現兩個矩陣相乘的C語言程式
    程式功能：實現兩個矩陣相乘的C語言程式，並將其輸出 代碼如下： 運行結果： ...
  • 保護代理模式-Access Proxy(Java實現)
    保護代理模式-Access Proxy 保護代理模式(Access Proxy), 也叫Protect Proxy. 這種代理用於對真實對象的功能做一些訪問限制, 在代理層做身份驗證. 通過了驗證, 才調用真實的主體對象的相應方法. 模擬場景如下: 某平臺的系統有查詢功能, 可以根據關鍵詞進行查詢, ...
  • Python常用正則表達式總結
    1 非負整數：^\d+$ 2 3 正整數：^[0-9]*[1-9][0-9]*$ 4 5 非正整數：^((-\d+)|(0+))$ 6 7 負整數：^-[0-9]*[1-9][0-9]*$ 8 9 整數：^-?\d+$ 10 11 非負浮點數：^\d+(\.\d+)?$ 12 13 正浮點數 : ^... ...
  • SpringBoot開源項目(企業信息化基礎平臺)
    JEEPlatform 一款企業信息化開發基礎平臺，可以用於快速構建企業後臺管理系統，集成了OA(辦公自動化)、SCM(供應鏈系統)、ERP(企業資源管理系統)、CMS(內容管理系統)、CRM(客戶關係管理系統)等企業系統的通用業務功能。Github鏈接：https://github.com/u01 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類