Java数据结构与算法：1.单链表

1.单链表的介绍：

2.单链表的添加第一种方式

3.单链表的添加第二种方式

1.单链表的介绍：

单链表是一种链式存取的数据结构，用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的，每个结点的构成：元素(数据元素的映象) + 指针(指示后继元素存储位置)，元素就是存储数据的存储单元，指针就是连接每个结点的地址数据。链表是有序的列表，以节点的方式来存储，是链式存储，每个节点包含data域，next域：指向下一个节点。

单链表逻辑结构

第一步：定义

//定义HeroNode
class HeroNode{
        public int no;
        public String name;
        public String nickname;
        public HeroNode next;//指向下一个节点
    public HeroNode(int no,String name,String nickname){
        this.no=no;//this是调用本类中的属性（成员变量）或者方法，将局部变量的值传递给成员变量
        this.name=name;
        this.nickname=nickname;
        }
    //重写tostring方法
    public String toString(){
        return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";
        }

}

第二步：创建

public  class SingleLinkedListDemo {
public static void main(String[] args) {
    //进行测试
    //先创建节点
    HeroNode hero1=new HeroNode(1,"宋江","及时雨");
    HeroNode hero2=new HeroNode(2,"卢俊义","玉麒麟");
    HeroNode hero3=new HeroNode(3,"吴用","智多星");
    HeroNode hero4=new HeroNode(4,"林冲","豹子头");
    //创建要给链表
    SingleLinkedList singleLinkedList=new SingleLinkedList();
	}
}

第三步：遍历

public void list(){//显示链表，遍历
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //因为头结点不能动，所以需要一个辅助遍历temp
        HeroNode temp=head.next;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            temp=temp.next;
        }

2.单链表的添加第一种方式

单链表的添加第一种方式，在添加数据时，直接添加到链表的尾部

思路分析：

1.先创建一个head头结点，作用就是表示单链表的头

2.每添加一个节点，就直接添加到链表的最后

3.通过辅助变量遍历

主要代码：SingleLinkList类中的add方法

class SingleLinkedList {
        //先定义一个头结点，头结点是不存放数据的，并且不能动
        //初始化头结点
    private HeroNode head = new HeroNode(0, "", "");
        //添加节点到链表的最后节点，第一步，找到当前节点的最后节点，第二步，将最后这个节点的next指向新的节点
    public void add(HeroNode heroNode){//节点的遍历
        //因为头结点不能动，所以需要一个辅助遍历temp
        HeroNode temp=head;
        //遍历链表，找到最后
        while (true){
        //找到链表的最后
            if (temp.next == null){
            break;
            }
        //如果没有找到最后,就将temp后移
            temp=temp.next;
        }
        //当退出循环时，temp就指向了链表的最后，将最后这个节点的next指向新的节点
        temp.next=heroNode;
        }
}

单链表的第一种方法代码实现：


public  class SingleLinkedListDemo {
    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1=new HeroNode(1,"宋江","及时雨");
        HeroNode hero2=new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3=new HeroNode(3,"吴用","智多星");
        HeroNode hero4=new HeroNode(4,"林冲","豹子头");
        //创建要给链表
        SingleLinkedList singleLinkedList=new SingleLinkedList();
        //加入
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);
        singleLinkedList.list();

    }

}
class SingleLinkedList {
    private HeroNode head = new HeroNode(0, "", "");
    public void add(HeroNode heroNode){//节点的遍历
        //因为头结点不能动，所以需要一个辅助遍历temp
        HeroNode temp=head;
        //遍历链表，找到最后
        while (true){
            //找到链表的最后
            if (temp.next == null){
                break;
            }
            //如果没有找到最后,就将temp后移
            temp=temp.next;
        }
        //当退出循环时，temp就指向了链表的最后，将最后这个节点的next指向新的节点
        temp.next=heroNode;
    }
public void list(){//显示链表，遍历
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //因为头结点不能动，所以需要一个辅助遍历temp
        HeroNode temp=head.next;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            temp=temp.next;
        }

    }

}
class HeroNode{
    public int no;
    public String name;
    public String nickname;
    public HeroNode next;
    public HeroNode(int no,String name,String nickname){
        this.no=no;
        this.name=name;
        this.nickname=nickname;
    }
    //为了显示方法，我们重写tostring
    public String toString(){
        return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";
    }

}

3.单链表的添加第二种方式

思路分析：

首先找到新添加的节点的位置，通过辅助变量遍历

新节点.next=temp.next

temp.next=新的节点

举个例子：A1（数据1，next）→A3（数据3，next）。将A2(数据2，next)插入到A1和A3之间。当A2插入到其中，首先判断A2所在位置，利用赋辅助变量遍历，当A2.序列>A3.序列时，满足插入条件，将A2.next指向A3.next，A1.nxet指向A2.next，就完成了单链表的插入。

主要代码：SingleLinkList类中的addByorder方法

public void addByOrder(HeroNode heroNode){
  HeroNode temp=head;
  boolean flag=false;//flag表示添加的编号是否存在
      while (true){
          if (temp.next == null){//说明在链表的最后
              break;
          }

          if (temp.next.no > heroNode.no){
              break;
          }else if (temp.next.no == heroNode.no){
          //说明希望添加的heronode编号已经存在
              flag=true;//说明编号存在
              break;
          }
          temp=temp.next;//后移，遍历当前链表
      }
      if (flag){
          System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入n",heroNode.no);
      }else{
          //插入到链表中，temp的后面
          heroNode.next=temp.next;
          temp.next=heroNode;
      }
  }

单链表的第二种方法代码实现：

public  class ArrayList {
    public static void main(String[] args) {
        //进行测试
        //先创建节点
        HeroNode hero1=new HeroNode(1,"宋江","及时雨");
        HeroNode hero2=new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3=new HeroNode(3,"吴用","智多星");
        HeroNode hero4=new HeroNode(4,"林冲","豹子头");
        //创建要给链表
        SingleLinkedList singleLinkedList=new SingleLinkedList();
        //加入
//        singleLinkedList.add(hero1);
//        singleLinkedList.add(hero2);
//        singleLinkedList.add(hero3);
//        singleLinkedList.add(hero4);
//        singleLinkedList.list();

        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.list();

    }

}
class SingleLinkedList {
    private HeroNode head = new HeroNode(0, "", "");
    public void add(HeroNode heroNode){//节点的遍历
        //因为头结点不能动，所以需要一个辅助遍历temp
        HeroNode temp=head;
        //遍历链表，找到最后
        while (true){
            //找到链表的最后
            if (temp.next == null){
                break;
            }
            //如果没有找到最后,就将temp后移
            temp=temp.next;
        }
        //当退出循环时，temp就指向了链表的最后，将最后这个节点的next指向新的节点
        temp.next=heroNode;
    }
    public void addByOrder(HeroNode heroNode){//添加节点到数组

        HeroNode temp=head;
        boolean flag=false;//flag表示添加的编号是否存在
        while (true){
            if (temp.next == null){//说明在链表的最后
                break;
            }
            //这个
            if (temp.next.no > heroNode.no){
                break;
            }else if (temp.next.no == heroNode.no){
                //说明希望添加的heronode编号已经存在
                flag=true;//说明编号存在
                break;
            }
            temp=temp.next;//后移，遍历当前链表
        }
        if (flag){
            System.out.printf("准备插入的英雄的编号%d已经存在了，不能加入n",heroNode.no);
        }else{
            //插入到链表中，temp的后面
            heroNode.next=temp.next;
            temp.next=heroNode;
        }
    }
public void list(){//显示链表，遍历
        if(head.next == null){
            System.out.println("链表为空");
            return;
        }
        //因为头结点不能动，所以需要一个辅助遍历temp
        HeroNode temp=head.next;
        while (true){
            if (temp == null){
                break;
            }
            //输出节点的信息
            System.out.println(temp);
            temp=temp.next;
        }

    }

}
class HeroNode{
    public int no;//public是公有访问
    public String name;
    public String nickname;
    public HeroNode next;//指向下一个节点，这个是heronode类的定义，他的定义是什么呢
    public HeroNode(int no,String name,String nickname){//构造器，负责初始化实例变量，就是对变量初始化，上面只是对对象开辟内存，等构造器来初始化这个内存
        this.no=no;//this是调用本类中的属性（成员变量）或者方法，将局部变量的值传递给成员变量
        this.name=name;
        this.nickname=nickname;
    }
    //为了显示方法，我们重写tostring
    public String toString(){
        //这里的no=不加双引号是因为直接输出，加了双引号的为变量，如果不加++，就为字符串，加了就为变量
        return "HeroNode[no="+no+",name="+name+",nickname="+nickname+"]";
    }

}

如果对您有帮助，点个关注吧，持续更新中，谢谢支持。如果有问题或错误，欢迎指出与我联系，谢谢。

Java数据结构与算法：1.单链表

Java相关栏目本月热门文章