一段回憶
曾幾何時(shí)，我是一個(gè)懵懵懂懂的寫(xiě)CRUD寫(xiě)到飛起的小菜鳥(niǎo)胆萧，當(dāng)時(shí)我最大的優(yōu)勢(shì)就是業(yè)務(wù)bug比別人要少庆揩，總是很多人夸我細(xì)心耐心，也能得到別人的賞識(shí)跌穗《┥危可是我自己從來(lái)沒(méi)有成就感，總是覺(jué)得內(nèi)心缺少了點(diǎn)什么蚌吸，總是覺(jué)得身邊這個(gè)是大神锈拨，那個(gè)也是大神，總是感覺(jué)自己在仰望著別人套利，我不想在渾渾噩噩間變成一只老菜鳥(niǎo)推励，我也希望自己能發(fā)點(diǎn)光鹤耍，也能點(diǎn)亮一點(diǎn)別人的道路。
以前提到數(shù)據(jù)結(jié)構(gòu)验辞，提到源碼等這些稿黄，我總是一臉羨慕的看著別人侃侃而談，其實(shí)心里也想變成那樣的人跌造，可是真要去學(xué)又總是給自己找各種各樣的理由去推脫杆怕，還有就是潛意識(shí)里覺(jué)得那些知識(shí)高深莫測(cè)且枯燥，我能學(xué)會(huì)嗎壳贪？逃避著陵珍、恐懼著。
直到18年的某一場(chǎng)面試违施，從頭到尾都聊的非常好互纯，薪資也談的差不多，最后別人忽然想起來(lái)問(wèn)我熟不熟悉數(shù)據(jù)結(jié)構(gòu)磕蒲，常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)有哪些留潦，能不能手寫(xiě)一個(gè)出來(lái)，至今都記得那是一次多么羞愧的否認(rèn)三連辣往，不熟悉不清楚不會(huì)寫(xiě)兔院。那人笑著跟我說(shuō)沒(méi)關(guān)系，就是回去后再也沒(méi)等到通知站削。
消除恐懼的最好辦法就是面對(duì)恐懼坊萝，知恥而后勇，回去后我就下定決心要讓數(shù)據(jù)結(jié)構(gòu)存在我的技能庫(kù)里许起，不要再次成為我的軟肋十偶，沒(méi)想到真正去面對(duì)數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)的時(shí)候，發(fā)現(xiàn)它并沒(méi)有那么難街氢，反而在學(xué)習(xí)的過(guò)程中有種醍醐灌頂?shù)母杏X(jué)扯键，好像知道自己以前的空虛和不自信來(lái)自哪里了，好像感覺(jué)到我與大神的區(qū)別在哪里了珊肃。
提到這一茬荣刑，是因?yàn)槲以赾sdn立了flag，要寫(xiě)一個(gè)數(shù)據(jù)結(jié)構(gòu)的系列文章伦乔，中間又懶惰了幾天厉亏，今天正式敲鍵盤(pán)前，想起了那段記憶烈和，沒(méi)想到被自己寫(xiě)下來(lái)竟有種看網(wǎng)課的感覺(jué)爱只，哈哈，話(huà)不多說(shuō)了招刹，如果你有共鳴恬试，那么就讓我?guī)е黄鸾怄i新的姿勢(shì)吧窝趣，呸，解鎖新技能之——設(shè)計(jì)模式训柴。
什么是數(shù)據(jù)結(jié)構(gòu)哑舒？
數(shù)據(jù)結(jié)構(gòu)(data structure)是帶有結(jié)構(gòu)特性的數(shù)據(jù)元素的集合，它研究的是數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的物理結(jié)構(gòu)以及它們之間的相互關(guān)系幻馁，并對(duì)這種結(jié)構(gòu)定義相適應(yīng)的運(yùn)算洗鸵，設(shè)計(jì)出相應(yīng)的算法，并確保經(jīng)過(guò)這些運(yùn)算以后所得到的新結(jié)構(gòu)仍保持原來(lái)的結(jié)構(gòu)類(lèi)型仗嗦。簡(jiǎn)而言之膘滨，數(shù)據(jù)結(jié)構(gòu)是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合，即帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合稀拐』鸬耍“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系，分為邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)德撬。
上面是百度百科的定義贡翘，通常情況下，我們說(shuō)的數(shù)據(jù)結(jié)構(gòu)可以理解成是指一組數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)砰逻。
如上圖所示，數(shù)據(jù)是存儲(chǔ)在計(jì)算機(jī)的內(nèi)存里的泛鸟，在存儲(chǔ)時(shí)蝠咆，決定了數(shù)據(jù)順序和位置關(guān)系的便是“數(shù)據(jù)結(jié)構(gòu)”。 如果你還不明白什么是數(shù)據(jù)結(jié)構(gòu)的話(huà)北滥，我再來(lái)舉個(gè)生活中的例子刚操，在手機(jī)沒(méi)有出現(xiàn)之前我們存電話(huà)號(hào)碼都是在筆記本上手抄，這樣每次新記一個(gè)電話(huà)號(hào)碼都是在最后一行后面加再芋，然后找的時(shí)候就需要在所有的號(hào)碼中找某一個(gè)菊霜，查找很不方便。
后來(lái)當(dāng)有了手機(jī)之后济赎，你們?cè)倏醇眩忝看翁砑右粋€(gè)新聯(lián)系人時(shí)，系統(tǒng)會(huì)根據(jù)你的存的人名的姓氏拼音首字母自動(dòng)加到姓氏那一組司训，當(dāng)你要查找某一個(gè)人的時(shí)候构捡，你可以搜索，也可以直接點(diǎn)擊右邊的首字母去查找壳猜，效率大大提高勾徽，微信聯(lián)系人的存儲(chǔ)結(jié)構(gòu)也是這樣，你們可以看一下统扳。 舉這個(gè)例子喘帚，是要你明白兩件事畅姊，第一個(gè)就是電話(huà)號(hào)碼存在筆記本或者存在手機(jī)上，這種存儲(chǔ)結(jié)構(gòu)的順序和位置關(guān)系就是“數(shù)據(jù)結(jié)構(gòu)”吹由。選擇合適的數(shù)據(jù)結(jié)構(gòu)若未，不但可以提高內(nèi)存的使用率，也可以提高查找的效率溉知。查找效率就是指算法陨瘩，數(shù)據(jù)結(jié)構(gòu)是為算法而生，當(dāng)然我們這里主要講數(shù)據(jù)結(jié)構(gòu)级乍，所以算法就不展開(kāi)多說(shuō)了舌劳。
數(shù)據(jù)結(jié)構(gòu)分類(lèi)
數(shù)據(jù)結(jié)構(gòu)分為邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。
邏輯結(jié)構(gòu)：指數(shù)據(jù)元素之間邏輯關(guān)系的數(shù)據(jù)結(jié)構(gòu)玫荣，這里的邏輯關(guān)系是指數(shù)據(jù)元素之間的前后間關(guān)系甚淡，與數(shù)據(jù)在計(jì)算機(jī)中的存儲(chǔ)位置無(wú)關(guān)。
物理結(jié)構(gòu)：指數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)存儲(chǔ)空間中的存放形式稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu)捅厂，也叫做存儲(chǔ)結(jié)構(gòu)贯卦。
數(shù)據(jù)的邏輯結(jié)構(gòu)主要分為線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)。
線(xiàn)性結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)的元素之間存在一對(duì)一線(xiàn)性關(guān)系焙贷，所有結(jié)點(diǎn)都最多只有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)撵割。常見(jiàn)的有數(shù)組、隊(duì)列辙芍、鏈表啡彬、棧。
非線(xiàn)性結(jié)構(gòu)：各個(gè)結(jié)點(diǎn)之間具有多個(gè)對(duì)應(yīng)關(guān)系故硅，一個(gè)結(jié)點(diǎn)可能有多個(gè)直接前趨結(jié)點(diǎn)和多個(gè)直接后繼結(jié)點(diǎn)庶灿。常見(jiàn)的有多維數(shù)組、廣義表吃衅、樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)等往踢。
數(shù)據(jù)的物理結(jié)構(gòu)（以后我都統(tǒng)一稱(chēng)存儲(chǔ)結(jié)構(gòu)），表示數(shù)據(jù)元素之間的邏輯關(guān)系徘层，一種數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)根據(jù)需要可以表示成多種存儲(chǔ)結(jié)構(gòu)峻呕，常用的存儲(chǔ)結(jié)構(gòu)有：
順序存儲(chǔ)：存儲(chǔ)順序是連續(xù)的，在內(nèi)存中用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線(xiàn)性表的各個(gè)數(shù)據(jù)元素惑灵。
鏈?zhǔn)酱鎯?chǔ)：在內(nèi)存中的存儲(chǔ)元素不一定是連續(xù)的山上，用任意地址的存儲(chǔ)單元存儲(chǔ)元素，元素節(jié)點(diǎn)存放數(shù)據(jù)元素以及通過(guò)指針指向相鄰元素的地址信息英支。
索引存儲(chǔ)：除建立存儲(chǔ)結(jié)點(diǎn)信息外佩憾，還建立附加的索引表來(lái)標(biāo)識(shí)節(jié)點(diǎn)的地址。索引表由若干索引項(xiàng)組成。
散列存儲(chǔ)：又稱(chēng)Hash存儲(chǔ)妄帘，由節(jié)點(diǎn)的關(guān)鍵碼值決定節(jié)點(diǎn)的存儲(chǔ)地址楞黄。
常用的數(shù)據(jù)結(jié)構(gòu)
- 數(shù)組（Array）
- 隊(duì)列（Queue）
- 鏈表（Linked List）
- 棧（Stack）
- 樹(shù)（Tree）
- 散列表（Hash）
- 堆（Heap）
- 圖（Graph）
下面我們來(lái)先對(duì)這幾個(gè)數(shù)據(jù)結(jié)構(gòu)有個(gè)大概的印象。
數(shù)組（Array）
數(shù)組是最簡(jiǎn)單抡驼、使用最頻繁的一種數(shù)據(jù)結(jié)構(gòu)鬼廓。它一種線(xiàn)性表數(shù)據(jù)結(jié)構(gòu)，用一組連續(xù)的內(nèi)存空間來(lái)存儲(chǔ)一組相同類(lèi)型的數(shù)據(jù)致盟。
如上圖所示碎税，數(shù)據(jù)是按照順序存儲(chǔ)在內(nèi)存的連續(xù)空間內(nèi)，arr后面的[]代表下標(biāo)馏锡，由于數(shù)據(jù)是存儲(chǔ)在連續(xù)空間內(nèi)的雷蹂，所以每個(gè)數(shù)據(jù)的內(nèi)存地址(在內(nèi)存上的位置)都可以通過(guò)數(shù)組下標(biāo)計(jì)算出來(lái)，從而可以直接訪(fǎng)問(wèn)目標(biāo)數(shù)據(jù)杯道，達(dá)到隨機(jī)訪(fǎng)問(wèn)的目的匪煌。
隊(duì)列（Queue）
隊(duì)列也是一種非常基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)党巾，其特點(diǎn)是先入先出萎庭，也就是我們常聽(tīng)到的FIFO（First in First Out），即操作數(shù)據(jù)是從兩端進(jìn)行的齿拂。
上圖就是生活中常見(jiàn)的使用隊(duì)列場(chǎng)景驳规，為了更方便大家理解，我再畫(huà)一個(gè)入隊(duì)列署海，出隊(duì)列的示意圖达舒，加深大家對(duì)隊(duì)列的印象。
鏈表（Linked List）
鏈表是一種物理存儲(chǔ)單元上非連續(xù)叹侄，非順序的存儲(chǔ)結(jié)構(gòu)。鏈表有一系列節(jié)點(diǎn)組成昨登，所謂節(jié)點(diǎn)就是指鏈表中的每一個(gè)元素趾代，每個(gè)節(jié)點(diǎn)包含兩個(gè)數(shù)據(jù)，一個(gè)是存儲(chǔ)元素的數(shù)據(jù)域（值）丰辣，另一個(gè)是存儲(chǔ)下一個(gè)節(jié)點(diǎn)地址的指針域撒强。
通俗點(diǎn)說(shuō)，鏈表數(shù)據(jù)一般都是分散存儲(chǔ)于內(nèi)存中 的笙什，無(wú)須存儲(chǔ)在連續(xù)空間內(nèi)飘哨。這樣大家可能還不能直觀的感受鏈表的非連續(xù)，我再畫(huà)一張圖：
假設(shè)上圖中100-108是一塊內(nèi)存中連續(xù)地址的內(nèi)存分布琐凭，假設(shè)101芽隆、103、106、107這幾個(gè)內(nèi)存地址都已經(jīng)存儲(chǔ)數(shù)據(jù)了胚吁，那剩下的100牙躺、102、104腕扶、105孽拷、108是不是就浪費(fèi)呢，答案是否定的半抱，我們可以使用鏈表的方式存儲(chǔ)數(shù)據(jù)脓恕。
棧（Stack）
棧也是一種數(shù)據(jù)呈線(xiàn)性排列的數(shù)據(jù)結(jié)構(gòu)，和上面的隊(duì)列相反窿侈，棧的特點(diǎn)先進(jìn)后出炼幔、后進(jìn)先出，就是常說(shuō)的LIFO（Last in First Out）棉磨。
作者大學(xué)畢業(yè)時(shí)去當(dāng)了兩年兵江掩，在部隊(duì)里面給彈匣裝子彈時(shí)就類(lèi)似棧的入棧操作，射擊時(shí)相當(dāng)于出棧操作乘瓤。（為了證明我拿過(guò)真槍?zhuān)乓粡堊髡弋?dāng)年的靚照給你們欣賞一下环形，哈哈。不過(guò)你們也不用著急衙傀，如果你們玩過(guò)玩具槍?zhuān)瑧?yīng)該也能稍微感受一下抬吟，嘿嘿）
防止大家嫉妒我的容顏，還是畫(huà)圖來(lái)說(shuō)明一下棧的入棧出棧操作统抬。
樹(shù)（Tree）
樹(shù)形結(jié)構(gòu)是一種層級(jí)式的數(shù)據(jù)結(jié)構(gòu)火本，由頂點(diǎn)（節(jié)點(diǎn)）和連接它們的邊組成。
數(shù)的結(jié)構(gòu)特點(diǎn)是：
每個(gè)節(jié)點(diǎn)有零個(gè)或多個(gè)子節(jié)點(diǎn)聪建；
沒(méi)有父節(jié)點(diǎn)的節(jié)點(diǎn)稱(chēng)為根節(jié)點(diǎn)钙畔；
每一個(gè)非根節(jié)點(diǎn)有且只有一個(gè)父節(jié)點(diǎn)；
除了根節(jié)點(diǎn)外金麸，每個(gè)子節(jié)點(diǎn)可以分為多個(gè)不相交的子樹(shù)擎析。
我們平時(shí)用到最多的就是二叉樹(shù)，我也以二叉樹(shù)來(lái)為例挥下，先看一下樹(shù)結(jié)構(gòu)：
二叉樹(shù)有幾下特點(diǎn)：
每個(gè)結(jié)點(diǎn)最多有兩顆子樹(shù)揍魂，結(jié)點(diǎn)的度最大為2。
左子樹(shù)和右子樹(shù)是有順序的棚瘟，次序不能顛倒现斋。
即使某結(jié)點(diǎn)只有一個(gè)子樹(shù)，也要區(qū)分左右子樹(shù)偎蘸。
個(gè)結(jié)點(diǎn)的值均大于其左子樹(shù)上任意一個(gè)結(jié)點(diǎn)的值庄蹋。比如 點(diǎn)的值瞬内。結(jié)點(diǎn)100大于其左子樹(shù)上的30，18和16蔓肯。
每個(gè)結(jié)點(diǎn)的值均小于其右子樹(shù)上任意 一個(gè)結(jié)點(diǎn)的值遂鹊。比如結(jié)點(diǎn) 100 小于其右子樹(shù)上的 120、130 和 135蔗包。
散列表（Hash）
散列表又叫哈希表秉扑，存儲(chǔ)的是由鍵(key)和值(value)組 成的數(shù)據(jù)，根據(jù)鍵直接訪(fǎng)問(wèn)存儲(chǔ)在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)调限。
從圖中可以看出舟陆，左邊很明顯是個(gè)數(shù)組，數(shù)組的每個(gè)成員包括一個(gè)指針耻矮，指向一個(gè)鏈表的頭秦躯，當(dāng)然這個(gè)鏈表可能為空，也可能元素很多裆装。我們根據(jù)元素的一些特征把元素分配到不同的鏈表中去踱承，也是根據(jù)這些特征，找到正確的鏈表哨免，再?gòu)逆湵碇姓页鲞@個(gè)元素茎活。哈希表查找數(shù)據(jù)的公式為：記錄的存儲(chǔ)位置=f(key)這里的對(duì)應(yīng)關(guān)系 f 成為散列函數(shù)，又稱(chēng)為哈希 (hash函數(shù))琢唾，而散列表就是把Key通過(guò)一個(gè)固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個(gè)整型數(shù)字载荔，然后就將該數(shù)字對(duì)數(shù)組長(zhǎng)度進(jìn)行取余，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)采桃，將value存儲(chǔ)在以該數(shù)字為下標(biāo)的數(shù)組空間里懒熙，這種存儲(chǔ)空間可以充分利用數(shù)組的查找優(yōu)勢(shì)來(lái)查找元素，所以查找的速度很快普办。我們將在后面詳細(xì)講解哈希表數(shù)據(jù)結(jié)構(gòu)工扎。
堆（Heap）
堆比較特殊，是一種圖的樹(shù)形結(jié)構(gòu)衔蹲。被用于實(shí)現(xiàn)“優(yōu)先隊(duì)列”(priority queues)定庵，優(yōu)先隊(duì)列是一種數(shù)據(jù)結(jié)構(gòu)，可以自由添加數(shù)據(jù)踪危，但取出數(shù)據(jù)時(shí)要從最小值開(kāi)始按順 序取出。在堆的樹(shù)形結(jié)構(gòu)中猪落，各個(gè)頂點(diǎn)被稱(chēng)為“結(jié)點(diǎn)”(node)贞远，數(shù)據(jù)就存儲(chǔ)在這些結(jié)點(diǎn)中。
只要滿(mǎn)足下面兩個(gè)特點(diǎn)的樹(shù)形結(jié)構(gòu)就是堆：
堆是一個(gè)完全二叉樹(shù)（所謂完全二叉樹(shù)就是除了最后一層其他層的節(jié)點(diǎn)個(gè)數(shù)都是滿(mǎn)的）笨忌。
堆中每一個(gè)節(jié)點(diǎn)的值都必須大于等于或者小于其子樹(shù)中每一個(gè)節(jié)點(diǎn)的值蓝仲。
下面我們看一下堆的結(jié)構(gòu)：
上面其實(shí)叫大頂堆，如果每一個(gè)節(jié)點(diǎn)小于子樹(shù)中每個(gè)節(jié)點(diǎn)的值，那就叫小頂堆袱结。
圖（Graph）
圖是相對(duì)復(fù)雜的一種數(shù)據(jù)結(jié)構(gòu)亮隙，由頂點(diǎn)和連接每對(duì)頂點(diǎn)的邊所構(gòu)成的圖形就是圖。
我們先來(lái)看圖：
上圖中的圓圈叫作“頂點(diǎn)”(Vertex垢夹，也叫“結(jié)點(diǎn)”)溢吻，連接頂點(diǎn)的線(xiàn)叫作“邊”（Edge）。也就是說(shuō)果元，由頂點(diǎn)和連接每對(duì)頂點(diǎn)的邊所構(gòu)成的圖形就是圖促王。 圖按照頂點(diǎn)指向的方向可分為無(wú)向圖和有向圖，像我上面的就叫無(wú)向圖而晒。 圖在存儲(chǔ)數(shù)據(jù)上有著比較復(fù)雜和高效的算法蝇狼，分別有鄰接矩陣 、鄰接表倡怎、十字鏈表迅耘、鄰接多重表、邊集數(shù)組等存儲(chǔ)結(jié)構(gòu)监署。常見(jiàn)的圖遍歷算法就是廣度優(yōu)先算法和深度優(yōu)先算法颤专。
總結(jié)
好了，上面我們用圖形并茂的方式介紹了什么是數(shù)據(jù)結(jié)構(gòu)以及常用的數(shù)據(jù)結(jié)構(gòu)焦匈，相信你對(duì)這些數(shù)據(jù)結(jié)構(gòu)的概念已經(jīng)有了一點(diǎn)粗略的印象血公。后面的文章我將對(duì)每一種數(shù)據(jù)結(jié)構(gòu)展開(kāi)進(jìn)行詳細(xì)的講解，并教你怎樣手寫(xiě)實(shí)現(xiàn)這些數(shù)據(jù)結(jié)構(gòu)缓熟。
原創(chuàng)不易累魔，如果你覺(jué)得本文還不錯(cuò)的話(huà)，還麻煩您幫忙點(diǎn)個(gè)在看够滑，或者幫忙轉(zhuǎn)發(fā)一下垦写，這比夸我?guī)浕蛘呓o我錢(qián)還更讓我激動(dòng)，謝謝大家彰触！
