单向链表结构图（单向链表是什么）

科技前沿 • 2025-05-12 15:53 • 阅读 46

大家好，我是讯享网，很高兴认识大家。

链表：用一组物理位置任意的存储单元来存放线性表的数据元素，逻辑次序和物理次序不一定相同。通过头指针进入链表，依次向后顺序扫描其余结点，因此各个寻找各个结点所花时间不相等（顺序存取法）。（顺序表为随机存取法）
结点=数据域+指针域。结点只有一个指针域为单链表，首尾相接为循环链表。
头结点：

嵌套定义指针*next
定义头结点的指针代表了整个链表，用LinkList L；定义某一结点的指针则用LNode *p。

初始化即为定义一个头指针并指向一个指针域为空的头结点。

判断为空：判断头结点的指针域是否为空。

链表仍存在，但链表中无元素，成为空链表。销毁会删除头结点，清空仅保留头结点（相当于恢复到初始化的状态）。
指针p指向要删除的结点，指针q指向p的下一个结点，依次遍历所有结点。p为NULL时结束，并将头结点的指针域指向NULL。

从链表的头指针出发，顺着链域next逐个结点往下搜索，直至搜索到第i个结点为止。因此，链表不是随机存取结构。
j用来遍历计数，p非空且j<i时继续搜索，j>i说明为异常情况。

获取数据的地址或者位于链表第几个元素。
算法：从第一个结点起，依次和数据e相比较，如果找到一个值和e相等的数据元素，则返回其地址或者位置；如果查遍整个链表等没有找到其值和e相等的元素，则返回0或者NULL。

需要返回的链表L以及删除的数据e用引用传递。q为指向待删除结点的指针。
线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为O（1）。但是由于要从头查找前驱结点，故插入和删除所耗时间复杂度为O（n）。

循环链表：首尾相接，表中最后一个结点的指针域指向头结点，整个链表形成一个环。
优点：从表中任意一个结点出发均可找到表中其他结点。

由于经常在首尾操作，故用尾指针来表示单循环链表。

循环链表的合并：Tb接在Ta后面

双向链表比单链表多一个前驱指针*prior