Java描述數(shù)據(jù)結構學習之鏈表的增刪改查詳解
前言
鏈表是一種常見的基礎數(shù)據(jù)結構，它是一種線性表，但在內(nèi)存中它并不是順序存儲的，它是以鏈式進行存儲的，每一個節(jié)點里存放的是下一個節(jié)點的“指針”。在Java中的數(shù)據(jù)分為引用數(shù)據(jù)類型和基礎數(shù)據(jù)類型，在Java中不存在指針的概念，但是對于鏈表而言的指針，指的就是引用數(shù)據(jù)類型的地址。
鏈表和數(shù)組都是線性的數(shù)據(jù)結構，對于數(shù)組而言其長度是固定的，由于在內(nèi)存中其是連續(xù)的，因此更適合做查找與遍歷，而鏈表在內(nèi)存中是并不是順序存儲的，但是由于其是通過“指針”構成的，因此在插入、刪除時比較數(shù)組更為的方便。
下面的代碼通過內(nèi)部類并結合遞歸的方式來實現(xiàn)了一個簡單的用Java語言描述的鏈表的數(shù)據(jù)結構，下面話不多說了，來一起看看詳細的介紹吧
鏈表數(shù)據(jù)結構的定義
首先來看一下，鏈表數(shù)據(jù)結構的定義，代碼如下：
class NodeManager {
private Node root; // 根節(jié)點
private int currentIndex = 0; // 節(jié)點的序號，每次操作從0開始
public void add(int data) {}
public void delNode(int data) {}
public void print() {}
public boolean findNode(int data) {}
public boolean updateNode(int oldData, int newData) {}
// 向索引之前插入
public void insert(int index, int data) {}
// 誰擁有數(shù)據(jù)，誰提供方法
class Node {
private int data;
private Node next; // 把當前類型作為屬性
public Node(int data) {
this.data = data;
}
public void setData(int data) {
this.data = data;
}
public int getData() {
return data;
}
// 添加節(jié)點
public void addNode(int data) {}
// 刪除節(jié)點
public void delNode(int data) {}
// 輸出所有節(jié)點
public void printNode() {}
// 查找節(jié)點是否存在
public boolean findNode(int data) {}
// 修改節(jié)點
public boolean updateNode(int oldData, int newData) {}
// 插入節(jié)點
public void insertNode(int index, int data) {}
}
}
對于鏈表的定義來說，NodeManager類是用來管理鏈表操作的，而成員內(nèi)部類Node是用于提供鏈表數(shù)據(jù)與鏈式結構的。對于類的使用者來說，并不直接訪問數(shù)據(jù)，因此操作的是NodeManager類，而內(nèi)部類Node提供了真正的數(shù)據(jù)管理，因此Node類需要提供真正的數(shù)據(jù)操作方法，對于NodeManager類中也需要提供一套由外部來操作鏈表的方法。因此，在NodeManager類和Node類中都提供了看似相同的方法，但實際的意義并不相同。
下面來查看NodeManager類和Node類中的add()方法，代碼如下：
public void add(int data) {
if ( root == null ) {
root = new Node(data);
} else {
root.addNode(data);
}
}
// 添加節(jié)點
public void addNode(int data) {
if ( this.next == null ) {
this.next = new Node(data);
} else {
this.next.addNode(data);
}
}
代碼中上面的方法是NodeManager類中的方法，而下面的方法是Node類中的方法。
在Manager類中提供了一個root的成員變量，它用于管理鏈表的頭節(jié)點，因此在添加節(jié)點時，會先判斷root是否為空，如果為空則直接將節(jié)點由root來進行保存，如果root不為空，則通過Node類中的addNode()方法來進行添加，添加到思路是找到當前鏈表的最后一個節(jié)點，并將新添加到節(jié)點賦值給最后一個節(jié)點的next成員變量中。
鏈表增刪改查
對于鏈表的其他操作也是相同的思路，關于鏈表增刪改查和輸出的完整代碼如下：
class NodeManager {
private Node root; // 根節(jié)點
private int currentIndex = 0; // 節(jié)點的序號，每次操作從0開始
public void add(int data) {
if ( root == null ) {
root = new Node(data);
} else {
root.addNode(data);
}
}
public void delNode(int data) {
if ( root == null ) return ;
if ( root.getData() == data ) {
Node tmp = root;
root = root.next;
tmp = null;
} else {
root.delNode(data);
}
}
public void print() {
if ( root != null ) {
System.out.print(root.getData() + " ");
root.printNode();
System.out.println();
}
}
public boolean findNode(int data) {
if ( root == null ) return false;
if ( root.getData() == data ) {
return true;
} else {
return root.findNode(data);
}
}
public boolean updateNode(int oldData, int newData) {
if ( root == null ) return false;
if ( root.getData() == oldData ) {
root.setData(newData);
return true;
} else {
return root.updateNode(oldData, newData);
}
}
// 向索引之前插入
public void insert(int index, int data) {
if ( index < 0 ) return ;
currentIndex = 0;
if ( index == currentIndex ) {
Node newNode = new Node(data);
newNode.next = root;
root = newNode;
} else {
root.insertNode(index, data);
}
}
// 誰擁有數(shù)據(jù)，誰提供方法
class Node {
private int data;
private Node next; // 把當前類型作為屬性
public Node(int data) {
this.data = data;
}
public void setData(int data) {
this.data = data;
}
public int getData() {
return data;
}
// 添加節(jié)點
public void addNode(int data) {
if ( this.next == null ) {
this.next = new Node(data);
} else {
this.next.addNode(data);
}
}
// 刪除節(jié)點
public void delNode(int data) {
if ( this.next != null ) {
if ( this.next.getData() == data ) {
Node tmp = this.next;
this.next = this.next.next;
tmp = null;
} else {
this.next.delNode(data);
}
}
}
// 輸出所有節(jié)點
public void printNode() {
if ( this.next != null ) {
System.out.print(this.next.getData() + " ");
this.next.printNode();
}
}
// 查找節(jié)點是否存在
public boolean findNode(int data) {
if ( this.next != null ) {
if ( this.next.getData() == data ) {
return true;
} else {
return this.next.findNode(data);
}
}
return false;
}
// 修改節(jié)點
public boolean updateNode(int oldData, int newData) {
if ( this.next != null ) {
if ( this.next.getData() == oldData ) {
this.next.setData(newData);
return true;
} else {
return this.next.updateNode(oldData, newData);
}
}
return false;
}
// 插入節(jié)點
public void insertNode(int index, int data) {
currentIndex ++;
if ( index == currentIndex ) {
Node newNode = new Node(data);
newNode.next = this.next;
this.next = newNode;
} else {
this.next.insertNode(index, data);
}
}
}
}
以上就是鏈表基本操作的完整代碼，下面寫一個調(diào)用的代碼進行測試，代碼如下：
public class LinkList {
public static void main(String[] args) {
NodeManager nm = new NodeManager();
System.out.println("鏈表的添加（添加5、4、3、2、1）");
nm.add(5);
nm.add(4);
nm.add(3);
nm.add(2);
nm.add(1);
nm.print();
System.out.println("鏈表的刪除（刪除3）");
nm.delNode(3);
nm.print();
System.out.println("鏈表的查找（查找1）");
System.out.println(nm.findNode(1));
System.out.println("鏈表的查找（查找10）");
System.out.println(nm.findNode(10));
System.out.println("鏈表的更新（把1更新為10）");
nm.updateNode(1, 10);
nm.print();
System.out.println("鏈表的插入（在第1個位置插入20）");
nm.insert(1, 20);
nm.print();
System.out.println("鏈表的插入（在第0個位置插入30）");
nm.insert(0, 30);
nm.print();
}
}
將代碼編譯、運行，結果如下圖：
對于Java中的集合類中用到了不少的數(shù)據(jù)結構的知識，等自己狀態(tài)好的時候學習學習Java集合類的源碼。我會努力做一個初級程序員！
總結
以上就是這篇文章的全部內(nèi)容了，希望本文的內(nèi)容對大家的學習或者工作具有一定的參考學習價值，如果有疑問大家可以留言交流，謝謝大家對腳本之家的支持。
相關文章
這篇文章主要介紹了使用java爬蟲爬取想要的資源，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-08-08
Java如何通過"枚舉的枚舉"表示二級分類的業(yè)務場景
這篇文章主要介紹了Java如何通過"枚舉的枚舉"表示二級分類的業(yè)務場景問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-06-06
這篇文章主要介紹了Java調(diào)用Windows的DOS命令的方法，其主要內(nèi)容思路是實現(xiàn)調(diào)用Windows的ipconfig命令，然后將輸出的信息通過IO流輸出到控制臺。有需要的小伙伴參考下2015-02-02
springboot 使用QQ郵箱發(fā)送郵件的操作方法
這篇文章主要介紹了springboot使用QQ郵箱發(fā)送郵件功能，本文通過實例圖文相結合給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值,需要的朋友可以參考下2021-10-10
工作中,我們經(jīng)常會遇到需要進行各種排序的需求，本文主要介紹了Java對中文進行排序的實現(xiàn)示例，具有一定的參考價值，感興趣的可以了解一下2024-02-02
這篇文章主要介紹了java 整型數(shù)與Integer的緩存深入理解的相關資料,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了Maven插件的安裝及使用，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2020-09-09
MyBatis多表關聯(lián)查詢的實現(xiàn)示例
本文主要介紹了MyBatis多表關聯(lián)查詢的實現(xiàn)示例，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-03-03
這篇文章主要介紹了使用MQ消息隊列的優(yōu)缺點詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-07-07
這篇文章主要介紹了Java在PDF中添加表格過程詳解，本文將介紹通過Java編程在PDF文檔中添加表格的方法。添加表格時，可設置表格邊框、單元格對齊方式、單元格背景色、單元格合并、插入圖片、設置行高、列寬、字體、字號等,需要的朋友可以參考下2019-07-07