為什么數(shù)組查詢(xún)比鏈表快？而插入刪除比鏈表效率低？
- 順序存儲(chǔ)可以想象成吃飯排隊(duì)，每個(gè)人領(lǐng)的號(hào)都是按順序來(lái)的满葛，服務(wù)員只要喊號(hào)就里立即可以找到對(duì)應(yīng)的人，新來(lái)的人都自動(dòng)加到隊(duì)尾谊却，如果有人想插隊(duì)，那么從他插隊(duì)的位置后面所有的人都要挪動(dòng)位置。
- 鏈接存儲(chǔ)可以想象成手拉手做游戲，每個(gè)人只知道自己手拉的是誰(shuí)，想要找到某個(gè)人必須從一個(gè)節(jié)點(diǎn)開(kāi)始往一個(gè)方向按順序一個(gè)一個(gè)查讳推，直到查到這個(gè)人，新來(lái)的人可以插到任意兩個(gè)人之間，只要原來(lái)的那兩個(gè)人把手放開(kāi)，和新來(lái)的拉起手即可庆尘，不需要其他人都跟著挪動(dòng)。
1.數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)分為順序存儲(chǔ)晤柄、鏈接存儲(chǔ)涂臣、索引存儲(chǔ)哭尝、散列存儲(chǔ)。
2.數(shù)組屬于順序存儲(chǔ)安吁，用一段連續(xù)的內(nèi)存位置來(lái)存儲(chǔ)网棍。
3.鏈表屬于鏈接存儲(chǔ)巍棱，用一組任意的存儲(chǔ)單元來(lái)存儲(chǔ)，不要求物理上相鄰窝稿。
數(shù)組和鏈表的優(yōu)缺點(diǎn)：
數(shù)組
使用方便伴榔，援奢，查詢(xún)效率比鏈表高，內(nèi)存為一連續(xù)的區(qū)域
缺點(diǎn)：大小固定绕娘，不適合動(dòng)態(tài)存儲(chǔ)脐湾，不方便動(dòng)態(tài)添加孟岛。
鏈表
優(yōu)點(diǎn)：可動(dòng)態(tài)添加刪除渠羞，大小可變斤贰，內(nèi)存可能是不連續(xù)內(nèi)存，鏈?zhǔn)酱鎯?chǔ)堵未。
缺點(diǎn)：只能通過(guò)順次指針訪問(wèn)，查詢(xún)效率低盏触。
訪問(wèn)：
數(shù)組可以隨機(jī)訪問(wèn)其中的元素渗蟹，鏈表則必須是順序訪問(wèn)，不能隨機(jī)訪問(wèn)
鏈表可以隨意擴(kuò)大赞辩，數(shù)組不能
處理速度由快到慢排序：
CPU寄存器 -> 緩存 -> 內(nèi)存 ->硬盤(pán)
- CPU 寄存器 – immediate access (0-1個(gè)CPU時(shí)鐘周期)
- CPU L1 緩存 – fast access (3個(gè)CPU時(shí)鐘周期)
- CPU L2 緩存 – slightly slower access (10個(gè)CPU時(shí)鐘周期)
- 內(nèi)存 (RAM) – slow access (100個(gè)CPU時(shí)鐘周期)
- 硬盤(pán) (file system) – very slow (10,000,000個(gè)CPU時(shí)鐘周期)
各級(jí)別的存儲(chǔ)器速度差異非常大雌芽，CPU寄存器速度是內(nèi)存速度的100倍，這就是為什么CPU產(chǎn)商發(fā)明了CPU緩存辨嗽。而這個(gè)CPU緩存世落，就是數(shù)組和鏈表區(qū)別的關(guān)鍵所在。
總結(jié)
CPU緩存會(huì)把一片連續(xù)的內(nèi)存空間讀入糟需，因?yàn)閿?shù)組結(jié)構(gòu)是連續(xù)的內(nèi)存地址屉佳，所以數(shù)組全部或者部分元素被連續(xù)存在CPU緩存里面，平均讀取 每個(gè)元素的時(shí)間只要3個(gè)CPU時(shí)鐘時(shí)間洲押。而鏈表的節(jié)點(diǎn)分散在堆空間里面武花，這時(shí)候CPU緩存幫不上忙，只能是去讀取內(nèi)存杈帐，平均讀取時(shí)間需要100個(gè)CPU時(shí)鐘周期体箕。 這樣算下來(lái)专钉，數(shù)組訪問(wèn)的速度比鏈表快33倍！
而數(shù)組大小固定累铅，插入和刪除都需要移動(dòng)元素跃须，鏈表可以動(dòng)態(tài)擴(kuò)充，插入刪除不需要移動(dòng)元素娃兽，只需要更改元素中的指針菇民。所以鏈表的插入刪除比數(shù)組效率高。
查詢(xún)比數(shù)組快换薄，刪除插入效率又高的方式就是散列存儲(chǔ)玉雾，hash
