dabocaiqq
dabocaiqq
采纳率66.6%
2020-03-16 00:15

Java语言如何实现双向链表的查找、插入、删除、排序呢

已采纳

Java语言如何实现双向链表的查找、插入、删除、排序呢
Java语言如何实现双向链表的查找、插入、删除、排序呢

  • 点赞
  • 写回答
  • 关注问题
  • 收藏
  • 复制链接分享
  • 邀请回答

2条回答

  • huazhan321 阿狸梦之堡风之寄语,愿您千帆历尽心依旧 11月前

    首先,要了解链接的本质就是一个包含量前向和后向节点的数据结构,然后第一个表头地址就是整个链表对象了;
    其次,链表的插入、删除需要找到对一个的节点,然后修正其前向、后向节点的指针:
    图片说明

    完整的实现参考这篇:https://www.cnblogs.com/excellencesy/p/8647849.html

    点赞 2 评论 复制链接分享
  • weixin_44058976 AKA二夕 1年前

    package com.linkedlist;

    public class DoubleLinkedListDemo {

        public static void main(String[] args) {
    
            System.out.println("双向链表的测试");
        // 先创建节点
        HeroNode2 hero1 = new HeroNode2(1, "宋江", "及时雨");
        HeroNode2 hero2 = new HeroNode2(2, "卢俊义", "玉麒麟");
        HeroNode2 hero3 = new HeroNode2(3, "吴用", "智多星");
        HeroNode2 hero4 = new HeroNode2(4, "林冲", "豹子头");
        // 创建一个双向链表
        DoubleLinkedList doubleLinkedList = new DoubleLinkedList();
        doubleLinkedList.add(hero1);
        doubleLinkedList.add(hero2);
        doubleLinkedList.add(hero3);
        doubleLinkedList.add(hero4);
    
        doubleLinkedList.showInfo();
    
        //修改
        HeroNode2 newHeroNode2 = new HeroNode2(4,"公孙胜","入云龙");
        doubleLinkedList.update(newHeroNode2);
        //删除
        doubleLinkedList.delete(2);
        System.out.println("修改之后的链表情况如下:");
        doubleLinkedList.showInfo();
    }
    

    }

    //创建一个双向链表
    class DoubleLinkedList{
    //先初始化一个头节点,头节点不要动,不存放具体的数据
    private HeroNode2 head = new HeroNode2(0,"","");

    //返回头节点
    public HeroNode2 getHead() {
        return head;
    }
    
    //添加一个节点到双向链表的最后
    public void add(HeroNode2 heroNode2){
        //因为head节点不能动,因此我们需要一个辅助变量temp
        HeroNode2 temp = head;
        //遍历链表,找到最后
        while (true) {
            //找到链表的最后
            if (temp.next == null) {
                break;
            }
            //如果没有找到将temp后移
            temp = temp.next;
        }
        //当退出while循环时,temp就指向了链表的最后
        //形成一个双向链表
        temp.next = heroNode2;
        heroNode2.pre = temp;
    }
    
    //修改一个节点的内容,可以看待双向链表的节点内容修改和单向链表一样
    //只是 节点类型改成HeroNode2
    public void update(HeroNode2 newHeroNode2){
        //判断是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //找到需要修改的节点,根据num编号
        //定义一个辅助变量
        HeroNode2 temp = head.next;
        boolean flag = true;
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.num == newHeroNode2.num){//找到
                flag = true;
                break;
            }
            temp = temp.next;
        }
        //根据flag判断是否找到需要修改的节点
        if (flag) {
            temp.name = newHeroNode2.name;
            temp.nickname = newHeroNode2.nickname;
        }else{//没有找到
            System.out.printf("没有找到 编号%d的节点,不能修改",newHeroNode2.num);
        }
    }
    
    //从双向链表中删除一个节点
    
    /**
     * 说明:
     * 1、对于双向链表,可以直接找到需要删除的这个节点
     * 2、找到后,自我删除即可
     */
    public void delete(int num){
        //判断当前链表是否为空
        if (head.next == null) {
            System.out.println("链表为空,无法删除");
            return;
        }
        HeroNode2 temp = head.next;//辅助变量(指针)
        boolean flag = false;//标志是否找到需要删除的节点
        while (true) {
            if (temp == null) {
                break;
            }
            if (temp.num == num) {
                //找到待删除节点的前一个节点temp
                flag = true;
                break;
            }
            temp = temp.next;//temp后移,遍历
        }
        //判断flag
        if (flag) {//找到
            //可以删除
            temp.pre.next = temp.next;
            //注:如果是最后一个节点,就不需要执行下面这句话,否则会出现空指针
            if (temp.next != null) {
                temp.next.pre = temp.pre;
            }else{
                System.out.printf("需要删除的%d节点不存在\n",num);
            }
        }
    }
    
    //遍历双向链表的方法
    //显示链表[遍历]
    public void showInfo(){
        //判断链表是否为空
        if (head.next == null) {
            System.out.println("链表为空");
            return;
        }
        //因为头节点不能动,因此我们需要一个辅助变量来遍历
        HeroNode2 temp = head.next;
        while (true) {
            //判断是否到链表最后
            if (temp == null) {
                break;
            }
            //输出节点信息
            System.out.println(temp);
            temp = temp.next;//将temp后移!!!
        }
    }
    

    }

    //定义HeroNode2,每个HeroNode2对象就是一个节点
    class HeroNode2{
    public int num;
    public String name;
    public String nickname;
    public HeroNode2 next;//指向下一个节点,默认为null
    public HeroNode2 pre;//指向前一个节点,默认为null

    public HeroNode2(int num, String name, String nickname){
        this.num = num;
        this.name = name;
        this.nickname = nickname;
    }
    
    //为了显示方法,重写toString方法
    @Override
    public String toString() {
        return "HeroNode2{" +
                "num=" + num +
                ", name='" + name + '\'' +
                ", nickname='" + nickname + '\'' +
                '}';
    }
    

    }

    点赞 评论 复制链接分享