程設的最後一個題目(二)

串列(Linked List):

    是一種基本的資料結構，我們可以用struct來做出來，它的基本樣子如下。

    有人會問，啊~~我們都有陣列了，為啥還要使用串列這個看起來很複雜的東西呢?

陣列與串列的比較:

1、存取:

    陣列裡的每個資料在記憶體裡是連續分部的，所以存取特定位置的值就很方便，例如使用a[2]就可以取得第3個資料的值。

陣列的記憶體分布

    由於串列裡的每個元素在記憶體裡分布是不連續的，我們如果想要存取特定的資料，我們必需把在它之前的資料都讀取過。假如我們想存取第三個資料，我們必需先找到第二筆資料的位置(第二筆資料的指標指向第三筆的位置)；如果我們想找到第二筆資料的位置，我們就必需先找到第一筆資料的位置........。

PS:那個first是指向第一個元素的指標，在串列生成時它就存在了，固定指著第一個元素的位置。

串列的記憶體分布

2、新增、移除資料:

    陣列的新增跟移除資料就比較麻煩了，如下。

    假如我們想把4加在1和2的中間.........

    這樣看來好像還可以，可是如果那是個裡面有10幾萬筆資料的陣列呢?要在前面新增一筆資料的話，那不就要移好幾萬次嗎?

    再來是陣列的大小，它是固定的。

陣列的大小(通常)是在一開始就要宣告好的(除非動態宣告啦)

    移除陣列的某一元素也滿麻煩的(如果你想保持資料的連續性的話)

那個最後面的數字被蓋過去也沒差

    同樣的，如果這個陣列裡也是有上萬筆資料，那做起來也會超麻煩。

    我們接著來看看串列的新增與移除。

這樣就新增好一筆資料了

    不管我們的串列有多大，想要在當中新增一筆資料，做的都是那幾件事(除非是加在最前面或最後面，這之後會談到)。開新空間、把要當它前一筆資料的struct的指標指向新開的記憶體空間、最後把值給新的struct並把新struct的指標指向要當它後一筆資料的struct的位置。

    接著是刪除，刪除就更簡單了。

    因為沒有一個指標有記住值為2的sturct的位置，所以我們從串列的一開始去遊歷資料的話，會經過1、4、3、到NULL，不會經過2，那個2等同被移除在串列外了(即使它有指著值為3的struct的位置)。

PS:因為struct的空間都是動態分配的，所以那個值為2的struct在程式結束後，並不會釋出它的記憶體空間，需要我們手動去釋放，如果沒釋放的話，它會一直佔著，直到電腦關機。

3、搜尋特定的值:

    這部分，陣列跟串列是差不多的(如果資料沒有排序過的話)，通常就是從頭到尾，一個一個慢慢的找。

總結:

以下是使用串列來做題目的好處。

1、插入、移除資料很快速又方便(雖然我們不會用到移除)，因為題目有要求資料要排序過，所以只要使用串列，把新的資料直接插到對的地方，這樣就不用再排了。

2、串列可以動態調整大小，有新資料的話就開一個新的空間，然後讓某個struct裡的指標指向新開的空間就好了。

3、用串列有加分。