1. 遍歷速度
雖然遍歷數(shù)組和鏈表的時(shí)間復(fù)雜度都是O(n),但是在實(shí)際中數(shù)組的速度要比鏈表快，這是為什么呢？
數(shù)組在內(nèi)存中的地址是連續(xù)相鄰的，而鏈表在內(nèi)存的地址是散列的，不連續(xù)的
-
CPU緩存會(huì)把一片連續(xù)的內(nèi)存空間讀入， 因?yàn)閿?shù)組結(jié)構(gòu)是連續(xù)的內(nèi)存地址， 所以數(shù)組全部或者部分元素被連續(xù)存
在CPU緩存里面，而鏈表的節(jié)點(diǎn)是分散在堆空間里面的，這時(shí)候CPU緩存幫不上忙，只能是去讀取內(nèi)存，
而緩存的速率要比內(nèi)存快。
2. 插入刪除比較
- 數(shù)組的中間插入（或刪除）一個(gè)元素，那么這個(gè)元素后的所有元素的內(nèi)存地址都要往后（前）移動(dòng)（數(shù)組的內(nèi)存地址是連續(xù)的），對(duì)最后一個(gè)元素插入（或刪除）時(shí)才比較快
- 而鏈表不需要改變內(nèi)存的地址，只需要修改節(jié)點(diǎn)的信息即可（包括指針指向，節(jié)點(diǎn)值）。
- 鏈表的擴(kuò)展性較好，定義數(shù)組時(shí)所占用的空間大小都是固定的，如果存儲(chǔ)滿了，無法擴(kuò)展，只能新建一個(gè)更大空間的數(shù)組。
所以可得知:
數(shù)組大小固定，不適合動(dòng)態(tài)存儲(chǔ)，動(dòng)態(tài)添加，內(nèi)存為一連續(xù)的地址，可隨機(jī)訪問，查詢較快，
而鏈表大小可變，擴(kuò)展性強(qiáng)，只能順著指針的方向查詢，速度較慢。
