链表的定义与使用

2020-11-13 本文已影响0人曾梦想仗剑天涯

链表实现简介

链表的本质是一个动态的对象数组，它可以实现若干个对象的存储；
在开发之中对象数组是一项非常实用的技术，并且利用其可以描述出“多”方的概念，例如：一个人有多本书，则在人的类里面一定要提供一个对象数组保存书的信息，但是传统的对象数组依赖于数组的概念，所以数组里面最大的确定在于：长度是固定的，正是因为如此所以在开发之中，传统的数组应用是非常有限的（数组的接收以及循环处理），但是如果要想进行灵活的数据保存，那么就必须自己来实现结构；

此图来源于李兴华老师

传统对象数组的开发操作依赖于脚标（索引）的控制，如果要想实现内容的动态维护，难道太高来，复杂度也攀升来，现在就可以发现，对于一成不动的数据可以实用对象数组来实现，但是对于可能随时变化的数据就必须实现一个可以动态扩充的对象数组；
所谓的链表实质性的本质是利用引用的逻辑关系来实现类似于数组的数据处理操作，以一种保存“多”方数据的形式，实现数组类似的功能；

此图来源于李兴华老师

如果想要实现链表处理，那么需要一个公共的结构，这个结构可以实现数据的保存以及下一个连接的指向，为了描述这样的逻辑，可以把每一个存储理解为一个节点，所以此时应该准备出一个节点类，但是这个节点类里面可以保存各种数据类型的数据；

此图来源于李兴华老师

//直接操作Node很麻烦
class Node<E> {
  private E data;
  private Node next;
  public Node(E data) {
    this.data = data;
  }
  public void setNext(Node next) {
    this.next = next;
  }
  public E getData() {
    return this.data;
  }
  public Node getNext() {
    return this.next;
  }
}
public class LinkDemo {
  public static void main(String [] args) {
    Node<String> n1 = new Node<String>("火车头");
    Node<String> n2 = new Node<String>("车厢一");
    Node<String> n3 = new Node<String>("车厢二");
    Node<String> n4 = new Node<String>("车厢三");
    Node<String> n5 = new Node<String>("车厢四");
    n1.setNext(n2);
    n2.setNext(n3);
    n3.setNext(n4);
    n4.setNext(n5);
    print(n1);
  }
  public static void print(Node<?> node) {
    if(node != null) {
      System.out.println(node.getData());
      print(node.getNext());
    }
  }
}

这样是肯定不行的，所以应该有一个专门的类来进行节点的引用关系配置，因为真实的使用者实际上关心的只是数据的存储与获取，所以现在应该对Node类进行包装处理；

此图来源于李兴华老师

数据保存：public void add(E e)

通过之前的分析可以发现进行链表操作的过程之中为了避免转型的异常应该使用泛型，同时也应该设计一个链表的标准接口，同时具体实现接口的时候还应该通过Node类做出节点的关系描述；

//基本结构
interface ILink<E> {    //设置泛型避免安全隐患
  public abstract void add(E e);
}
class LinkImpl<E> implements ILink<E> {
  private class Node {    //保存节点的数据类型
    private E data;   //保存的数据
    private Node next;    //保存下一个引用
    public Node(E data) {   //有数据的情况下才有意义
      this.data = data;
    }
  }
  public void add(E e) {
  
  }
}

在现在所定义的类之中并没有出现有setter和getter方法，是因为内部类的私有属性也方便外部类直接访问；

//实现数据增加
interface ILink<E> {    //设置泛型避免安全隐患
  public abstract void add(E e);
}
class LinkImpl<E> implements ILink<E> {
  private class Node {    //保存节点的数据类型
    private E data;   //保存的数据
    private Node next;    //保存下一个引用
    public Node(E data) {   //有数据的情况下才有意义
      this.data = data;
    }
    //第一次调用： this = LinkImpl.root
    //第二次调用:  this = LinkImpl.root.next
    //第三次调用:  this = LinkImpl.root.next.next
    public void addNode(Node newNode) {   //保存新的node数据
      if(this.next == null) {   //当下一个节点为null时
        this.next = newNode;    //保存当前节点
      } else {
        this.next.addNode(newNode);
      }
    }
  }
  //-------------------以下是ILink类中定义的成员
  private Node root;    //根元素
  //-------------------以下是ILink类中定义的方法
  public void add(E e) {
    if(e == null) {   //保存的数据为null
      return;   //方法调用直接结束
    }
    //数据本身并不具有关联特性，只有Node类有，那么想实现关联处理就必须将数据包装在Node类之中
    Node newNode = new Node(e);   //创建一个新的节点
    if(this.root == null) {   //现在没有根节点
      this.root = newNode;    //第一个节点作为根节点
    } else {
      this.root.addNode(newNode);//将新节点保存在合适的位置
    }
  }
}
public class LinkDemo {
  public static void main(String [] args) {
    ILink<String> all = new LinkImpl<String>();
    all.add("Hello");
    all.add("World");
  }
}

Link类只负责数据的操作和根节点的处理，而所有后续节点的处理全部都是由Node类负责完成的；

获取数据长度：public int size()

在链表之中往往需要保存有大量的数据，那么这些数据往往需要进行数据个数的统计操作，所以应该在LinkImpl子类里面追加有数据统计信息，同时当增加或删除数据时都应该对个数进行修改；
在ILink接口里面追加一个获取数据个数的方法;

public abstract int size();   //获取数据的个数

在LinkImpl子类里面追加一个个数统计的属性；

private int count;

在add()方法里面进行数据个数的追加;

public void add(E e) {
  if(e == null) {   //保存的数据为null
    return;   //方法调用直接结束
  }
  //数据本身并不具有关联特性，只有Node类有，那么想实现关联处理就必须将数据包装在Node类之中
  Node newNode = new Node(e);   //创建一个新的节点
  if(this.root == null) {   //现在没有根节点
    this.root = newNode;    //第一个节点作为根节点
  } else {
    this.root.addNode(newNode);//将新节点保存在合适的位置
  }
  this.count ++;
}

需要在LinkImpl子类里面来返回数据的个数；

public int size() {
  return this.count;
}

只是对于数据保存中的一个辅助功能；

空集合判断：public boolean isEmpty()

链表里面可以保存有若干个数据，如果现在链表还没有保存数据，则就表示一个空集合，所以应该提供有一个是否是空集合判断；
在ILink接口里面追加有判断方法；

public abstract boolean isEmpty();   //判断是否为空集合

在LinkImpl里面覆写此方法

public boolean isEmpty() {
  //return this.root == null;
  return this.count == 0;
}

使用根节点或者长度判断其本质是一样的；

返回集合数据：public Object [] toArray()

链表本身属于一个动态对象数组，那么既然是对象数组，就可以把所有的数据以数组的形式返回，这个时候就可以定义一个toArray()方法，但是这个方法只能返回一个Object型的数组；

此图来源于李兴华老师

在ILink接口里面追加新的处理方法；

public abstract Object [] toArray();    //将元素以数组的形式返回

在LinkImpl子类里面追加两个属性；

private int foot;   //操作数组的脚标
private Object [] returnData;   //返回的数据保存

在Node类中递归获取数据；

//第一次调用：this = LinkImpl.root
//第二次调用:  this = LinkImpl.root.next
//第三次调用:  this = LinkImpl.root.next.next
public void toArrayNode() {
  LinkImpl.this.returnData[LinkImpl.this.foot++] = this.data;
  if(this.next != null) {   //还有下一个数据
    this.next.toArrayNode();
  }
}

在进行数据返回的时候一定要首先判断是否为空集合；

public Object [] toArray() {
  if(this.isEmpty()) {    //空集合
    return null;    //没有数据
  }
  this.foot = 0;    //脚标清零
  this.returnData = new Object [this.count];    //根据已有长度开辟数组
  this.root.toArrayNode();    //利用Node类递归获取数据
  return this.returnData;
}

集合的数据一般如果要返回肯定要以对象数组的形式返回；

获取指定索引数据：public E get(int index)

链表可以像数组一样进行处理，所以也应该可以像数组一样根据索引获取数据，在这样的情况下，就可以继续利用递归的形式来完成；

此图来源于李兴华老师

在ILink接口里面追加新的方法；

public abstract E get(int index);   //根据索引获取数据

在Node类里面追加有根据所以获取数据的处理；

public E getNode(int index) {
  if(LinkImpl.this.foot++ == index) {
    return this.data;
  } else {
    return this.next.getNode(index);
  }
}

在LinkImpl子类里面定义数据获取的实现；

public E get(int index) {
    if(index >= this.count) {   //所以应该在指定范围之内
      return null;
    }
    this.foot = 0;    //重制索引的下标
    return this.root.getNode(index);
  }

*这一特点和数组是很相似的，但是需要注意的是，数组获取一个数据的时间复杂度为1，而链表获取数据的时间复杂度为n；

修改指定索引数据：public void set(int index, E data)

根据索引获取了指定数据，那么就可以进行数据的修改；
在ILink接口中追加有新的方法；

public void set(int index, E data)

在Node类之中提供有数据修改的处理支持；

public void setNode(int index, E data) {
  if(LinkImpl.this.foot++ == index) {   //索引相同
    this.data = data;   //修改数据
  } else {
    this.next.setNode(index, data);
  }
}

在LInkImpl子类里面进行方法覆写；

public void set(int index, E data) {
  if(index >= this.count) {
    return;
  }
  this.foot = 0;
  this.root.setNode(index, data);
}

这种操作的时间复杂度也是n，因为依然需要进行数据的便利处理；

判断指定数据是否存在：public boolean contains(E data)

在一个集合里面往往存在有大量的数据，有时候需要判断某个数据是否存在，这个时候就可以通过对象比较的模式（equals()方法）来完成判断；
在ILink接口中追加判断的方法；

public abstract boolean contains(E data);   //判断数据是否存在

在Node类中进行依次判断；

public boolean containsNode(E data) {
  if(data.equals(this.data)) {
    return true;
  } else {
    if(this.next == null) {
      return false;
    } else {
      return this.next.containsNode(data);
    }
  }
}

在LinkImpl里面实现此方法；

public boolean contains(E data) {
  if(data == null) {
    return false;
  }
  return this.root.containsNode(data);
}

由于整个链表没有null数据的存在，所以整体的程序在判断的时候直接使用每一个节点数据发出equals()方法调用即可；

数据的删除：public void remove(E data)

数据删除指的是可以从集合里删除掉指定的一个数据内容，也就是说此时传递的是数据内容，那么如果要实现这种删除操作依然需要对象比较的支持，但是对于集合数据的删除需要考虑两种情况：
要删除的是根节点数据（LinkImpl与根节点有关，所以这个判断由根节点完成）：

此图来源于李兴华老师

要删除的不是根节点数据（由Node类负责完成）：

此图来源于李兴华老师

在ILink接口里面追加新的删除方法；

public abstract void remove(E data);    //删除指定数据

在LinkImpl子类里面实现根节点的判断；

public void remove(E data) {
  if(this.contains(data)) {   //判断数据是否存在
    if(this.root.data.equals(data)) {   //根节点为要删除的节点
      this.root = this.root.next;   //根节点的下一个节点
    }
    this.count--;
  }
}

如果现在根节点并不是要删除的节点，那么就需要进行后续节点判断，但是请一定要记住此时根节点已经判断完成来，再判断应该从根节点的下一个节点开始判断，在Node类中追加删除处理；

public void removeNode(Node previous, E data) {
  if(data.equals(this.data)) {
    previous.next = this.next;    //空出当前节点
  } else {
    if(this.next != null) {   //有后续节点
      this.next.removeNode(this, data);   //向后继续删除
    }
  }
}

完善LinkImpl子类中的remove()方法；

public void remove(E data) {
  if(this.contains(data)) {   //判断数据是否存在
    if(this.root.data.equals(data)) {   //根节点为要删除的节点
      this.root = this.root.next;   //根节点的下一个节点
    } else {    //如果不是根节点，交由Node类进行处理
      this.root.next.removeNode(this.root, data);
    }
    this.count--;
  }
}

删除的逻辑依靠的就是引用的改变处理完成的；

清空链表：public void clean()

有些时候需要进行链表数据的清空，这个时候就可以直接根据根元素来进行控制，只要root设置为了null，那么后续的节点就都不存在了；
在ILink接口里面追加有清空处理方法；

public abstract void clean();   //清空集合

在LinkImpl子类里面覆写此方法

public void clean() {
  this.root = null;   //后续的所有节点都没了
  this.count = 0;   //个数清零
}

这些就是链表的基本功能，当然，这只是一个最简单最基础的单向链表实现；

interface ILink<E> {    //设置泛型避免安全隐患
  public abstract void add(E e);    //增加数据
  public abstract int size();   //获取数据的个数
  public abstract boolean isEmpty();   //判断是否为空集合
  public abstract Object [] toArray();    //将元素以数组的形式返回
  public abstract E get(int index);   //根据索引获取数据
  public abstract void set(int index, E data);   //修改索引数据
  public abstract boolean contains(E data);   //判断数据是否存在
  public abstract void remove(E data);    //删除指定数据
  public abstract void clean();   //清空集合
}
class LinkImpl<E> implements ILink<E> {
  private class Node {    //保存节点的数据类型
    private E data;   //保存的数据
    private Node next;    //保存下一个引用
    public Node(E data) {   //有数据的情况下才有意义
      this.data = data;
    }
    //第一次调用： this = LinkImpl.root
    //第二次调用:  this = LinkImpl.root.next
    //第三次调用:  this = LinkImpl.root.next.next
    public void addNode(Node newNode) {   //保存新的node数据
      if(this.next == null) {   //当下一个节点为null时
        this.next = newNode;    //保存当前节点
      } else {
        this.next.addNode(newNode);
      }
    }
    //第一次调用：this = LinkImpl.root
    //第二次调用:  this = LinkImpl.root.next
    //第三次调用:  this = LinkImpl.root.next.next
    public void toArrayNode() {
      LinkImpl.this.returnData[LinkImpl.this.foot++] = this.data;
      if(this.next != null) {   //还有下一个数据
        this.next.toArrayNode();
      }
    }
    public E getNode(int index) {
      if(LinkImpl.this.foot++ == index) {   //索引相同
        return this.data;   //返回当前数据
      } else {
        return this.next.getNode(index);
      }
    }
    public void setNode(int index, E data) {
      if(LinkImpl.this.foot++ == index) {   //索引相同
        this.data = data;   //修改数据
      } else {
        this.next.setNode(index, data);
      }
    }
    public boolean containsNode(E data) {
      if(data.equals(this.data)) {
        return true;
      } else {
        if(this.next == null) {
          return false;
        } else {
          return this.next.containsNode(data);
        }
      }
    }
    public void removeNode(Node previous, E data) {
      if(data.equals(this.data)) {
        previous.next = this.next;    //空出当前节点
      } else {
        if(this.next != null) {   //有后续节点
          this.next.removeNode(this, data);   //向后继续删除
        }
      }
    }
  }
  //-------------------以下是ILink类中定义的成员
  private Node root;    //根元素
  private int count;    //保存数据个数
  private int foot;   //操作数组的脚标
  private Object [] returnData;   //返回的数据保存
  //-------------------以下是ILink类中定义的方法
  public void add(E e) {
    if(e == null) {   //保存的数据为null
      return;   //方法调用直接结束
    }
    //数据本身并不具有关联特性，只有Node类有，那么想实现关联处理就必须将数据包装在Node类之中
    Node newNode = new Node(e);   //创建一个新的节点
    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.root == null;
    return this.count == 0;
  }
  public Object [] toArray() {
    if(this.isEmpty()) {    //空集合
      return null;    //没有数据
    }
    this.foot = 0;    //脚标清零
    this.returnData = new Object [this.count];    //根据已有长度开辟数组
    this.root.toArrayNode();    //利用Node类递归获取数据
    return this.returnData;
  }
  public E get(int index) {
    if(index >= this.count) {   //所以应该在指定范围之内
      return null;
    }
    this.foot = 0;    //重制索引的下标
    return this.root.getNode(index);
  }
  public void set(int index, E data) {
    if(index >= this.count) {
      return;
    }
    this.foot = 0;
    this.root.setNode(index, data);
  }
  public boolean contains(E data) {
    if(data == null) {
      return false;
    }
    return this.root.containsNode(data);
  }
  public void remove(E data) {
    if(this.contains(data)) {   //判断数据是否存在
      if(this.root.data.equals(data)) {   //根节点为要删除的节点
        this.root = this.root.next;   //根节点的下一个节点
      } else {    //如果不是根节点，交由Node类进行处理
        this.root.next.removeNode(this.root, data);
      }
      this.count--;
    }
  }
  public void clean() {
    this.root = null;   //后续的所有节点都没了
    this.count = 0;   //个数清零
  }
}
public class LinkDemo {
  public static void main(String [] args) {
    ILink<String> all = new LinkImpl<String>();
    System.out.println("数据增加之前size = " + all.size() + "、是否为空集合：" + all.isEmpty());
    all.add("Hello");
    all.add("World");
    all.add("!");
    all.remove("World");
    all.clean();
    System.out.println("数据增加之后size = " + all.size() + "、是否为空集合：" + all.isEmpty());
    System.out.println("----------------输出集合数据--------------------");
    Object [] result = all.toArray();
    if(result != null) {
      for(Object obj : result) {
        System.out.println(obj);
      }
    }
    System.out.println("----------------根据索引获取数据----------------");
    System.out.println(all.get(0));
    System.out.println(all.get(1));
    System.out.println(all.get(2));
    System.out.println("----------------根据索引修改数据----------------");
    all.set(0, "你好");
    System.out.println(all.get(0));
    System.out.println(all.get(1));
    System.out.println("----------------判断数据是否存在----------------");
    System.out.println(all.contains("Hello"));
    System.out.println(all.contains("World"));
  }
}

链表的定义与使用

链表实现简介

数据保存：public void add(E e)

获取数据长度：public int size()

空集合判断：public boolean isEmpty()

返回集合数据：public Object [] toArray()

获取指定索引数据：public E get(int index)

修改指定索引数据：public void set(int index, E data)

判断指定数据是否存在：public boolean contains(E data)

数据的删除：public void remove(E data)

清空链表：public void clean()

猜你喜欢

热点阅读