單連結串列的建立

單連結串列的建立

大家好，今天來詳細說一下單連結串列的建立過程。

單連結串列是我們在學習資料結構時見到的第一種動態記憶體分配的結構，而這也是單連結串列和陣列之間最大的區別，因為陣列被分配的記憶體是固定的，而單連結串列的記憶體是在執行時分配的。

因此，想要給單連結串列分配記憶體，我們就得首先知道函數malloc()，即memory allocate（記憶體分配）的縮寫，它是c語言標準函數庫中的函數，用法是void *malloc(unsigned int size)。其作用是在記憶體的動態儲存區中分配一個長度為size的連續空間。此函數的返回值是分配區域的起始地址（即指向該分配域的開頭位置的指標）

瞭解了malloc函數以後，我們來建立連結串列中最重要的部分：結點(node)。每個結點中都儲存了資料，但是，每個結點並不是獨立存在的，因為連結串列是由多個結點連線組成，那麼我們該怎麼連線每一個結點呢？我們需要用到指標(pointer)，用指標來指向另一個（下一個）結點的地址，這樣就可以將每個結點按自己的想法連線起來。所以，每個結點都至少由兩部分組成：資料和指向下一個節點地址的指標。

知道了如何抽象地去建立連結串列之後，我們將用C語言程式碼來建立連結串列。

首先，我們需要用到結構體(structure)來定義結點node：裡面包括一個int型別的資料data，struct node型別的指標link。

接下來，我們首先用malloc函數建立第一個長度為結點大小的連續空間，用來儲存結點中的資料和指標。我們把這個連續空間定義為head，即頭結點。我們在頭結點中輸入資料，再定義指標link的值為null，即不指向任何地址。這樣，我們就建立了一個獨立的結點。

我們可以用同樣的方法，建立第二個(current1)，第三個(current2)，直到我們需要數量的獨立結點。如下圖所示，我們建立了三個獨立節點。

但是，我們在之前已經知道，多個獨立結點並不能稱之為連結串列，連結串列是需要將結點連線起來的，所以我們還需要用程式碼來將他們連線起來。

我們已經知道，head結點的指標不指向任何地址。現在，我想讓他指向第二個結點current1，以此來連線第一個結點和第二個結點，形成一個只有兩個結點的連結串列。我們只需要再後面新增一句：head->link = current1。即link的值是current1的地址。用同樣的方法，我們可以連線第二個和第三個結點current2，即

current1->link = current2。如下圖程式碼所示。

但是，按照我們上面的這種方法。如果我們需要建立一萬個結點，那豈不是需要建立一萬個指標指向各自的下一個結點？這樣的方法非常的繁瑣且佔用記憶體空間，因此，我將介紹第二種方法，只需要兩個指標就可以完成所有結點的連線。

建立前兩個結點的方法同上，兩個結點分別為head，current1。建立第三個結點時不同的是，我們需要再次使用指標current1。在給第三個結點分配空間後，令current1 = malloc(sizeof(struct node))，即current1不再是第二個結點空間的首地址，而是第三個結點空間的首地址。這樣，我們可以用和第二個節點同樣的方法賦值第三個結點的data和link，另外一個不同的地方就是：我們將第三個結點的地址(current1)賦值給head->link->link，即可完成第二節點和第三結點的連線。示意圖和程式碼如下。

 綜上，我們建立了一條具有三個結點的單連結串列。現在，我們可以對連結串列進行增、刪、改、查等一系列操作了！