上一篇文章以iOS自动释放池初步认识了链表,本篇主要从链表的组成,插入,删除三个部分进一步了解。
之所以了解链表,是因为在了解队列数据结构时,发现一些概念比较模糊,因此重新梳理下,链表指针域是插入和删除如何处理的
链表简介
链式存储概念:链式存储表示的特点是用一组任意存储单元存储数据元素,这组存储单元可以是连续也可以是不连续
简单来说,线性表的链式存储结构生成的表,称为“链表”,链表是一种物理存储单元上非连续,非顺序的存储结构,数据元素之间的逻辑顺序通过链表中的指针链接次序实现。
链表由一系列结点组成,结点可以在运行时动态生成。
链表组成
数据元素有两部分组成,本身信息,成为“值域”;
指向直接后继的指针,成为“指针域”
这两部分信息组成数据元素的存储结构,成为节点,很多节点联系一起,组成链表
头结点
:有时,链表第一个结点之前会增设一个结点,结点的数据域不存放数据,此结点成为头结点。头结点指针域为NULL,表明链表是空表
首元结点
:链表第一个元素所在结点,头结点后面的第一个结点,因为头结点可能没有。(头结点具备会让问题解决变得简单)
头指针
:指向链表第一个结点位置,是一个指针指向链表头结点或者首元节点,头指针没有分配存储空间,只是进行了声明。
链表特点
由于链表分散存储,在存储上不连续,为了表示每个数据元素和直接后继数据元素之间的关系,还需存储指示下一后继元素的信息。
为了找一个数,必须从头找,特别麻烦。
插入删除
链表插入,链表的首部,链表中间,链表末端三种。
新结点插入的next指针,指向插入位置后的结点
新结点插入前的结点,next指针指向新结点,也就是插入结点
插入操作,找到插入位置的上一个结点,并根据next指针找到下一个结点,
将插入位置next指针指向 找到的下一个结点。插入位置的next指针指向新的结点。
删除操作:将结点从链表摘了,分离逻辑关系,手动释放结点,回收内存空间。修改删除节点的next指针,将上个节点next指针指向删除节点下一个节点,完成逻辑连接
网友评论