单链表的实现

单链表是用一组任意的存储单元存放线性表的元素，通过指针链接各结点。每个结点包含数据域和指针域。

┌────────┬────────┐
│  data  │  next  │
│ 数据域  │ 指针域  │
└────────┴────────┘

typedef struct LNode {
    ElemType data;        // 数据域
    struct LNode *next;   // 指针域
} LNode, *LinkList;

带头结点 vs 不带头结点

带头结点（推荐）：

[头结点] → [a₁] → [a₂] → ... → [aₙ] → NULL
  ↑
 L (指向头结点)

• 头结点不存储有效数据
• 空表：$L\text{->next == NULL}$
• 优点：统一了空表和非空表的操作

不带头结点：

[a₁] → [a₂] → ... → [aₙ] → NULL
↑
L

• 空表：$L == NULL$
• 缺点：插入删除第一个元素需要特殊处理

1. 初始化（带头结点）

bool InitList(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode));
    if (*L == NULL) return false;
    (*L)->next = NULL;
    return true;
}

2. 头插法建立链表

LinkList List_HeadInsert(LinkList *L) {
    LNode *s;  ElemType x;
    *L = (LNode *)malloc(sizeof(LNode));
    (*L)->next = NULL;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        s->next = (*L)->next;   // 新结点先指向原首元结点
        (*L)->next = s;          // 头结点指向新结点
        scanf("%d", &x);
    }
    return *L;
}

3. 尾插法建立链表

LinkList List_TailInsert(LinkList *L) {
    *L = (LNode *)malloc(sizeof(LNode));
    LNode *s, *r = *L;  // r 为尾指针
    ElemType x;
    scanf("%d", &x);
    while (x != 9999) {
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;             // 尾指针后移
        scanf("%d", &x);
    }
    r->next = NULL;
    return *L;
}

4. 按位序插入 ListInsert(&L, i, e)

bool ListInsert(LinkList L, int i, ElemType e) {
    if (i < 1) return false;
    LNode *p = L;       // p 指向头结点
    int j = 0;          // 当前 p 指向第 j 个结点
    while (p != NULL && j < i - 1) { p = p->next; j++; }
    if (p == NULL) return false;   // i 超出范围
    LNode *s = (LNode *)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;   // ① 先接
    p->next = s;         // ② 再断
    return true;
}

5. 删除操作 ListDelete(&L, i, &e)

bool ListDelete(LinkList L, int i, ElemType *e) {
    if (i < 1) return false;
    LNode *p = L;  int j = 0;
    while (p->next != NULL && j < i - 1) { p = p->next; j++; }
    if (p->next == NULL) return false;
    LNode *q = p->next;     // q 指向待删结点
    *e = q->data;
    p->next = q->next;      // 断链
    free(q);
    return true;
}

6. 查找与求表长

LNode *GetElem(LinkList L, int i) {      // 按位查找，O(n)
    if (i < 0) return NULL;
    LNode *p = L;  int j = 0;
    while (p != NULL && j < i) { p = p->next; j++; }
    return p;
}
LNode *LocateElem(LinkList L, ElemType e) {  // 按值查找，O(n)
    LNode *p = L->next;
    while (p != NULL && p->data != e) p = p->next;
    return p;
}
int Length(LinkList L) {                 // 求表长，O(n)
    int len = 0;  LNode *p = L->next;
    while (p != NULL) { len++; p = p->next; }
    return len;
}