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