java数据结构实现单链表
程序员文章站
2022-09-26 23:31:41
参考于 尚硅谷Java数据结构与java算法,韩顺平数据结构与算法1.什么是链表:链表是有序的列表,但是它在内存中可以以不连续空间存放,存储如下根据上图,可以发现:链表是以节点的方式来存储,是链式存储每个节点包含 data 域,next域:指向下一个节点.链表的各个节点不一定是连续存储.链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定(头节点一般不存储数据,只用于作为标识)因而带头节点的单链表的逻辑结构可以看作:2.单链表的实现需求:使用带head头节点的单链表;...
1.什么是链表:
链表是有序的列表,但是它在内存中可以以不连续空间存放,存储如下
根据上图,可以发现:
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含 data 域,next域:指向下一个节点.
- 链表的各个节点不一定是连续存储.
-
链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定(头节点一般不存储数据,只用于作为标识)
因而带头节点的单链表的逻辑结构可以看作:
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,则添加失败,并给出提示)
思路分析如下:
- 首先找到新添加的节点的位置是通过辅助变量temp(指针),通过遍历来搞定
- temp指向位于要添加位置的前一个节点
- 要添加的节点.next = temp.next
- 将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)
- 先找到该节点,通过遍历
- 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 删除节点:
思路分析如下:
- 我们先找到需要删除的这个节点的前一个节点temp
- temp.next = temp.next. next
- 被删除的节点,将不会有其它引用指向,会被垃圾回收机制回收
//删除节点 //思路: //头节点不能动,需要一个辅助指针来帮助找到待删除节点的前一个节点 //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(); } }
运行结果:
完整代码实现:
这里我们可以以内部类的方式编写该代码:
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