Zi 字媒體

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。例如我要建一個 “名字對應年齡的資料結構”： 12345678 #define NAME_LENGTH 255struct MyStruct{ char Name[NAME_LENGTH]; int Age; struct MyStruct* Next; // 一定要有這行！}; 資料結構知道了以後，我們會需要知道這個鏈結串列的 頭 跟 尾，故在全域變數中宣告兩個 struct 變數並指向 NULL： 12 struct MyStruct* _head = NULL;struct MyStruct* _end = NULL; 動態增加 (Add) 接著可以開始來實現 Add function 了！整個概念就是： 先用 malloc 動態跟記憶體要了一塊 struct 大小的空間。 接著把資料填入 struct 內 然後確保 struct 指向下一個 item 的位址為 NULL 確認現在要加入的資料是不是第一筆資料，如果是則將剛剛全域的 head 指向現在 malloc 的位址！如果不是則將現在的位址放到全域 end 的下一筆資料 (next)！ 最後告訴大家尾巴的位址就是現在這個位址！(所以如果是第一筆資料則頭 (head) 跟尾 (end) 的位址會指向同一個地方) 1234567891011121314151617181920212223242526272829 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 的差別而已，故放在一起展示。 1234567891011121314151617181920212223242526 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 的可玩性還是滿多的，未來專案有用到再來跟大家補充說明！ 完整的 sample code 我放在 github 上了，歡迎下載玩玩看！ github sample code：https://github.com/leoli-git/MySampleCode/tree/main/MyLinkedList