快捷導(dǎo)航

Java描述數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之鏈表的增刪改查詳解

更新時(shí)間：2018年05月21日 08:57:53 作者：tosser

這篇文章主要給大家介紹了關(guān)于Java描述數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)之鏈表的增刪改查的相關(guān)資料，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧

前言

鏈表是一種常見(jiàn)的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，它是一種線性表，但在內(nèi)存中它并不是順序存儲(chǔ)的，它是以鏈?zhǔn)竭M(jìn)行存儲(chǔ)的，每一個(gè)節(jié)點(diǎn)里存放的是下一個(gè)節(jié)點(diǎn)的“指針”。在Java中的數(shù)據(jù)分為引用數(shù)據(jù)類型和基礎(chǔ)數(shù)據(jù)類型，在Java中不存在指針的概念，但是對(duì)于鏈表而言的指針，指的就是引用數(shù)據(jù)類型的地址。

鏈表和數(shù)組都是線性的數(shù)據(jù)結(jié)構(gòu)，對(duì)于數(shù)組而言其長(zhǎng)度是固定的，由于在內(nèi)存中其是連續(xù)的，因此更適合做查找與遍歷，而鏈表在內(nèi)存中是并不是順序存儲(chǔ)的，但是由于其是通過(guò)“指針”構(gòu)成的，因此在插入、刪除時(shí)比較數(shù)組更為的方便。

下面的代碼通過(guò)內(nèi)部類并結(jié)合遞歸的方式來(lái)實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的用Java語(yǔ)言描述的鏈表的數(shù)據(jù)結(jié)構(gòu)，下面話不多說(shuō)了，來(lái)一起看看詳細(xì)的介紹吧

鏈表數(shù)據(jù)結(jié)構(gòu)的定義

首先來(lái)看一下，鏈表數(shù)據(jù)結(jié)構(gòu)的定義，代碼如下：

class NodeManager {
 private Node root; // 根節(jié)點(diǎn)
 private int currentIndex = 0; // 節(jié)點(diǎn)的序號(hào)，每次操作從0開(kāi)始
 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) {}
 // 誰(shuí)擁有數(shù)據(jù)，誰(shuí)提供方法
 class Node {
 private int data;
 private Node next; // 把當(dāng)前類型作為屬性
  public Node(int data) {
  this.data = data;
 }
 
 public void setData(int data) {
  this.data = data;
 }
 
 public int getData() {
  return data;
 }
 
 // 添加節(jié)點(diǎn)
 public void addNode(int data) {}
 
 // 刪除節(jié)點(diǎn)
 public void delNode(int data) {}
 
 // 輸出所有節(jié)點(diǎn)
 public void printNode() {}

 // 查找節(jié)點(diǎn)是否存在
 public boolean findNode(int data) {}
 
 // 修改節(jié)點(diǎn)
 public boolean updateNode(int oldData, int newData) {}
 
 // 插入節(jié)點(diǎn)
 public void insertNode(int index, int data) {}
 }
}

對(duì)于鏈表的定義來(lái)說(shuō)，NodeManager類是用來(lái)管理鏈表操作的，而成員內(nèi)部類Node是用于提供鏈表數(shù)據(jù)與鏈?zhǔn)浇Y(jié)構(gòu)的。對(duì)于類的使用者來(lái)說(shuō)，并不直接訪問(wèn)數(shù)據(jù)，因此操作的是NodeManager類，而內(nèi)部類Node提供了真正的數(shù)據(jù)管理，因此Node類需要提供真正的數(shù)據(jù)操作方法，對(duì)于NodeManager類中也需要提供一套由外部來(lái)操作鏈表的方法。因此，在NodeManager類和Node類中都提供了看似相同的方法，但實(shí)際的意義并不相同。

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

public void add(int data) {
 if ( root == null ) {
  root = new Node(data);
 } else {
  root.addNode(data);
 }
}

// 添加節(jié)點(diǎn)
public void addNode(int data) {
 if ( this.next == null ) {
  this.next = new Node(data);
 } else {
  this.next.addNode(data);
 }
}

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

在Manager類中提供了一個(gè)root的成員變量，它用于管理鏈表的頭節(jié)點(diǎn)，因此在添加節(jié)點(diǎn)時(shí)，會(huì)先判斷root是否為空，如果為空則直接將節(jié)點(diǎn)由root來(lái)進(jìn)行保存，如果root不為空，則通過(guò)Node類中的addNode()方法來(lái)進(jìn)行添加，添加到思路是找到當(dāng)前鏈表的最后一個(gè)節(jié)點(diǎn)，并將新添加到節(jié)點(diǎn)賦值給最后一個(gè)節(jié)點(diǎn)的next成員變量中。

鏈表增刪改查

對(duì)于鏈表的其他操作也是相同的思路，關(guān)于鏈表增刪改查和輸出的完整代碼如下：

class NodeManager {
 private Node root;  // 根節(jié)點(diǎn)
 private int currentIndex = 0; // 節(jié)點(diǎn)的序號(hào)，每次操作從0開(kāi)始
 
 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);
  }
 }
 
 // 誰(shuí)擁有數(shù)據(jù)，誰(shuí)提供方法
 class Node {
  private int data;
  private Node next; // 把當(dāng)前類型作為屬性
  
  public Node(int data) {
   this.data = data;
  }
  
  public void setData(int data) {
   this.data = data;
  }
  
  public int getData() {
   return data;
  }
  
  // 添加節(jié)點(diǎn)
  public void addNode(int data) {
   if ( this.next == null ) {
    this.next = new Node(data);
   } else {
    this.next.addNode(data);
   }
  }
  
  // 刪除節(jié)點(diǎn)
  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é)點(diǎn)
  public void printNode() {
   if ( this.next != null ) {
    System.out.print(this.next.getData() + " ");
    this.next.printNode();
   }
  }
  
  // 查找節(jié)點(diǎn)是否存在
  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é)點(diǎn)
  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é)點(diǎn)
  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);
   }
  }
 }
}

以上就是鏈表基本操作的完整代碼，下面寫(xiě)一個(gè)調(diào)用的代碼進(jìn)行測(cè)試，代碼如下：

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個(gè)位置插入20）");
  nm.insert(1, 20);
  nm.print();
  System.out.println("鏈表的插入（在第0個(gè)位置插入30）");
  nm.insert(0, 30);
  nm.print();
 }
}

將代碼編譯、運(yùn)行，結(jié)果如下圖：