黑马程序员技术交流社区

标题: 数据结构——链表 [打印本页]
作者: 乾之三爻    时间: 2018-3-27 10:46
标题: 数据结构——链表
学完数组后，直到数组可以存储多个数据，还可以根据索引对数组中的数据进行操作，但是数组也有明显的缺点：数组的长度固定，创建数组时就要指定长度，之后若想再网数组中添加元素，则无法完成。
后来了解到了有链表这种方便的根据，将数组存储在节点中，通过配置节点关系，实现
动态变化，相当于动态数组（暂时不考虑使用集合）。一时兴起，就写了个简单的链表，链表中使用到了内部类，映射，this关键字，引用传递，方法递归等知识，写的比较简单，功能也比较单一，大神有更好的方法请指教。
代码如下：
Person类
分析：链表中有一个删除指定数据节点的remove()方法，因此节点中存储的数据，即Person类对象要实现对象比较的方法，判断两个对象是否相等。
代码:
package com.itheima.linknode;
public classPerson {
      private String name;
      private int age;
      public Person(){         
      }
      public Person(String name,int age) {
         this.name = name;
         this.age = age;
      }
      public void setName(String name) {
         this.name = name;
      }
      public String getName() {
         return this.name;
      }
      public void setAge(int age) {
         this.age = age;
      }
      public int getAge() {
         return this.age;
      }
      //对象比较
      public boolean compare(Person person) {
         if(this == person) {
            return true;
         }
         if(person == null) {
            return false;
         }
         if(this.name.equals(person.name) && this.age == person.age) {
            return true;
         }
         return false;
      }
      
      public String getInfo() {
         return "姓名：" + this.name + ",年龄：" + this.age;
      }  
}


LinkNode类
    LinkNode类实现链表数据CRUD功能，在LinkNode类内部有一个Node类，Node类为节点类，用于操作节点，因为Node类只需要被LinkNode类调用，而且为了方便Node类访问LinkNode类中的成员变量，因此将Node类以内部类的形式定义在LinkNode类内部。
代码：
package com.itheima.linknode;
public classLink {
   private Node root; //根节点
   private int count; //统计个数
   private int foot;  //用于标记索引顺序
   private Person[] retData; //保存对象数组
   //*************************以下为内部类*****************************
   //Node类不希望 被其他类使用，但是Link类要使用Node类来操作数据节点
   private class Node{   //存储数据和配置节点关系
      private Person data;     //暂定要保存的数据为String类型
      private Node next; //下一个节点
      public Node(Person data) {
         this.data = data;
      }
      
      //增加数据
      public void addNode(Node newNode) {
         if(this.next == null) {
            this.next = newNode;
         }else{
            this.next.addNode(newNode);
         }
      }
      //查询
      public Person getNode(int index) {
         if(index == Link.this.foot++) {    //符合查找索引
            return this.data;
         }else{
            return this.next.getNode(index);
         }
      }
      //查询数据与当前数据符合
      public boolean containsNode(Person data) {
         if(data.compare(this.data)) {
            return true;
         }else{
            if(this.next != null){
                return this.next.containsNode(data);
            }else{
                return false;
            }
         }
      }
      //删除
      public void removeNode(Node previous,Person data) {
         if(this.data.compare(data)) {      //当前节点满足删除数据条件
            previous.next = this.next;
         }else{
            this.next.removeNode(this, data);
         }
      }
      //将全部节点转换为对象数组
      public void toArrayNode() {
         Link.this.retData[Link.this.foot++] = this.data;
         if(this.next != null) {
            this.next.toArrayNode();
         }
      }
   }
   //*******************************************以上为内部类
   //增加数据
   public void add(Person data) {
      if(data == null) {
         return;  //若要保存的数据为空，则直接返回
      }
      NodenewNode= newNode(data);  //将数据封装为节点
      if(this.root == null) {
         this.root = newNode;  //新节点作为根节点
      }else{
         this.root.addNode(newNode);
      }
      this.count++;   //增加个数
   }
   //取得链表中节点个数
   public int size() {
      return this.count;
   }
   //判断链表是否为空
   public boolean isEmpty() {
      return this.count == 0;
   }
   //清空链表
   public void clear() {
      this.root = null;
      this.count = 0;
   }
   //取得指定索引的数据
   public Person get(int index) {
      if(index > this.count) {
         return null;
      }
      this.foot = 0;  //让脚标从0开始
      return this.root.getNode(index);
   }
   //查询是否包含指定数据
   public boolean contains(Person data) {
      if(data == null) {
         return false;//没有数据
      }
      return this.root.containsNode(data);
   }
   //删除数据
   public void remove(Person data) {
      if(this.contains(data)) { //查找到数据
         if(this.root.data.compare(data)) {
            this.root = this.root.next;  //改变根节点
         }else{
            this.root.next.removeNode(this.root, data);
         }
         this.count--;
      }
   }
   //将链表中的节点转为对象数组
   public Person[] toArray() {
      if(this.count == 0) {
         return null;//没有数据
      }
      this.foot = 0;
      this.retData = new Person[this.count]; //开辟数组
      this.root.toArrayNode();//交给Node类处理
      return this.retData;
   }
}







欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2