顺序表虽然乖，却有个小委屈：头插要全体搬家，扩容还可能牵动整块土地。于是就有了单链表——一个个小节点散落在内存各处，靠指针手拉手连成一串。想插人就地站进去牵好手，谁也不用搬家。

节点是什么呀

typedef int STLData;

typedef struct STL {
    STLData data;          // 节点里装的数据
    struct STL* next;      // 指向下一个节点，手拉手的绳子的感觉
}STLNode;

每个节点自带两样东西：数据，和一根牵着下一个节点的手。最后一个节点的 next 指向 NULL，意思是「我后面没有人啦」。打印整条链表也像散步一样简单：

void STLPrint(STLNode* phead)
{
    STLNode* p = phead;
    while (p)
    {
        printf("%d->", p->data);
        p = p->next;
    }
    printf("NULL\n");
}

先造一个新节点

STLNode* STLButNode(STLData x)
{
    STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
    if (newnode == NULL)
    {
        perror("malloc fail");
        exit(1);
    }
    newnode->data = x;
    newnode->next = NULL;   // 先不牵任何人
    return newnode;
}

尾插：走到最后再牵手

void STLPushBack(STLNode** phead, STLData x)
{
    assert(phead);
    STLNode* newnode = STLButNode(x);
    if (*phead == NULL)          // 空链表：新节点就是头
        *phead = newnode;
    else                         // 非空：先找到尾巴
    {
        STLNode* ptail = *phead;
        while (ptail->next)      // 走到最后一个节点停
            ptail = ptail->next;
        ptail->next = newnode;
    }
}

注意这里是二级指针！要改变 int 就传 int*，要改变 int*（也就是头指针 plist 本身）就得传 int**。空链表插第一个节点时，改的正是头指针自己。

头插就痛快多了——新节点牵住旧头，再把头指针交出去：

void STLPushFront(STLNode** phead, STLData x)
{
    assert(phead);
    STLNode* newnode = STLButNode(x);
    newnode->next = *phead;
    *phead = newnode;
}

尾删的小心翼翼

删尾巴要分两种情况：只有一个节点时，直接 free 并把头指针置空；不止一个时，得牵着前一个节点一起走到最后，free 掉尾巴后把前一个的 next 置空。

void STLDelBack(STLNode** phead)
{
    assert(phead && *phead);      // 空链表没得删
    if ((*phead)->next == NULL)   // 只有一个节点
    {
        free(*phead);
        *phead = NULL;
    }
    else
    {
        STLNode* p = *phead;      // p 记住倒数第二个
        STLNode* ptail = *phead;
        while (ptail->next)
        {
            p = ptail;
            ptail = ptail->next;
        }
        free(ptail);
        ptail = NULL;
        p->next = NULL;
    }
}

查找与按位插删

STLNode* STLFind(STLNode* head, STLData x)
{
    STLNode* p = head;
    while (p)
    {
        if (p->data == x)
            return p;       // 找到啦，把节点地址交出来
        p = p->next;
    }
    return NULL;            // p 走到 NULL 还没遇到，就是没有
}

找到 pos 之后就可以插删啦。pos 之前插入要从头找 pos 的前一个；而 pos 之后插入完全不需要头指针，拿到 pos 就能玩：

void STLInsertBack(STLNode* pos, STLData x)   // pos 之后插入
{
    assert(pos);
    STLNode* newnode = STLButNode(x);
    newnode->next = pos->next;
    pos->next = newnode;
}

void STLAfterDel(STLNode* pos)                // 删 pos 后面那个
{
    assert(pos && pos->next);
    STLNode* del = pos->next;
    pos->next = del->next;
    free(del);
    del = NULL;
}

这也是链表做题时偏爱「找前一个」或「在后面动手」的小秘密——不动头指针，事情就简单一半。

那 pos 之前插入和删除 pos 自己呢？它们都得找到 pos 的前一个，顺便还要照顾 pos 恰好是头结点的情况：

void STLInsertFront(STLNode** phead, STLNode* pos, STLData x)
{
    assert(phead && *phead && pos);
    STLNode* newnode = STLButNode(x);
    if (pos == *phead)          // pos 就是头，等价于头插
    {
        STLPushFront(phead, x);
    }
    else                        // 找到 pos 的前一个 p
    {
        STLNode* p = *phead;
        while (p->next != pos)
            p = p->next;
        // p -> newnode -> pos
        newnode->next = pos;
        p->next = newnode;
    }
}

void STLDel(STLNode** phead, STLNode* pos)
{
    assert(phead && *phead && pos);
    if (pos == *phead)          // 删的是头结点
    {
        STLNode* p = (*phead)->next;
        free(*phead);
        *phead = p;
    }
    else
    {
        STLNode* p = *phead;
        while (p->next != pos)
            p = p->next;
        p->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

挥手告别也要一节一节

void STLDestory(STLNode** phead)
{
    STLNode* p = *phead;
    while (p)
    {
        STLNode* next = p->next;  // 先记住下一只手
        free(p);
        p = next;
    }
    *phead = NULL;
}

销毁时一定先用 next 记下下一个节点再 free——不然这条线就断在手里，剩下的节点再也找不到了。

愿当下的花如你所见般美丽