[C/Cpp] 透過 鏈結串列(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。
例如我要建一個 “名字對應年齡的資料結構”:

1
2
3
4
5
6
7
8
#define NAME_LENGTH 255

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

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

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

動態增加 (Add)

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

  1. 先用 malloc 動態跟記憶體要了一塊 struct 大小的空間。
  2. 接著把資料填入 struct 內
  3. 然後確保 struct 指向下一個 item 的位址為 NULL
  4. 確認現在要加入的資料是不是第一筆資料,
    如果是則將剛剛全域的 head 指向現在 malloc 的位址!
    如果不是則將現在的位址放到全域 end 的下一筆資料 (next)!
  5. 最後告訴大家尾巴的位址就是現在這個位址!
    (所以如果是第一筆資料則頭 (head) 跟尾 (end) 的位址會指向同一個地方)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
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 的差別而已,故放在一起展示。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
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


✏以上就是本次的內容,
💡希望對正在閱讀的你也有幫助,若有誤的地方也歡迎指教。
❓若有什麼疑問歡迎下方留言,我會盡速回復您!


支持|不只是個工程師

如果這篇文章對你有幫助,請幫我
拍拍手|LikeCoin基金將會分發LikeCoin獎勵創作者
追蹤| Facebook & Instagram
也歡迎點我小額訂閱【不只是個工程師】

歡迎關注我的其它發布渠道