Java版单链表讲解

链表介绍

链表是有序的列表&＃xff0c;但是它在内存中是存储如下

1.链表是以节点的方式来存储,是链式存储
2.每个节点包含 data 域&＃xff0c; next 域&＃xff1a;指向下一个节点.
3.如图&＃xff1a;发现链表的各个节点不一定是连续存储.
4.链表分带头节点的链表和没有头节点的链表&＃xff0c;根据实际的需求来确定

单链表介绍

单链表&＃xff08;带头节点&＃xff09;逻辑结构示意图如下

单链表应用实例

使用带head头的单向链表实现 –漫威英雄排行榜管理
完成对英雄人物的增删改查操作&＃xff0c; 注: 删除和修改,查找

• 第一种方法在添加英雄时&＃xff0c;直接添加到链表的尾部
• 第二种方式在添加英雄时&＃xff0c;根据排名将英雄插入到指定位置 (如果有这个排名&＃xff0c;则添加失败&＃xff0c;并给出提示)

package linkedlist;public class SingleLinkedListDemo {public static void main(String[] args) {//测试//先创建节点HeroNode heroNode1 &＃61; new HeroNode(1, "托尼·史塔克", "钢铁侠");HeroNode heroNode2 &＃61; new HeroNode(2, "班纳博士", "绿巨人");HeroNode heroNode3 &＃61; new HeroNode(3, "斯嘉丽", "黑寡妇");HeroNode heroNode4 &＃61; new HeroNode(4, "帕克", "蜘蛛侠");HeroNode heroNode5 &＃61; new HeroNode(5, "洛基", "神");//创建链表SingleLinkedList singleLinkedList &＃61; new SingleLinkedList();//加入singleLinkedList.addByOrder(heroNode5);singleLinkedList.addByOrder(heroNode2);singleLinkedList.addByOrder(heroNode1);singleLinkedList.addByOrder(heroNode4);singleLinkedList.addByOrder(heroNode3);singleLinkedList.addByOrder(heroNode3);//显示
// singleLinkedList.list();//测试修改节点的代码HeroNode newHeroNode &＃61; new HeroNode(2, "baihaibai", "AHAHAHA");singleLinkedList.update(newHeroNode);singleLinkedList.list();System.out.println();//删除节点singleLinkedList.del(1);singleLinkedList.del(3);singleLinkedList.list();}
}
//定义SingleLinkedList 管理我们的英雄
class SingleLinkedList{//先初始化一个头节点&＃xff0c;头节点不要动&＃xff0c;不存放具体的数据private HeroNode head &＃61; new HeroNode(0, "", "");//添加节点到单链表//思路&＃xff0c;当不考虑编号顺序时//1&＃xff0c;找到当前链表的最后节点//2&＃xff0c;将最后这个节点的next 指向新的节点public void add(HeroNode heroNode){//因为head节点不能动&＃xff0c;因此我们需要一个辅助遍历tempHeroNode temp &＃61; head;//遍历链表&＃xff0c;找到最后while(true){if(temp.next &＃61;&＃61; null){break;}//如果没有找到最后&＃xff0c;将temp后移temp &＃61; temp.next;}//当退出while循环时&＃xff0c;temp就指向了链表的最后//将最后这个节点的next 指向 新的节点temp.next &＃61; heroNode;}public void list(){//判断链表是否为空if(head.next &＃61;&＃61; null){System.out.println("链表为空");return;}//因为头节点不能动&＃xff0c;需要一个辅助变量遍历整个链表HeroNode temp &＃61; head.next;while(true){//判断是否到链表最后if(temp &＃61;&＃61; null){break;}//输出节点的信息System.out.println(temp);//将temp后移&＃xff0c;一定要记住要后移&＃xff0c;不然是死循环temp &＃61; temp.next;}}//第二种方式添加英雄时&＃xff0c;根据排名将英雄插入到指定位置//(如果有这个排名&＃xff0c;则添加失败&＃xff0c;并给出提示)public void addByOrder(HeroNode heroNode){//因为头节点不能动&＃xff0c;因此我们仍然通过一个辅助指针&＃xff08;变量&＃xff09;来帮助找到添加的位置//因为单链表&＃xff0c;因为我们找的temp 是位于 添加位置的前一个节点&＃xff0c;否则插入不了HeroNode temp &＃61;head;boolean flag &＃61; false;//flag 标志添加的编号是否存在&＃xff0c;默认为falsewhile(true){if(temp.next &＃61;&＃61; null){//说明temp已经在链表的最后break;}if(temp.next.no>heroNode.no){//位置找到&＃xff0c;就在temp的后面插入break;}else if(temp.next.no&＃61;&＃61;heroNode.no){flag &＃61; true;break;}temp &＃61; temp.next;//后移&＃xff0c;遍历当前链表}//判断flag的值if(flag){System.out.println("准备插入的英雄编号已经存在"&＃43;heroNode.no);}else{//插入到链表中&＃xff0c;temp的后面heroNode.next &＃61; temp.next;temp.next&＃61;heroNode;}}//根据newHeroNode 的no来修改即可public void update(HeroNode newHeroNode){//判断是否为空if(head.next&＃61;&＃61;null){System.out.println("链表为空");return;}//找到需要修改的节点&＃xff0c;根据no编号//定义一个辅助变量HeroNode temp &＃61; head.next;boolean flag &＃61; false;//表示是否找到该节点while(true){if(temp &＃61;&＃61; null){break;//已经遍历完链表}if(temp.no&＃61;&＃61;newHeroNode.no){//找到flag&＃61; true;break;}temp &＃61; temp.next;}if(flag){temp.name &＃61; newHeroNode.name;temp.nickname &＃61; newHeroNode.nickname;}else{//没有找到System.out.println("没有找到编号为"&＃43;newHeroNode.no&＃43;"节点&＃xff0c;不能修改");}}//删除节点//思路//1 head不能动&＃xff0c;因此我们需要一个temp辅助节点找到删除节点的前一个结点//2 说明我们在比较时&＃xff0c;是temp.next.no 和 需要删除的节点no比较public void del(int no){HeroNode temp &＃61; head;boolean flag &＃61; false;//标志是否找到待删除结点的前一个结点while(true){if(temp.next&＃61;&＃61;null){//已经到链表的最后break;}if(temp.next.no&＃61;&＃61;no){//找到了待删除节点的其前一个结点flag &＃61; true;break;}temp &＃61; temp.next;}//判断flagif(flag){//找到 可以删除temp.next &＃61; temp.next.next;}else{System.out.println("要删除的节点"&＃43;no&＃43;"不存在");}}}//定义HeroNode,每个HeroNode对象就是一个节点
class HeroNode{public int no;public String name;public String nickname;public HeroNode next;//指向下一个节点//构造器public HeroNode(int no,String name,String nickname){super();this.no &＃61; no;this.name &＃61; name;this.nickname &＃61; nickname;}//重写toString()&＃64;Overridepublic String toString() {return "HeroNode [no&＃61;" &＃43; no &＃43; ", name&＃61;" &＃43; name &＃43; ", nickname&＃61;" &＃43; nickname &＃43; "]";}}