链表数据结构详解：定义、操作与对比

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

若不带头结点，插入第 1 个位置时需修改头指针 L，其余逻辑类似。

7. 插入结点操作（指定结点）

已知结点 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;
}

前插（技巧）： 将新结点插在 p 之后，然后交换 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;
}

8. 删除结点操作

找到第 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;
}

9. 建表操作

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

LinkList List_HeadInsert(LinkList& L) {
    LNode* s;
    int 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;
}

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

LinkList List_TailInsert(LinkList& L) {
    int x;
    L = (LNode*)malloc(sizeof(LNode));
    LNode* s, * r = L;
    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;
}

三、双链表的定义

单链表查找、插入、删除的时间复杂度通常为 O(n)，因为只能单向遍历。双链表增加了前驱指针 prior，可双向访问，插入与删除操作在已知结点情况下时间复杂度可降至 O(1)。

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

四、双链表的基本操作

1. 初始化

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

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

2. 插入

在已知结点 p 后插入 s，需同时处理前后指针的连接。

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

3. 删除

删除 p 的后继结点，需重新连接 p 与其后继的后继，并释放内存。

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

4. 销毁

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

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

五、循环链表的定义

1. 循环单链表

表尾结点的 next 指向头结点，而非 NULL。判空条件变为 L->next == L。

2. 循环双链表

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

六、静态链表的定义

静态链表是用数组模拟链式存储。next 域存储的是数组下标（游标），而非内存地址。数组大小固定，无法动态扩容，但无需频繁申请释放内存。

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

以 next == -1 作为结束标志。

七、顺序表和链表的区别

顺序表适合读多写少的场景，链表适合频繁插入删除的场景。