欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

java数据结构实现单链表

程序员文章站 2022-09-26 23:31:41
参考于 尚硅谷Java数据结构与java算法,韩顺平数据结构与算法1.什么是链表:链表是有序的列表,但是它在内存中可以以不连续空间存放,存储如下根据上图,可以发现:链表是以节点的方式来存储,是链式存储每个节点包含 data 域,next域:指向下一个节点.链表的各个节点不一定是连续存储.链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定(头节点一般不存储数据,只用于作为标识)因而带头节点的单链表的逻辑结构可以看作:2.单链表的实现需求:使用带head头节点的单链表;...

1.什么是链表:

链表是有序的列表,但是它在内存中可以以不连续空间存放,存储如下
java数据结构实现单链表
根据上图,可以发现:

  1. 链表是以节点的方式来存储,是链式存储
  2. 每个节点包含 data 域,next域:指向下一个节点.
  3. 链表的各个节点不一定是连续存储.
  4. 链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定(头节点一般不存储数据,只用于作为标识)
    因而带头节点的单链表的逻辑结构可以看作:
    java数据结构实现单链表

2.单链表的实现

需求:
使用带head头节点的单链表;
每个节点data域有no(No.顺序)和name字段,和指向下一节点的next;
需要实现对每个节点的增删改查操作

实现思路与代码:

2.1 首先我们创建这个节点类:

//定义SingleNode,每个SingleNode对象就是一个节点 class SingleNode{ public int no; public String name; //no和name可以认为是节点的数据部分 public SingleNode next; //指向下一个节点 //构造器 public SingleNode(int no, String name) { this.no = no; this.name = name; } //为了显示方法,重新显示toString(不打印next节点,否则或造成将后续节点全部打印) @Override public String toString() { return "SingleNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } } 

2.2 然后我们写一个链表类,初始化一个头节点,然后在链表类中编写链表的增删改查方法:

//定义一个SingleLinkedList 管理链表 class SingleLinkedList{ //先初始化一个头节点,一般头节点不存储数据 private SingleNode head=new SingleNode(0,""); } 

2.3 添加节点的方法(这里按照需求,可以有两种添加方式):

2.3.1 直接添加到链表的尾部

//添加节点到单向链表 //当不考虑编号顺序时 //1.找到当前节点的最后节点 //2.将最后这个节点的next指向 新的节点 public void add(SingleNode singleNode){ //因为head头不能动,因此我们需要一个辅助遍历temp(类似于指针),先将temp指向head节点 SingleNode temp=head; //遍历链表,找到最后 while (true){ //找到链表的最后 if(temp.next==null){ break; } //如果没有找到最后,继续指向下一个 temp=temp.next; } //当退出while循环时,temp就指向了链表的最后 //将最后这个节点的next,指向新的节点 temp.next=singleNode; } 

2.3.2 按照no将节点插入到指定位置(如果有这个no,则添加失败,并给出提示)
思路分析如下:
java数据结构实现单链表

  1. 首先找到新添加的节点的位置是通过辅助变量temp(指针),通过遍历来搞定
  2. temp指向位于要添加位置的前一个节点
  3. 要添加的节点.next = temp.next
  4. 将temp.next=新添加的节点
//第二种方式在添加节点时,根据no将节点插入到指定位置 //如果有这个no,则添加失败,并给出提示 public void addByOrder(SingleNode singleNode){ //因为头节点不能动,需要一个辅助指针来帮助找到添加的位置(指向前一位) //因为单链表,因此我们找的tmep是位于添加位置的前一个节点,否则插入不了 SingleNode temp=head; boolean flag=false;//flag标志添加的编号是否存在,默认为false while(true){ if(temp.next==null){//说明temp已经在链表的最后 break; } if(temp.next.no>singleNode.no){ //位置找到,就在temp的后面插入 break; }else if(temp.next.no==singleNode.no){ //说明希望添加的编号已经存在 flag=true;//说明编号存在 break; } temp=temp.next; //后移,遍历当前链表 } //是否添加,判断flag的值 if(flag){//不能添加,说明编号存在 System.out.printf("准备插入的节点的编号 %d 已经存在了,不能加入\n",singleNode.no); }else { //插入到链表中,tmep的后面 singleNode.next=temp.next; temp.next=singleNode; } } 

2.3 修改节点data
思路分析如下:
(这里我们直接传入一个newNode,通过no找到节点,然后替换data)

  1. 先找到该节点,通过遍历
  2. temp.name = newNode.name ;
 //修改节点的信息,根据no编号来修改,即no编号不能改。 //说明:根据newNode的no来修改即可 public void update(SingleNode newNode){ //判断是否为空 if(head.next==null){ System.out.println("链表为空~"); return; } //找到需要修改的节点,根据no编号 //先定义一个辅助遍历 SingleNode temp=head.next; boolean flag=false;//表示是否找到该节点 while(true){ if(temp==null){ break; //已经遍历完链表 } if(temp.no==newNode.no){ //找到 flag=true; break; } temp=temp.next; } //根据flag 判断是否找到要修改的节点 if(flag){ temp.name=newNode.name; }else { System.out.printf("没有找到 编号 %d 的节点,不能修改\n",newNode.no); } } 

2.4 删除节点:
思路分析如下:
java数据结构实现单链表

  1. 我们先找到需要删除的这个节点的前一个节点temp
  2. temp.next = temp.next. next
  3. 被删除的节点,将不会有其它引用指向,会被垃圾回收机制回收
//删除节点 //思路: //头节点不能动,需要一个辅助指针来帮助找到待删除节点的前一个节点 //2.我们在比较时,时temp.next.no和需要删除的节点的no比较 public void del(int no){ SingleNode temp=head; boolean flag=false; //标志是否找到待删除节点 while(true){ if(temp.next==null){ //已经到链表末尾 break; } if(temp.next.no==no){ //找到的待删除节点的前一个节点temp flag=true; break; } temp=temp.next; //temp后移,遍历 } if(flag){//找到。可以删除 temp.next=temp.next.next; //删除的节点会因为垃圾回收机制被回收 }else { System.out.printf("要删除的%d 节点不存在\n",no); } } 

2.5 遍历链表

//显示链表,通过辅助变量 遍历 public void list(){ //判断链表是否为空 if (head.next == null) { System.out.printf("链表为空"); return; } //因为头节点,不能动,因此我们需要一个辅助变量来变量 SingleNode temp=head.next; while (true){ //判断是否到链表最后 if(temp==null){ break; } //不为空,输出节点信息 System.out.println(temp); //将temp后移 temp=temp.next; } } 

2.6 组合代码,编写主函数进行测试

public class SingleLinkedListDemo { public static void main(String[] args) { //进行测试 //先创建节点 SingleNode node1 = new SingleNode(1, "北京"); SingleNode node2 = new SingleNode(2, "上海"); SingleNode node3 = new SingleNode(3,"广州"); SingleNode node4 = new SingleNode(4, "深圳"); //创建一个单链表 SingleLinkedList singleLinkedList=new SingleLinkedList(); /*
        //加入
        singleLinkedList.add(node1);
        singleLinkedList.add(node2);
        singleLinkedList.add(node3);
        singleLinkedList.add(node4);
        */ //加入按照编号的顺序 singleLinkedList.addByOrder(node1); singleLinkedList.addByOrder(node2); singleLinkedList.addByOrder(node3); singleLinkedList.addByOrder(node4); singleLinkedList.list(); //测试修改节点的代码 SingleNode newHeroNode=new SingleNode(3,"重庆"); //显示 singleLinkedList.update(newHeroNode); System.out.printf("修改后的链表:\n"); singleLinkedList.list(); //删除一个节点 singleLinkedList.del(1); System.out.printf("删除后的链表情况:\n"); singleLinkedList.list(); } } 

运行结果:
java数据结构实现单链表

完整代码实现:

这里我们可以以内部类的方式编写该代码:
SingleLinkedListDemo.java:

/*
* 单链表
* */ public class SingleLinkedListDemo { public static void main(String[] args) { //进行测试 //先创建节点 SingleNode node1 = new SingleNode(1, "北京"); SingleNode node2 = new SingleNode(2, "上海"); SingleNode node3 = new SingleNode(3,"广州"); SingleNode node4 = new SingleNode(4, "深圳"); //创建一个单链表 SingleLinkedList singleLinkedList=new SingleLinkedList(); /*
        //加入
        singleLinkedList.add(node1);
        singleLinkedList.add(node2);
        singleLinkedList.add(node3);
        singleLinkedList.add(node4);
        */ //加入按照编号的顺序 singleLinkedList.addByOrder(node1); singleLinkedList.addByOrder(node2); singleLinkedList.addByOrder(node3); singleLinkedList.addByOrder(node4); singleLinkedList.list(); //测试修改节点的代码 SingleNode newHeroNode=new SingleNode(3,"重庆"); //显示 singleLinkedList.update(newHeroNode); System.out.printf("修改后的链表:\n"); singleLinkedList.list(); //删除一个节点 singleLinkedList.del(1); System.out.printf("删除后的链表情况:\n"); singleLinkedList.list(); } } //定义一个SingleLinkedList 管理链表 class SingleLinkedList{ //先初始化一个头节点,头节点不要动,一般头节点不存储数据 private SingleNode head=new SingleNode(0,""); //添加节点到单向链表 //当不考虑编号顺序时 //1.找到当前节点的最后节点 //2.将最后这个节点的next指向 新的节点 public void add(SingleNode singleNode){ //因为head头不能动,因此我们需要一个辅助遍历temp(类似于指针),先将temp指向head节点 SingleNode temp=head; //遍历链表,找到最后 while (true){ //找到链表的最后 if(temp.next==null){ break; } //如果没有找到最后,继续指向下一个 temp=temp.next; } //当退出while循环时,temp就指向了链表的最后 //将最后这个节点的next,指向新的节点 temp.next=singleNode; } //第二种方式在添加节点时,根据no将节点插入到指定位置 //如果有这个no,则添加失败,并给出提示 public void addByOrder(SingleNode singleNode){ //因为头节点不能动,需要一个辅助指针来帮助找到添加的位置(指向前一位) //因为单链表,因此我们找的tmep是位于添加位置的前一个节点,否则插入不了 SingleNode temp=head; boolean flag=false;//flag标志添加的编号是否存在,默认为false while(true){ if(temp.next==null){//说明temp已经在链表的最后 break; } if(temp.next.no>singleNode.no){ //位置找到,就在temp的后面插入 break; }else if(temp.next.no==singleNode.no){ //说明希望添加的编号已经存在 flag=true;//说明编号存在 break; } temp=temp.next; //后移,遍历当前链表 } //是否添加,判断flag的值 if(flag){//不能添加,说明编号存在 System.out.printf("准备插入的节点的编号 %d 已经存在了,不能加入\n",singleNode.no); }else { //插入到链表中,tmep的后面 singleNode.next=temp.next; temp.next=singleNode; } } //修改节点的信息,根据no编号来修改,即no编号不能改。 //说明:根据newNode的no来修改即可 public void update(SingleNode newNode){ //判断是否为空 if(head.next==null){ System.out.println("链表为空~"); return; } //找到需要修改的节点,根据no编号 //先定义一个辅助遍历 SingleNode temp=head.next; boolean flag=false;//表示是否找到该节点 while(true){ if(temp==null){ break; //已经遍历完链表 } if(temp.no==newNode.no){ //找到 flag=true; break; } temp=temp.next; } //根据flag 判断是否找到要修改的节点 if(flag){ temp.name=newNode.name; }else { System.out.printf("没有找到 编号 %d 的节点,不能修改\n",newNode.no); } } //删除节点 //思路: //头节点不能动,需要一个辅助指针来帮助找到待删除节点的前一个节点 //2.我们在比较时,时temp.next.no和需要删除的节点的no比较 public void del(int no){ SingleNode temp=head; boolean flag=false; //标志是否找到待删除节点 while(true){ if(temp.next==null){ //已经到链表末尾 break; } if(temp.next.no==no){ //找到的待删除节点的前一个节点temp flag=true; break; } temp=temp.next; //temp后移,遍历 } if(flag){//找到。可以删除 temp.next=temp.next.next; //删除的节点会因为垃圾回收机制被回收 }else { System.out.printf("要删除的%d 节点不存在\n",no); } } //显示链表,通过辅助变量 遍历 public void list(){ //判断链表是否为空 if (head.next == null) { System.out.printf("链表为空"); return; } //因为头节点,不能动,因此我们需要一个辅助变量来变量 SingleNode temp=head.next; while (true){ //判断是否到链表最后 if(temp==null){ break; } //不为空,输出节点信息 System.out.println(temp); //将temp后移 temp=temp.next; } } } //定义SingleNode,每个SingleNode对象就是一个节点 class SingleNode{ public int no; public String name; //no和name可以认为是节点的数据部分 public SingleNode next; //指向下一个节点 //构造器 public SingleNode(int no, String name) { this.no = no; this.name = name; } //为了显示方法,重新显示toString(不打印next节点,否则或造成将后续节点全部打印) @Override public String toString() { return "SingleNode{" + "no=" + no + ", name='" + name + '\'' + '}'; } } 

本文地址:https://blog.csdn.net/qq_28840013/article/details/108035096