Java实现带头结点的单链表

链表的特点

张家川回族自治网站建设公司创新互联,张家川回族自治网站设计制作,有大型网站制作公司丰富经验。已为张家川回族自治上千余家提供企业网站建设服务。企业网站搭建\成都外贸网站建设要多少钱,请找那个售后服务好的张家川回族自治做网站的公司定做!

1,以节点方式存储,是链式结构。

2,每个节点包含data域,next域:指向下一个节点。

3,链表的各个节点不一定是连续存储。

4,链表分为带头节点和不带头节点两种类型的链表。

实现原理

添加节点:如下图所示,首先遍历原有链表,找到最后一个节点,将要增加的节点添加到该节点的后面。下面介绍如何找到最后一个节点。

Java实现带头结点的单链表

思路是这样的,先遍历整个链表,定义一个辅助变量temp,用于暂时存储遍历出来的各个节点。首先将head头节点赋给temp(从头节点开始遍历),通过一个死循环不断的遍历节点的next,直到temp.next==null时,该节点temp就是链表的最后一个节点,只需要将该节点的next指向新增节点就行了。

修改节点:首先遍历整个链表,通过传入的编号去匹配原有的链表的编号,找到对应的编号将节点里面的数据替换即可。

删除节点:如图所示,要删除某一节点,需要遍历整个链表,找到该节点对应的编号,再将该前一个节点的next指向要删除的节点的后面的一个节点,即(temp.next = temp.next.next)。由于被删除的节点没有被引用,将会被垃圾回收机制回收掉。

Java实现带头结点的单链表

主要代码

package cn.mrlij.linkedlist;
/***
 * 单链表的实现
 * @author dreamer
 *
 */
public class SingleLinkedList {
 public static void main(String[] args) {
 SingleLinkedListDemo s = new SingleLinkedListDemo();
 HeroNode h2 = new HeroNode(1, "宋江", "及时雨");
 HeroNode h3 = new HeroNode(3, "卢俊义", "玉麒麟");
 HeroNode h4 = new HeroNode(4, "吴用", "智多星");
 HeroNode h5 = new HeroNode(2, "林冲", "豹子头");
 s.addByOrder(h2);
 s.addByOrder(h3);
 s.addByOrder(h4);
 s.addByOrder(h5);
 System.out.println("修改前————");
 s.list();
// HeroNode h6 = new HeroNode(4, "有用", "超星星");
// s.update(h6);
 s.del(1);
 s.del(4);
 s.del(2);
 s.del(3);
 System.out.println("删除后————");
 s.list();
 }
 
}
class SingleLinkedListDemo{
 //创建一个头结点,初始化数据,头结点不要动,不放具体的数据
 private HeroNode head = new HeroNode(0,"","");
 //添加英雄
 public void add(HeroNode node) {
 //先找出最后的一个节点,把新加的节点放在最后一个节点的后面
 HeroNode temp = head;
 while(true) {
  if(temp.next == null) {
  break;
  }
  temp = temp.next;
 }
 temp.next = node;
 }
 public void addByOrder(HeroNode node) {
 HeroNode temp = head;
 boolean flag = false;
 while(true) {
  if(temp.next == null) {
  break;
  }
  if(temp.next.no>node.no) {
  break;
  }else if(temp.next.no == node.no) {
  flag = true;
  break;
  }
  temp = temp.next;
 }
 if(flag) {
  System.out.println("编号"+node.no+"已经存在了!");
 }else {
  node.next = temp.next;
  temp.next = node;
 }
 }
 public void update(HeroNode node ) {
 if(head.next == null) {
  System.out.println("链表为空!");
  return;
 }
 HeroNode temp = head.next;
 boolean flag = false;
 while(true) {
  if(temp == null) {
  break;
  }
  if(temp.no == node.no) {
  flag = true;
  break;
  }
  temp = temp.next;
 }
 if(flag) {
  temp.name = node.name;
  temp.nickname = node.name;
 }else {
  System.out.println("不存在该节点!");
 }
 }
 //删除节点
 public void del(int no) {
 if(head.next == null) {
  System.out.println("链表为空!");
  return;
 }
 HeroNode temp = head;
 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("该节点不存在!");
 }
 }
 public void list() {
 HeroNode temp = head;
 if(temp.next == null) {
  System.out.println("链表为空!");
  return;
 }
 while(true) {
  if(temp.next == null) {
  break;
  }
  System.out.println(temp.next);
  temp = temp.next; 
 }
 }
}
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 + "]";
 }
 
 
 
}

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持创新互联。


文章题目:Java实现带头结点的单链表
分享路径:http://scyanting.com/article/pscpse.html