专栏首页hui顺序表与链表的比较

顺序表与链表的比较

链式存储结构的优点:

  • 结点空间可以动态申请和释放。
  • 数据元素的逻辑次序靠结点的指针来指示,插入和删除时不需要移动数据元素。

链式存储结构的缺点:

  • 存储密度小,每个结点的指针域需额外占用存储空间。当每个结点的数据域所占字节不多时,指针域所占存储空间的比重显得很大。
  • 链式存储结构是非随机存取结构。对任一结点的操作都要从头指针依指针链查找到该结点,这增加了算法的复杂度。

存储密度

存储密度是指结点数据本身所占的存储量和整个结点结构中所占的存储量之比,即:

存储密度 = 结点数据本身占用的空间 / 结点占用的空间总量

结点的数据域a1占8个字节,地址域占4个字节,所以存储密度 = 8 / 12 = 67%

一般地,存储密度越大,存储空间的利用率就越高。显然,顺序表的存储密度为1 (100%) ,而链表的存储密度小于1。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 树和二叉树

    ​ 2. 当 n > 1 时,其余结点可分为 m(m > 0)个互不相交的有限集T1、T2,… ,Tm,其中每一个集合本身又是一颗树,并且称为根的 子树(Sub...

    忆想不到的晖
  • 单链表的头尾插法详解

    head 结点的数据域为空 head -> data = NULL, ,地址域为空 head -> next = NULL;

    忆想不到的晖
  • C语言实现单链表

    单链表是由多个结点链接组成,它的每个结点包含两个域,一个数据域和一个链接域(地址域)。

    忆想不到的晖
  • Django的ORM

    调用如下方法会返回查询集 filter all order_by exclude 返回条件之外的数据

    KEVINGUO_CN
  • 利用人工智能帮助警方判断罪犯危险程度

    工作在一线的警察正在对剑桥大学犯罪学家研发的人工智能系统进行试验,以利用过去的五年犯罪史统计指导警方的工作。

    思谱云汇
  • SLAM程序阅读(第8讲 半稠密直接法)

    这期我们来继续读一下半稠密直接法求解位姿的程序direct_semidense.cpp。

    小白学视觉
  • LintCode 1671. 玩游戏(贪心、难)

    N 个人在玩游戏,每局游戏有一个裁判和 N-1 个平民玩家。给出一个数组 A, A[i] 代表玩家 i 至少需要成为平民 A[i] 次,返回最少进行游戏的次数。

    Michael阿明
  • [深度概念]·模型集成(Ensemble)解析

    曾经听过一句话,”Feature为主,Ensemble为后”。Feature决定了模型效果的上限,而Ensemble就是让你更接近这个上限。Ensemble讲究...

    小宋是呢
  • flask 项目后台源码安装部署(微信报修小程序源码讲解一)

    这里不详细讲解如何手动安装 flask 及其扩展 , 我针对项目源码使用 PyCharm 开发工具教你如何正确的运行源代码。

    热心的程序员
  • 数据库中日期的插入(Oracle和Mysql)

    时间静止不是简史

扫码关注云+社区

领取腾讯云代金券