C 語言:鏈結串列(Linked List)的建立與刪除

結構陣列是一種很常用的資料結構。(若還不清楚什麼是結構陣列的讀者,歡迎參考此篇)但它有一個很明顯的缺點…

 

我們宣告了一個結構,裡面有三個元素。

記憶體去儲存這個資料時,是依序放在記憶體裡面的。

如果我們想要在第一個元素和第二個元素之間、插入一個元素,比如在 Tyuzu 和 Mina 之間插入一個 Sana,要怎麼做呢?

為了保持原本的順序,必須把 Mina 和之後的 Momo 全部都往後移動,才能給 Sana 空出空間。

不覺得超級麻煩嗎…

為了解決這樣的問題,這邊來為大家介紹一個好用的資料結構——鏈結串列 (Linked List)。

 

鏈結串列 (Linked List)

利用指標,把原本的三個結構變數串起來。

在第一個結構後面加一個指標、讓它指向下一個結構;在第二個結構後面,再加一個指標,讓它指向下一個結構… 依次連接。

透過這樣的方式,能讓每個能彈性擴充。

當我們想在 Tzuyu 和 Mina 之間插入一個 Sana 時,就讓 Tzuyu 指向 Sana,再讓 Sana 指向後面 Mina。

鏈結串列的好處是彈性靈活,能動態跟記憶體要空間、或釋放空間。

鏈結串列,就是把陣列 (Array) 切成小塊,然後在裡面裝上追蹤器,不但更靈活、也更省記憶體空間呢!

這邊就要用到兩種運算元——NEW 和 DELETE 啦。

鏈結串列由以下元素構成:

  • 起始:指向鏈結串列第一個節點的指標
  • 鏈結串列的節點
    • 當前節點的資料
    • 下一個節點的地址
  • 結尾:最後一個節點連接的地址寫「NULL」,表示鏈結串列結束。

 

動態跟記憶體要空間: new, delete

我們平常都是事先宣告好所要使用的變數,當程式開始執行時,這些變數就會自動被配置記憶體空間。 比如 int 型就會被配置 4 個 byte 的記憶體空間。

然而有時有些變數並不知道何時會被使用,希望能在使用到的時候再配置空間給變數,所以我們可以動態的跟記憶體要空間、再在不需要後釋放掉它。

這裡用到的運算元分別是「new」與「delete」。


new 是用來跟記憶體要一個用來存放 4 個 byte 的 int 型變數所需要的空間,並傳回該空間的地址。我們再把地址存入指標 ptr 裡面。

如果要在配置完成後指定儲存值,可以這樣宣告:


要刪除這個空間,很簡單:

 

我們也可以動態配置陣列:

表示跟記憶體要了 100 個 int 大小的空間,再回傳空間的第一個位址,存入指標 ptr 裡面。

要釋放掉這塊空間,就在 delete 後面加上 [] ,表示要釋放掉的是指標 ptr 後面的一塊陣列區域:

 

把 NEW 和 DELETE 運用到鏈結串列上…

可以先建立一個結構,包含一個值 (value) 和一個指標 (pointer):

首先宣告一個指向 girl 型的指標 head,

然後用 new 跟記憶體要一塊 girl 類型的記憶體空間,並將這塊位址賦值給 head 指標。

有了這樣的結構,我們就可以通過這種方式,來申請一片 girl 類型的記憶體儲存空間。

 

逐步創建鏈結串列

Step 1:建立第一個節點。

從第一節點開始,用 new 申請一塊 girl 類型的儲存空間,並且賦值——宣告一個 head 指標指向它。

為了建立後續的節點,我們宣告一個臨時的指標 current ,讓它指向新建立的節點、並表明我們現在正在哪,也就是 girl *current = head。

 

Step 2:我們得先決定,要不要建立一個新的節點?

YES: 再申請一塊 girl 記憶體空間,所以 new girl 。再用剛剛宣告的指標,讓它的 next 指向下一個節點,變成 current -> next = girl; 。

同時,為了能夠建立後續的節點,得把 current 往前移動一個節點,使得 current 指向最新建立的節點,變成 current =current -> next;

建立完後,再次回到 Step 2 的問題,考慮要不要建立一個新節點。

YES 的話則和上述過程相同。

NO: 若不需要,那我們就要把最後節點指向下一個節點的 next 設定為 NULL。

 

這個過程的完整程式碼寫下來就會是:

印出來的結果:

先指定有 3 個節點,接下來輸入 3 個數字作為三個節點的值,最後把結果印出來。

(´_ゝ`)… 有沒有覺得結果明明和陣列一樣,為什麼寫成鏈結串列,就這麼難呢?

在這邊還不能發揮鏈結串列真正的功用噢!如果只有這樣的話也不用特地寫成鏈結串列版了。

 

刪除節點

來試試看刪除節點吧!

Step 1:刪除的節點位於第一個位置。

由於是要刪掉第一個節點,直接讓 head 指向下一個節點就可以了,也就是 head->next 把 head 原本的值蓋掉,就已經完成刪除了。

但如果光只有這樣的話,並沒有把 head 原本的空間釋放出來。

所以我們先用一個 temp 把要被刪除的節點地址先存起來,再 head = head->next ,最後 delete temp 把這個節點佔用的記憶體空間釋放出來。

Step 2:刪除中間的節點。

要刪除中間的節點,可以把前一個節點、直接指向它後一個節點。

但這樣有兩個問題:不知道第三個節點的地址是什麼怎麼指?指完後,那中間第二個節點的空間沒有釋放出來啊?

這時候就需要 2 個輔助的指標來幫助我們完成刪除。用 temp 指標來找這個要被刪除的節點。然後利用另外一個指標 follow 來跟在 temp 的後面。

最後再把 temp 指標 delete 掉,就成功釋放該節點了。

實際用程式碼寫出來,就會是:

來看看印出來的結果:

指定 5 個年紀 17, 18, 19, 20, 21 為 TWICE 鏈結串列的值。

然後指定要刪除 19,再印出來:

指定 4 個年紀 18, 19, 21, 20 為 TWICE 鏈結串列的值。

指定要刪除 35 (這當然不會是花樣年華少女的年紀呀),印出找不到。

 

如果想要能跑出上面結果的完整程式碼,附註在這邊歡迎拿去玩:

今天的 Linked List 教學就到這邊結束啦!我們學會了利用 struct 來「建立」和「刪除」鏈結串列的方法。

大家是不是都會用了呢?

下一篇的鏈結串列教學,會來教如何把資料插入指定的位置!

 

來源:xkcd

(拍拍)指來指去超容易搞混亂 O_Q… 要 Hold 住啊啊~

4 thoughts on “C 語言:鏈結串列(Linked List)的建立與刪除

  1. YM says:

    還不錯,加油!

    可以介紹一下 Linked List 的應用,對初學者來說,可能會比較有興趣。
    好早以前,為了寫一個排版系統的 Editor ( @SunOS, 1989) ,當時是用了 Double Linked List。

    那個時代的 Workstation,只有 16MB RAM, 20MHz 68020,要處理大量的中文字形,還蠻有挑戰。
    幸好 SunOS 4.0 發明了 Memory Mapping (mmap),解決了一大難題。

    • Lynn says:

      其實我自己就是初學者,還不是很熟LINKED LIST到底有那些應用XDD 目前只拿來build stack和queue而已= =

發表迴響

你的電子郵件位址並不會被公開。 必要欄位標記為 *