數組與鏈表

怎麼說呢，這兩個東西對我來說很熟悉又很陌生。熟悉是因為寫代碼的時候經常會用到，陌生呢就是...還是換種說法，就好像你認識一個人，你看到他就知道他是誰，你還知道他是幹嘛的，但是呢，這個人的性格你不知道，你不知道他是怎麼樣的一個人，大概就是一種利用關係吧。

但今天呢，我良心發現，我得了解他兩，這樣我才可以更好的與他們愉快合作。

如何認識他們呢？先從底層入手

我們先了解一下內存這個東西：

假設你去看演出，需要將東西寄存。寄存處有一個柜子，柜子有很多抽屜。每個抽屜可放一樣東西，你有兩樣東西要寄存，因此要了兩個抽屜。你將兩樣東西存放在這裡。現在你可以去看演出了！這大致就是計算機內存的工作原理。計算機就像是很多抽屜的集合體，每個抽屜都有地址。

fe0ffeeb是一個內存單元的地址。

需要將數據存儲到內存時，你請求計算機提供存儲空間，計算機給你一個存儲地址。需要存

儲多項數據時，有兩種基本方式——數組和鏈表。但它們並非都適用於所有的情形，因此知道它們的差別很重要。接下來介紹數組和鏈表以及它們的優缺點。

數組與鏈表

有時候，需要在內存中存儲一系列元素。假設你要編寫一個管理待辦事項的應用程序，為此需要將這些待辦事項存儲在內存中。應使用數組還是鏈表呢？鑒於數組更容易掌握，我們先將待辦事項存儲在數組中。使用數組意味著所有待辦事項在內存中都是相連的（緊靠在一起的）。

當你添加第四個待辦事項的時候，咦，這個內存讓別人給佔了，這可怎麼辦呢？

這就像你與朋友去看電影，找到地方就坐後又來了一位朋友，但原來坐的地方沒有空位置，只得再找一個可坐下所有人的地方。在這種情況下，你需要請求計算機重新分配一塊可容納4個待辦事項的內存，再將所有待辦事項都移到那裡。

如果又來了一位朋友，而當前坐的地方也沒有空位，你們就得再次轉移！真是太麻煩了。同樣，在數組中添加新元素也可能很麻煩。如果沒有了空間，就得移到內存的其他地方，因此添加新元素的速度會很慢。一種解決之道是「預留座位」：即便當前只有3個待辦事項，也請計算機提供10個位置，以防需要添加待辦事項。這樣，只要待辦事項不超過10個，就無需轉移。這是一個不錯的權變措施，但你應該明白，它存在如下兩個缺點。

• 你額外請求的位置可能根本用不上，這將浪費內存。你沒有使用，別人也用不了。
• 如果超過了預留的位置的話，又得轉移。

可以看出這種預留措施雖然看起來能解決問題，但是還是有很多瑕疵的，這個時候我們的另一個朋友鏈表就登場了啊。

鏈表

鏈表的元素可以存儲在內存的任何地方。

每個元素都存放了下一個元素的地址

就像闖關遊戲一樣，每過一關就可以挑戰下一關，這樣我們就不用擔心數組那樣的問題了。而且當我們做插入，刪除的操作時，也很方便只需要改變元素所指向下一個元素的地址就Ok了.

使用鏈表時，根本就不需要移動元素。這還可避免另一個問題。假設你與五位朋友去看一部很火的電影。你們六人想坐在一起，但看電影的人較多，沒有六個在一起的座位。使用數組時有時就會遇到這樣的情況。假設你要為數組分配10 000個位置，內存中有10 000個位置，但不都靠在一起。在這種情況下，你將無法為該數組分配內存！鏈表相當於說「我們分開來坐」，因此，只要有足夠的內存空間，就能為鏈表分配內存。

可能到這裡你就有點不明白了，既然鏈表這麼好，那我們為什麼不只用鏈表，還用數組幹什麼。

當然是因為闖關遊戲都得一關接一關的玩啊，比如你想看到最後的大BOSS，那你就得把前面所有的關卡給過了才行。但數組不用啊，這貨里的元素在內存里都是連一塊的呀。

例如，假設有一個數組，它包含五個元素，起始地址為00，那麼元素#5的地址是多少呢？

只需執行簡單的數學運算就知道：04。需要隨機地讀取元素時，數組的效率很高，因為可迅速找到數組的任何元素。在鏈表中，元素並非靠在一起的，你無法迅速計算出第五個元素的內存地址，而必須先訪問第一個元素以獲取第二個元素的地址，再訪問第二個元素以獲取第三個元素的地址，以此類推，直到訪問第五個元素。

寫了這麼多，可我還是感覺和他們不太熟......