单链表的实现

链表是有序的列表，但是在内存中存储图下图所示

1. 链表是以 节点 的方式来存储，是 链式存储
2. 每个节点包含 data 域、next 域，指向下一个节点
3. 链表的各个节点 不一定是连续存储，如上图所示
4. 链表还分：带头节点、不带头节点，根据实际需求来确定

上面进行了一个简单的介绍，下面分几部分来讲解

单链表

单链表（带头节点）逻辑结构 示意图如下，当下一个节点为 空 的时候，该链表就结束了

注意：是逻辑结构，前面说过，在内存中节点不是一个接一个的。

单链表的应用实例

虑这样一个场景：使用带 head 头的 单向链表 实现水浒英雄排行榜管理

1. 完成对英雄人物的 增删改查 操作
2. 第一种方法：在添加英雄时，直接添加到链表的尾部

1. 第二种方法：在添加英雄时，根据排名将英雄插入到指定位置如果有这个排名，则添加失败，并给出提示

如上图所示，添加流程。有一个 Heronode 节点，他的定义如下

class Heronode {
  int no;
  String name;
  String nickName;
  Heronode next; 
    public Heronode(int id,String name,String nickName){
        this.id=id;
        this.name=name;
        this.nickName=nickName;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "id=" + id +
                ", name='" + name + ''' +
                ", nickName='" + nickName + ''' +
                '}';
    }
}

单链表-无排序实现

首先定义头结点

Heronode headNode=new Heronode(0,"","");

增加节点

    public  void add(Heronode node){
        Heronode temp=headNode;
        while (true){
            if(temp.next==null){
                break;
            }
            temp=temp.next;
        }
        temp.next=node;
    }

新增节点并根据id排序

//有序添加节点
    public void addByOrder(Heronode node){
        Heronode temp=headNode;
        boolean exist=false;
        while (true){
            //首先需要判断下一个节点是否为空
            if(temp.next==null){
                break;
            }
            //因为是按id顺序排序，当链表下一个节点大于插入节点id时退出循环
            if(temp.next.id>node.id){
                break;
            }
            if(temp.next.id==node.id)
            {
                exist=true;
                break;
            }
            temp=temp.next;
        }
        if(exist){
            System.out.printf("插入编号%d已经存在，不能再插入",node.id);
            return;
        }
        //将插入节点指针指向当前节点的下一个指针
        node.next=temp.next;
        //将当前节点下一个节点设为插入节点
        temp.next=node;
    }

根据id修改节点属性

 public void update(Heronode node){
        Heronode temp=headNode;
        boolean exist=false;
        while (true){
            if(temp==null){
                break;
            }
            if(temp.id==node.id){
                exist=true;
                break;
            }
            temp=temp.next;
        }
      if(exist){
            temp.name=node.name;
            temp.nickName=node.nickName;
        }else {
            System.out.printf("未找到需要修改的编号id为%s",node.id);
        }
    }

根据id删除节点

  public void delete(int no){
      if(headNode.next==null){
          System.out.println("当前链表为空，无需要删除的节点");
          return;
      }
      Heronode temp=headNode;
      boolean exist=false;
      while (true){
       if(temp.next==null){
          break;
       }
       if(temp.next.id==no){
           exist=true;
           break;
       }
       temp=temp.next;
      }
      if(!exist){
          System.out.println("未找到需要删除的节点");
          return;
      }
      //将需要删除的节点的指针引用设为孤立的会自动被垃圾回收
      temp.next=temp.next.next;
  }

遍历节点并输出节点信息

    public void list(){
        if(headNode.next==null){
            System.out.println("链表为空");
        }
        Heronode temp=headNode.next;
        while (true){
            if(temp==null){
                break;
            }
            System.out.println(temp);
            temp=temp.next;
        }

    }

获取链表的长度

    public int length(){
        if(headNode.next==null){
            return 0;
        }
        Heronode temp=headNode.next;
        int len=0;
        while (temp!=null){
          temp=temp.next;
          len++;
        }
        return len;
    }

获取倒数第k个节点

  
    public Heronode findLastIndexNode(int k){
        //先调用已实现方法获取链表的长度
        int len=length();
        if(len==0){
            return null;
        }
        if(k<0||k>len)
        {
            return  null;
        }
        Heronode temp=headNode.next;
        for (int i = 0; i  
单链表的翻转 
 
    public void reverse(){
          if (headNode.next == null) {
            return;
        }
        //当前节点
        Heronode currentNode=headNode.next;
        Heronode nextNode=null;
        //临时节点
        Heronode  temporaryNode=new Heronode(0,"","");
        while (currentNode!=null){
            nextNode=currentNode.next;
            currentNode.next=temporaryNode.next;
            temporaryNode.next=currentNode;
            currentNode=nextNode;
        }
        headNode.next=temporaryNode.next;
    }
 
单链表通过Stack进行反序遍历 
 
    public void reversePrint(){
        Stackstack=new Stack<>();
        Heronode node=headNode.next;
        while (node!=null){
            stack.push(node);
            node=node.next;
        }
        while (!stack.empty()){
            System.out.println(stack.pop());
        }
    }