什么是双向链表,一篇搞懂双向链表

这篇具有很好参考价值的文章主要介绍了什么是双向链表,一篇搞懂双向链表。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

双向链表

还不清楚单向链表的同学可以去看我另一篇文章,实践总结:一篇搞懂链表——单链表和双指针技巧

首先,我们先看下双向链表(下文用双链表表述)的图示,见下图:
什么是双向链表,一篇搞懂双向链表,数据结构与算法,链表,数据结构
与单链表不同的是,双链表有两个方向,对应单链表节点中的一个引用字段next,双链表每个节点中都含有两个引用字段,我们用prev和next表示。

也就是在双链表中的每个节点,包含一个数值val,还包括两个引用字段,一个是prev 指向前一个节点,next 指向后一个节点。

添加操作 - 双链表

如果我们想在现有的结点 prev 之后插入一个新的结点 cur,我们可以将此过程分为两个步骤:

  1. 链接 cur 与 prev 和 next,其中 next 是 prev 原始的下一个节点;
    什么是双向链表,一篇搞懂双向链表,数据结构与算法,链表,数据结构
  2. prev 和 next再次指向cur
    什么是双向链表,一篇搞懂双向链表,数据结构与算法,链表,数据结构
    这两步在代码上的实现,可以简化为:
new_node.next = curr.next
new_node.prev = curr
curr.next.prev = new_node
curr.next = new_node

删除操作 - 双链表

如果我们想从双链表中删除一个现有的结点 cur,我们可以简单地将它的前一个结点 prev 与下一个结点 next 链接起来。
举个例子:
什么是双向链表,一篇搞懂双向链表,数据结构与算法,链表,数据结构

设计一个双链表

要求:
实现一个向链表。

实现 MyLinkedList 类:

  1. MyLinkedList() 初始化 MyLinkedList 对象。
  2. int get(int index) 获取链表中下标为 index 的节点的值。如果下标无效,则返回 -1 。
  3. void addAtHead(int val) 将一个值为 val的节点插入到链表中第一个元素之前。在插入完成后,新节点会成为链表的第一个节点。
  4. void addAtTail(int val) 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
  5. void addAtIndex(int index, int val) 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。如果 index 等于链表的长度,那么该节点会被追加到链表的末尾。如果 index 比长度更大,该节点将 不会插入 到链表中。
  6. void deleteAtIndex(int index) 如果下标有效,则删除链表中下标为 index 的节点。

代码实现:文章来源地址https://www.toymoban.com/news/detail-839143.html

class ListNode:
    def __init__(self, val=0):
        self.val = val
        # 标记向后的变量
        self.next = None
        # 标记向前的变量
        self.prev = None


class MyLinkedList:
    def __init__(self):
        # 初始化头节点
        self.head = None
        # 初始化尾节点
        self.tail = None
        self.size = 0

    # 获取链表中下标为 index 的节点的值
    def get(self, index: int) -> int:
        # 在index有效的范围内,遍历得到curr即可
        if 0 <= index < self.size:
            curr = self.head
            for _ in range(index):
                curr = curr.next
            return curr.val
        else:
            return -1

    #将一个值为 val 的节点插入到链表中第一个元素之前
    def addAtHead(self, val: int) -> None:
        self.addAtIndex(0, val)

    # 将一个值为 val 的节点追加到链表中作为链表的最后一个元素。
    def addAtTail(self, val: int) -> None:
        self.addAtIndex(self.size, val)

    # 将一个值为 val 的节点插入到链表中下标为 index 的节点之前。
    def addAtIndex(self, index: int, val: int) -> None:
        if index < 0 or index > self.size:
            return None
        new_node = ListNode(val)
        # 插入头节点
        if index == 0:
            new_node.next = self.head
            if self.head:
                self.head.prev = new_node
            else:
                self.tail=new_node
            self.head = new_node
            self.size += 1
            return
        if index == self.size:
            new_node.prev = self.tail
            if self.tail:
                self.tail.next = new_node
            else:
                self.head=new_node
            self.tail = new_node
            self.size += 1
            return
        if 0 < index < self.size:
            curr = self.head
            # 从头节点遍历链表到index的前一位
            for _ in range(index - 1):
                curr = curr.next
            new_node.next = curr.next
            new_node.prev = curr
            curr.next.prev = new_node
            curr.next = new_node
            self.size += 1
            return
        return

    # 删除链表中下标为 index 的节点。
    def deleteAtIndex(self, index: int) -> None:
        # 如果删除的是头节点
        if index == 0:
            # 当链表长度等于1时
            if self.size == 1:
            	# 删除之后链表就为空了
                self.head = None
                self.tail = None
                self.size -= 1
            else:
                self.head = self.head.next
                self.head.prev = None
                self.size -= 1
             # 删除尾节点
        elif index == self.size - 1:
            self.tail = self.tail.prev
            self.tail.next = None
            self.size -= 1
        elif 0 < index < self.size - 1:
            curr = self.head
            # 遍历到当前节点
            for _ in range(index):
                curr = curr.next
            # 当前节点的前一个节点指向当前节点下一个节点
            curr.prev.next = curr.next
            # 当前节点后一个节点的前一个节点,是当前节点的前一个节点
            curr.next.prev = curr.prev
            self.size-=1
        return None

到了这里,关于什么是双向链表,一篇搞懂双向链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 一篇搞懂Java多线程运行机制

    Java是一种支持多线程编程的语言。多线程可以让程序同时执行多个任务,从而提高程序的效率和响应速度。在本篇博客中,我将介绍Java多线程的基础知识,包括线程的创建、启动、中断以及线程同步等方面。 什么是程序? 程序是为完成特定任务,用某种语言编程写的一组指

    2023年04月15日
    浏览(43)
  • 如何理解场外期权交易?个股期权一篇搞懂

    场外期权是一种金融衍生品,指在非集中性的交易场所进行的非标准化的金融期权合约。它是一种买卖双方达成的合约,赋予买方在未来的某一特定日期以特定价格购买或出售一种资产的权利,但不必承担必须履行的义务。下文科普如何理解场外期权交易?个股期权一篇搞懂

    2024年04月24日
    浏览(52)
  • 一篇搞懂数学在OpenGL中的应用及矩阵

    目录 一、图形学中的矩阵 1.矩阵的计算公式 2.矩阵变换 3.为什么旋转,平移都是左乘矩阵,不能右乘 4.齐次坐标系统 5.变换先后顺序 二、利用矩阵来变换图形 (补充) 三、OpenGL中的三种变换矩阵  话不多说,我把我看的视频链接贴出来,下面的笔记是由视频学习和自己的补

    2024年02月03日
    浏览(36)
  • 基于IIC通信的显示器OLED编程详解(一篇搞懂)

    上一篇博客介绍了IIC通信,这篇我们就来玩玩oled模块。当然选用的是IIC接口,因为市面上还有一种是SPI接口的。对于oled长啥样,采用了什么材料,工艺怎么怎么样等等这里就不作任何介绍,搞得眼花缭乱的,对我们用它做开发也没任何帮助,同时节省读者阅读时间。为什么

    2024年02月09日
    浏览(52)
  • 数据结构-链表结构-双向链表

    双向链表也叫双链表,与单向链表不同的是,每一个节点有三个区域组成:两个指针域,一个数据域 前一个指针域:存储前驱节点的内存地址 后一个指针域:存储后继节点的内存地址 数据域:存储节点数据 以下就是双向链表的最基本单位 节点的前指针域指向前驱,后指针

    2024年02月04日
    浏览(46)
  • 【数据结构】双向奔赴的爱恋 --- 双向链表

    关注小庄 顿顿解馋๑ᵒᯅᵒ๑ 引言:上回我们讲解了单链表(单向不循环不带头链表),我们可以发现他是存在一定缺陷的,比如尾删的时候需要遍历一遍链表,这会大大降低我们的性能,再比如对于链表中的一个结点我们是无法直接访问它的上一个结点,那有什么解决方法呢

    2024年04月08日
    浏览(94)
  • 数据结构—双向链表

    目录 1.  链表的种类 2.  最实用的两种链表类型 3.  实现双向带头循环链表                   3.1 创建头节点         3.2 实现双向循环功能—返回头指针         3.3  尾插           3.4 头插         3.5 尾删         3.6 头删 4.  实现两个重要接口函数  

    2023年04月23日
    浏览(68)
  • 数据结构——双向链表

    🍇系列专栏:🌙数据结构 🍉  欢迎关注:👍点赞🍃收藏🔥留言 🍎 博客主页:🌙_麦麦_的博客_CSDN博客-领域博主 🌙如果我们都不能够拥有黑夜,又该怎样去仰望星空?   目录 一、前言 二、正文——双向链表的实现 2.1模块化 2.2 数据类型与结构体定义  2.3链表的初始化

    2024年02月02日
    浏览(47)
  • 数据结构双向链表

    Hello,好久不见,今天我们讲链表的双向链表,这是一个很厉害的链表,带头双向且循环,学了这个链表,你会发现顺序表的头插头删不再是一个麻烦问题,单链表的尾插尾删也变得简单起来了,那废话不多说,让我们开始我们的学习吧! 首先我们要了解它的物理和逻辑结构

    2024年02月11日
    浏览(44)
  • 数据结构---双向链表

    单向链表:一块内存指向下一个内存。 单链表存在一些缺陷: 1.查找速度慢。 2.不能从后往前找。 3.找不到前驱。 链表的结构分为8种: 1.单向和双向 2.带头和不带头 带头的链表有一个带哨兵位的头结点,这个节点不存储有效数据。 好处 :尾插更方便,不需要二级指针了,

    2024年02月02日
    浏览(45)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包