单向链表的java实现 详细讲解
链表的介绍
概念
链表是有序的列表,但是它在内存中是存储如下
小结:
- 链表是以节点的方式来存储,是链式存储
- 每个节点包含 data 域, next 域:指向下一个节点.
- 如图:发现链表的各个节点不一定是连续存储.
- 链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定
单链表的应用实例
案例
使用带head头的单向链表实现 –水浒英雄排行榜管理完成对英雄人物的增删改查操作, 注: 删除和修改,查找
解题思路
1、增加
2、顺序添加(按照no由小到大排序)
3、修改和删除节点(原理差不多)
代码实现
1、新建英雄类,定义编号,名字,绰号,下一个节点的基本属性
class HeroNode{ public int no; public String name; public String nickName; public HeroNode next; public HeroNode(){} 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 + '}'; }}
2、新建LinkedList类,实现节点的增删改查方法
class SingleLinkedList{ private HeroNode hero=new HeroNode(0,"",""); public SingleLinkedList(){} //增加节点 public void add(HeroNode heroNode){ HeroNode temp=hero; while (true){ if (temp.next==null){ break; } temp=temp.next; } temp.next=heroNode; } //按照编号顺序排列 public void addOrderly(HeroNode heroNode){ HeroNode temp=hero; boolean isExist=false; //判断该编号是否存在 while (true){ if (temp.next==null){ break; }else if (temp.next.no>heroNode.no){ break; }else if (temp.next.no==heroNode.no){ isExist=true; break; } temp=temp.next; } if (isExist){ System.out.println("该编号已存在~~~"+heroNode.no); }else{ heroNode.next=temp.next; temp.next=heroNode; } } //遍历节点 public void list(){ HeroNode temp=hero; if (temp.next==null){ System.out.println("未有节点信息~~~"); return; } while (true){ temp=temp.next; System.out.println(temp); if (temp.next==null){ break; } } } //更新节点信息 public void update(HeroNode newNode){ if (hero.next==null){ System.out.println("节点为空~~~"); return; } boolean isFind=false; HeroNode temp=hero.next; while (true){ if (temp.next==null){ break; }else if (temp.next.no==newNode.no){ isFind=true; break; } temp=temp.next; } if (isFind){ temp.next.name=newNode.name; temp.next.nickName=newNode.nickName; }else{ System.out.println("未找到该元素~~~"); } } //删除节点信息 public void delete(int no){ if (hero.next==null){ System.out.println("节点为空~~~"); return; } boolean isFind=false; HeroNode temp=hero; while (true){ if (temp.next==null){ break; }else if (temp.next.no==no){ isFind=true; break; } temp=temp.next; } if (isFind){ temp.next=temp.next.next; }else{ System.out.println("未找到该元素~~~"); } }}
3、代码整合,整合英雄类和linkedList类
package com.qf.linkedList;public class SingleLinkedListDemo { public static void main(String[] args) { HeroNode heroNode1=new HeroNode(1,"宋江","及时雨"); HeroNode heroNode2=new HeroNode(2,"卢俊义","玉麒麟"); HeroNode heroNode3=new HeroNode(3,"吴用","智多星"); HeroNode heroNode4=new HeroNode(4,"林冲","豹子头"); SingleLinkedList singleLinkedList=new SingleLinkedList(); //add 添加节点 /* singleLinkedList.add(heroNode3); singleLinkedList.add(heroNode4); singleLinkedList.add(heroNode1); singleLinkedList.add(heroNode2); singleLinkedList.list();*/ //按照编号顺序添加节点 singleLinkedList.addOrderly(heroNode3); singleLinkedList.addOrderly(heroNode4); singleLinkedList.addOrderly(heroNode1); singleLinkedList.addOrderly(heroNode2); singleLinkedList.list(); //更新节点信息 System.out.println("更新后的节点"); HeroNode newNode=new HeroNode(3,"吴用new","智多星new"); singleLinkedList.update(newNode); singleLinkedList.list(); //删除节点信息 System.out.println("删除后的节点"); singleLinkedList.delete(3); singleLinkedList.delete(1); singleLinkedList.delete(2); singleLinkedList.list(); }}class HeroNode{ public int no; public String name; public String nickName; public HeroNode next; public HeroNode(){} 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 + '}'; }}class SingleLinkedList{ private HeroNode hero=new HeroNode(0,"",""); public SingleLinkedList(){} //增加节点 public void add(HeroNode heroNode){ HeroNode temp=hero; while (true){ if (temp.next==null){ break; } temp=temp.next; } temp.next=heroNode; } //按照编号顺序排列 public void addOrderly(HeroNode heroNode){ HeroNode temp=hero; boolean isExist=false; //判断该编号是否存在 while (true){ if (temp.next==null){ break; }else if (temp.next.no>heroNode.no){ break; }else if (temp.next.no==heroNode.no){ isExist=true; break; } temp=temp.next; } if (isExist){ System.out.println("该编号已存在~~~"+heroNode.no); }else{ heroNode.next=temp.next; temp.next=heroNode; } } //遍历节点 public void list(){ HeroNode temp=hero; if (temp.next==null){ System.out.println("未有节点信息~~~"); return; } while (true){ temp=temp.next; System.out.println(temp); if (temp.next==null){ break; } } } //更新节点信息 public void update(HeroNode newNode){ if (hero.next==null){ System.out.println("节点为空~~~"); return; } boolean isFind=false; HeroNode temp=hero.next; while (true){ if (temp.next==null){ break; }else if (temp.next.no==newNode.no){ isFind=true; break; } temp=temp.next; } if (isFind){ temp.next.name=newNode.name; temp.next.nickName=newNode.nickName; }else{ System.out.println("未找到该元素~~~"); } } //删除节点信息 public void delete(int no){ if (hero.next==null){ System.out.println("节点为空~~~"); return; } boolean isFind=false; HeroNode temp=hero; while (true){ if (temp.next==null){ break; }else if (temp.next.no==no){ isFind=true; break; } temp=temp.next; } if (isFind){ temp.next=temp.next.next; }else{ System.out.println("未找到该元素~~~"); } }}