定義

在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時候，最開始接觸到的一種數(shù)據(jù)結(jié)構(gòu)就是線性表，對于線性表的定義是： 零個或多個數(shù)據(jù)元素的有限序列 ，那對于線性表來講，又分為順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，對于順序存儲結(jié)構(gòu)來說，也就是數(shù)組，數(shù)組的每個元素之間的地址是連續(xù)的；對于鏈?zhǔn)酱鎯碚f，也就是平常所說的鏈表，鏈表每個元素之間的地址并不是連續(xù)的，而是分散的，他們之間的聯(lián)系通過結(jié)點的 next 指針來建立。本文盡可能地將鏈表的知識詳細地敘述，所涉及的鏈表類型包括：單鏈表，雙鏈表，循環(huán)鏈表，每個鏈表的操作涉及到創(chuàng)建鏈表，刪除鏈表，插入鏈表結(jié)點，刪除鏈表結(jié)點。

單鏈表

何為單鏈表呢，看定義往往讓人一時摸不到頭腦，直接通過圖的形式來展示：

image-20210725104003036

可以看到結(jié)點與結(jié)點之間都是通過一個指針來建立聯(lián)系的，所以對于鏈表結(jié)點的定義往往遵循如下的形式：

typedef struct Node
{
    int data;
    struct Node *next;
}ListNode,*LinkList;

而對于單鏈表來說，其還可以進行細分，可以分為帶頭結(jié)點的單鏈表和不帶頭結(jié)點的單鏈表，具體是什么意思呢？我們下面分別對這兩種形式進行敘述。

帶頭結(jié)點的單鏈表

說到頭結(jié)點，就必須要與另外一個概念進行對比闡述，就是頭指針，頭指針并不是一個結(jié)點，它的作用是指向鏈表的第一個結(jié)點，也就是說我們是通過頭指針來找到鏈表的；那頭結(jié)點的意思是什么呢？頭結(jié)點是一個結(jié)點，但是這個結(jié)點的數(shù)據(jù)域是沒有值的，它的存在是方便我們對于鏈表的操作，比方說如果要往鏈表中插入一個結(jié)點，而這個結(jié)點插入的位置就是第一個結(jié)點（如果有頭結(jié)點，那么頭結(jié)點就是第0個結(jié)點），如果沒有頭結(jié)點的存在，那么就需要更改頭指針的值，而如果有頭結(jié)點的存在，頭指針的值是一直不用變的。下圖是帶有頭結(jié)點的鏈表的示意圖：

image-20210725103816693

單鏈表的創(chuàng)建

在知道了單鏈表的基本形式之后，那自然也就需要創(chuàng)建一個單鏈表了，在創(chuàng)建一個單鏈表時，主要分為兩種創(chuàng)建方法，分別是頭插法和尾插法，下面分別就這兩種方法進行敘述。

頭插法創(chuàng)建單鏈表

其創(chuàng)建鏈表所遵循的一個基本步驟如下所示：

image-20210725110252272

從上圖可以看出來頭插法創(chuàng)建單鏈表的一個基本過程，同時可以看到，因為有頭結(jié)點的存在，在每次新增結(jié)點的時候，頭指針的值也是不變的，依據(jù)上述原理，寫出創(chuàng)建單鏈表的代碼，如下所示：

void AddNodeHead(LinkList *head, int value)
{
    ListNode* Node = (ListNode*)malloc(sizeof(ListNode));
    if (Node == NULL)
            return;

    /* 如果是首次插入結(jié)點，那么應(yīng)該創(chuàng)建頭結(jié)點 */
    if (*head == NULL)
    {
        *head = (ListNode*)malloc(sizeof(ListNode));
        if (*head == NULL)
                return;     
        (*head)->next = NULL;
    }
    Node->data = value;
    Node->next = NULL;
    (*head)->next = Node;
}

頭插法創(chuàng)建鏈表有一個特點就是，它所形成的鏈表的順序是反的，也就是說后插入的鏈表結(jié)點反而在前面，如果從第一個結(jié)點開始遍歷的話，那遍歷得到的元素的順序是倒過來的；那怎么樣才能使得鏈表的插入的順序和遍歷的順序一致呢？這個時候就需要引入尾插法創(chuàng)建單鏈表了。

尾插法創(chuàng)建單鏈表

尾插法也就正如其名字所表征的含義一樣，它的意思是從尾部逐漸將結(jié)點插入，其所遵循的一個基本過程如下圖所示：

image-20210725111844263

代碼如下所示：

void AddNodeTail(LinkList *head,int value)
{
    LinkList Node = (LinkList)malloc(sizeof(ListNode));
    if (Node == NULL)
            return;
    /* 創(chuàng)建一個臨時結(jié)點 */
    LinkList TempNode = NULL;

    /* 先創(chuàng)建頭結(jié)點 */
    if (*head == NULL)
    {
        *head = (LinkList)malloc(sizeof(ListNode));
        (*head)->next = NULL;
    }

    TempNode = (*head);
    Node->data = value;
    Node->next = NULL;
    while (TempNode->next)
    {
        TempNode = TempNode->next;
    }
    TempNode->next = Node;
}

按照順序插入一個結(jié)點

如果按照上述兩種方式構(gòu)建的鏈表是每個元素都是從前往后依次遞減的，現(xiàn)在要將一個數(shù)按照順序插入到鏈表中，那么其所遵循的基本原理示意圖如下所示：

image-20210725203214469

根據(jù)上述的結(jié)點插入示意圖,寫出如下所示的代碼：

void IncertNode(LinkList head, int value)
{
    if (head == NULL)
        return;

    LinkList temp = head;
    LinkList Node = (LinkList)malloc(ListNode);
    if (Node == NULL)
        return;

    while (temp->next && value > temp->next->data)
    {
        temp = temp->next;
    }
    Node->data = value;
    Node->next = temp->next;
    temp-> next = Node;
}

通過上述的代碼我們可以看到，我們在進行遍歷找到要插入的那個結(jié)點的時候，引入了一個臨時變量來實現(xiàn)這個功能；實際上可以將這個地方進行簡化，通過函數(shù)調(diào)用傳遞給形參的是值拷貝，那么對于傳進去的 head 變量來說，其變量的地址是不會改變的。

void IncertNode(LinkList head, int value)
{
    if (head == NULL)
        return;

    LinkList Node = (LinkList)malloc(ListNode);  

    while (head->next && value > head->next->data)
    {
        head = head->next;
    }
    Node->data = value;
    Node->next = head->next;
    head->next = Node;
}

可以看到，代碼比最初那個版本要少了一個臨時變量，但是其功能是沒有變化的。

刪除鏈表結(jié)點

在敘述了插入結(jié)點之后，那如何進行刪除結(jié)點操作呢？刪除一個結(jié)點的操作所遵循的基本步驟如下如圖所示：

image-20210725204142199

根據(jù)上述示意圖的原理，刪除結(jié)點的代碼如下所示：

void DeleteNode(LinkList head, int target)
{
    LinkList temp = NULL;

    if (head == NULL || head->next == NULL)
            return;

    while (head->next && head->next->data != target)
    {
        head = head->next;
    }

    temp = head->next;
    head-next = temp->next;
    free(temp);
}

刪除鏈表

刪除鏈表的意思也就是將鏈表的每個結(jié)點都釋放掉，變成一個空鏈表，而對于帶頭結(jié)點的鏈表來說，空鏈表是包含頭結(jié)點在內(nèi)的，刪除鏈表就需要將其他結(jié)點釋放掉，具體的代碼如下所示：

void DeleteList(LinkList* head)
{
    if (*head == NULL || (*head)->next == NULL)
        return;

    LinkList tempNodeP = (*head)->next;
    LinkList tempNodeQ = NULL;

    while (tempNodeP)
    {
        tempNodeQ = tempNodeP->next;
        free(tempNodeP);
        tempNodeP = tempNodeQ;
    }
    (*head)->next = NULL;
}

打印鏈表結(jié)點

最后，就是打印當(dāng)前鏈表的元素了，原理也比較簡單，直接給出源代碼：

void PrintLinkList(LinkList head)
{
    if (head->next == NULL || head == NULL)
    {
        printf("No Element\\r\\n");
        return;
    }
    while (head->next)
    {
        printf("%d ",head->next->data);
        head = head->next;
    }
    printf("\\r\\n");
}

不帶頭結(jié)點的單鏈表

知道了帶頭結(jié)點的單鏈表，那么不帶頭結(jié)點的單鏈表也就顯而易見了，示意圖如下所示：

image-20210725104153366

通過上圖可以知道，如果插入的結(jié)點或者是刪除的結(jié)點是第一個結(jié)點的話，那么就需要改變頭指針的值。

單鏈表的創(chuàng)建

上述中，敘述了關(guān)于帶頭結(jié)點的單鏈表的創(chuàng)建，本小節(jié)敘述的是不帶頭結(jié)點的單鏈表的創(chuàng)建，不帶頭結(jié)點的單鏈表創(chuàng)建的原理和上述一致，就不在這里給出具體的步驟圖了，直接給出操作的代碼。

頭插法創(chuàng)建單鏈表

void AddNodeHeadWithNh(LinkList *head, int value)
{
    LinkList NodeTemp = (LinkList)malloc(sizeof(ListNode)); 
    if (NodeTemp == NULL)
        return;

    NodeTemp->data = value;
    NodeTemp->next = *head;
    *head = NodeTemp;
}

可以看到，如果不帶頭結(jié)點的單鏈表，相對于帶頭結(jié)點的單鏈表，要簡單很多，最突出的一點就是不用再創(chuàng)建頭結(jié)點了。

尾插法創(chuàng)建單鏈表

void AddNodeTailWNh(LinkList *head, int value)
{
    LinkList temp = NULL;

    LinkList Node = (LinkList)malloc(sizeof(ListNode));
    if (Node == NULL)
        return;

    Node->data = value;
    Node->next = NULL;

    if (*head == NULL)
        *head = Node;
    else
    {
        temp = *head;
        while (temp->next)
        {
            temp = temp->next;  
        }
        temp->next = Node;  
    }
}

尾插法創(chuàng)建單鏈表不帶頭節(jié)點，要稍微復(fù)雜一點，就是涉及到如果最開始是空鏈表，那么插入第一個結(jié)點的時候，需要更改頭指針的值，如果不是第一次插入，那么也就不需要改變了；上述代碼中，引入了一個臨時結(jié)點用于遍歷，回顧上述中的一個點，就是說在遍歷的時候，可以通過不引入臨時結(jié)點的方式來簡化代碼，因為函數(shù)調(diào)用傳入形參的是值傳遞，改進的代碼如下所示：

void AddNodeTailWNH(LinkList *head, int value)
{
    LinkList Node = (LinkList)malloc(sizeof(ListNode));
    if (Node == NULL)
            return;

    Node->data = value;
    Node->next = NULL;

    /* 如果是第一次插入 */
    if (*head == NULL)
        (*head) = Node;
    else
    {
        while ((*head)->next)
        {
            head = &(*head)->next;
        }
        (*head)->next = Node;
    }
}

按照順序插入一個結(jié)點

void IncertNodeWNH(LinkList *head, int value)
{
    LinkList Node = (LinkList)malloc(sizeof(ListNode));
    if (Node == NULL)
        return;
     Node->data = value;

    if (*head == NULL)
    {
        *head = Node;
        Node->next = NULL;
    }

    LinkList Curr = *head;
    LinkList Pre = NULL;
    /* 假設(shè)鏈表是從小到大排列的 */
    while (Curr && value > Curr->data)
    {
        Pre = Curr;
        Curr = Curr->next;
    }
    /* 如果要插入的結(jié)點就是第一個結(jié)點 */
    if (Pre == NULL)
    {
        Node->next = *head;
        *head = Node; 
    }
    else
    {
        Node->next = Curr;
        Pre->next = Node;
    }
}

在上述代碼中，如果鏈表一開始就是為空的，那么就將頭指針指向第一個結(jié)點就好了，如果鏈表有元素，但是要插入的元素位于第一個元素之前，那么也需要將頭指針進行更改，這里通過引入一個當(dāng)前結(jié)點和前一個結(jié)點的方式來完成這個功能。同樣的，依據(jù)前面對于程序的改進思路，也可以減少定義兩個結(jié)點的方式來完成，只不過就是說需要增加一個標(biāo)志位，來記錄是插入的位置是不是第一個結(jié)點，代碼如下所示：

void IncertNode(LinkList *head, int value)
{
    LinkList Node = (LinkList)malloc(sizeof(ListNode));
    if (Node == NULL)
        return;

    LinkList Temp = NULL; 
    Node->data = value;

    int count = 0; 

    /* 假設(shè)鏈表的結(jié)點是按照從小到大 */
    while ((*head)->next && value > (*head)->next->data)
    {
        head = &(*head)->next;
        count++;
    }
    if (!count)
    {
        Node->next = *head;
        *head = Node;
    }
    else
    {
        Node->next = (*head)->next;
        (*head)->next = Node;   
    } 
}

刪除鏈表結(jié)點

刪除鏈表結(jié)點和插入鏈表結(jié)點兩種對鏈表的操作是差不多的，在刪除鏈表結(jié)點的時候，我們采用的方式同樣是定義一個當(dāng)前結(jié)點，一個上一個結(jié)點，代碼如下所示：

void DeleteNode(LinkList *head, int target)
{
    LinkList Pre = NULL;
    LinkList Cur = *head;

    if (*head == NULL)
        return;

    while (Cur != NULL && Cur->data != target)
    {
        Pre = Cur;
        Cur = Cur->next;
    }

    /* 如果要刪除的結(jié)點就是第一個結(jié)點 */
    if (Pre == NULL)
    {
        *head = Cur->next;
    }
    else
    {
        Pre->next = Cur->next;
    }   

    free(Cur);
}

跟上面一樣的思路，我們同樣可以依據(jù)上面的想法來簡化我們的代碼，簡化之后的代碼如下所示：

void DeleteNode(LinkList *head, int target)
{
    LinkList Temp = NULL;

    for (; *head != NULL ; head = &(*head)->next)
    {
        if ((*head)->data == target)
        {
            Temp = (*head);
            (*head) = (*head)->next;

            free(Temp);
            break; 
        }   
    } 
}

刪除鏈表

在刪除鏈表的操作上和帶頭結(jié)點的鏈表基本一致，差別就在于說是帶頭結(jié)點的不刪除頭結(jié)點，下面是刪除鏈表的代碼：

void ClearLinkList(LinkList *head)
{
    if (*head == NULL)
        return;

    LinkList tempNode  = NULL;
    LinkList tempNodeQ = *head; 

    while (tempNodeQ)
    {
        tempNode = tempNodeQ->next;
        free(tempNodeQ);
        tempNodeQ = tempNode;
    }
    *head = NULL;   
}

打印鏈表

打印鏈表的操作也較為簡單，具體代碼如下所示：

void PrintLinkListWithNh(LinkList head)
{
    if (head == NULL)
        return;

    while (head)
    {
        printf("%d ",head->data);
        head = head->next;
    }
    printf("\\r\\n");
    return;
}

小結(jié)

上述就是關(guān)于單鏈表的一個簡單的敘述，當(dāng)然，鏈表的知識不僅僅是當(dāng)鏈表，還有雙向鏈表，循環(huán)鏈表，雙向循環(huán)鏈表等等，剩余的 內(nèi)容在后期的博客中將進行敘述，這次的分享就到這里啦。