数据结构核心：链表（单链表、双链表及循环链表）

链表结构详解

一、单链表的定义

单链表是线性表的链式存储结构。它通过一组任意的存储单元来存储数据元素，并通过指针建立数据元素之间的关系。每个结点包含数据域和指针域，其中指针域指向后继结点的地址。

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

注意区分 LNode*（表示一个结点）与 LinkList（表示整个链表）。由于元素在内存中离散分布，单链表不支持随机存取，查找特定元素需从头遍历。

头节点与头指针

无论是否有头节点，头指针始终指向链表的第一个结点。头结点是带头链表中的第一个结点，通常不存储有效信息。引入头结点的优势在于统一了空表和非空表的处理逻辑，且第一个数据结点的位置操作与其他位置一致。

二、单链表的基本操作

1. 初始化

带头结点： 申请一块内存作为头结点，将 next 指针置为 NULL。

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

不带头结点： 直接将头指针设为 NULL。

bool InitList(LinkList& L) {
    L = NULL;
    return true;
}

2. 判空

检查头指针的 next 是否为 NULL。若为空则返回 true。

bool Empty(LinkList L) {
    return L->next == NULL;
}

3. 求表长

遍历链表统计数据结点个数。

int Length(LinkList L) {
    int len = 0;
    LNode* p = L;
    while (p->next != NULL) {
        p = p->next;
        len++;
    }
    return len;
}

4. 按序号查找结点

从表头开始遍历，找到第 i 个结点。若越界或链表过短则返回 NULL。

LNode* GetElem(LinkList L, int i) {
    LNode* p = L;
    int j = 0;
    while (p != NULL && j < i) {
        p = p->next;
        j++;
    }
    return p;
}

5. 按值查找表结点

遍历链表寻找第一个值为 e 的结点。

LNode* LocateElem(LinkList L, ElemType e) {
    LNode* p = L->next;
    while (p != NULL && p->data != e)
        p = p->next;
    return p;
}

6. 插入结点操作

指定位置插入： 先定位到第 i-1 个结点，再执行指针修改。

bool ListInsert(LinkList& L, int i, ElemType 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) return false;
    
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

指定结点前插： 利用已知结点 p，在其后插入新结点并交换数据，避免重新遍历。

bool InsertPriorNode(LNode* p, ElemType e) {
    if (p == NULL) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->next = p->next;
    p->next = s;
    s->data = p->data;
    p->data = e;
    return true;
}

指定结点后插： 直接在 p 之后插入新结点。

bool InsertNextNode(LNode* p, ElemType e) {
    if (p == NULL) return false;
    LNode* s = (LNode*)malloc(sizeof(LNode));
    s->data = e;
    s->next = p->next;
    p->next = s;
    return true;
}

7. 删除结点操作

定位到第 i-1 个结点，释放第 i 个结点内存。

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

8. 建立单链表

头插法： 每次新结点插在头结点之后，生成的链表顺序与输入顺序相反。

LinkList List_HeadInsert(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    L->next = NULL;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        s->next = L->next;
        L->next = s;
        scanf("%d", &x);
    }
    return L;
}

尾插法： 维护尾指针 r，新结点插在尾部，保持输入顺序。

LinkList List_TailInsert(LinkList& L) {
    L = (LNode*)malloc(sizeof(LNode));
    LNode* r = L;
    int x;
    scanf("%d", &x);
    while (x != 9999) {
        LNode* s = (LNode*)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;
        r = s;
        scanf("%d", &x);
    }
    r->next = NULL;
    return L;
}

三、双链表的定义

双链表在单链表基础上增加了前驱指针 prior，可双向遍历。结点结构如下：

typedef struct DNode {
    ElemType data;
    struct DNode* prior, * next;
} DNode, *DLinklist;

双链表插入与删除操作的时间复杂度可优化至 O(1)，因为可以直接访问前驱结点。

四、双链表的基本操作

1. 初始化

申请头结点，将 prior 和 next 均置为 NULL。

bool InitDLinklist(DLinklist& L) {
    L = (DNode*)malloc(sizeof(DNode));
    if (!L) return false;
    L->prior = NULL;
    L->next = NULL;
    return true;
}

2. 插入结点

在已知结点 p 后插入结点 s，需同时调整前后指针关系。

bool InsertNextDNode(DNode* p, DNode* s) {
    if (!p || !s) return false;
    s->next = p->next;
    if (p->next) p->next->prior = s;
    s->prior = p;
    p->next = s;
    return true;
}

3. 删除结点

删除结点 p 的后继结点，需断开前后连接并释放内存。

bool DeleteNextNode(DNode* p) {
    if (!p) return false;
    DNode* q = p->next;
    if (!q) return false;
    p->next = q->next;
    if (q->next) q->next->prior = p;
    free(q);
    return true;
}

4. 销毁链表

循环删除所有数据结点，最后释放头结点。

void DestroyList(DLinklist& L) {
    while (L->next != NULL)
        DeleteNextNode(L);
    free(L);
    L = NULL;
}

五、循环链表

1. 循环单链表

表尾结点的 next 指针指向头结点，形成环状。判空条件变为 L->next == L。

2. 循环双链表

头结点的 prior 指针也指向表尾结点。判空需同时检查 next 和 prior 是否指向头指针。

六、静态链表

使用数组模拟链式存储，next 字段存储数组下标而非地址。适合无法动态分配内存的环境，但长度固定。

#define MaxSize 50
typedef struct {
    ElemType data;
    int next;
} SLinkList[MaxSize];

以 -1 作为结束标志。

七、顺序表和链表的区别

特性	顺序表	链表
存取方式	随机存取 O(1)	顺序存取 O(n)
物理结构	连续存储	离散存储
空间分配	需预分配，扩容成本高	动态分配，利用碎片空间
插入/删除	需移动大量元素	仅需修改指针

顺序表适合频繁查询的场景，而链表更适合频繁插入删除且长度不确定的场景。