其他链表

双向链表

每个结点有两个指针域,分别指向前驱和后继,支持双向遍历。代价是每个结点多一个指针,空间开销更大。

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

简述单链表和双链表的区别及各自适用场景。

单链表双链表前驱指针应用场景

解题思路:

本题考查单链表与双链表在结点结构上的差异及其取舍。答题时先从“指针域个数”这一结构差异说起,再分别给出各自的典型适用场景。

详细步骤:

  1. 单链表:每个结点只有一个指向后继的指针,结构简单、占用空间少,适合只需向一个方向遍历的场景。
  2. 双链表:每个结点有两个指针,分别指向前驱和后继,支持双向遍历,但每个结点多占一个指针空间。
  3. 场景选择:需要在两个方向上频繁移动时选双链表,典型如文本编辑器的光标移动、LRU 缓存等。

最终答案:

单链表:每个节点只有一个指向后继的指针,结构简单、占用空间少,适合只需向一个方向遍历的场景。双链表:每个节点有两个指针分别指向前驱和后继,支持双向遍历,但每个结点多占一个指针空间。适合需要频繁在两个方向移动的场景,如文本编辑器的光标移动、LRU 缓存等。

发现内容有问题?

告诉我们哪里需要改进。