链表介绍
-单链表示意图
具有如下特征:
1.链表以节点方式存储，是链式存储
2.每个节点包含data域、next域: 指向下一个节点.
3.如上图：可以看待链表的每一个节点不一定是连续存储的。
4.链表分带头节点和没有头节点的链表:根据实际需求确定的。
下面来分析下如何实现这个结构
使用一个例子来表示，使用带head头的单向链表实现---水浒英雄榜管理。
添加英雄的时候选择两种方式：
image.png
2.按照英雄排名，插入到制定的位置，如果有这个排名了，添加失败。
image.png
3.修改节点功能，先找到该节点位置再修改，如果没存在，那么就提示失败。
4.删除节点。示意图如下:
image.png
下面来实现代码的演示:
public class SingleLinkList {
public static void main(String[] args) {
SingleLinkListDemo singleLinkListDemo = new SingleLinkListDemo();
singleLinkListDemo.list();
//调试方法一添加
/* singleLinkListDemo.add(new HeroNode(1,"宋江","及时雨"));
singleLinkListDemo.add(new HeroNode(2,"卢俊义","玉麒麟"));
singleLinkListDemo.add(new HeroNode(3,"吴用","智多星"));
singleLinkListDemo.add(new HeroNode(4,"林冲","豹子头"));*/
//调试方法二添加
singleLinkListDemo.addByOrder(new HeroNode(1,"宋江","及时雨"));
singleLinkListDemo.addByOrder(new HeroNode(5,"卢俊义","玉麒麟"));
singleLinkListDemo.addByOrder(new HeroNode(4,"吴用","智多星"));
singleLinkListDemo.addByOrder(new HeroNode(2,"林冲","豹子头"));
singleLinkListDemo.addByOrder(new HeroNode(2,"林冲","豹子头"));
singleLinkListDemo.list();
singleLinkListDemo.updateNode(new HeroNode(2,"林冲(修改版)","飞豹子头"));
singleLinkListDemo.list();
singleLinkListDemo.updateNode(new HeroNode(18,"林冲(修改版2)","飞豹子头2"));
singleLinkListDemo.list();
singleLinkListDemo.delNode(2);
singleLinkListDemo.list();
singleLinkListDemo.delNode(17);
singleLinkListDemo.list();
System.out.println("");
singleLinkListDemo.addByOrder(new HeroNode(2,"林冲","豹子头"));
singleLinkListDemo.list();
}
}
/** 定义SingleLinkList 管理*/
class SingleLinkListDemo{
/** 初始化一个头节点，对象就是一个头节点 */
private HeroNode head=new HeroNode(0,"","");
/**
* 添加节点到单链表
*
* 1. 找到当前链表的最后节点
* 2.将最后这个节点的next指向新的节点。
* */
/**
* 第一种，插入到最后一条节点的下一个
* @param heroNode
*/
public void add(HeroNode heroNode){
//因为head节点不能动，因此需要一个辅助节点
HeroNode temp=head.next;
while(true){
//找到链表的最后一个元素，这时候退出循环
if(temp==null){
break;
}
//如果没有找到最后，向后移动
temp=temp.next;
}
//把醉胡这个节点的下一个节点指向新节点。
temp=heroNode;
}
/** 第二种添加，根据排名将英雄插入指定位置*/
public void addByOrder(HeroNode heroNode){
HeroNode temp=head;
int no = heroNode.no;
//判断是否需要插入
boolean flag= false;
while(true){
//这节点为null说明已经在节点的最后了。
if(temp.next==null){
flag=true;
break;
}
if(temp.next.no < heroNode.no){
//把temp指向下一个节点
temp=temp.next;
continue;
}else if(temp.next.no == heroNode.no){
System.out.println("这个排名的英雄已经存在了");
break;
}else {
//是否能插入设置为true
flag=true;
break;
}
}
if(flag){
HeroNode next=temp.next;
temp.next=heroNode;
heroNode.next=next;
}
}
public void updateNode(HeroNode heroNode){
HeroNode temp=head;
//判断存在该节点
boolean flag= false;
while(true){
if(temp.next==null){
break;
}
if(temp.next.no < heroNode.no){
//把temp指向下一个节点
temp=temp.next;
continue;
}else if(temp.next.no == heroNode.no){
flag=true;
break;
}
}
if(flag){
temp.next.name=heroNode.name;
temp.next.nickname=heroNode.nickname;
System.out.println("成功修改该节点"+temp.next);
}else{
System.out.println("该节点不存在");
}
}
/** 执行删除指定节点 */
public void delNode(int no){
HeroNode temp=head;
//判断存在该节点
boolean flag= false;
while(true){
if(temp.next==null){
break;
}
if(temp.next.no < no){
//把temp指向下一个节点
temp=temp.next;
continue;
}else if(temp.next.no == no){
flag=true;
break;
}
}
if(flag){
temp.next=temp.next.next;
System.out.println("成功删除节点");
}else{
System.out.println("该节点不存在");
}
}
/** 遍历链表*/
public void list(){
//判断链表是否为null
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;
}
}
}
/** 定义一个HeroNode节点，每个对象代表一个节点*/
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 + '\'' +
'}';
}
}
相关代码部分解析分析，都在代码里了。
