資料結構與算法——連結清單連結清單

題型1：數組和連結清單的差別是什麼？

數組和連結清單的差別主要表現在以下幾個方面：

1）邏輯結構。數組必須事先定義固定的長度，不能适應資料動态地增減。當數組中插入、删除資料項時，需要移動其他資料項。而連結清單采用動态配置設定記憶體的形式實作，可以适應資料動态第增減的情況，需要時可以用new/malloc配置設定記憶體空間，不需要時使用delete/free将已配置設定的空間釋放，插入和删除元素不需要移動資料項。

2）記憶體結構。數組從棧中配置設定空間，連結清單從堆中配置設定空間。

3）數組中的資料在記憶體中是順序存儲的，而連結清單是随機存儲的。數組的随機通路效率很高，可以直接定位，但插入、删除操作的效率比較低。連結清單的插入、删除操作不需要移動元素。

4）連結清單不存在越界的問題，數組有越界的問題。

題型2：對單連結清單進行排序

方法1：使用冒泡排序

方法2：使用直接插入排序

方法3：使用歸并排序

 當我們需要對連結清單進行排序時，由于不能對它的元素進行随機通路，是以更适合使用歸并排序，大名鼎鼎的快速排序用到連結清單上，效率也很低，原因還是在于不能對連結清單中的元素進行随機通路，同理，采用堆排序更是不可能的事情。

        算法具體實作時需要一個指向頭節點（連結清單的第一個節點，連結清單中不包含額外的一個節點來作頭節點）的指針，這是因為在算法實作的時候，不大可能第一個節點正好就是所有元素中最小的一個，則連結清單的頭節點會改變，是以我們需要一個指向頭節點的指針來存儲不斷變化的頭節點。

算法思想：

MergeSort(headRef)