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

插入与删除

插入操作需注意指针修改顺序，防止断链。指定位置插入时需先找到前驱节点。指定结点前插可通过复制数据域技巧简化指针操作。

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

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

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

双链表的定义

双链表增加了 prior 指针，可双向遍历。结点结构包含 data、prior 和 next。虽然查找复杂度仍为 O(n)，但插入和删除操作因可直接访问前驱节点，效率更高。

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

双链表的基本操作

初始化与销毁

初始化需分配头结点并置前后指针为空。销毁时需遍历释放所有节点内存。

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

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

插入与删除

双链表后插需同时维护前后指针的指向关系，确保双向链接完整。

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

循环链表与静态链表

循环单链表将尾结点的 next 指向头结点，判空条件变为 L->next == L。循环双链表进一步要求头结点的 prior 也指向尾结点。

静态链表使用数组模拟链表，下标代替指针。其优势在于无需动态内存管理，但长度固定，灵活性较差。

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

顺序表和链表的区别

顺序表适合频繁查询的场景，而链表更适合频繁插入删除且数据量不确定的情况。