数据结构核心：链表详解与实现

求表长

遍历链表计数，直到遇到 NULL。

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

按序号查找结点

从表头开始遍历，找到第 i 个结点。

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

按值查找表结点

遍历链表寻找匹配 ElemType e 的结点。

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

插入结点操作

指定位置插入

在位置 i 前插入新元素 e。需先找到第 i-1 个结点，修改指针指向。

bool ListInsert(LinkList& L, int i, ElemType e) {
    if (i < 1) return false;
    LNode* p = L;
    int j = 0;
    // 找到第 i-1 个结点
    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，在其后插入 e。

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;
}

指定结点前插

已知结点 p，在其前插入 e。通常采用'后插 + 交换数据'的技巧实现，避免重新遍历。

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;
}

删除结点操作

删除第 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;
}

建立单链表

头插法

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

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* s, * r = L;
    int 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;
}

双链表的定义

双链表在单链表基础上增加了 prior 指针，指向直接前驱。这使得双向遍历成为可能，插入和删除操作在已知结点时效率更高（O(1)）。

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

双链表的基本操作

初始化

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

插入与删除

双链表的双向特性要求同时维护前后指针的连接。

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

// 删除后继
bool DeleteNextNode(DNode* p) {
    if (p == NULL) return false;
    DNode* q = p->next;
    if (q == NULL) return false;
    p->next = q->next;
    if (q->next != NULL) q->next->prior = p;
    free(q);
    return true;
}

销毁

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

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

循环链表的定义

循环单链表

表尾结点的 next 指针指向头结点，形成环状。

• 判空：L->next == L
• 判尾：p->next == L

循环双链表

头结点的 prior 指针也指向表尾结点。

• 判空：L->next == L && L->prior == L

静态链表的定义

静态链表使用数组模拟链式存储。next 字段存储的是数组下标而非内存地址。

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

以 -1 作为结束标志。其优势在于无需动态内存管理，但长度固定且存在碎片问题。

顺序表和链表的区别

顺序表适合频繁读取、长度固定的场景；链表适合频繁增删、长度不确定的场景。