链表-单链表【C语言】

     对于顺序表来说，虽然各个数据之间地址是连续的，查找起来效率高，但是插入数据的话要改变数据的位置，效率比较低。所以用'链表'来弥补顺序表的劣势，如果以后动用的数据插入的 *** 作比较多，就可以使用'链表'这种数据结构来提升效率。

---

单链表：

单链表是一个节点指向下一个节点，只有一个指针且指向下一个节点。

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode，*pSListNode;

        用结构体自定义一个类型，此类型中包含数据和一个结构体指针，把多个结构体类型用指针连接起来，此种数据结构称之为链表。（有且只有一个指针，指向下一个结构体类型称之为单链表）

PS：链表注意链表尾节点要指向NULL。

数据插入：

头插法：

        因为每次插入数据的时候需要申请一个结构体类型的空间，这里每个结构体类型称之为'节点'。

SListNode* BuySListNode(SLTDateType x)
{
    SListNode* pNode = (SListNode*)malloc(sizeof(SListNode));
    assert(pNode);
    pNode->data = x;
    return pNode;
}

PS：因为每次插入数据都要申请一个节点，所以可以把申请节点的 *** 作打包成一个函数。 

        头插法就是把每个节点插入到头节点前面，自己再变为头节点。

void SListPushFront(SListNode** pplist, SLTDateType x)
{
    SListNode* Node = BuySListNode(x);
    SListNode* p = *pplist;
    if (*pplist== NULL) {
        *pplist = Node;
        (*pplist)->next = NULL;
    }
    else {
        Node->next = p;
        *pplist = Node; //插入节点头，插入的节点变为头结点
    }
}

        要注意，这里插入节点有两个情况一个是当链表为空的时候（没有节点），那么要直接要插入的节点就是头节点，直接把节点赋值给头节点。

        然后一个是存在节点的情况，那么直接让节点的Next指针指向原来链表的头节点，自己变为头节点。

PS：要注意函数第一个参数传入的是一个二级指针，此参数传入的是链表的头节点。如果传入的的一级指针，虽然也可以遍历链表，但是相当于传的值，其形参是链表的头指针的临时拷贝，不能修改头节点的指向。

        换言之，如果要修改头节点指向，要使用二级指针。

尾插法：

        尾插法要把节点插入链表的结尾，要注意链表最后的节点指向空。

void SListPushBack(SListNode** pplist, SLTDateType x)
{
    SListNode* Node = BuySListNode(x);
    SListNode* p = *pplist;
    if (*pplist == NULL) {
        *pplist = Node;
        (*pplist)->next = NULL;
    }
    else {
        while (p->next != NULL) {
            p = p->next;
        }
        p->next = Node;
        Node->next = NULL;
    }
}

        还是有两种情况，一是链表为空，那么插入的节点就是头节点。一是存在节点，遍历查询到尾节点，然后再在尾节点上插入节点，最后为节点指向空。

PS：这里其实也发现了尾节点指向空的一层含义，就是为了方便查找尾节点。也要知道单链表是不能随机查找的，只能顺着链表遍历。

 中间位置插入：

SListNode* SListFind(SListNode* plist, SLTDateType x)
{
    assert(plist);

    while (plist!= NULL) {
    
        if (plist->data == x)
            return plist;
        plist = plist->next;

    }
    return NULL;
}//查找数据位置

void SListInsertAfter(SListNode* pos, SLTDateType x)
{
    assert(pos);
    SListNode* Node = BuySListNode(x);
    Node->next = pos->next;
    pos->next = Node;
}//位置后插入数据

        这里代码是查找数据返回节点位置，和在指定节点位置后插入数据。这里要注意知道其节点位置后是只能往后面插入数据的，不能在其前面插入数据。这是插入数据的 *** 作造成的局限性。

        首先这里有个节点要插入链表，

        那么就要让C节点插入AB之间，就要让A节点指向C，然后C节点指向B。 

 ​​​​

         这里只需要知道一个节点的位置，就能插入了。比如这知道了A的位置，那么B就是A->next，那么只需要C先指向B，C->next=A->next；再让A指向C，A->next=C；这样插入数据就完成了。（要注意一定要先让C指向B，不然先让A指向C的话，就不能通过A找到B了，因为A->next已经指向了C，而C还没跟B有关联）

         所以这里也就知道了为什么不能往节点前面插入数据，插入数据需要两个节点，而单链表是往后走的，能知道其下一个的节点，但是不能知道上一个节点。

PS：因为其插入数据要两个节点，所以如果链表为空，那么不适用此插入法。

PS：这里也发现了链表的优势了，插入数据的时候，只需要改变节点的指针，并不需要像顺序表那样移动数据，如果数据结构中数据特别多，那么链表插入数据比顺序表效率很多。 

 数据删除：

 头删：

void SListPopFront(SListNode** pplist)
{
    assert(*pplist);

    if ((*pplist)->next == NULL) {
        free(*pplist);
        *pplist = NULL;
    }
    else {
        SListNode* p = *pplist;
        *pplist = (*pplist)->next;
        free(p);
    }
}

        注意如果链表为空肯定不用删除了，所以要断言一下。

        然后有两种情况一个是只有一个节点的情况，这里只要释放此节点再置为空就行了。一个是多个节点，因为是删除头节点，那么删除头节点后，原来的头节点的下一个节点变为头节点。

尾删： 

void SListPopBack(SListNode** pplist)
{
    assert(*pplist);
    if ((*pplist)->next==NULL) {
        free(*pplist);
        *pplist = NULL;
    }
    else {
        SListNode* Prev = NULL;
        SListNode* tail = *pplist;
        while (tail->next!=NULL) {
            Prev = tail;
            tail = tail->next;
        }
        free(tail);
        Prev->next = NULL;
    }
}//因为删除了最后一个节点，倒数第二个节点指向了一个野指针，所以要指向NULL

        也有两个情况，只有一个节点的时候跟上面一样。多个节点的时候，因为是尾删，所以要查找尾节点，但是因为这里释放最后一个节点后，上一个节点变为尾节点，但是其没指向空，所以要定义一个变量来接收要删除节点的上一个节点，删除尾节点后，让其指向空（NULL）。

尾删的另一种写法:   

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

        此写法巧妙，发现并不需要多定义一个变量来接收尾节点的上一个节点，因为查找到的节点就是尾节点的上一个节点。 

中间位置删除： 

void SListEraseAfter(SListNode* pos)
{
    assert(pos);
    if (pos->next==NULL) {
        return;
    }
    else {
        SListNode* p = pos->next->next;
        free(pos->next);
        pos->next = p;
    }
}

        

        假设删除C节点，那么先让A跟B连接，把C让出来， 

 

         然后再释放C节点。如果只是单纯的释放C节点，相当把C节点后面的所有节点全部删除了。

PS：会发现链表删除数据也只需要改变一下指针的指向，并不需要像顺序表那样把数据整体往前移动，效率比较高。

链表全部释放：

void SListDestory(SListNode* plist)
{
    assert(plist);
    SListNode* p = NULL;

    while (plist != NULL) {
        p = plist;
        plist = plist->next;
        free(p);
    }
}

        要先找到下一个节点，再释放前面一个节点的数据。 不然直接释放节点，下一个节点就找不到了。

---

 写完后记得测试一下：

打印链表：

void SListPrint(SListNode* plist)
{
    while (plist!=NULL) {
        printf("%d->",plist->data);
        plist = plist->next;
    }
    printf("NULL\n");
}

        写一个打印链表数据的函数，方便观察链表。

 

Perfect!