定義

在學習數據結構的時候，最開始接觸到的一種數據結構就是線性表，對于線性表的定義是： 零個或多個數據元素的有限序列 ，那對于線性表來講，又分為順序存儲結構和鏈式存儲結構，對于順序存儲結構來說，也就是數組，數組的每個元素之間的地址是連續的；對于鏈式存儲來說，也就是平常所說的鏈表，鏈表每個元素之間的地址并不是連續的，而是分散的，他們之間的聯系通過結點的 next 指針來建立。本文盡可能地將鏈表的知識詳細地敘述，所涉及的鏈表類型包括：單鏈表，雙鏈表，循環鏈表，每個鏈表的操作涉及到創建鏈表，刪除鏈表，插入鏈表結點，刪除鏈表結點。

單鏈表

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

image-20210725104003036

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

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

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

帶頭結點的單鏈表

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

image-20210725103816693

單鏈表的創建

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

頭插法創建單鏈表

其創建鏈表所遵循的一個基本步驟如下所示：

image-20210725110252272

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

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

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

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

尾插法創建單鏈表

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

image-20210725111844263

代碼如下所示：

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

    /* 先創建頭結點 */
    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;
}

按照順序插入一個結點

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

image-20210725203214469

根據上述的結點插入示意圖,寫出如下所示的代碼：

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

通過上述的代碼我們可以看到，我們在進行遍歷找到要插入的那個結點的時候，引入了一個臨時變量來實現這個功能；實際上可以將這個地方進行簡化，通過函數調用傳遞給形參的是值拷貝，那么對于傳進去的 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;
}

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

刪除鏈表結點

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

image-20210725204142199

根據上述示意圖的原理，刪除結點的代碼如下所示：

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

刪除鏈表

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

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

打印鏈表結點

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

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

不帶頭結點的單鏈表

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

image-20210725104153366

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

單鏈表的創建

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

頭插法創建單鏈表

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

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

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

尾插法創建單鏈表

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

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

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

按照順序插入一個結點

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

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

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; 

    /* 假設鏈表的結點是按照從小到大 */
    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;   
    } 
}

刪除鏈表結點

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

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

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

    free(Cur);
}

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

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

刪除鏈表

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

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

小結

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