1. 數(shù)組和鏈表的區(qū)別
1.1 數(shù)組的特點
- 在內(nèi)存中佃乘，數(shù)組是一塊連續(xù)的區(qū)域。 拿上面的看電影來說，這幾個人在電影院必須坐在一起。
- 數(shù)組需要預(yù)留空間实檀，在使用前要先申請占內(nèi)存的大小惶洲，可能會浪費內(nèi)存空間。 比如看電影時膳犹，為了保證10個人能坐在一起恬吕，必須提前訂好10個連續(xù)的位置。這樣的好處就是能保證10個人可以在一起须床。但是這樣的缺點是币呵，如果來的人不夠10個，那么剩下的位置就浪費了侨颈。如果臨時有多來了個人余赢，那么10個就不夠用了，這時可能需要將第11個位置上的人挪走哈垢，或者是他們11個人重新去找一個11連坐的位置妻柒，效率都很低。如果沒有找到符合要求的作為耘分，那么就沒法坐了举塔。
- 插入數(shù)據(jù)和刪除數(shù)據(jù)效率低，插入數(shù)據(jù)時求泰，這個位置后面的數(shù)據(jù)在內(nèi)存中都要向后移央渣。刪除數(shù)據(jù)時，這個數(shù)據(jù)后面的數(shù)據(jù)都要往前移動渴频。 比如原來去了5個人芽丹，然后后來又去了一個人要坐在第三個位置上，那么第三個到第五個都要往后移動一個位子卜朗，將第三個位置留給新來的人拔第。 當(dāng)這個人走了的時候，因為他們要連在一起的场钉，所以他后面幾個人要往前移動一個位置蚊俺，把這個空位補上。
- 隨機讀取效率很高逛万。因為數(shù)組是連續(xù)的泳猬，知道每一個數(shù)據(jù)的內(nèi)存地址，可以直接找到給地址的數(shù)據(jù)宇植。
- 并且不利于擴展得封，數(shù)組定義的空間不夠時要重新定義數(shù)組。
鏈表的特點
- 在內(nèi)存中可以存在任何地方当纱，不要求連續(xù)呛每。 在電影院幾個人可以隨便坐。
- 每一個數(shù)據(jù)都保存了下一個數(shù)據(jù)的內(nèi)存地址坡氯，通過這個地址找到下一個數(shù)據(jù)晨横。 第一個人知道第二個人的座位號洋腮，第二個人知道第三個人的座位號……
- 增加數(shù)據(jù)和刪除數(shù)據(jù)很容易。 再來個人可以隨便坐手形，比如來了個人要做到第三個位置啥供，那他只需要把自己的位置告訴第二個人，然后問第二個人拿到原來第三個人的位置就行了库糠。其他人都不用動伙狐。
- 查找數(shù)據(jù)時效率低，因為不具有隨機訪問性瞬欧，所以訪問某個位置的數(shù)據(jù)都要從第一個數(shù)據(jù)開始訪問贷屎，然后根據(jù)第一個數(shù)據(jù)保存的下一個數(shù)據(jù)的地址找到第二個數(shù)據(jù)，以此類推艘虎。 要找到第三個人唉侄，必須從第一個人開始問起。
- 不指定大小野建，擴展方便属划。鏈表大小不用定義，數(shù)據(jù)隨意增刪候生。
各自的優(yōu)缺點
數(shù)組的優(yōu)點
- 隨機訪問性強
- 查找速度快
數(shù)組的缺點
- 插入和刪除效率低
- 可能浪費內(nèi)存
- 內(nèi)存空間要求高同眯，必須有足夠的連續(xù)內(nèi)存空間。
- 數(shù)組大小固定唯鸭，不能動態(tài)拓展
鏈表的優(yōu)點
- 插入刪除速度快
- 內(nèi)存利用率高须蜗，不會浪費內(nèi)存
- 大小沒有固定，拓展很靈活肿孵。
鏈表的缺點
- 不能隨機查找唠粥，必須從第一個開始遍歷，查找效率低
| - | 數(shù)組 | 鏈表 |
|---|---|---|
| 讀取 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 刪除 | O(n) | O(1) |
