要实现对一组数据的增删查改，我们可以用动态顺序表来实现。但是动态顺序表也有它的缺陷，那就是要对某个位置的数据进行删除，或者在某个数据之前或之后插入数据，就要改变部分数据原有的位置。

而用链表的话，就不会有这种情况，只需要让指针指向对应的位置就可以。

链表有很多种，今天就来讲解单链表是如何实现增删查改的。

这是一张单链表的逻辑图：

可以看到，每一个节点都有对应的存储的数据data，以及一个next指针。data用于存放数据，next指针指向下一个节点。然后在链表尾要指向一个空指针，表示这个链表到此结束。

这是一个单链表节点的基本形态：

typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;

 

一、申请节点

SLTNode* BuyListNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->Data = x;newnode->Next = NULL;return newnode;
}

申请节点就是你传一个数据x，然后使用malloc函数开辟一个空间，用newnode指向这块空间。如果开闭失败了，那么指针就为空，然后就会提示开辟失败。如果开辟成功了，那么，这块空间里的data的值就是x，然后呢，由于这是新开辟的空间，还不知道他有没有下一个节点，那就暂时让next指向空。

二、单链表打印

void SLTPrint(SLTNode* phead)
{SLTNode* cur = phead;while (cur){printf("%d->", cur->Data);cur = cur->Next;}printf("NULL\n");
}

单链表打印就是把头节点的地址传给这个函数，然后呢，用cur将头节点的指针存起来。只要cur不是空，那么while循环就继续，就会打印当前节点的数据，每次打印之后，cur就指向下一个节点。

三、单链表尾插

void SLTPushBack(SLTNode** pphead,SLTDataType x)
{SLTNode* newnode = BuyListNode(x);if (pphead == NULL){*pphead = newnode;}else{SLTNode* tail = *pphead;while (tail->Next != NULL){tail = tail->Next;}tail->Next = newnode;}
}

要注意我们的第一个参数是个二级指针，我们是用二级指针对指针进行操作。

进入这个函数之后，先使用buylistnode申请一块空间，用newnode将这块空间的地址存储起来。然后看头节点是不是空的，如果是空的，那就将刚刚申请的空间地址，给头结点就可以了。如果头节点不是空的，那就先假定头节点是尾节点。就要将头节点的地址给尾节点的指针，然后进入while循环。只要当前节点的下一个节点不为空，那么while循环就继续，然后让当前指针指向下一个节点的地址。直到找到最后一个节点，就把刚申请的newnode给尾节点的下一个节点（在此之前，尾节点的下一个节点是空）。

四、单链表头插

void SLTPushFront(SLTNode** pphead,SLTDataType x)
{SLTNode* newnode = BuyListNode(x);newnode->Next=*pphead;*pphead = newnode;
}

头插很简单，就是先申请一块空间，然后让这块空间的next指向头节点，把newnode给头节点的指针。

五、单链表尾删

void SLTPopBack(SLTNode** pphead)
{if ((*pphead)->Next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* tail = *pphead;while (tail->Next->Next != NULL){tail = tail->Next;}free(tail->Next);tail->Next = NULL;}
}

单链表的尾删要考虑两种情况，如果说这个链表只有一个节点，那么我们就free掉这块空间，然后将指针指空就可以了。

如果不是只有一个节点，那就要去遍历了。只要当前节点的下一个的节点的下一个节点不是空，那么while循环就继续。如果当前节点的下一个节点的下一个节点是空了，那就free掉当前节点的下一个节点就可以了，然后将指向下一个节点的指针置空。因为这里有考虑到下一个的节点的下一个节点，那么如果不考虑只有一个节点的情况，就会发生越界。

六、单链表头删

void SLTPopFront(SLTNode** pphead)
{SLTNode* first = *pphead;*pphead = first->Next;free(first);first = NULL;
}

单链表的头删很简单，就是用first将头结点的指针存储起来，让头节点指向first的下一个节点，然后free掉first所指向的空间，再将first指针置空就可以了。

七、单链表查找

SLTNode* SLTFind(SLTNode** pphead, SLTDataType x)
{SLTNode* cur = *pphead;while (cur){if (cur->Data == x){return cur;}cur = cur->Next;}return NULL;
}

将链表头节点的指针给cur，然后去遍历。只要cur不是空，那么while循环就继续。如果当前空间的data等于要查找的数据，就返回当前节点的指针。如果找不到，要查找的数据，那么在遍历结束后就返回空指针。

八、单链表删除

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead);assert(pos);if (*pphead == pos){SLTPopFront(*pphead);}else{SLTNode* prev = pphead;while (prev->Next != pos){prev = prev->Next;}prev->Next = pos->Next;free(pos);pos = NULL;}
}

在这里，pphead是头节点的指针，pos是要删除的节点的指针。假如要删除的节点就是头节点，那么头删就可以。如果不是的话，就遍历。prev存储的是要删除的节点的前一个节点，找到要删除的节点之后，就让prev指向当前节点的下一个节点，然后free掉当前节点，再将当前节点的指针置空。

九、单链表在pos位置之后插入x

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = BuySLTNode(x);newnode->Next = pos->Next;pos->Next = newnode;
}

这个用图来解释更明确……

十、单链表删除pos位置之后的值

void SLTEraseAfter(SLTNode* pos)
{assert(pos);assert(pos->Next);SLTNode* del = pos->Next;pos->Next = del->Next;free(del);del = NULL;
}

同样，上图......