定義

在學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)的時(shí)候，最開始接觸到的一種數(shù)據(jù)結(jié)構(gòu)就是線性表，對(duì)于線性表的定義是： 零個(gè)或多個(gè)數(shù)據(jù)元素的有限序列 ，那對(duì)于線性表來講，又分為順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，對(duì)于順序存儲(chǔ)結(jié)構(gòu)來說，也就是數(shù)組，數(shù)組的每個(gè)元素之間的地址是連續(xù)的；對(duì)于鏈?zhǔn)酱鎯?chǔ)來說，也就是平常所說的鏈表，鏈表每個(gè)元素之間的地址并不是連續(xù)的，而是分散的，他們之間的聯(lián)系通過結(jié)點(diǎn)的 next 指針來建立。本文盡可能地將鏈表的知識(shí)詳細(xì)地?cái)⑹觯婕暗逆湵眍愋桶ǎ簡捂湵恚p鏈表，循環(huán)鏈表，每個(gè)鏈表的操作涉及到創(chuàng)建鏈表，刪除鏈表，插入鏈表結(jié)點(diǎn)，刪除鏈表結(jié)點(diǎn)。

單鏈表

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

image-20210725104003036

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

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

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

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

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

image-20210725103816693

單鏈表的創(chuàng)建

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

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

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

image-20210725110252272

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

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

    /* 如果是首次插入結(jié)點(diǎn)，那么應(yīng)該創(chuàng)建頭結(jié)點(diǎn) */
    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)建鏈表有一個(gè)特點(diǎn)就是，它所形成的鏈表的順序是反的，也就是說后插入的鏈表結(jié)點(diǎn)反而在前面，如果從第一個(gè)結(jié)點(diǎn)開始遍歷的話，那遍歷得到的元素的順序是倒過來的；那怎么樣才能使得鏈表的插入的順序和遍歷的順序一致呢？這個(gè)時(shí)候就需要引入尾插法創(chuàng)建單鏈表了。

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

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

image-20210725111844263

代碼如下所示：

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

    /* 先創(chuàng)建頭結(jié)點(diǎn) */
    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;
}

按照順序插入一個(gè)結(jié)點(diǎn)

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

image-20210725203214469

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

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

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

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

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

刪除鏈表結(jié)點(diǎn)

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

image-20210725204142199

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

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

刪除鏈表

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

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é)點(diǎn)

最后，就是打印當(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é)點(diǎn)的單鏈表

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

image-20210725104153366

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

單鏈表的創(chuàng)建

上述中，敘述了關(guān)于帶頭結(jié)點(diǎn)的單鏈表的創(chuàng)建，本小節(jié)敘述的是不帶頭結(jié)點(diǎn)的單鏈表的創(chuàng)建，不帶頭結(jié)點(diǎn)的單鏈表創(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é)點(diǎn)的單鏈表，相對(duì)于帶頭結(jié)點(diǎn)的單鏈表，要簡單很多，最突出的一點(diǎn)就是不用再創(chuàng)建頭結(jié)點(diǎn)了。

尾插法創(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é)點(diǎn)，要稍微復(fù)雜一點(diǎn)，就是涉及到如果最開始是空鏈表，那么插入第一個(gè)結(jié)點(diǎn)的時(shí)候，需要更改頭指針的值，如果不是第一次插入，那么也就不需要改變了；上述代碼中，引入了一個(gè)臨時(shí)結(jié)點(diǎn)用于遍歷，回顧上述中的一個(gè)點(diǎn)，就是說在遍歷的時(shí)候，可以通過不引入臨時(shí)結(jié)點(diǎn)的方式來簡化代碼，因?yàn)楹瘮?shù)調(diào)用傳入形參的是值傳遞，改進(jìn)的代碼如下所示：

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

按照順序插入一個(gè)結(jié)點(diǎn)

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é)點(diǎn)就是第一個(gè)結(jié)點(diǎn) */
    if (Pre == NULL)
    {
        Node->next = *head;
        *head = Node; 
    }
    else
    {
        Node->next = Curr;
        Pre->next = Node;
    }
}

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

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é)點(diǎn)是按照從小到大 */
    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é)點(diǎn)

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

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ǎng)h除的結(jié)點(diǎn)就是第一個(gè)結(jié)點(diǎn) */
    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é)點(diǎn)的鏈表基本一致，差別就在于說是帶頭結(jié)點(diǎn)的不刪除頭結(jié)點(diǎn)，下面是刪除鏈表的代碼：

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)于單鏈表的一個(gè)簡單的敘述，當(dāng)然，鏈表的知識(shí)不僅僅是當(dāng)鏈表，還有雙向鏈表，循環(huán)鏈表，雙向循環(huán)鏈表等等，剩余的 內(nèi)容在后期的博客中將進(jìn)行敘述，這次的分享就到這里啦。