順序表和連結串列的區別

　　演示機型：華為MateBook X 系統版本：win10 1、儲存分配方式不同：順序儲存結構是用一段連續的儲存單元依次儲存線性表的資料元素，單項鍊表是採用鏈式儲存結構，用一組任意的儲存單元存放線性表的元素。

　　2、空間利用率不同：順序表的空間利用率顯然要比連結串列高。因連結串列在儲存資料時，每次只申請一個節點的空間，且空間的位置是隨機的，這種申請儲存空間的方式會產生很多空間碎片，一定程式上造成了空間浪費。不僅如此，由於連結串列中每個資料元素都必須攜帶至少一個指標，因此連結串列對所申請空間的利用率也沒有順序表高。

　　3、開闢空間的方式不同：順序表儲存資料實行的是 “一次開闢，永久使用”，即儲存資料之前先開闢好足夠的儲存空間，空間一旦開闢後期無法改變大小（使用動態陣列的情況除外）。而連結串列則不同，連結串列儲存資料時一次只開闢儲存一個節點的物理空間，如果後期需要還可以再申請。因此，若只從開闢空間方式的角度去考慮，當儲存資料的個數無法提前確定，又或是物理空間使用緊張以致無法一次性申請到足夠大小的空間時，使用連結串列更有助於問題的解決。

　　1、基於儲存的考慮

　　順序表的儲存空間是靜態分配的，在程式執行之前必須明確規定它的儲存規模，事先對“MAXSIZE”要有合適的設定，。如果對線性表的長度或儲存規模難以估計時，不宜採用順序表;連結串列不用事先估計儲存規模，但連結串列的儲存密度較低。

　　2、基於操作的考慮

　　在順序表中按序號訪問元素的時間效能為O(1)，而連結串列中按序號訪問的時間效能是O(n)，所以如果經常做的運算是按序號訪問資料元素，顯然順序表優於連結串列;在連結串列中作插入、刪除，也要找插入位置，但是比較操作，顯然連結串列較優。

　　3、基於開發的語言考慮

　　順序表容易實現，任何高階語言中都有陣列型別，連結串列的操作是基於指標的，有些語言不支援指標型別，並且相對指標來講順序表較簡單。總之，兩種儲存結構各有長短，選擇那一種儲存方式應由實際問題決定。通常“較穩定”的線性表選擇順序儲存，而頻繁做插入刪除的即動態性較強的線性表宜選擇鏈式儲存。

　　陣列和連結串列的區別如下：

　　1、陣列是一種線性表資料結構。它用一組連續的記憶體空間，來儲存一組具有相同型別的資料。最大的特點就是支援隨機訪問，但插入、刪除操作也因此變得比較低效，平均情況時間複雜度為O（n）。在平時的業務開發中，我們可以直接使用程式語言提供的容器類，但是，如果是特別底層的開發，直接使用陣列可能會更合適。

　　2、連結串列它並不需要一塊連續的記憶體空間，它透過“指標”將一組零散的記憶體，空間可擴容，比較常用的是單鏈表，雙鏈表和迴圈連結串列。和陣列相比，連結串列更適合插入、刪除操作頻繁的場景，查詢的時間複雜度較高。不過，在具體軟體開發中，要對陣列和連結串列的各種效能進行對比，綜合來選擇使用兩者中的哪一個。