其他链表
每个结点有两个指针域,分别指向前驱和后继,支持双向遍历。代价是每个结点多一个指针,空间开销更大。
typedef struct DNode {
int data;
struct DNode *prior, *next;
} DNode, *DLinkList;
插入操作(在 p 结点后插入 s):
s->prior = p;
s->next = p->next;
p->next->prior = s;
p->next = s;
- 循环单链表:最后一个结点的指针指向头结点(或首元结点),使整个链表首尾相连,可从任一结点出发访问全部结点。
- 循环双链表:头结点的 prior 指向尾结点,尾结点的 next 指向头结点。
循环链表常用于需要频繁在首尾操作的场景(如约瑟夫环、操作系统进程调度)。
用数组模拟链表,结点的”指针”用数组下标(游标)代替,适用于不支持指针的高级语言或内存受限场景。
习题 1
简述单链表和双链表的区别及各自适用场景。
解题思路:
本题考查单链表与双链表在结点结构上的差异及其取舍。答题时先从“指针域个数”这一结构差异说起,再分别给出各自的典型适用场景。
详细步骤:
- 单链表:每个结点只有一个指向后继的指针,结构简单、占用空间少,适合只需向一个方向遍历的场景。
- 双链表:每个结点有两个指针,分别指向前驱和后继,支持双向遍历,但每个结点多占一个指针空间。
- 场景选择:需要在两个方向上频繁移动时选双链表,典型如文本编辑器的光标移动、LRU 缓存等。
最终答案:
单链表:每个节点只有一个指向后继的指针,结构简单、占用空间少,适合只需向一个方向遍历的场景。双链表:每个节点有两个指针分别指向前驱和后继,支持双向遍历,但每个结点多占一个指针空间。适合需要频繁在两个方向移动的场景,如文本编辑器的光标移动、LRU 缓存等。
