C語言 Linked List 鏈結串列：實現 C# List 的功能

Leo

2022 年 5 月 4 日

C語言 Linked List 鏈結串列
如何實現 C# 中 List 這個好用的功能！？

　　C# 有很多好用的功能，其中 List 絕對是榜上有名。有時候需要放大量資料到記憶體當中，然而若不知道該放多少資料，而是隨著使用者來動態決定大小的話。

　　既不可能一開始就決定陣列大小，若宣告太大則浪費空間；若宣告太小則放不下！若使用 malloc 動態宣告，也是需要先在一開始就先知道要用多大的大小才能宣告。

　　如果今天我希望有用到才增加，沒用到就刪除，能最有效率的使用記憶體空間，則 List 絕對是箇中翹楚！

　　然而 C/C++ 中沒有像 C# 這麼方便的語法糖，直接 var list = new List(); 就能使用，尤其在 MCU 領域中更是以 C 語言為主，且對記憶體的使用斤斤計較，因此今天就來探討該如何自己實現基礎的 List 功能，又名 “鏈結串列 (Linked List)”！

　　首先需要了解一個簡單的 List 要有什麼功能？需要能動態增加 (Add)；能動態刪除 (Clear)；能動態取出 (Display)。

　　那要怎麼實現上述提到的功能呢？首先要先建立一個 struct 這個 struct 看你需要放什麼資料就建什麼樣的 struct，只是最後一定要有一個自己這個 struct 的指標來指向下一個 item。

例如我要建一個 “名字對應年齡的資料結構”：

#define NAME_LENGTH 255

struct MyStruct
{
	char Name[NAME_LENGTH];
	int Age;
	struct MyStruct* Next; // 一定要有這行！
};

資料結構知道了以後，我們會需要知道這個鏈結串列的頭跟尾，故在全域變數中宣告兩個 struct 變數並指向 NULL：

struct MyStruct* _head = NULL;
struct MyStruct* _end = NULL;

動態增加 (Add)

接著可以開始來實現 Add function 了！整個概念就是：

先用 malloc 動態跟記憶體要了一塊 struct 大小的空間
接著把資料填入 struct 內
然後確保 struct 指向下一個 item 的位址為 NULL
確認現在要加入的資料是不是第一筆資料？
如果是則將剛剛全域的 head 指向現在 malloc 的位址
如果不是則將現在的位址放到全域 end 的下一筆資料 (next)
最後告訴大家尾巴的位址就是現在這個位址
(所以如果是第一筆資料則頭 (head) 跟尾 (end) 的位址會指向同一個地方)

bool LinkedList_Add(char* name, int age)
{
	struct MyStruct* current = NULL;
	// 動態跟記憶體要一個空間，如果沒有空間了則 malloc 會返回 NULL
	current = (struct MyStruct*)malloc(sizeof(struct MyStruct));
	if (current == NULL)
		return false;

	// 將資料填入
	strncpy(current->Name, name, NAME_LENGTH - 1);
	current->Name[NAME_LENGTH - 1] = '\0';
	current->Age = age;
	// 確保最後資料為 NULL
	current->Next = NULL;

	// 如果是第一筆資料則 head 為 NULL，故資料添加到 head
	// 反之則將資料添加到最後面 (end) 的資料的下一筆 (next)
	if (_head == NULL)
		_head = current;
	else
	{
		_end->Next = current;
	}

	// 最後面的資料就是現在添加的資料
	_end = current;

	return true;
}

動態清除 (Clear) & 動態顯示 (Display)

接著因為 malloc 的資料是放在 heap，而不是 stack，所以不會自己釋放。必須要自己 free 來釋放記憶體，否則會造成 memory leak。而清除 (clear) 與顯示 (display) 的概念是相似的，只是取出與 free 的差別而已，故放在一起展示：

void LinkedList_Display(void)
{
	// 從 head 取出現在的資料，如果是 NULL 則代表沒有添加任何資料
	// 由於每一筆資料都會確保 next 為 NULL，除非有下一筆資料添加，故若 next 為NULL 則代表沒有下一筆資料！
	struct MyStruct* current = NULL;
	current = _head;
	while (current != NULL)
	{
		printf("%s's Age is %d\n", current->Name, current->Age);
		current = current->Next;
	}
}

void LinkedList_Clear(void)
{
	// 概念與 display 相似，
	// 只是由於 malloc 是將記憶體放在 heap，而不是 stack，所以並不會自己釋放，必須要自己 free 來釋放記憶體，否則會造成 memory leak
	struct MyStruct* current = NULL;
	current = _head;
	while (current != NULL)
	{
		_end = current;
		current = current->Next;
		free(_end);
	}
}

　　至此，一個簡單的 Linked List 就完成了！雖然還沒達到 List 這麼樣的靈活變化，但對我目前的專案來說已經足夠。其實整個 Linked List 的可玩性還是滿多的，未來專案有用到再來跟大家補充說明。

原文連結Leo Studio

CC BY-NC-ND 2.0 授权