数据结构与算法(三):双向链表[通俗易懂]

数据结构与算法(三):双向链表[通俗易懂]一、双向链表双向链表与单链表基本相似,但是最大的区别在于双向链表在节点中除了指向下一节点的next指针外,还有指向前一节点的prev指针,这使得双向链表在可以在任意节点从头尾两个方向进行遍历,是“双

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

一、双向链表

双向链表与单链表基本相似,但是最大的区别在于双向链表在节点中除了指向下一节点的next指针外,还有指向前一节点的prev指针,这使得双向链表在可以在任意节点从头尾两个方向进行遍历,是“双向”的。

和单链表相比,双向链表在删除和查询等方面明显在操作上更具有灵活性,但是会消耗更多的内存,需要根据使用条件进行取舍。

java中的LinkedHashMap的本质即是一个双向链表。

数据结构与算法(三):双向链表[通俗易懂]

二、双向链表的简单实现

修改原来的Node类,在里面添加一个新成员变量Node prev

/**
 * @Author:huang
 * @Date:2020-06-20 10:19
 * @Description:节点类
 */
public class Node {

    //节点序号
    int num;

    //数据
    Object data;

    //下一个节点
    Node next;

    //上一节点
    Node prev;

    public Node(int num, Object data) {
        this.num = num;
        this.data = data;
    }

    @Override
    public String toString() {
        return "Node{" +
            "num=" + num +
            ", data=" + data +
            '}';
    }
}

1.添加

添加与单向链表代码逻辑一样,但是新节点在添加时需要修改prev指针指向原来的尾节点。

举个例子,对于无排序插入,原本有节点A,现在要插入一个B:

  1. 找到A,然后让A.next指向B
  2. B.prev指向A

而对于排序插入,就是原有节点A,C,要在中间插入B:

  1. 找到A,让B.prev指向A
  2. B.next指向A.next,也就是让B的next指向C
  3. A.next.prev指向B,也就是让C的prev指向B
  4. A.next指向B
/**
 * 添加节点到链表
 * @param node 要插入的节点
 */
public void add(Node node) {
    Node temp = head;
    //遍历链表
    while (true) {
        if (temp.next == null) {
            break;
        }
        //不是尾节点就继续遍历下一个节点
        temp = temp.next;
    }
    //将尾节点指向即将插入的新节点
    temp.next = node;
    node.prev = temp;
}

/**
 * 按顺序添加节点到链表
 * @param node 要插入的节点
 */
public void addByOrder(Node node) {
    Node temp = head;
    //遍历链表
    while (true) {
        //如果链表到底了就直接插入
        if (temp.next == null) {
            temp.next = node;
            node.prev = temp;
            return;
        }
        else if (temp.next.num > node.num){
            //如果后一节点比当新节点大,就插入当前节点
            node.prev = temp;
            node.next = temp.next;

            temp.next.prev = node;
            temp.next = node;
            return;
        }else if (temp.next.num == node.num){
            //如果后一节点等于新节点,抛异常
            throw new RuntimeException("插入节点与已有节点序号重复!");
        }
        //如果后一节点比当前节点小,就继续遍历
        temp = temp.next;
    }
}

2.删除

由于相对单链表,双向链表的节点可以自己找到上一节点,所以删除的时候可以直接找到要删除的节点进行操作。

举个例子,假设有节点A,B,C,现在要删除B:

  1. 找到B,让B.prev.next=B.next,也就是让A的next指向C
  2. B.next.prev=B.prev,也就是让C的prev指向A

如果要删除的节点已经是尾节点了,那就跟单链表一样了。

/**
 * 删除节点
 * @param num 要删除的节点编号
 */
public void delete(int num) {
    Node temp = head;
    //判断链表是否为空
    if (temp.next == null) {
        throw new RuntimeException("链表为空!");
    }
    //遍历链表
    while (true) {
        //如果链表到底了
        if (temp.next == null) {
            throw new RuntimeException("编号为" + num + "的节点不存在!");
        }
        //如果找到了待删除节点的前一个节点
        if (temp.num == num) {
            //判断待删除节点是否为尾节点
            if (temp.next == null){
                temp.prev.next = null;
            }else {
                temp.prev.next = temp.next;
                temp.next.prev = temp.prev;
            }
            return;
        }
        //继续遍历下一节点
        temp = temp.next;
    }
}

3.修改,查询(与单链表一致)

由于修改和查询与单链表基本一致,这里就不在赘述了,直接放代码:

/**
 * 展示链表
 */
public void show() {
    //判断链表是否为空
    if (head.next == null) {
        throw new RuntimeException("链表为空!");
    }
    Node temp = head.next;
    //遍历链表
    while (true) {
        if (temp == null) {
            break;
        }
        System.out.println(temp.toString());
        temp = temp.next;
    }
}

/**
 * 根据序号获取节点
 * @param num 要获取的节点序号
 * @return
 */
public Node get(int num){
    //判断链表是否为空
    if (head.next == null) {
        throw new RuntimeException("链表为空!");
    }
    Node temp = head.next;
    //遍历链表
    while (true) {
        if (temp == null) {
            throw new RuntimeException("编号为" + num + "的节点不存在!");
        }
        if (temp.num == num) {
            return temp;
        }
        temp = temp.next;
    }
}

/**
 * 修改节点
 * @param node 要更新的节点
 */
public void update(Node node) {
    Node temp = head;
    //判断链表是否为空
    if (temp.next == null) {
        throw new RuntimeException("链表为空!");
    }
    //获取要更新的节点序号
    int nodeNum = node.num;
    //遍历链表
    while (true) {
        //如果已经遍历完链表
        if (temp == null) {
            throw new RuntimeException("编号为" + temp.num + "的节点不存在!");
        }
        //如果找到了该节点
        if (temp.num == nodeNum) {
            temp.data = node.data;
            return;
        }
        //继续遍历下一节点
        temp = temp.next;
    }
}
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/170817.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • imx6 添加matrix keypad

    imx6 添加matrix keypadfreescale增加matrixkeypad1.添加设备树,imx6有矩阵键盘功能,支持8*8的键盘kernel_imx/arch/arm/boot/dts/imx6qdl.dtsi/*addedbyyue.zhong*/#include//键值定义的地方,这是一个链接文件,指向kernel_imx/include/dt-bindings/input/i

  • VMware虚拟机安装ubuntu16.04系统教程[通俗易懂]

    对于没有接触过Ubuntu系统的小伙伴来说,直接在物理机上安装Ubuntu单系统或者windows、Ubuntu双系统一件比较刺激的事情,因为一不小心可能就会把电脑整崩溃,或者出现各种问题,所以在一开始可以用虚拟机熟悉演练一下Ubuntu系统很有必要,今天把这个过程分享一下,希望朋友们能够一次性地顺利安装好,愉快地进行体验玩耍,话不多说,教程奉上。由于本台电脑是2010的机器了…

  • java字符串分割方法

    java字符串分割方法java分割字符串split()方法实现功能编写一个将字符串分段的类,传入:需分段的字符串与字符个数(以此个数进行分段),输出:按指定字符个数进行分段后的若干字符串(汉字算单个字符)。功能实现要求分析字符串传入字符串分段字符串输出实现思路Java是一个面向对象设计类语言,自身提供了很多方法帮助我们实现想要的功能。那么如何实现字符串传入功能?我们需要了解一个Java类—-Scanner类,这是一个用于扫描输入文本的新的实用程序。自Java5版本添加了java.util.Sc

  • 关于 RenderControl 的问题

    关于 RenderControl 的问题主要解决RenderControl时提示控件必须放在具有runat=server的窗体标记内”错误的解决方法1,http://www.cnblogs.com/zhangronghua/archive/2008/11/07/951899.html2,http://hi.baidu.com/tyrant8203/blog/item/615d77082777c0960a7b82b6.html…

  • leapftp乱码_如何用网格本做笔记

    leapftp乱码_如何用网格本做笔记生活对我下了手2019年7月23星期二大晴天1.主要掌握怎么连接服务器2.单个文件上传3.整个文件夹上传leapftp界面主要功能板块介绍1.管理ftp服务器配置的地方2.服务器网站文件窗口界面3.上传状态的窗口界面4.正在上传的文件窗口界面5.本地电脑文件窗口界面怎么连接ftp服务器服务器上要有ftp服务,1.你要有ftp服务器的账号,2.你要有ftp服务器的密…

    2022年10月28日
  • eclipse汉化教程(官方汉化包,傻瓜式操作,附带中英文快捷切换方式)

    eclipse汉化教程(官方汉化包,傻瓜式操作,附带中英文快捷切换方式)eclipse汉化教程(官方汉化包,傻瓜式操作)首先到eclipseIDE中,点击‘Help’>‘Installnewsoftware…’在弹出的Install窗口中点击Add按钮Name任意填Location填https://download.eclipse.org/technology/babel/update-site/R0.18.3/2021-03/这里解释一下这个Location的出处,是在Eclipse官方的babel语言包project网页上找的,可能不是最

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号