数据结构——单链表

**不能毁灭我的，终将使我更强大 **

大家好，我是纪宁。

上篇文章介绍了数据结构的入门——顺序表，比较简单。这篇文章我们来学习链表（单链表），难度稍微增加了一点，不过只要C语言的结构和指针部分的知识扎实，那么也是可以轻松拿捏的。

注：博主也在持续学习中，如知识点或代码有问题欢迎在评论区指出。

指针http://t.csdn.cn/4kCnXC语言自定义类型http://t.csdn.cn/VEicT

一、链表

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的。

这里非连续的意思就是链表的每一部分可以在内存的任意一块区域存在，且这块区域的地址是随机的，所以一般用动态内存来开辟这块空间的地址。而链表的每一部分都称为一个节点，每个节点分为两部分：数据域和指针域

链表分为单链表、双向链表和循环链表。

二、单链表

单链表的结构比较简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多，后面博主会专门出一个关于单链表刷题的文章，大家继续关注。

单链表的每个节点分为两部分，一部分存储数据，一部分存储下一个节点的地址。前一个节点中存储着下一个节点的地址，这也是单链表能连起来的原因。

三、实现单链表

这部分先介绍单链表的基本结构，再介绍单链表的增删查改等基本接口。

1.定义节点

typedef int SLTDataType;
typedef struct SListNode
{
    SLTDataType Data;
    struct SListNode* next;
}SLTNode;

将单链表中的数据类型重定义为 SLDataType 类型，并定义一个单链表节点的结构体，其中节点的一部分是当前节点的数据，另一部分则是指向下一节点的指针。

2.由数据生成节点

SLTNode* BuySListNode(SLTDataType x)
{
    SLTNode* nownode=(SLTNode*)malloc(sizeof(SLTNode));
    if (nownode == NULL)
    {
        perror("malloc fail");
        exit(-1);
    }
    else 
    {
        nownode->Data = x;
        nownode->next = NULL;
        return nownode;
    }
}

首先，每次生成节点都要开辟一个节点的空间，开辟成功后，将它的数据域赋值为 x ，指针域赋值为NULL，并返回开辟的空间强转后的首地址。

3.连接并打印链表

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

将链表的头指针赋值给一个节点类型的指针，然后使用这个节点指针对单链表进行遍历。

4.单链表的基本接口

头插

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{
    assert(pphead);
    SLTNode*nownode = BuySListNode(x);
    nownode->next = *pphead;
    *pphead = nownode;
}

单链表的头插只需要让链表的头指针的指向要插入的节点，再让这个节点的指针域指向原来头节点的地址。需要注意的是要改变头指针的指向，需要将头指针的地址作为函数参数传过去，并用一个二级指针接收，解引用时即可改变头指针的指向。

方法是先用一个指针将生成的节点地址存起来，然后将它的指针域改为原来的头节点，最后让头指针指向新生成的节点。

头删

void SLTPopFront(SLTNode** pphead)
{
    assert(*pphead);
    if ((*pphead)->next==NULL)
    {
        *pphead = NULL;
    }
    else
    {
        SLTNode* oldnode = *pphead;
        *pphead = (*pphead)->next;
        free(oldnode);
        oldnode=NULL;
    }
}

单链表的头删要分为一个节点和多个节点的情况。

当发现头指针指向的头节点的指针域为空时，说明这个单链表只有一个节点，那么只需要将这个节点指针置空即可。

否则，说明这个单链表至少有两个节点，则要用另一种方法：因为第一个节点中存储着第二个节点的地址，所以要先将第一个节点的指针域存起来，然后，将这个地址赋值给头指针，最后将头节点开辟的空间释放。

尾插

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{
    SLTNode* nownode = BuySListNode(x);
    if (*pphead == NULL)
    {
        *pphead = nownode;
    }
    else
    {
        SLTNode* nod = *pphead;
        while (nod->next != NULL)
        {
            nod = nod->next;
        }
        nod->next = nownode;
    }
}

单链表的尾插要看单链表中是否已有节点。

如果单链表中没有节点，就将头指针指向新创建的节点。如果单链表中已有节点，就得先找到最后一个节点的位置，再改变最后一个节点的指针域指向新创建的节点。

尾删

void SLTPopBack(SLTNode** pphead)
{
    assert(*pphead);
    if ((*pphead)->next == NULL)
    {
        free(*pphead);
        *pphead = NULL;
    }
    else
    {
        /*SLTNode* nod = *pphead;*/
        /*while (nod->next->next != NULL)
        {
            nod = nod->next;
        }
        free(nod->next);
        nod->next = NULL;*/
        SLTNode* tail= *pphead;
        SLTNode* tailprev = NULL;
        while (tail->next != NULL)
        {
            tailprev = tail;
            tail = tail->next;
        }
        free(tail);
        tail = NULL;
        tailprev->next = NULL;
    }
}

单链表的尾删也分为两种：一个节点和多个节点。

单链表只有一个节点的时候，直接将它的这个节点空间释放。当有多个节点的时候，首先要找到最后与一个节点的位置，将最后一个节点释放掉，并要让让倒数第二个节点的指针域置空。因为当只有一个节点的时候要改变头节点的指向，所以函数传参也要传头指针的地址。

由数据Data找节点

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{
    SLTNode* cur = phead;
    while (cur != NULL)
    {
        if (cur->Data == x)
            return cur;
        else
        {
            cur = cur->next;
        }
    }
        return NULL;
}

在pos之前插入节点

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
    if (pos== *pphead)//头插
    {
        SLTPushFront(pphead, x);
    }
    else
    {
        SLTNode* cur = *pphead;
        while (cur->next != pos)
        {
            cur = cur->next;
        }
        SLTNode* prewnode = NULL;
        prewnode = BuySListNode(x);
        prewnode->next = pos;
        cur->next = prewnode;
    }
}

在pos之后插入节点

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{
    assert(pos);
    SLTNode* nextnode = pos->next;
    pos->next = BuySListNode(x);
    pos->next->next = nextnode;
}

删除pos节点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{
    if (pos == *pphead)
    {
        *pphead = (*pphead)->next;
    }
    else
    {
        SLTNode* cur = *pphead;
        while (cur->next != pos)
        {
            cur = cur->next;
        }
        cur->next = pos->next;
        free(pos);
        pos = NULL;
    }
}

删除pos节点，首先得找到pos节点前面的节点（所以要传头指针进行遍历），让它的指针域指向pos的下一个节点，再将pos节点释放。 传头指针地址的原因是有可能要删除的就是第一个节点，要改变头指针指向。

删除pos之后的节点

void SLTEraseAfter(SLTNode* pos)
{
    assert(pos);
    assert(pos->next);//检查尾节点
    SLTNode*node = pos->next;
    pos->next = node->next;
    free(node);
    node = NULL;
}

单链表的实现及基本接口就介绍到这里，下篇文章将更新单链表常见的一些面试、笔试题。