栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

数据结构 - 链表

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

数据结构 - 链表

基本介绍

链表是以节点的方式来存储,属于链式存储,各节点不一定是连续存储的。
每个节点包含 存放数值的data域 和 指向下一个节点的next域 。

链表的创建和遍历 思路
  1. 先创建一个头节点,表示链表的头部且后续不能更改。
  2. 后面每添加一个节点,就直接放在链表的最后。
  3. 在遍历时要创建一个新的辅助变量。
代码实现
package com.zls.demo03;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //添加节点
        singleLinkedList.add(hero1);
        singleLinkedList.add(hero2);
        singleLinkedList.add(hero3);
        singleLinkedList.add(hero4);
        //展示
        singleLinkedList.list();

    }
}

//定义单链表 用于管理英雄
class SingleLinkedList{
    //初始化头节点,不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    //添加节点到单项链表
    public void add(HeroNode heroNode){
        //辅助遍历
        HeroNode temp = head;
        //遍历找到最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }
        //退出循环后temp指向了链表的最后
        //将最后这个节点的next指向新节点
        temp.next = heroNode;
    }

    //遍历展示链表
    public void list(){
        if (head.next == null){
            System.out.println("链表为空");
            return ;
        }
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

//定义节点 每个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 + ''' +
                '}';
    }
}

按顺序加入节点 思路
  1. 先找到要添加的节点的位置
  2. 新节点.next = temp.next
  3. temp.next = 新节点
代码实现
package com.zls.demo03;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //添加节点
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);
        singleLinkedList.addByOrder(hero2);
        
        //展示
        singleLinkedList.list();

    }
}

//定义单链表 用于管理英雄
class SingleLinkedList{
    //初始化头节点,不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    //添加节点到单项链表
    public void add(HeroNode heroNode){
        //辅助遍历
        HeroNode temp = head;
        //遍历找到最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }
        //退出循环后temp指向了链表的最后
        //将最后这个节点的next指向新节点
        temp.next = heroNode;
    }

    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;
        while (temp.next != null && temp.next.no <= heroNode.no){
            if (temp.next.no == heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("准备插入的英雄编号已经存在了,不能再次添加");
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //遍历展示链表
    public void list(){
        if (head.next == null){
            System.out.println("链表为空");
            return ;
        }
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

//定义节点 每个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 + ''' +
                '}';
    }
}

修改节点信息 思路
  1. 通过变量找到要修改的节点
  2. temp.name = newHeroNode.name
代码实现
package com.zls.demo03;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //添加节点
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);

        //展示
        singleLinkedList.list();


        //修改节点
        HeroNode newHeroNode = new HeroNode(2,"小卢","玉麒麟~~");
        singleLinkedList.update(newHeroNode);

        //展示
        System.out.println("修改链表后:");
        singleLinkedList.list();
    }
}

//定义单链表 用于管理英雄
class SingleLinkedList{
    //初始化头节点,不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    //添加节点到单项链表
    public void add(HeroNode heroNode){
        //辅助遍历
        HeroNode temp = head;
        //遍历找到最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }
        //退出循环后temp指向了链表的最后
        //将最后这个节点的next指向新节点
        temp.next = heroNode;
    }

    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;
        while (temp.next != null && temp.next.no <= heroNode.no){
            if (temp.next.no == heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("准备插入的英雄编号已经存在了,不能再次添加");
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改节点的信息,根据no编号修改
    public void update(HeroNode newHeroNode){
        if (head.next == null){
            System.out.println("链表为空");
            return ;
        }
        HeroNode temp = head.next;
        boolean flag = false;
        while (temp != null){
            if(temp.no == newHeroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else{
            System.out.println("该节点不存在");
        }
    }


    //遍历展示链表
    public void list(){
        if (head.next == null){
            System.out.println("链表为空");
            return ;
        }
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

//定义节点 每个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 + ''' +
                '}';
    }
}

删除节点 思路
  1. 先找到需要删除的节点的前一个节点temp
  2. temp.next = temp.next.next
  3. 被删除的节点不会有其他引用指向,会被垃圾回收机制回收。
代码实现
package com.zls.demo03;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        //先创建节点
        HeroNode hero1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode hero2 = new HeroNode(2,"卢俊义","玉麒麟");
        HeroNode hero3 = new HeroNode(3,"吴用","智多星");
        HeroNode hero4 = new HeroNode(4,"林冲","豹子头");

        SingleLinkedList singleLinkedList = new SingleLinkedList();
        //添加节点
        singleLinkedList.addByOrder(hero1);
        singleLinkedList.addByOrder(hero4);
        singleLinkedList.addByOrder(hero3);
        singleLinkedList.addByOrder(hero2);

        //展示
        singleLinkedList.list();

        //删除节点
        singleLinkedList.del(1);
        singleLinkedList.del(3);

        System.out.println("删除后的节点展示");
        singleLinkedList.list();
    }
}

//定义单链表 用于管理英雄
class SingleLinkedList{
    //初始化头节点,不存放具体的数据
    private HeroNode head = new HeroNode(0,"","");

    //添加节点到单项链表
    public void add(HeroNode heroNode){
        //辅助遍历
        HeroNode temp = head;
        //遍历找到最后一个节点
        while (temp.next != null) {
            temp = temp.next;
        }
        //退出循环后temp指向了链表的最后
        //将最后这个节点的next指向新节点
        temp.next = heroNode;
    }

    public void addByOrder(HeroNode heroNode){
        HeroNode temp = head;
        boolean flag = false;
        while (temp.next != null && temp.next.no <= heroNode.no){
            if (temp.next.no == heroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("准备插入的英雄编号已经存在了,不能再次添加");
        }else {
            heroNode.next = temp.next;
            temp.next = heroNode;
        }
    }

    //修改节点的信息,根据no编号修改
    public void update(HeroNode newHeroNode){
        if (head.next == null){
            System.out.println("链表为空");
            return ;
        }
        HeroNode temp = head.next;
        boolean flag = false;
        while (temp != null){
            if(temp.no == newHeroNode.no){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            temp.name = newHeroNode.name;
            temp.nickName = newHeroNode.nickName;
        }else{
            System.out.println("该节点不存在");
        }
    }

    public void del(int no){
        HeroNode temp = head;
        boolean flag = false;
        while(temp.next != null){
            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(){
        if (head.next == null){
            System.out.println("链表为空");
            return ;
        }
        HeroNode temp = head.next;
        while (temp != null) {
            System.out.println(temp);
            temp = temp.next;
        }
    }

}

//定义节点 每个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 + ''' +
                '}';
    }
}

Java实例 使用场景

需要通过循环迭代来访问列表中的某些元素。
需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。

  • LinkedList 继承了 AbstractSequentialList 类。
  • LinkedList 实现了 Queue 接口,可作为队列使用。
  • LinkedList 实现了 List 接口,可进行列表的相关操作。
  • LinkedList 实现了 Deque 接口,可作为队列使用。
  • LinkedList 实现了 Cloneable 接口,可实现克隆。
  • LinkedList 实现了 java.io.Serializable 接口,即可支持序列化,能通过序列化去传输。
使用
import java.util.LinkedList;

public class SingleLinkedListDemo {
    public static void main(String[] args) {
        LinkedList sites = new LinkedList();
        sites.add("Google");
        sites.add("Runoob");
        // 使用 add() 添加元素
        sites.add("Taobao");
        System.out.println(sites);

        // 使用 addFirst() 在头部添加元素
        sites.addFirst("Wiki");
        System.out.println(sites);

        // 使用 addLast() 在尾部添加元素
        sites.addLast("CSDN");
        System.out.println(sites);

        // 使用 removeFirst() 移除头部元素
        sites.removeFirst();
        System.out.println(sites);

        // 使用 removeLast() 移除尾部元素
        sites.removeLast();
        System.out.println(sites);

        // 使用 getFirst() 获取头部元素
        System.out.println(sites.getFirst());
        
        // 使用 getLast() 获取尾部元素
        System.out.println(sites.getLast());
    }
}

转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/948939.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号