每日科普 · 2026-09-19 周六

考研 408 × 求职面试

知识点 · 数据结构 · 基础

静态链表的存储结构与操作

静态链表是用数组模拟单链表：先开一个固定大小的数组，每个元素就是一个结点，包含 data 和 next。next 不存内存地址，而存下一个结点的数组下标，通常称为游标。
存储结构：数组 0 号常作头结点，数据结点和空闲结点都在同一数组中；空闲结点用 next 串成备用链表，-1 表示空。
初始化：把头结点 next 置 -1，把所有空闲结点链接成备用链表。
插入：先从备用链表取一个空闲结点（分配），填入数据，再修改相关游标，把它挂到目标位置。
删除：把待删结点从数据链表摘除，再把它插回备用链表（回收）。
查找/遍历：从 head 的 next 开始，按 next 下标一路跳到 -1。
优点是无需指针、可在不支持指针的语言中实现链表；缺点是容量固定，游标管理易错，插入删除仍要改多个 next。

每日一题 · 数据结构

静态链表的存储结构与操作

关于静态链表，下列说法正确的是：
A. 结点中的 next 存放下一个结点的内存地址
B. 静态链表不能进行插入和删除
C. 静态链表用数组存储结点，next 通常存下一个结点的数组下标
D. 静态链表必须用 malloc 动态申请结点

解析

选 C。静态链表用数组模拟链表，结点的 next 是游标（数组下标），不是指针地址。它同样能插入、删除，只是要先从备用链表分配结点，删除后回收结点；容量由数组大小决定，不需要 malloc。A 把游标误认为地址，B、D 说法错误。

面试小贴士 · 数据结构

静态链表的存储结构与操作

常问与动态链表区别、备用链表、插入删除。答：数组存结点，next 存下标，0 号常为头结点，空闲结点串成备用链表；插入先分配再改游标，删除后回收。易错：下标当指针、-1 边界、头结点处理。

代码实现 · C

代码示例

#include <stdio.h>
#define MAXSIZE 10
typedef struct { int data; int next; } Node;
Node space[MAXSIZE]; int head = 0, avail;
void init() {
    space[head].next = -1;
    for (int i = 1; i < MAXSIZE - 1; i++) space[i].next = i + 1;
    space[MAXSIZE - 1].next = -1; avail = 1;
}
int mallocNode() {
    if (avail == -1) return -1;
    int i = avail; avail = space[avail].next; return i;
}
void freeNode(int i) { space[i].next = avail; avail = i; }
void insertHead(int x) {
    int i = mallocNode(); if (i == -1) return;
    space[i].data = x; space[i].next = space[head].next; space[head].next = i;
}
void deleteHead() {
    int p = space[head].next; if (p == -1) return;
    space[head].next = space[p].next; freeNode(p);
}
void traverse() {
    for (int p = space[head].next; p != -1; p = space[p].next) printf("%d ", space[p].data);
    putchar('\n');
}
int main() {
    init(); insertHead(10); insertHead(20); traverse();
    deleteHead(); traverse(); return 0;
}