Java实现对单链表的增删修改与遍历

叁歲伎倆 2022-11-30 13:00 84阅读 0赞

首先，链表是存储数据有序的列表，每个数据都存在一个节点之中，每个节点组成的存储结构中都会存在一个地址，数据域和指向下一个节点地址的next域（其实这个next域就是下个节点的地址），内存中链表的分布结构图如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODU3OTU1_size_16_color_FFFFFF_t_70_pic_center]  
每个链表可以有一个头结点或者可以没有(具体应用场景具体对待)，以数据a2为例，next域指向的是a3这个节点的地址,如果下一个指针没有节点的话，next域就会是null,也就是说a6为最后一个节点，这就是所谓的链表中的链式存储的方式。

**综上就三点：**

*  链表以节点的方式进行存储
 *  每个节点包括数据域，next域，并且next域是指向下一个节点地址的
 *  各个节点之间并不一定是连续存储的

为了便于理解，我们可以用逻辑结构进行分析即可,这样就会便于理解了：  
![在这里插入图片描述][20200824212526170.png_pic_center]  
下面通过一个简单的实际中的例子实现对单链表的增删改查

英雄节点类(`HeroNode.java`)，内部保存了英雄人物的基本数据和next域

/** * 声明一个node节点 * @author jektong * @Date 2020-8-23 16:45:38 */
    public 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()方法好打印各个节点的信息
    	@Override
    	public String toString() { 
    		return "HeroNode [no=" + no + ", name=" + name + ", 
    				nickName=" + nickName + "]";
    	}	
    }

**1. 添加节点**

添加节点的思路是这样的：

*  首先创建一个头结点不放任何的数据
 *  添加每一个节点只需要判断当前节点的下个节点是否为空即可，空就添加
 *  链表是静态的，需要借助一个辅助节点变量进行遍历整个链表

这次添加不考虑编号的顺序，直接添加至链表的末尾  
定义一个`SingleLinkedList.java`的类：

/** * @author jektong * @Date 2020-8-23 17:03:39 */
    public class SingleLinkedList { 
    	//初始化一个头节点
    	private HeroNode headNode = new HeroNode(0, "", "");
    	//添加节点到单向列表中
    	//不考虑编号的顺序直接添加至尾部即可
    	public void add(HeroNode heroNode) { 
    		//定义辅助变量进行遍历链表,初始变量指向头结点
    		HeroNode temp = headNode;
    		//循环遍历
    		while(true) { 
    			//找到链表的最后，当前节点的下个节点域诶null,说明该节点就是最后节点了
    			if(temp.next == null) { 
    				break;//退出循环
    			}
    			//如果没有找到最后就将temp后移，继续遍历
    			temp = temp.next;
    		}
    		//退出while循环之后
    		//将添加进来的节点加入到该节点之后即可即可
    		temp.next = heroNode; 
    	}
    	
    	//遍历链表
    	public void list() { 
    		//判断当前链表是否为空
    		if(headNode.next == null) { 
    			System.out.println("链表为空");
    			return;
    		}
    		//不为空定义一个初始化辅助变量指向头结点的下一个节点
    		HeroNode temp = headNode.next;
    		while(true) { 
    			//判断是否到链表的最后
    			if(temp == null) { 
    				break;
    			}
    			//输出节点的信息
    			System.out.println(temp);
    			//将temp进行后移动
    			temp = temp.next;
    		}
    	}
    }

经过测试上述代码是没有问题的

下面通过**编号顺序**进行添加：

*  首先要找到添加的位置（通过遍历的方式）
 *  新的节点.next = temp.next;
 *  temp.next = 新的节点

代码：源代码添加一个`addOrderBy()`方法

//考虑编号的顺序添加
    //若有相同的编号则添加失败
    public void addOrderBy(HeroNode heroNode) { 
    	//通过辅助指针找位置（因为head是不能动的）
    	//还有一点，temp必须是处于待添加节点的前一个节点，不然会添加失败
    	HeroNode temp = headNode;
    	//定义一个标志位否存在此编号，默认为不存在
    	boolean flag = false;
    	//循环开始
    	while(true) { 
    		//临时变量的下一个为null则直接加入后面 
    		if(temp.next == null) { 
    			break;
    		//临时变量的下一个no大于添加新的node的no，可以添加
    		}else if(temp.next.no > heroNode.no) { 
    			break;
    		}else if(temp.next.no == heroNode.no) { //no重复
    			flag = true;//不可添加
    			break;
    		}
    		//继续往后进行遍历
    		temp = temp.next;
    	}
    	
    	if(flag) { //为true,不可添加
    		System.out.println(heroNode.no + "此节点已经存在，不可添加！");
    	}else { //可以进行添加，就两步骤
    		heroNode.next = temp.next;
    		temp.next = heroNode;
    	}
    }

**2.修改**

修改肯定是通过编号进行修改的，首先判断链表不可为空就需要找到删除的编号no

//修改节点中的数据，根据no进行修改
    public void update(HeroNode newHeroNode) { 
    	//判断链表是否为空
    	if(headNode.next == null) { 
    		System.out.println("节点为空，不可进行修改！！！");
    		return;
    	}
    	//找到需要修改的节点编号no,定义辅助变量temp
    	HeroNode temp = headNode.next;
    	boolean flag = false;
    	while(true) { 
    		if(temp == null) { 
    			break;//遍历结束
    		}
    		//编号找到，修改标志
    		if(temp.no == newHeroNode.no) { 
    			flag = true;
    			break;
    		}
    		//没有找到就往下找
    		temp = temp.next;
    	}
    	if(flag) { //找到了进行赋值
    		temp.name = newHeroNode.name;
    		temp.nickName = newHeroNode.nickName;
    	}else { //没有找到
    		System.out.println("没有找到节点" + newHeroNode.no + "的数据");
    	}
    }

**3.删除节点**

找到要删除的节点编号，直接将指针移动到下下个节点即可，`temp.next=temp.next.next;`

//删除节点元素
    public void del(int no) { 
    	//辅助指针指向头结点
    	HeroNode temp = headNode;
    	//标志是否找到待删除的节点
    	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;
    	}else { 
    		System.out.println("无法删除，要删除的节点" + no +"不存在");
    	}
    }

以上全部关于链表的基本操作已经分析完了  
总的代码和测试的代码如下：

package com.jektong.linkedList;
    
    /** * @author jektong * @Date 2020-8-23 17:03:39 */
    public class SingleLinkedList { 
    //初始化一个头节点
    private HeroNode headNode = new HeroNode(0, "", "");
    //添加节点到单向列表
    //不考虑编号顺序直接添加至尾部
    public void add(HeroNode heroNode) { 
    	//定义辅助变量进行遍历链表
    	HeroNode temp = headNode;
    	while(true) { 
    		//找到链表的最后
    		if(temp.next == null) { 
    			break;
    		}
    		//如果没有找到最后就将temp后移
    		temp = temp.next;
    	}
    	//退出while循环之后，temp指向了null
    	//将添加进来的节点加入即可
    	temp.next = heroNode; 
    }
    
    //考虑编号的顺序添加
    //若有相同的编号则添加失败
    public void addOrderBy(HeroNode heroNode) { 
    	//通过辅助指针找位置（head不动的）
    	HeroNode temp = headNode;
    	//定义一个标志位否存在此节点，默认为不存在
    	boolean flag = false;
    	//循环开始
    	while(true) { 
    		if(temp.next == null) { //临时变量的下一个为null则直接加入后面
    			break;
    		}else if(temp.next.no > heroNode.no) { //临时变量的下一个no大于添加新的node的no，可以添加
    			break;
    		}else if(temp.next.no == heroNode.no) { //no重复
    			flag = true;
    			break;
    		}
    		//继续往后进行遍历
    		temp = temp.next;
    	}
    	
    	if(flag) { 
    		System.out.println(heroNode.no + "此节点已经存在，不可添加！");
    	}else { 
    		heroNode.next = temp.next;
    		temp.next = heroNode;
    	}
    }
    
    //修改节点中的数据，根据no进行修改
    public void update(HeroNode newHeroNode) { 
    	//判断是否为空
    	if(headNode.next == null) { 
    		System.out.println("节点为空，不可进行修改！！！");
    		return;
    	}
    	//找到需要修改的节点
    	HeroNode temp = headNode.next;
    	boolean flag = false;
    	while(true) { 
    		if(temp == null) { 
    			break;//遍历结束
    		}
    		if(temp.no == newHeroNode.no) { 
    			flag = true;
    			break;
    		}
    		temp = temp.next;
    	}
    	if(flag) { 
    		temp.name = newHeroNode.name;
    		temp.nickName = newHeroNode.nickName;
    	}else { //没有找到
    		System.out.println("没有找到节点" + newHeroNode.no + "的数据");
    	}
    }
    
    //删除节点元素
    public void del(int no) { 
    	//辅助指针指向头结点
    	HeroNode temp = headNode;
    	//标志是否找到待删除的节点
    	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;
    	}else { 
    		System.out.println("无法删除，要删除的节点" + no +"不存在");
    	}
    }
    //遍历链表
    public void list() { 
    	//判断链表是否为空
    	if(headNode.next == null) { 
    		System.out.println("链表为空");
    		return;
    	}
    	HeroNode temp = headNode.next;
    	while(true) { 
    		//判断是否到链表的最后
    		if(temp == null) { 
    			break;
    		}
    		//输出节点的信息
    		System.out.println(temp);
    		//指向下一个节点
    		temp = temp.next;
    	}
    }
    }

测试代码：

package com.jektong.linkedList;
    public class TestSingleLinkedList { 
    	public static void main(String[] args) { 
    		HeroNode hero1 = new HeroNode(1, "张三", "小张");
    		HeroNode hero2 = new HeroNode(2, "李四", "小李");
    		HeroNode hero3 = new HeroNode(3, "王五", "小王");
    		
    		SingleLinkedList list = new SingleLinkedList();
    		list.addOrderBy(hero1);
    		list.addOrderBy(hero3);
    		list.addOrderBy(hero2);
    		list.list();
    		System.out.println("修改之后====");
    		HeroNode newHero3 = new HeroNode(5, "王六", "小王六");
    		list.update(newHero3);
    		list.list();	
    		System.out.println("删除之后====");
    		list.del(1);
    		list.del(3);
    		list.del(2);
    		list.list();
    	}
    }

运行结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODU3OTU1_size_16_color_FFFFFF_t_70_pic_center 1]  
请自行测试

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODU3OTU1_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/32a2b8f29ac54a6a85d23c3f7b656a5f.png
[20200824212526170.png_pic_center]: /images/20221123/f9cbfce91df84094877f992ab2ca7251.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxODU3OTU1_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/ec45211fd8b54d1dbb29928f6cdd5fc6.png