Java描述数据结构学习之链表的增删改查详解

前言

链表是一种常见的基础数据结构，它是一种线性表，但在内存中它并不是顺序存储的，它是以链式进行存储的，每一个节点里存放的是下一个节点的“指针”。在java中的数据分为引用数据类型和基础数据类型，在java中不存在指针的概念，但是对于链表而言的指针，指的就是引用数据类型的地址。

链表和数组都是线性的数据结构，对于数组而言其长度是固定的，由于在内存中其是连续的，因此更适合做查找与遍历，而链表在内存中是并不是顺序存储的，但是由于其是通过“指针”构成的，因此在插入、删除时比较数组更为的方便。

下面的代码通过内部类并结合递归的方式来实现了一个简单的用java语言描述的链表的数据结构，下面话不多说了，来一起看看详细的介绍吧

链表数据结构的定义

首先来看一下，链表数据结构的定义，代码如下：

class nodemanager {
 private node root; // 根节点
 private int currentindex = 0; // 节点的序号，每次操作从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) {}
 // 谁拥有数据，谁提供方法
 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;
 }
 
 // 添加节点
 public void addnode(int data) {}
 
 // 删除节点
 public void delnode(int data) {}
 
 // 输出所有节点
 public void printnode() {}

 // 查找节点是否存在
 public boolean findnode(int data) {}
 
 // 修改节点
 public boolean updatenode(int olddata, int newdata) {}
 
 // 插入节点
 public void insertnode(int index, int data) {}
 }
}

对于链表的定义来说，nodemanager类是用来管理链表操作的，而成员内部类node是用于提供链表数据与链式结构的。对于类的使用者来说，并不直接访问数据，因此操作的是nodemanager类，而内部类node提供了真正的数据管理，因此node类需要提供真正的数据操作方法，对于nodemanager类中也需要提供一套由外部来操作链表的方法。因此，在nodemanager类和node类中都提供了看似相同的方法，但实际的意义并不相同。

下面来查看nodemanager类和node类中的add()方法，代码如下：

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

// 添加节点
public void addnode(int data) {
 if ( this.next == null ) {
  this.next = new node(data);
 } else {
  this.next.addnode(data);
 }
}

代码中上面的方法是nodemanager类中的方法，而下面的方法是node类中的方法。

在manager类中提供了一个root的成员变量，它用于管理链表的头节点，因此在添加节点时，会先判断root是否为空，如果为空则直接将节点由root来进行保存，如果root不为空，则通过node类中的addnode()方法来进行添加，添加到思路是找到当前链表的最后一个节点，并将新添加到节点赋值给最后一个节点的next成员变量中。

链表增删改查

对于链表的其他操作也是相同的思路，关于链表增删改查和输出的完整代码如下：

class nodemanager {
 private node root;  // 根节点
 private int currentindex = 0; // 节点的序号，每次操作从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);
  }
 }
 
 // 谁拥有数据，谁提供方法
 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;
  }
  
  // 添加节点
  public void addnode(int data) {
   if ( this.next == null ) {
    this.next = new node(data);
   } else {
    this.next.addnode(data);
   }
  }
  
  // 删除节点
  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);
    }
   }
  }
  
  // 输出所有节点
  public void printnode() {
   if ( this.next != null ) {
    system.out.print(this.next.getdata() + " ");
    this.next.printnode();
   }
  }
  
  // 查找节点是否存在
  public boolean findnode(int data) {
   if ( this.next != null ) {
    if ( this.next.getdata() == data ) {
     return true;
    } else {
     return this.next.findnode(data);
    }
   }
   
   return false;
  }
  
  // 修改节点
  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;
  }
  
  // 插入节点
  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);
   }
  }
 }
}

以上就是链表基本操作的完整代码，下面写一个调用的代码进行测试，代码如下：

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中的集合类中用到了不少的数据结构的知识，等自己状态好的时候学习学习java集合类的源码。我会努力做一个初级程序员！

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，如果有疑问大家可以留言交流，谢谢大家对的支持。