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

数据结构之双向链表(Java代码)

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

数据结构之双向链表(Java代码)

目录
  • 为什么会有双向链表
    • 单向链表的缺点
    • 双向链表示意图
  • Java代码实现

为什么会有双向链表

首先要明白单链表,对单链表还比较朦胧的可以去下面的链接扫一眼。
数据结构之单链表超详细

单向链表的缺点
  • 查找的方向只能是一个方向,就是说只能根据头结点开始逐个遍历找到下一个节点,而不能根据下一个节点找到上一个结点。双向链表则可以向前或向后进行查找。
  • 单向链表不能自我删除,需要使用辅助结点,就是要找到要删除节点的前一个节点来进行删除操作。双向链表,则可以进行自我删除。
双向链表示意图


说明:
分析双向链表的遍历,添加,修改,删除的操作思路===》代码实现l)

  • 遍历方和单链表一样,只是可以向前,也可以向后查找

  • 添加(默认添加到双向链表的最后)
    (1)先找到双向链表的最后这个节点
    (2) temp.next = newHeroNode
    (3) newHeroNode.pre = temp;

  • 修改思路和原来的单向链表一样

  • 删除
    (1)因为是双向链表,因此,我们可以实现自我删除某个节点
    (2)直接找到要删除的这个节点,比如 temp
    (3)temp.pre.next =temp.next
    (4) temp.next.pre = temp.pre;

Java代码实现
package LinkList.Double;

import com.sun.xml.internal.bind.v2.model.core.ID;

import javax.xml.stream.FactoryConfigurationError;
import java.beans.beancontext.BeanContext;


public class DoubleLinkListTest {
    public static void main(String[] args) {

       HeroNode heroNode1 = new HeroNode(1,"宋江","及时雨");
        HeroNode heroNode2 = new HeroNode(2,"杨志","青面兽");
       HeroNode heroNode3 = new HeroNode(4,"卢俊义","玉麒麟");
        HeroNode heroNode4 = new HeroNode(5,"吴用","智多星");
       HeroNode heroNode5 = new HeroNode(7,"鲁智深","花和尚");
       HeroNode heroNode6 = new HeroNode(8,"周通","小霸王");

        DoubleLinkList doubleLinkList = new DoubleLinkList();
        doubleLinkList.addLast(heroNode1);
        doubleLinkList.addLast(heroNode2);
        doubleLinkList.addLast(heroNode3);
        doubleLinkList.addLast(heroNode4);
        doubleLinkList.addLast(heroNode5);
        doubleLinkList.addLast(heroNode6);

        //遍历
        System.out.println("初始化的链表");
        doubleLinkList.show();

        // 删除no = 5
        doubleLinkList.delete(8);
        System.out.println("删除后的链表");
        doubleLinkList.show();

        HeroNode heroNode7 = new HeroNode(5,"吴用","猪头");
        doubleLinkList.update(heroNode7);
        System.out.println("修改后的链表");
        doubleLinkList.show();

        //测试安装编号升序插入结点
        HeroNode heroNode8 = new HeroNode(3,"杨志1","青面兽1");
        doubleLinkList.insertByOrder(heroNode8);
        //按照编号升序插入
        System.out.println("按编号升序插入的链表");
        doubleLinkList.show();

    }
}


class DoubleLinkList{

    private HeroNode head = new HeroNode(0,"","");


    
    public HeroNode getHead() {
        return this.head;
    }


    
    public void addLast(HeroNode heroNode){
        HeroNode temp = head;
        // 遍历链表 找到最后一个节点
        while (true){
            if (temp.next == null){
                break;
            }
            // 指针后移
            temp = temp.next;
        }
        // 退出循环,也就意外着找到了最后
        temp.next = heroNode;
        heroNode.pre = temp;
    }



    
    public void insertByOrder(HeroNode heroNode){
        //因为头结点不动,需要借助一个辅助,来帮助找到合适添加位置
        //单链表,temp是位于添加位置的前一个结点,否则插入失败, 因为我们可以根据上一个结点找到下一个节点位置,但是不能根据下一个节点找到上一个结点位置。
        HeroNode temp = head.next;
        // 添加no是否存在,默认为false
        boolean flag = false;

        while (true){
            // 找到链表结尾
            if (temp == null){
                break;
            }
            // 找到插入位置,就在temp的后面
            if (temp.next.no > heroNode.no){
                break;
            }else if (temp.next.no == heroNode.no){ //要添加的no已经存在
                flag = true; //说明编号存在
                break;
            }
            temp = temp.next;
        }

        if (flag){
            throw new RuntimeException("待插入的编号:"+ heroNode.no + ",已经存在,插入失败。");
        }else {
            //将结点插入到temp后面
            heroNode.pre = temp.pre;
            temp.pre = heroNode;

            heroNode.next = temp.next;
            temp.next = heroNode;


        }
    }


    
    public void update(HeroNode heroNode){
        if (isEmpty()){
            throw new RuntimeException("链表没有元素");
        }
        HeroNode temp = head.next;
        // 是否找到该结点
        boolean flag = false;
        // 循环遍历
        while (true){
            // 遍历结束
            if (temp == null){
                break;
            }
            // 找到该结点
            if (temp.no == heroNode.no){
                flag = true;
                break;
            }
            // 指针后移
            temp = temp.next;
        }
        // 找到改结点,进行修改
        if (flag){
            temp.name = heroNode.name;
            temp.nickName = heroNode.nickName;
        }else {
            throw new RuntimeException("链表没有改元素no:" + heroNode);
        }
    }

    
    public void delete(int no){
        // 空链表
        if (isEmpty()){
            throw new RuntimeException("链表没有元素");
        }

        // 是否找到该结点
        boolean flag = false;

        HeroNode temp = head.next;

        while (true){
            //遍历到了链表末尾
            if(temp == null){
                break;
            }
            if (temp.no == no){
                flag = true;
                break;
            }
            temp = temp.next;
        }

        // 找到该元素
        if (flag){
            temp.pre.next = temp.next;
            // 若是删除最后一个节点,不能只能直接执行这句,因为最后一结点为NULL,否则会NPM
            if (temp.next != null){
                temp.next.pre = temp.pre;
            }

        }else {
            throw new RuntimeException("结点不存在");
        }
    }

    
    public void show(){
        if (isEmpty()){
            throw new RuntimeException("链表没有元素");
        }

        HeroNode temp = head.next;
        while (true){
            if (temp == null){
                break;
            }
            // 输出当前节点信息
            System.out.println(temp);
            // 指针后移
            temp = temp.next;
        }
    }

    
    public boolean isEmpty(){
        return head.next == null;
    }

}




class HeroNode{

    // 编号
    public int no;

    // 姓名
    public String name;

    // 昵称
    public String nickName;

    // 指向下一个节点
    public HeroNode next;

    // 指向前一个结点
    public HeroNode pre;

    // 构造器
    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 + ''' +
                '}';
    }
}


输出结果

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

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

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