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集合类的源码。我会努力做一个初级程序员!

总结

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

(0)

相关推荐

  • Java 数据结构链表操作实现代码

    链表是一种复杂的数据结构,其数据之间的相互关系使链表分成三种:单链表.循环链表.双向链表,下面将逐一介绍.链表在数据结构中是基础,也是重要的知识点,这里讲下Java 中链表的实现, JAVA 链表操作:单链表和双链表 主要讲述几点: 一.链表的简介 二.链表实现原理和必要性 三.单链表示例 四.双链表示例 一.链表的简介 链表是一种比较常用的数据结构,链表虽然保存比较复杂,但是在查询时候比较便捷,在多种计算机语言都相应的应用,链表有多种类别,文章针对单链表和双链表进行分析.链表中数据就像被一个链

  • java 数据结构之删除链表中的元素实例代码

    java 删除链表中的元素 以下实例演示了使用 Clear() 方法来删除链表中的元素: import java.util.*; public class Main { public static void main(String[] args) { LinkedList<String> lList = new LinkedList<String>(); lList.add("1"); lList.add("8"); lList.add(&q

  • 详解java数据结构与算法之双链表设计与实现

    在单链表分析中,我们可以知道每个结点只有一个指向后继结点的next域,倘若此时已知当前结点p,需要查找其前驱结点,那么就必须从head头指针遍历至p的前驱结点,操作的效率很低,因此如果p有一个指向前驱结点的next域,那效率就高多了,对于这种一个结点中分别包含了前驱结点域pre和后继结点域next的链表,称之为双链表.本篇我们将从以下结点来分析双链表 双链表的设计与实现 双链表的主要优点是对于任意给的结点,都可以很轻易的获取其前驱结点或者后继结点,而主要缺点是每个结点需要添加额外的next域,因

  • java数据结构之实现双向链表的示例

    复制代码 代码如下: /** * 双向链表的实现 * @author Skip * @version 1.0 */public class DoubleNodeList<T> { //节点类 private static class Node<T>{  Node<T> perv;  //前节点  Node<T> next;  //后节点  T data;    //数据 public Node(T t){   this.data = t;  } } priv

  • Java数据结构之简单链表的定义与实现方法示例

    本文实例讲述了Java数据结构之简单链表的定义与实现方法.分享给大家供大家参考,具体如下: 一.概述: 1.原理: 只有一个数据项(链接点Link),每个数据插入时都是对第一个数据的引用. 2.插入数据说明: 当链表没有数据时,插入的值就是第一个数据,如果链表里有数据,就把当前的数据的next指针指向第一个数据. 3.插入数据图: 4.特点:先进后出 5.实现功能: 数据插入,指定位置插入,显示,查询,删除等 6.删除原理 7.插入头节点原理 二.实现: 1.创建节点 /** * @描述 节点

  • java 数据结构单链表的实现

    java 数据结构单链表的实现 单链表实现链表的打印及元素删除操作,链表的实现主要是next属性的定义,将一堆节点关联起来的.实现简单的链表如下: public class LinkNode { private int value; private LinkNode next; public LinkNode(int x) { value = x; } public LinkNode getNext(){ return next; } public void setNext(LinkNode n

  • JAVA 数据结构链表操作循环链表

    JAVA 链表操作:循环链表 主要分析示例: 一.单链表循环链表 二.双链表循环链表 其中单链表节点和双链表节点类和接口ICommOperate<T>与上篇一致,这里不在赘述.参考:JAVA链表操作:单链表和双链表http://www.jb51.net/article/95113.htm 一.单链表循环链表 package LinkListTest; import java.util.HashMap; import java.util.Map; public class SingleCycle

  • Java模拟有序链表数据结构的示例

    有序链表: 按关键值排序.删除链头时,就删除最小(/最大)的值,插入时,搜索插入的位置. 插入时需要比较O(N),平均O(N/2),删除最小(/最大)的在链头的数据时效率为O(1), 如果一个应用需要频繁的存取(插入/查找/删除)最小(/最大)的数据项,那么有序链表是一个不错的选择 优先级队列 可以使用有序链表来实现 有序链表的插入排序: 对一个无序数组,用有序链表来排序,比较的时间级还是O(N^2) 复制时间级为O(2*N),因为复制的次数较少,第一次放进链表数据移动N次,再从链表复制到数组,

  • java实现数据结构单链表示例(java单链表)

    复制代码 代码如下: /** * 单向链表 * */public class NodeList<E> { private static class Node<E> { // 节点类  E data; // 节点上的数据  Node<E> next; // 指向下一个节点 Node(E e) {   this.data = e;   this.next = null;  } } private Node<E> head; // 链表的头节点 private N

  • Java模拟单链表和双端链表数据结构的实例讲解

    模拟单链表 线性表: 线性表(亦作顺序表)是最基本.最简单.也是最常用的一种数据结构. 线性表中数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的. 线性表的逻辑结构简单,便于实现和操作. 在实际应用中,线性表都是以栈.队列.字符串等特殊线性表的形式来使用的. 线性结构的基本特征为: 1.集合中必存在唯一的一个"第一元素": 2.集合中必存在唯一的一个 "最后元素" : 3.除最后一个元素之外,均有 唯一的后继(后件):

随机推荐