數(shù)組和鏈表是兩種基本的數(shù)據(jù)結(jié)構(gòu)咐低，他們在內(nèi)存存儲上的表現(xiàn)不一樣痒筒，所以也有各自的特點(diǎn)。
大致總結(jié)一下特點(diǎn)和區(qū)別岭皂，拿幾個(gè)人一起去看電影時(shí)坐座位為例郊霎。
數(shù)組的特點(diǎn)
- 在內(nèi)存中，數(shù)組是一塊連續(xù)的區(qū)域爷绘。 拿上面的看電影來說书劝，這幾個(gè)人在電影院必須坐在一起。
- 數(shù)組需要預(yù)留空間土至，在使用前要先申請占內(nèi)存的大小购对，可能會(huì)浪費(fèi)內(nèi)存空間。 比如看電影時(shí)陶因，為了保證10個(gè)人能坐在一起骡苞，必須提前訂好10個(gè)連續(xù)的位置。這樣的好處就是能保證10個(gè)人可以在一起。但是這樣的缺點(diǎn)是解幽，如果來的人不夠10個(gè)贴见，那么剩下的位置就浪費(fèi)了。如果臨時(shí)有多來了個(gè)人躲株，那么10個(gè)就不夠用了片部，這時(shí)可能需要將第11個(gè)位置上的人挪走，或者是他們11個(gè)人重新去找一個(gè)11連坐的位置霜定，效率都很低档悠。如果沒有找到符合要求的作為，那么就沒法坐了望浩。
- 插入數(shù)據(jù)和刪除數(shù)據(jù)效率低辖所，插入數(shù)據(jù)時(shí)，這個(gè)位置后面的數(shù)據(jù)在內(nèi)存中都要向后移磨德。刪除數(shù)據(jù)時(shí)奴烙，這個(gè)數(shù)據(jù)后面的數(shù)據(jù)都要往前移動(dòng)。 比如原來去了5個(gè)人剖张，然后后來又去了一個(gè)人要坐在第三個(gè)位置上切诀，那么第三個(gè)到第五個(gè)都要往后移動(dòng)一個(gè)位子，將第三個(gè)位置留給新來的人搔弄。 當(dāng)這個(gè)人走了的時(shí)候幅虑，因?yàn)樗麄円B在一起的，所以他后面幾個(gè)人要往前移動(dòng)一個(gè)位置顾犹，把這個(gè)空位補(bǔ)上倒庵。
- 隨機(jī)讀取效率很高。因?yàn)閿?shù)組是連續(xù)的炫刷，知道每一個(gè)數(shù)據(jù)的內(nèi)存地址擎宝，可以直接找到給地址的數(shù)據(jù)。
- 并且不利于擴(kuò)展浑玛，數(shù)組定義的空間不夠時(shí)要重新定義數(shù)組绍申。
鏈表的特點(diǎn)
- 在內(nèi)存中可以存在任何地方，不要求連續(xù)顾彰。 在電影院幾個(gè)人可以隨便坐极阅。
- 每一個(gè)數(shù)據(jù)都保存了下一個(gè)數(shù)據(jù)的內(nèi)存地址，通過這個(gè)地址找到下一個(gè)數(shù)據(jù)涨享。 第一個(gè)人知道第二個(gè)人的座位號筋搏，第二個(gè)人知道第三個(gè)人的座位號……
- 增加數(shù)據(jù)和刪除數(shù)據(jù)很容易。 再來個(gè)人可以隨便坐厕隧，比如來了個(gè)人要做到第三個(gè)位置奔脐，那他只需要把自己的位置告訴第二個(gè)人俄周，然后問第二個(gè)人拿到原來第三個(gè)人的位置就行了。其他人都不用動(dòng)髓迎。
- 查找數(shù)據(jù)時(shí)效率低栈源，因?yàn)椴痪哂须S機(jī)訪問性，所以訪問某個(gè)位置的數(shù)據(jù)都要從第一個(gè)數(shù)據(jù)開始訪問竖般，然后根據(jù)第一個(gè)數(shù)據(jù)保存的下一個(gè)數(shù)據(jù)的地址找到第二個(gè)數(shù)據(jù)，以此類推茶鹃。 要找到第三個(gè)人涣雕，必須從第一個(gè)人開始問起。
- 不指定大小闭翩，擴(kuò)展方便挣郭。鏈表大小不用定義，數(shù)據(jù)隨意增刪疗韵。
各自的優(yōu)缺點(diǎn)
數(shù)組的優(yōu)點(diǎn)
- 隨機(jī)訪問性強(qiáng)
- 查找速度快
數(shù)組的缺點(diǎn)
- 插入和刪除效率低
- 可能浪費(fèi)內(nèi)存
- 內(nèi)存空間要求高兑障，必須有足夠的連續(xù)內(nèi)存空間。
- 數(shù)組大小固定蕉汪，不能動(dòng)態(tài)拓展
鏈表的優(yōu)點(diǎn)
- 插入刪除速度快
- 內(nèi)存利用率高流译，不會(huì)浪費(fèi)內(nèi)存
- 大小沒有固定，拓展很靈活者疤。
鏈表的缺點(diǎn)
- 不能隨機(jī)查找福澡，必須從第一個(gè)開始遍歷，查找效率低
| - | 數(shù)組 | 鏈表 |
|---|---|---|
| 讀取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 刪除 | O(n) | O(1) |
