美文网首页
初始链表(2)

初始链表(2)

作者: 萧修 | 来源:发表于2023-03-25 10:06 被阅读0次

    上一篇文章以iOS自动释放池初步认识了链表,本篇主要从链表的组成,插入,删除三个部分进一步了解。
    之所以了解链表,是因为在了解队列数据结构时,发现一些概念比较模糊,因此重新梳理下,链表指针域是插入和删除如何处理的

    链表简介

    链式存储概念:链式存储表示的特点是用一组任意存储单元存储数据元素,这组存储单元可以是连续也可以是不连续

    简单来说,线性表的链式存储结构生成的表,称为“链表”,链表是一种物理存储单元上非连续,非顺序的存储结构,数据元素之间的逻辑顺序通过链表中的指针链接次序实现。

    链表由一系列结点组成,结点可以在运行时动态生成。

    链表组成

    数据元素有两部分组成,本身信息,成为“值域”;
    指向直接后继的指针,成为“指针域”
    这两部分信息组成数据元素的存储结构,成为节点,很多节点联系一起,组成链表

    头结点:有时,链表第一个结点之前会增设一个结点,结点的数据域不存放数据,此结点成为头结点。头结点指针域为NULL,表明链表是空表

    首元结点:链表第一个元素所在结点,头结点后面的第一个结点,因为头结点可能没有。(头结点具备会让问题解决变得简单)

    头指针:指向链表第一个结点位置,是一个指针指向链表头结点或者首元节点,头指针没有分配存储空间,只是进行了声明。

    链表特点

    由于链表分散存储,在存储上不连续,为了表示每个数据元素和直接后继数据元素之间的关系,还需存储指示下一后继元素的信息。

    为了找一个数,必须从头找,特别麻烦。

    插入删除

    链表插入,链表的首部,链表中间,链表末端三种。
    新结点插入的next指针,指向插入位置后的结点
    新结点插入前的结点,next指针指向新结点,也就是插入结点

    插入操作,找到插入位置的上一个结点,并根据next指针找到下一个结点,
    将插入位置next指针指向 找到的下一个结点。插入位置的next指针指向新的结点。

    删除操作:将结点从链表摘了,分离逻辑关系,手动释放结点,回收内存空间。修改删除节点的next指针,将上个节点next指针指向删除节点下一个节点,完成逻辑连接

    相关文章

      网友评论

          本文标题:初始链表(2)

          本文链接:https://www.haomeiwen.com/subject/qsxnrdtx.html