赞
踩
单链表是一种链式存取的数据结构,用一组地址任意的存储单元存放线性表中的数据元素。链表中的数据是以结点来表示的,每个结点的构成:元素(数据元素的映象) + 指针(指示后继元素存储位置),元素就是存储数据的存储单元,指针就是连接每个结点的地址数据。
单链表(带头结点) 逻辑结构示意图如下:
首先定义一个节点类
//定义一个HeroNode类,每个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 + '\'' + '}'; } }
定义一个链表类SingleLinkedList,在其中定义添加节点的add()方法和遍历链表的showList()方法
class SingleLinkedList{ //先初始化一个头结点(一般不存放具体数据) private HeroNode head = new HeroNode(0,null,null); /* 添加节点到单链表 当不考虑编号顺序时 1.找到当前链表的最后节点 2.将尾结点的next指向新节点 */ public void add(HeroNode heroNode){ //因为head节点不能动,所以创建一个辅助遍历的节点temp HeroNode temp = head; //遍历链表,寻找尾结点 while (true){ //该节点已经是尾结点及跳出循环 if (temp.next == null){ break; } //若仍不是尾结点则继续遍历 temp = temp.next; } //退出while循环时,temp就指向了链表的尾结点 //将尾结点的next指向要插入的新节点 temp.next = heroNode; } //显示链表(遍历) public void showList(){ //判断链表是否为空 if (head == null){ System.out.println("该链表为空链表!"); return; } //因为头节点不能动,所以使用一个辅助节点进行遍历 HeroNode temp = head.next; while (true){ if (temp.next == null){ System.out.println(temp); break; } System.out.println(temp); temp = temp.next; } } }
/* 在添加英雄时,根据排名将英雄插入到指定位置 (如果有这个排名,则添加失败,并给出提示) */ public void addByOrder(HeroNode heroNode){ //因为头结点不能动,因此我们仍然通过辅助节点temp帮助找到添加的位置 //单链表中,因为我们找的temp是位于添加位置的前一个节点,否则插入不了 HeroNode temp = head; boolean flag = false; //标志添加节点的编号是否存在,默认为false while (true){ if (temp.next == null){ //说明已经遍历完链表了 break; } if (temp.next.no > heroNode.no){ //说明已找到位置,就在temp后面插入 break; }else if (temp.next.no == heroNode.no){ //说明希望添加的heroNode的编号已然存在 flag = true; //说明编号存在 break; } temp = temp.next; //遍历当前链表 } if (flag){ //节点编号已存在,无法添加 System.out.println("节点编号" + heroNode.no + "已存在,无法添加"); } else { heroNode.next = temp.next; temp.next = heroNode; } }
//修改节点信息,根据编号no修改,即编号no不能修改 public void update(HeroNode newHeroNode){ //判断是否为空 if (head.next == null){ System.out.println("该链表为空链表!"); return; } //根据编号no找到需要修改的节点 //定义一个辅助遍历的变量temp HeroNode temp = head.next; boolean flag = false; //表示是否找到该节点 while (true){ if (temp == null){ break; //已遍历完链表 } if (temp.no == newHeroNode.no){ //找到要修改的节点 flag = true; break; } temp = temp.next; } //根据flag判断节点是否被找到 if (flag){ temp.name = newHeroNode.name; temp.nickName = newHeroNode.nickName; }else { System.out.println("没有找到编号为" + newHeroNode.no + "的节点,无法修改"); } }
/* 删除节点思路: 1.头节点head不能动,因此我们需要一个temp辅助节点找到待删除节点的前一个节点 2.说明我们在比较时,是 temp.next.no 与 需要删除的节点的no比较 */ public void delete(int no){ HeroNode temp = head; boolean flag = false; //表示是否找到待删除节点 while (true){ if (temp.next == null){ //已经到链表的最后 break; } if (temp.next.no == no){ //找到的待删除节点的前一个节点temp flag = true; break; } //temp后移,继续遍历 temp = temp.next; } if (flag){ temp.next = temp.next.next; }else { System.out.println("无法编号为" + no + "的节点"); } } = true; break; } //temp后移,继续遍历 temp = temp.next; } if (flag){ temp.next = temp.next.next; }else { System.out.println("无法编号为" + no + "的节点"); } }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。