在 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)。
