數組，鏈表，二叉樹，這些是為了解決什麼問題而出現的呢？

最近開始真正的複習一波數據結構了，然後也更新了一波自己的學習方法，於是覺得奇怪，為什麼會有數組這種東西呢？鏈表呢？二叉樹呢？個人覺得凡事東西/概念出現了一定是為了解決什麼問題而出現的，就像數據結構的概念的出現其實就是絕對的算力跟不上數據的級別，如果很大很大的數據在很短（可以忽略不計）的時間內被處理，個人認為數據結構這種東西也不會出現。

扯遠了，數組呢？why?數組會出現？

在計算機科學中，數組數據結構（英語：array data structure），簡稱數組（英語：Array），是由相同類型的元素（element）的集合所組成的數據結構，分配一塊連續的內存來存儲。利用元素的索引（index）可以計算出該元素對應的存儲地址。-----wiki百科

而且據我google的結果，數組的出現其實是為了解決計算機定址問題，但是現在數組已經成為了人們日常使用的數據結構之一了。

what?數值有什麼用呢？

其實數組的用處還是蠻大的，當數據對象存儲在數組中時，個別對象通常藉由非負整數的索引變數來選取。索引也稱為下標，可將數組的值對應到存儲對象。

簡單來說就是元素標識和計算（矩陣其實也是數組的一種）。

how? 數組是怎麼起作用的呢？

數組的主要作用就是方便人們進行計算和標識相關的數據。

演算法的時間複雜度： 也稱演算法漸進時間複雜度，其實就是對某種演算法的時間增長率的一個表現。

遍曆數組的時間複雜度為O（1）,而插入的演算法時間複雜度為O（n）（每插入一個數移動的數字程序步的時間複雜度的數量級都為N），所以為O（n）。

why?為什麼鏈表會出現？

鏈表開發於1955-56，由當時所屬於蘭德公司（英語：RAND Corporation）的艾倫紐維爾（Allen Newell），克里夫肖（Cliff Shaw）和赫伯特西蒙（Herbert Simon）在他們編寫的信息處理語言（IPL）中做為原始數據類型所編寫。IPL被作者們用來開發幾種早期的人工智慧程序，包括邏輯推理機，通用問題解算器和一個計算機象棋程序。-----wiki百科

what? 鏈表是是什麼?（不涉及雙向鏈表，暫時直講單鏈表）

相對於數組來說，鏈表對數據插入和刪除的時間複雜度都低了很多，鏈表插入和刪除的時間複雜度都為O（1）,因此，在頻繁插入和刪除的數據中，鏈表有很大的優勢，但是遍歷又成了一個比較大的問題，因為鏈表的遍歷，相對較為麻煩，每次遍歷鏈表都是要從頭開始，那麼遍歷鏈表的時間複雜度為O（N)，另外因為多了一個指針，空間上，鏈表空間複雜度要稍微多一點。因此很難說，鏈表一定是有某種特定的用處，主要還是分問題情景，諸如要求，時間空間，大小之類的。

why?二叉樹是什麼？為什麼會出現？

二叉樹是一個連通的無環圖，並且每一個頂點的度不大於3。有根二叉樹還要滿足根節點的度不大於2。有了根節點之後，每個頂點定義了唯一的父節點，和最多2個子節點。然而，沒有足夠的信息來區分左節點和右節點。如果不考慮連通性，允許圖中有多個連通分量，這樣的結構叫做森林 ----wiki.

但是上面並沒有提到二叉樹為什麼會出現？

個人觀點：二叉樹的確是為了解決數組和鏈表都不太好解決的問題，而被人們發明的一種數據結構。

從數據結構的角度來講，很大程度上是因為當遇到實際問題中那種既需要多次查找又需要多次更改的數據的時候（比如資料庫），這個時候其實數組和鏈表都是不合適的，當然非要用也可以，但是從時間和空間複雜度上來講都沒有比較好的解決這個問題。

但是根據某大神的說法：其實就是對數組和鏈表取了一個折中的辦法，因為就查找和插入來說，無論是鏈表還是數組都是O(N)+O(1),但是二叉樹呢？O(logn)+O（logn）(這裡暫時先 不說最壞的情況，而且最壞的情況也無非是退化為順序表）

2O（logN）其實是比O（N）數量級要小很多的，所以才會出現這種數據結構。

但是問題還沒解決，其實不光是二叉樹,N叉樹的出現也是為了緩解這樣尷尬的局面，但是問題是，這樣的局面下N叉樹還是二叉樹其實意義都是一樣的，起碼從數量級上是如此的，至於N叉樹無非是人們在工程上對不同的問題發現好像N叉樹更好用而已。