单链表的基本操作

单链表是最基本的链式存储结构，用一组任意的存储单元存放数据元素，每个结点包含两个域：

• 数据域（data）：存储元素的信息
• 指针域（next）：存储直接后继结点的存储地址

单链表非随机存取：不能直接访问第 i 个结点，必须从头指针出发沿 next 逐个查找。

两种实现思路

带头结点：第一个结点不存数据，仅作标识。空表与非空表处理统一，无需对首结点特殊处理——408 默认带头结点。

不带头结点：第一个结点直接存数据，插入/删除需判断是否修改头指针，代码更复杂。

typedef struct LNode {
    int data;              // 数据域（考试中常用 int）
    struct LNode *next;    // 指针域
} LNode, *LinkList;

插入（第 i 位插入 e）

1. 令 p = L, j = 0
2. 当 j < i-1 且 p != NULL：p = p->next, j++
3. 若 p == NULL，位置不合法，返回 false
4. 分配新结点 s；s->data = e
5. s->next = p->next    // 先接后断！
6. p->next = s          // 再接前
7. 返回 true

删除（删第 i 位，e 带回）

1. 令 p = L, j = 0
2. 当 j < i-1 且 p != NULL：p = p->next, j++
3. 若 p == NULL 或 p->next == NULL，位置不合法
4. 令 q = p->next        // q 指向待删结点
5. e = q->data
6. p->next = q->next     // 跨过待删结点
7. free(q)；返回 true

查找

按位 GetElem：p = L->next, j = 1；当 j < i 且 p != NULL 时 p=p->next, j++；返回 p
按值 LocateElem：p = L->next；当 p != NULL 且 p->data != e 时 p = p->next；返回 p
求表长 Length：p = L->next, count = 0；p != NULL 时 count++, p = p->next；返回 count

插入操作

// 在第 i 个位置插入元素 e（带头结点）
bool ListInsert(LinkList L, int i, int e) {
    if (i < 1) return false;         // 位置不合法
    LNode *p = L;  int j = 0;
    while (p != NULL && j < i - 1) { // 找第 i-1 个结点
        p = p->next;  j++;
    }
    if (p == NULL) return false;
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;              // 先接后断（核心！）
    p->next = s;
    return true;
}

删除操作

bool ListDelete(LinkList L, int i, int *e) {
    if (i < 1) return false;
    LNode *p = L;  int j = 0;
    while (p != NULL && j < i - 1) { p = p->next; j++; }
    if (p == NULL || p->next == NULL) return false;
    LNode *q = p->next;
    *e = q->data;
    p->next = q->next;               // 断开 q
    free(q);
    return true;
}

头插法建表

LinkList HeadInsert(int a[], int n) {
    LinkList L = (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    for (int i = 0; i < n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = a[i];
        s->next = L->next;   // 插到头结点之后
        L->next = s;
    }
    return L;
}

尾插法建表

LinkList TailInsert(int a[], int n) {
    LinkList L = (LinkList)malloc(sizeof(LNode));
    LNode *r = L;                    // r 始终指向尾结点
    for (int i = 0; i < n; i++) {
        LNode *s = (LNode *)malloc(sizeof(LNode));
        s->data = a[i];
        r->next = s;
        r = s;
    }
    r->next = NULL;                  // 尾结点的 next 置空
    return L;
}