您现在的位置是：首页 > 后台技术 > 数据结构与算法数据结构与算法

单链表(图文)

第十三双眼睛2022-06-05【数据结构与算法】人已围观

简介链表

链表是有序得列表，但是在内存中是不连续的。
链表是以节点的方式来存储数据的。
每个节点包含data域,next域,data域用来存储数据，next域用来指向下一个节点
链表分为带头节点的和不带头节点的，根据需要来定

先创建一个英雄节点

package com.xingchen.day003;
public class HeroNode {
   public String no;
   public String name;
   public String nickName;
   public HeroNode next;
   public HeroNode() {
       super();
   }
   public HeroNode(String no, String name, String nickName) {
       super();
       this.no = no;
       this.name = name;
       this.nickName = nickName;
   }
   @Override
   public String toString() {
       return "HeroNode [no=" + no + ", name=" + name + ", nickName=" + nickName + "]";
   }
}

再创建一个链表

package com.xingchen.day003;
public class SingleLinkedList {
   private HeroNode headNode = new HeroNode("0","","");
   // 添加node
   public void add(HeroNode node){
       HeroNode temp = headNode;
       while(true){
           if(temp.next==null){
               break;
           }
           temp = temp.next;
       }
       temp.next = node;
   }
   // 遍历链表
   public void list(){
       if(headNode.next==null){
           System.out.println("链表为空");
           return;
       }
       HeroNode temp = headNode.next;
       while(true){
           if(temp==null){
               break;
           }
           System.out.println(temp);
           temp=temp.next;
       }
   }
}

测试

package com.xingchen.day003;
public class SingleLinkedListDemo {
   public static void main(String[] args) {
       HeroNode node1 = new HeroNode("1","宋江","及时雨");
       HeroNode node2 = new HeroNode("2","卢俊义","玉麒麟");
       HeroNode node3 = new HeroNode("3","吴用","智多星");
       HeroNode node4 = new HeroNode("4","林冲","豹子头");
       SingleLinkedList list = new SingleLinkedList();
       list.add(node1);
       list.add(node2);
       list.add(node3);
       list.add(node4);
       list.list();
   }
}

结果如下：

HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]

下面实现按顺序添加的单向链表
增加一个按顺序插入的方法

// 按照顺序添加
public void addWithOrder(HeroNode node){
   HeroNode temp = headNode;
   //标记要添加的节点是否已经存在
   boolean flag = false;
   while(true){
       if(temp.next==null){
           break;
       }
       if(temp.next.no>node.no){
           break;
       }
       if(temp.next.no==node.no){
           flag=true;
           break;
       }
       temp=temp.next;
   }
   if(flag){
       System.out.println("数据已经存在");
       return;
   }
   node.next = temp.next;
   temp.next=node;
}

测试结果

数据已经存在
HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]

单向链表的修改
增加一个修改方法

// 根据编号来修改
public void update(HeroNode node){
   if(headNode.next==null){
       System.out.println("链表为空");
       return;
   }
   HeroNode temp = headNode;
   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.nickName;
   }else{
       System.out.println("没有找到要修改的节点:"+node.no);
   }
}

测试一下

package com.xingchen.day003;
public class SingleLinkedListDemo {
   public static void main(String[] args) {
       HeroNode node1 = new HeroNode(1,"宋江","及时雨");
       HeroNode node2 = new HeroNode(2,"卢俊义","玉麒麟");
       HeroNode node3 = new HeroNode(3,"吴用","智多星");
       HeroNode node4 = new HeroNode(4,"林冲","豹子头");
       SingleLinkedList list = new SingleLinkedList();
       list.addWithOrder(node1);
       list.addWithOrder(node4);
       list.addWithOrder(node3);
       list.addWithOrder(node2);
       list.list();
       System.out.println("========");
       HeroNode node5 = new HeroNode(2,"小卢","玉麒麟xxx");
       list.update(node5);
       list.list();
   }
}

测试结果

HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]
修改后的结果
HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=小卢, nickName=玉麒麟xxx]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]

增加一个删除方法

// 删除一个节点
public void delete(int no){
   HeroNode temp=headNode;
   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("节点不存在:"+no);
   }
}

测试一下

package com.xingchen.day003;
public class SingleLinkedListDemo {
   public static void main(String[] args) {
       HeroNode node1 = new HeroNode(1,"宋江","及时雨");
       HeroNode node2 = new HeroNode(2,"卢俊义","玉麒麟");
       HeroNode node3 = new HeroNode(3,"吴用","智多星");
       HeroNode node4 = new HeroNode(4,"林冲","豹子头");
       SingleLinkedList list = new SingleLinkedList();
       list.addWithOrder(node1);
       list.addWithOrder(node4);
       list.addWithOrder(node3);
       list.addWithOrder(node2);
       list.list();
       list.delete(3);
       System.out.println("删除后的结果");
       list.list();
   }
}

测试结果如下：

HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=3, name=吴用, nickName=智多星]
HeroNode [no=4, name=林冲, nickName=豹子头]
删除后的结果
HeroNode [no=1, name=宋江, nickName=及时雨]
HeroNode [no=2, name=卢俊义, nickName=玉麒麟]
HeroNode [no=4, name=林冲, nickName=豹子头]

Tags：

很赞哦！ ()

上一篇：队列(图文)

下一篇：双向链表(图文)