type
status
date
slug
summary
tags
category
icon
password

链表的介绍

概念

链表是有序的列表,但是它在
内存中是存储
如下
notion image
小结:
  1. 链表是以节点的方式来存储,是链式存储
  1. 每个节点包含 data 域, next 域:指向下一个节点.
  1. 如图:发现链表的各个节点不一定是连续存储.
  1. 链表分带头节点的链表和没有头节点的链表,根据实际的需求来确定

单链表的应用实例

案例

使用带head头的单向链表实现 –
水浒英雄排行榜
管理完成对英雄人物的
增删改查操作
, 注: 删除和修改,查找
notion image

解题思路

1、增加
notion image
2、顺序添加(按照no由小到大排序)
notion image
3、修改和删除节点(原理差不多)
notion image

代码实现

1、新建英雄类,定义编号,名字,绰号,下一个节点的基本属性
class HeroNode{    public int no;    public String name;    public String nickName;    public HeroNode next;    public HeroNode(){}    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  +                '}';   } }
2、新建LinkedList类,实现节点的增删改查方法
class SingleLinkedList{    private HeroNode hero=new HeroNode(0,"","");    public SingleLinkedList(){}    //增加节点    public void add(HeroNode heroNode){        HeroNode temp=hero;        while (true){            if (temp.next==null){                break;           }            temp=temp.next;       }        temp.next=heroNode;   }    //按照编号顺序排列    public void addOrderly(HeroNode heroNode){        HeroNode temp=hero;        boolean isExist=false;  //判断该编号是否存在        while (true){            if (temp.next==null){                break;           }else if (temp.next.no>heroNode.no){                break;           }else if (temp.next.no==heroNode.no){                isExist=true;                break;           }            temp=temp.next;       }        if (isExist){            System.out.println("该编号已存在~~~"+heroNode.no);       }else{            heroNode.next=temp.next;            temp.next=heroNode;       }   }    //遍历节点    public void list(){        HeroNode temp=hero;        if (temp.next==null){            System.out.println("未有节点信息~~~");            return;       }        while (true){            temp=temp.next;            System.out.println(temp);            if (temp.next==null){                break;           }       }   }    //更新节点信息    public void update(HeroNode newNode){        if (hero.next==null){            System.out.println("节点为空~~~");            return;       }        boolean isFind=false;        HeroNode temp=hero.next;        while (true){            if (temp.next==null){                break;           }else if (temp.next.no==newNode.no){                isFind=true;                break;           }            temp=temp.next;       }        if (isFind){            temp.next.name=newNode.name;            temp.next.nickName=newNode.nickName;       }else{            System.out.println("未找到该元素~~~");       }   }    //删除节点信息    public void delete(int no){        if (hero.next==null){            System.out.println("节点为空~~~");            return;       }        boolean isFind=false;        HeroNode temp=hero;        while (true){            if (temp.next==null){                break;           }else if (temp.next.no==no){                isFind=true;                break;           }            temp=temp.next;       }        if (isFind){           temp.next=temp.next.next;       }else{            System.out.println("未找到该元素~~~");       }   } }
3、代码整合,整合英雄类和linkedList类
package com.qf.linkedList; public class SingleLinkedListDemo {    public static void main(String[] args) {        HeroNode heroNode1=new HeroNode(1,"宋江","及时雨");        HeroNode heroNode2=new HeroNode(2,"卢俊义","玉麒麟");        HeroNode heroNode3=new HeroNode(3,"吴用","智多星");        HeroNode heroNode4=new HeroNode(4,"林冲","豹子头");        SingleLinkedList singleLinkedList=new SingleLinkedList();        //add 添加节点      /* singleLinkedList.add(heroNode3);        singleLinkedList.add(heroNode4);        singleLinkedList.add(heroNode1);        singleLinkedList.add(heroNode2);        singleLinkedList.list();*/        //按照编号顺序添加节点        singleLinkedList.addOrderly(heroNode3);        singleLinkedList.addOrderly(heroNode4);        singleLinkedList.addOrderly(heroNode1);        singleLinkedList.addOrderly(heroNode2);        singleLinkedList.list();        //更新节点信息        System.out.println("更新后的节点");        HeroNode newNode=new HeroNode(3,"吴用new","智多星new");        singleLinkedList.update(newNode);        singleLinkedList.list();        //删除节点信息        System.out.println("删除后的节点");        singleLinkedList.delete(3);        singleLinkedList.delete(1);        singleLinkedList.delete(2);        singleLinkedList.list();   } } class HeroNode{    public int no;    public String name;    public String nickName;    public HeroNode next;    public HeroNode(){}    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  +                '}';   } } class SingleLinkedList{    private HeroNode hero=new HeroNode(0,"","");    public SingleLinkedList(){}    //增加节点    public void add(HeroNode heroNode){        HeroNode temp=hero;        while (true){            if (temp.next==null){                break;           }            temp=temp.next;       }        temp.next=heroNode;   }    //按照编号顺序排列    public void addOrderly(HeroNode heroNode){        HeroNode temp=hero;        boolean isExist=false;  //判断该编号是否存在        while (true){            if (temp.next==null){                break;           }else if (temp.next.no>heroNode.no){                break;           }else if (temp.next.no==heroNode.no){                isExist=true;                break;           }            temp=temp.next;       }        if (isExist){            System.out.println("该编号已存在~~~"+heroNode.no);       }else{            heroNode.next=temp.next;            temp.next=heroNode;       }   }    //遍历节点    public void list(){        HeroNode temp=hero;        if (temp.next==null){            System.out.println("未有节点信息~~~");            return;       }        while (true){            temp=temp.next;            System.out.println(temp);            if (temp.next==null){                break;           }       }   }    //更新节点信息    public void update(HeroNode newNode){        if (hero.next==null){            System.out.println("节点为空~~~");            return;       }        boolean isFind=false;        HeroNode temp=hero.next;        while (true){            if (temp.next==null){                break;           }else if (temp.next.no==newNode.no){                isFind=true;                break;           }            temp=temp.next;       }        if (isFind){            temp.next.name=newNode.name;            temp.next.nickName=newNode.nickName;       }else{            System.out.println("未找到该元素~~~");       }   }    //删除节点信息    public void delete(int no){        if (hero.next==null){            System.out.println("节点为空~~~");            return;       }        boolean isFind=false;        HeroNode temp=hero;        while (true){            if (temp.next==null){                break;           }else if (temp.next.no==no){                isFind=true;                break;           }            temp=temp.next;       }        if (isFind){           temp.next=temp.next.next;       }else{            System.out.println("未找到该元素~~~");       }   } }

结果

1、add 添加节点

notion image

2、addOrderly(有序)添加节点

notion image

3、update 更新节点

notion image

4、delete 删除节点

notion image

如有不正确的,还请指出!!!

 
单向链表栈的java实现 详细讲解插值查找算法