順序表和連結清單的優缺點

順序表

定義：在記憶體中用位址連續的一塊存儲空間順序存放線性表的各元素。在程式設計語言中，一維數組在記憶體中占用的存儲空間是一維連續的存儲空間，是以我們用一維數組存儲資料來表示順序表。

優點：

1. 由于順序表是用數組來存儲資料，記憶體空間連續，當通路資料時可以達到使用數組下标的方式随機通路。
2. CPU高速緩存的命中率高。

解釋：

資料儲存在記憶體中，資料是在CPU裡進行運算的(邏輯和算術)。但是CPU速度太快，記憶體的速度跟不上CPU的速度。于是在CPU和記憶體之間存在一些寄存器和緩存器，用來儲存資料。當CPU要使用資料時先在這些緩存器裡讀取資料，沒有讀到時就到記憶體中讀取資料，然而資料讀到緩存器不是一個資料一個資料讀的，它是按照計算機的不同，在記憶體中連續讀一段資料存在緩存器中，由于數組空間連續，讀到緩存器中的有效資料多，是以緩存命中率高。

缺點：

1. 空間有限，不夠時需要增容(性能有消耗)，并且會存在一定的空間浪費。(擴容一般按2倍或者1.5倍進行增容，如果資料存儲過少，導緻空間浪費)。
2. 頭部或者中間插入/删除資料，要挪動資料，效率低。時間複雜度O(N)。

連結清單(帶頭雙向循環連結清單)

定義：連結清單是一種實體存儲結構上非連續、非順序的存儲結構，資料元素的邏輯順序是通過連結清單中的指針連結次序實作的 。

優點：

1. 按需配置設定記憶體，需要存儲一個資料時，就申請一塊空間，不會存在空間浪費。
2. 可以在任意位置插入和删除資料，時間複雜度位O(N)。

缺點：

1. 不支援随機通路。
2. 導緻緩存污染，低命中率。

緩存拿資料為在記憶體中連續讀一段資料，由于連結清單實體結構非連續，導緻拿取資料時有效數字大機率隻有一個，其他資料為非有效資料，可能會覆寫緩存器中的其它有效資料。

總結

順序表和連結清單相輔相成的，各有的的優點和缺點。我們并不能說哪一個更好。他們應用在不同的領域會有不同的效果，是以兩者我們都需要好好掌握。