在 C 語言中使用鏈結串列的優勢

更新於 2024/10/24發佈於 2024/10/24閱讀時間約 8 分鐘

在 C 語言中，陣列的大小是固定的，並且使用連續的記憶體空間。如果要在陣列中間插入新元素，可能會變得麻煩。例如，當我要在 1, 2, 3 後插入 4 時，若後面的記憶體區塊已被佔用，就無法直接插入。此時，必須找到足夠大的空間來重新複製資料。這樣的過程不僅耗時，也不靈活。

這時，鏈結串列就派上用場了！

插入4，要先找到其他的儲存格。圖片來源：CS50。

鏈結串列是什麼？

鏈結串列是一種更靈活的資料結構，它不需要連續的記憶體空間，。鏈結串列由一連串的節點組成，每個節點包含資料和一個指向下一個節點的指標。當需要插入新元素時，只需更新指標來連接新節點，這樣就避免了重新分配大區塊記憶體的麻煩。

程式碼的顯示

指到下一個節點

之前的文章提過，C 語言可以自己建立資料型態：

演算法 | Big O 複雜度| Pseudocode 偽代碼

typedef struct
{
    string name;
    string number;
}person;

而鏈結串列會有一個 node 節點，而他會指向下個地址

#include <stdio.h>

typedef struct node
{
    int number;
    struct node *next; //指向下個 node
} node;

node *life; //建立一個指標變數life，他指向的資料型別是node

但是隨便指向沒有資料的地方，會出現電腦隨便丟垃圾訊息。所以我們要分配記憶體給他，

node *n = malloc(sizeof(node));// n是個指標變數，指向的值的資料型別是node
(*n).number = 1: // *指向下個node，"."的意思是在資料型別為number的地方

(*n).number = 1 可以簡化成 n->number =1

圖像化鏈結串列

命令列參數中的數字插入一個鏈結串列 (linked list) ，插到最前面

圖片來源：CS50

接下來，如何把 n 連起來換給 list，把 n 賦值給 list。

接下來如何把１和２串在一起？不是直接 list = n !

數字插入一個鏈結串列（linked list）中

新的節點 (數字) 插入到兩個已有節點之間的程式碼如下，往下還有圖片說明：

#include <cs50.h>
#include <stdio.h>
#include <stdlib.h>

// 定義一個節點的結構，包含數字和指向下一個節點的指標
typedef struct node
{
    int number;         // 節點中的數字
    struct node *next;  // 指向下一個節點的指標
}
node;

int main(int argc, char *argv[])
{
    // 初始化鏈結串列為空
    node *list = NULL;

    // 逐一處理每個命令列參數
    for (int i = 1; i < argc; i++)
    {
        // 將參數轉換成整數
        int number = atoi(argv[i]);

        // 為該數字分配一個新的節點
        node *n = malloc(sizeof(node));
        if (n == NULL)  // 檢查是否成功分配記憶體
        {
            return 1;   // 若失敗，返回錯誤代碼 1
        }
        n->number = number;  // 將數字儲存在節點中
        n->next = NULL;      // 新節點的下一個指標先設為空

        // 如果鏈結串列為空，將這個節點作為鏈結串列的第一個節點
        if (list == NULL)
        {
            list = n;
        }

        // 如果該數字應該放在鏈結串列的開頭
        else if (n->number < list->number)
        {
            n->next = list;  // 將新節點的指標指向原本的第一個節點
            list = n;        // 新節點成為鏈結串列的第一個節點
        }

        // 如果該數字應該放在串列的中間或末端
        else
        {
            // 遍歷鏈結串列，尋找適當的位置插入
            for (node *ptr = list; ptr != NULL; ptr = ptr->next)
            {
                // 如果已經到了鏈結串列的末端
                if (ptr->next == NULL)
                {
                    ptr->next = n;  // 將新節點加在末端
                    break;
                }

                // 如果該數字應該插入在中間某個位置
                if (n->number < ptr->next->number)
                {
                    n->next = ptr->next;  // 新節點指向後續節點
                    ptr->next = n;        // 前一個節點指向新節點
                    break;
                }
            }
        }
    }

    // 印出鏈結串列中的數字
    for (node *ptr = list; ptr != NULL; ptr = ptr->next)
    {
        printf("%i\n", ptr->number);
    }

    // 釋放記憶體
    node *ptr = list;
    while (ptr != NULL)
    {
        node *next = ptr->next;  // 保存下一個節點的位置
        free(ptr);               // 釋放當前節點
        ptr = next;              // 移動到下一個節點
    }
}

從中間插入新的數值

陣列與鏈結串列的 Big O 複雜度

從效能角度來看，陣列和鏈結串列在不同操作上的表現各有所長：

插入或刪除元素：對於陣列來說，插入或刪除元素可能需要移動大部分的元素，因此是 O(n) 的時間複雜度；而鏈結串列只需要調整指標，因此是 O(1)。
找特定位置的元素：陣列可以直接通過索引快速找到任意位置的元素，這是 O(1) 的操作；而鏈結串列則需要遍歷所有節點來找到目標位置，要從第一個開始找陣列，因此是 O(n)。