Python | 四、链表

发布时间：2024年01月14日

为什么需要链表

  • 在Python中，引入链表这一结构没有像C++等语言那样有很多好处，因为Python里的列表和字符串结构已经十分灵活且大小可变，仍保留的好处如下：
    • 列表、字符串等结构是连续存储的，因此如果有一块较小的内存区域，这些数据结构将无法充分利用该内存空间，只能另寻大块的连续空间进行存储，这就导致了内存浪费

链表基本定义

  • 链表中的每一个节点（元素）都由两部分构成，data（数据域）和next（指针域），其中data存储当前节点的数据内容，next存储下一节点的地址信息
  • 链表中的第一个节点称为头结点headnode，最后一个节点的next为空（None）
    • 链表结构示意图
  • 链表的【存储方式】：链表在内存中不是连续存储的，通过节点的指针域链接，而每个节点具体分配到什么地址视具体的存储方式视操作系统的内存管理而定。如下图链表起始节点为2，终止节点为7，各个节点分布在内存的不同地址空间上，通过指针串联在一起
    • 链表的存储方式

其它链表类型

  • 前面所提到的链表为基础的单链表，下面介绍几种其它链表类型
  • 【双链表】，顾名思义，双链表就是双向链表，即每个节点既存储了上一个节点的地址，又存储了下一个节点的地址
    • 双链表头节点所存储的上一节点地址为空（None）
    • 双链表示意图
  • 【循环链表】，即首尾相连的链表，此时链表里最后一个节点存储的地址为首节点的地址
    • 循环链表可以用来解决约瑟夫环的问题
    • 循环链表示意图

链表的定义

  • （未完待续）
文章来源:https://blog.csdn.net/weixin_45055622/article/details/135572717
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
最新文章