3.数据结构与算法学习笔记（单链表的增删改查） 3.数据结构与算法学习笔记：单

链表（Linked List）链表是有序的列表

1. 链表分两种，带头节点的链表和没有带头节点的链表，根据实际需求来确定 2. 链表是以节点的方式来存储的，是链式存储 3. 每个节点包括data域，next域，指向下一个节点 4. 如图：发现链表的各个节点不一定是连续存放的

文章图片

? 在内存中的实际结构

文章图片

? 逻辑结构
单链表的应用实例：使用带head头的单向链表实现–水浒英雄排行榜的管理

1. 完成对英雄人物的增删改查操作2. 第一种方法在添加英雄时，直接添加到链表的尾部3. 第二种方法在添加英雄时，根据排名将英雄插入到指定位置（如果有这个排名，则添加失败，并且给出提示）

【3.数据结构与算法学习笔记（单链表的增删改查）】思路分析：

添加： 1.创建一个head头节点，表示单链表的头 2.每添加一个节点，就直接加入到链表的最后遍历 3.判断遍历结果，如果next为空，那么就跳出循环，把添加进去的数据设置成这个节点对象的next（新节点） 4.如果不为空，那么把next（新节点）的值设置给节点，继续遍历新节点

文章图片

package com.ry.linkedlist; public class singleLinkendDemo { public static void main(String[] args) { //进行测试 //先创建一个节点 heroNode her01 = new heroNode(1, "宋江", "及时雨"); heroNode her02 = new heroNode(2, "卢俊义", "玉麒麟"); heroNode her03 = new heroNode(3, "吴用", "智多星"); heroNode her04 = new heroNode(4, "林冲", "豹子头"); //创建一个链表 glLinkedList list = new glLinkedList(); list.add(her01); list.add(her02); //list.add(her03); //list.add(her04); //显示 list.list(); } }//定义管理类 class glLinkedList{ //实例化一个固定的头节点，要保证它不能动 privateheroNode herd= new heroNode(0,"",""); //添加节点到单向链表 /* * 思路：当不考虑编号序列时候 * 1.找到当前链表的最后节点 * 2.最后将这个节点的next指向新的节点 * */public voidadd(heroNode heronode){heroNode temp=herd; //遍历链表找到链表的最后 while(true){ //如果找到了链表的最后 if (temp.next==null){ break; } //如果没有找到最后，将temp后移 temp=temp.next; } //当退出while循环的时候，temp就指向了链表的最后 //最后将这个节点的next指向新的节点 temp.next=heronode; }//显示链表【遍历】 public void list(){ //判断链表是否为空 if(herd.next==null){ System.out.println("链表为空"); return; } //因为头节点不能动，因此我们需要一个辅助变量来遍历 heroNode temp=herd.next; while(true){ //判断是否到链表最后 if (temp==null){ break; } //输出节点的信息 System.out.println(temp); //将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; }@Override public String toString() { return "heroNode{" + "no=" + no + ", name='" + name + '\'' + ", nickname='" + nickname + '\'' + ", next=" + next + '}'; } }

增：查：单链表按顺序来插入节点

需要按照编号的顺序添加1.首先找到新添加的节点的位置，是通过辅助变量（指针），通过遍历来搞定2.新的节点的.next=temp.next3.将temp.next=新的节点

public void addByOrder (heroNode heronode){ //因为头节点不能动，因此我们仍然通过一个辅助指针（变量）来帮助找到添加的位置 //因为单链表，因为我们要找的temp是位于添加位置的前一个节点，否则插入不了 heroNode temp=herd; boolean flag=false; while(true){ if (temp.next==null){ break; } if (temp.next.no>heronode.no){ break; }else if(temp.next.no==heronode.no){ //说明想要添加的值已经才能在 flag=true; break; }temp=temp.next; } if (flag){ System.out.println("要插入的节点"+heronode.no+"已经存在"); }else { heronode.next=temp.next; temp.next=heronode; } }

改：单链表节点的修改，根据编号来修改即编号不能修改

public void update(heroNode newheronode){ //判断节点的next是否为空 if(herd.next==null){ System.out.println("链表为空"); return; } //如果不为空 //找到需要修改的节点，根据编号 //定义一个辅助变量 heroNode temp=herd.next; boolean flag=false; while(true){ if (temp==null){ break; //已经遍历完列表了 } if (temp.no==newheronode.no){ //找到了 flag=true; break; } //如果当前节点未找到，把指针后移一位 temp=temp.next; } //根据flag判断是否找到要修改的节点 if(flag){ //根据已经找到节点返回的flag，把编号相同的节点的值name和nickname修改 temp.name=newheronode.name; temp.nickname=newheronode.nickname; }else{ System.out.println("没有找到编号"+newheronode.no+"不能修改"); } }

删：从单链表中删除一个节点的思路

1.我们先找到需要删除的这个节点的前一个节点temp 2.temp.next=temp.next.next 3.被删除的节点，将不会有其他引用指向，会被垃圾回收机制回收

//删除节点 //1.head不能动，因此我们需要一个temp辅助节点找到待删除的节点 //2.我们在比较时，是temp.next.no和需要删除的节点的no进行比较 public void del(int no){ heroNode temp=herd; boolean flag=false; while(true){ if (temp.next==null){ break; } if (temp.next.no==no){ //找到待删除 // 节点的前一个节点temp flag=true; break; } temp=temp.next; } //判断flag if (flag){ temp.next=temp.next.next; }else{ System.out.println("要删除的"+no+"节点不存在"); } }