怎麼理解資料結構？它有什麼用

前言

借用一句很出名的話：程式=演算法+資料結構。從這句話中，我們可以感受到資料結構的地位和重要性。今天咱們不聊這句話背後所包含的意義，咱們只聊資料結構。

說實話，寫下Hello World的時，到後來很長一段時間，我都在質疑資料結構的重要性？這玩意有啥用啊？什麼棧、佇列、二叉樹？有啥用，還沒有我寫兩行程式碼有用。

今天，咱們就來好好看一看資料結構存在的意義。

文章所用demo，是Java語言，但是放心，思想都是一樣的、

出場角色

正文開始，還是有必要做一個小小的自我介紹。

MDove

：快吃不上的Androider，系列文章的逗哏Coder。

小A

：系列文章的彩筆擔當，專業級捧哏，剛入坑小Javaer。

正文

陣列

小A

：我說MDove，今天有人給我說讓我好好學習資料結構，對我以後有幫助。我就不大明白，大學裡教的那些佇列，棧啥的？有毛線用？我寫程式碼，Ctrl+C/V。我學那些玩意幹啥！

MDove

：那還不是為了裝那啥…裝…作很厲害的樣子…其實資料結構不是對你以後有幫助，而是從你開始寫程式碼時就有幫助，而且一直貫穿你的程式碼生涯！

小A

：啊？我怎麼沒有感覺到對我有用呢？

MDove

：用沒用過陣列？

小A

：這個還真用過…

MDove

：陣列就是我們寫程式碼接觸最早的資料結構。用法也很簡單：

int［］ x = newint［10］；

MDove

：那現在問你一個問題，我們都知道使用陣列，需要先new一個指定長度的陣列。那我如果想不指定長度，而且希望可以動態的變長或者縮短怎麼辦？

小A

：我知道，用List！

List x =new ArrayList（）；

x。add（666）；

MDove

：OK，既然你提到了List，那麼你知道ArrayList是實現的麼？

小A

：不知道啊…

MDove

：有時間你去看一下它的原始碼，它的底層就是用陣列實現的。當我們呼叫add方法是，ArrayList為我們初始化陣列，在即將越界的時候，使用copy的方式，幫我們對陣列進行擴容。所以它的本質依靠了陣列。

連結串列出場

MDove

：我們都知道，陣列不善於刪除/增加某個下標的元素，因為需要移動其下邊後邊的所有元素。那現在我想高效的刪除/增加怎麼辦？

小A

：我覺得，可以透過更快的演算法來定位到需要移動的下標。

MDove

：這是一種方案，屬於用更高效的演算法。但是再快的演算法也做不到一下子就完成定位和移動。我現在需要一個時間複雜度O（1）的方案，怎麼辦？

小A

：這個…我真不知道。

MDove

：另一個數據結構就被創造出來了，連結串列。因為連結串列結構的特殊性，所以對於刪除/增加。連結串列只需要改變next變數的指向即可。所有它可以做到O（1）。是不是能夠感受到資料結構的作用了？

小A

：這種情況下使用連結串列，哎，你別說，我好像有些感覺了。特定業務下，為了完成特定的操作，使用特定的資料結構。是不是這樣？

MDove

：沒錯，我們日常所謂的用不到資料結構，只是因為程式語言本身已經幫我們封裝好了資料結構。如果我們去看一看這些Api的原始碼實現，我們就會發現大量的資料結構思想。

MDove

：在比如說：HashMap的原理，就是使用了陣列加連結串列。但是隨著業務的負責，這種結構已經不大能夠滿足業務需求了。因為隨著衝突的增多，僅靠連結串列+連結串列法的思想根本沒辦法應對大量的衝突，因此會導致很嚴重的效能問題。所以在JDK1。8之後，HashMap增加了紅黑樹的思想，借用紅黑樹的自平衡的屬性，保證了即使大量衝突也不會降低搜素效能。

小A

：平時開發只調用Api，完全沒有考慮它們背後的實現。看樣子是自己井底之蛙了。

思考

MDove

：這並不怪你，畢竟Api本身就是封裝出來供我們開發者呼叫的。但是，作為開發者，如果我們一味的只調用Api，那有什麼意義？呼叫Api誰不會？現在IDE這麼強大，GitHub，百度/谷歌，Ctrl+C/V，誰不會寫程式碼？

MDove

：如果某一天，沒有了搜尋引擎，沒有了GitHub。我們就沒辦法寫程式碼了？當然這一天肯定不會來臨。沒錯這一天不會來臨，但是你不感覺到焦慮麼？

小A

：臥槽，你說的我冷汗都冒了出來。好像是這個道理，我除了吊Api什麼都不會。

MDove

：嘿嘿嘿，沒事。你越關注我，我越聊一些深入的話題。你越督促我，我越提高文章質量~

小A