數據結構作為嵌入式工程師必修課程之一，今天，我們就來講一講數據結構中最簡單的鏈表，包含鏈表的初始化、插入和遍歷操作。 鏈表在項目開發中使用的場景很多，跟數組相比，它的優點就是，容量沒有限制，插入刪除效率比較高。

? 數組在內存中是一塊連續的存儲空間，而且隨著存儲數據的不斷增多，想要找到這么一大塊的連續內存也比較困難。

? 但是鏈表就能解決這個問題，它由節點組成，每個節點占用的內存不會很大，而且各個節點之間也不需要連續，為了方便訪問，只要把下一個節點的地址記在上一個節點的指針域中就行，這樣，所有節點之間就像有跟線一樣串聯起來。

? 跟數組相比，它的隨機插入效率也要高很多。比如數組有100個元素，想要在第一個位置插入一個元素，那么每個元素都得向后移動一個位置，把第一個位置騰出來，數據量越大，移動的效率越低。 鏈表的插入完全不一樣，不管在什么位置插入，只要適當的修改幾個指針就能解決問題。

? 鏈表可以有頭節點，也可以沒有頭節點，為了方便編程，我們一般都會加上頭節點。

? 有了頭節點，就有了頭指針，用來保存頭節點的地址。

? 既然鏈表是由很多個節點組成，第一步就得用代碼來表示節點。節點分為數據域和指針域，數據域可以是任意類型，我們就用int吧，指針域保存下一個節點的地址，把這兩個成員放在結構體中，后面就用Node來表示節點。

typedef struct Node
{
    int data;
    struct Node *next;
}Node;

? 所謂鏈表的初始化，就是形成一個空的鏈表，空的鏈表只有一個頭節點，數據域沒有數據，指針域為空。


? 定義頭指針head，初始化的時候，因為要修改head的數值，所以必須傳它的地址。

Node *head = NULL;


int ret = InitLink(&head);
if (SUCCESS == ret)
{   
    printf("鏈表初始化成功
");
}   
else
{   
    printf("鏈表初始化失敗
");
}

? 先申請一個節點，把節點的地址保存在head中，節點的指針域為NULL，初始化的工作就完成了。

int InitLink(Node **h)
{
    if (NULL == h)
        return FAILURE;


    (*h) = (Node *)malloc(sizeof(Node));
    if ((*h) == NULL)
    {   
        return FAILURE;
    }   


    (*h)->next = NULL;


    return SUCCESS;
}

? 鏈表的插入操作是一個經典的筆試題。

? 過程就是：定義指針指向頭節點，把指針移動到要插入位置的前一個位置，同時判斷插入的位置是否合法，申請新的節點，填好指針域和數據域，最后再修改前一個節點的指針域，形成一個新的鏈表。

? 繼續寫代碼，主函數中通過for循環，往鏈表中插入10個節點，插入的數據隨機生成，位置就指定為i + 1，意思就是第一次往第一個位置插入，第二次往第二個位置插入，這種插入方法我們把它稱作尾插法。

srand(time(NULL));
int num;
for (int i = 0; i < 10; i++)
{   
    num = rand() % 20; 


    ret = InsertLink(head, i + 1, num);
    if (SUCCESS == ret)
    {   
        printf("插入 %d 成功
", num);
    }   
    else
    {   
        printf("插入 %d 失敗
", num);
    }   
}

? 來實現插入的功能。

? 先定義一個指針，指向頭節點，根據插入的位置移動移動指針。接下來就是判斷插入的位置是否合法，有兩種情況要排除，一種是插入的位置小于等于0，一種是插入的位置太大，比如鏈表一共5個節點，在第七個位置插入肯定不行。然后在堆空間申請一個新的節點，填寫數據域和指針域，最后把q指向的節點指針域改成新申請的節點，插入的操作就完成了。

int InsertLink(Node *h, int p, int num)
{
    if (NULL == h)
        return FAILURE;


    Node *q = h;
    int k = 1;


    while (k < p && q)
    {   
        q = q->next;
        k++;
    }   


    if (!q || k > p)
    {
        return FAILURE;
    }


    Node *n = (Node *)malloc(sizeof(Node) * 1);
    if (NULL == n)
    {
        return FAILURE;
    }


    n->data = num;
    n->next = q->next;
    q->next = n;


    return SUCCESS;
}

? 運行看下現象，10個節點都顯示插入成功。

root@Turbo:test# ./main
鏈表初始化成功
插入 1 成功
插入 3 成功
插入 4 成功
插入 8 成功
插入 18 成功
插入 0 成功
插入 16 成功
插入 5 成功
插入 6 成功
插入 1 成功

? 但是到底有沒有形成鏈表，還得遍歷看下。

? 遍歷操作只需要借助指針，每經過一個節點，打印該節點的數據就行。定義指針p，指向第一個節點，注意，第一個節點不是頭節點，而是第一個保存數據的節點。只要指針p不為空，就說明鏈表還沒有到最后，打印該節點數據，然后讓p繼續往下。

void TraverseLink(Node *h) 
{
    if (NULL == h)
        return;


    Node *p = h->next;
    while (p) 
    {   
        printf("%d ", p->data);
        p = p->next;
    }   
    printf("
");
}

? 運行看下結果，也沒有問題。

? 這就是鏈表的幾個基本操作，尤其是插入操作，基本是筆試必考，如果你有就業的需求，不妨把這段代碼背下來。
? ?

　　審核編輯：湯梓紅

?