链表
一、链表简介
1、什么是单链表
- 单链表是一直链式存储的线性结构。
- 单链表中的数据是以节点的形式存在的，每个节点有data域和next域组成，data域中存放的是节点的具体信息，next域中存放的是直接后继的存储位置。
2、链表分类
-
单链表
-
单向循环链表
-
双向循环链表
3、应用场景
二、单链表实现
1、实现方式一：尾部添加节点
1.1、创建节点类
- 图示
@H_404_56@class HeroNode { public int no; public String name; public String nickName;//以上三项就是data域 public HeroNode next;//next域 public HeroNode(int no,String name,String nickName) {//为什么只有数据域? this.no = no; this.name = name; this.nickName = nickName; } @Override public String toString() {//这里不能加入next,如果加入,会是什么情况?===>>>打印所有以后的结点 return "HeroNode{" + "no=" + no + ",name='" + name + '\'' + ",nickName='" + nickName + '\'' + '}'; } }
- 注意事项
- 构造器中，参数只有数据域部分。因为新节点本来的next域就是空的，在插入的时候才会进行赋值。
- toString方法，同样只有数据域的信息。如果写了next域会发生什么？next域存放的是下一个节点的信息，如果写上next域，就会打印下一个节点的信息。
1.2、创建链表类
-
首先要考虑链表包含哪些信息
-
图示
@H_404_56@//2-1 创建单链表ADT:SingleLinkedList类,来管理这些节点 class SingleLinkedList{ //带头节点的单链表 private HeroNode head = new HeroNode(0,"",""); /* add方法 1.因为是添加,所以要给我要添加的东西--->在形参提供节点 2.因为是添加到结尾,所以要先找到结尾--->辅助变量temp,从head开始后移 @param heroNode */ public void add(HeroNode heroNode){ //辅助变量 HeroNode temp = head; //这是一种套路,先看是否到了结尾,再后移,形成一种循环 while(true){ if(temp.next == null){ break; } temp = temp.next; } temp.next = heroNode; } /* list方法 遍历思想:完整思想--->从最小不间断的考虑到最大--->链表为0,1,2,3...n个节点分别要做什么 */ public void list(){ //0个节点的情况 if(head.next == null){ System.out.println("链表为空"); return; } //不为零的情况:这类情况可以统一考虑 HeroNode temp = head.next; while(true){ if (temp == null){ break; } System.out.println(temp); temp = temp.next; } } /* delete方法 1.删除要知道删除谁--->形参传入No 2.delete方法要找到删除的结点--->遍历找到 2.1找到结尾,返回 2.2找到对应的No,返回 2.3否则,继续 */ public void del(int no){ HeroNode temp = head; boolean flag = false; while(true){ if(temp.next == null){ break; } if (temp.next.no == no){ flag = true; break; } temp = temp.next; } if (flag){ temp.next = temp.next.next;//JVM自动回收 System.out.println("delete ok"); }else{ System.out.printf("要删除的结点%d不存在",no); } } }
2、实现方式二：顺序添加节点
-
实现思路：找到要插入节点的插入位置最为关键
- 用辅助变量temp来遍历链表，用布尔变量来标志是否找到插入位置
- 循环的跳出条件是找到结尾：
temp.next == null - 循环的进行条件是
插入节点的编号 > temp的编号 - 找到的条件是
temp.next.no > heroNode.no - 已存在的条件是
temp.next.no == heroNode.no
-
注意
- 因为是单链表，temp要保持在要插入节点的前一个位置，否则无法插入。（因为插入要用到插入的前一个节点，但是单链表无法表示前一个节点的信息）
-
代码实现
@H_404_56@public void addByOrder(HeroNode heroNode){ HeroNode temp = head; boolean isExist = false; while (temp.next != null){ if (temp.next.no > heroNode.no){ break; }else if(temp.next.no == heroNode.no){ isExist = true; break; } temp = temp.next; } if (isExist){ System.out.printf("准备插入的节点 %d 已存在\n",heroNode.no); }else { heroNode.next = temp.next; temp.next = heroNode; } }
3、删改的方法
- delete方法的实现
@H_404_56@/* delete方法 1.删除要知道删除谁--->形参传入No 2.delete方法要找到删除的结点--->遍历找到 3.因为是单链表,无法得到前一个节点的信息,所以要找到目标节点时,temp指向的是目标节点的前一个节点. */ public void delete(int no){ if (head.next == null){ System.out.println("单链表为空,无法删除"); return; } HeroNode temp = head; boolean isFound = false; while(temp.next != null){ if (temp.next.no == no){ isFound = true; break; } temp = temp.next; } if (isFound){ temp.next = temp.next.next;//JVM自动回收 System.out.println("delete ok"); }else{ System.out.printf("要删除的结点%d不存在\n",no); } }
- update方法实现
@H_404_56@/* 修改节点信息:以编号为基准,修改名字和昵称 */ public void update(HeroNode newHeroNode){ //先判断链表为空的情况,这样可以避免创建两个临时使用的变量 if (head.next == null){ System.out.println("链表为空,无法修改"); return; } HeroNode temp = head.next; boolean isFound = false; while (temp != null){ if (newHeroNode.no == temp.no){ isFound = true; break; } temp = temp.next; } if (isFound){ temp.name = newHeroNode.name; temp.nickName = newHeroNode.nickName; }else{ System.out.printf("没有找到要修改的结点%d\n",newHeroNode.no); } }
