《數(shù)據(jù)結(jié)構(gòu)》這門課是計(jì)算機(jī)專業(yè)的核心課程，但往往卻讓人頭痛，因?yàn)楸容^抽象，當(dāng)然了，也許你足夠聰明，并不覺得它有多難，但對(duì)我而言，是有點(diǎn)難度，后來我仔細(xì)想了想，到底哪里難？我得出這么個(gè)結(jié)論：長(zhǎng)篇大論，缺乏圖表。現(xiàn)在的人都喜歡看電影，看電視劇，很少人還熱衷于看小說吧，密密麻麻的文字不如一些圖來得直觀。

另外，我們大多數(shù)人是做應(yīng)用的，不是做研究的，所以我們只需要知道2+3=5，而不需要知道a+b=c。所以我就不深入理論，再說自己也沒那個(gè)能力。

好，接下去我就用最一般的例子，最通俗易懂的圖，算法和盡量少的文字，描述某作者需要長(zhǎng)篇大論方可完成教材。

一、大圈表示法

面試時(shí)候如果讓你寫一個(gè)算法，要求復(fù)雜度為Ο(n)，你明白是什么意思嗎？說起數(shù)據(jù)結(jié)構(gòu)，就先提一下這個(gè)表示法吧，后面會(huì)用到。

“Ο”，其實(shí)不是英文的“O”，它是個(gè)希臘字母，發(fā)音大概是“歐麥克隆”，所以我們一般說“圈”而不是跟英文的O一樣的發(fā)音。簡(jiǎn)單地說，大圈表示法是一種用于表示算法復(fù)雜度數(shù)量級(jí)的方法。要精確描述這個(gè)表示法，很難，不過我們不需要懂那么精確，只要八九不離十就可以了。下面我列個(gè)表，復(fù)雜度從低到高，大家就知道其意義：

另外還有個(gè)叫指數(shù)復(fù)雜度，這里不提，因?yàn)橐姷脤?shí)在太少，“指數(shù)級(jí)遞增”本身就是一個(gè)很夸張的形容詞，我們也要避免這種復(fù)雜度的出現(xiàn)。還需要說明的一點(diǎn)是大圈表示法是時(shí)間遞增數(shù)量級(jí)的表示方法，注意“遞增”兩個(gè)字，所以并不是說復(fù)雜度為Ο(1)的算法消耗的時(shí)間一定比復(fù)雜度為Ο(n)的算法少。

如果你還是不太明白大圈表示法，不用擔(dān)心，繼續(xù)往下看，會(huì)慢慢明白的。

二、動(dòng)態(tài)數(shù)組（Dynamic Array）
接下去介紹最最基本的兩種數(shù)據(jù)結(jié)構(gòu)，即動(dòng)態(tài)數(shù)組和單向鏈表，其它數(shù)據(jù)結(jié)構(gòu)其實(shí)都可以通過這兩者衍生出來。BTW：如果算法太簡(jiǎn)單，我就不列出代碼，只稍微描述一下。

 
這就是一個(gè)最基本的動(dòng)態(tài)數(shù)組，pData記錄了數(shù)組第一個(gè)元素的位置，Unit Size記錄了每個(gè)元素的大小，（這樣可以方便地找到第N個(gè)元素了）Unit Number記錄了元素的數(shù)目。

獲取數(shù)組中第N個(gè)元素，是很簡(jiǎn)單的，無需多說。

但已知某位置，要插入一個(gè)元素，就稍微有點(diǎn)難，因?yàn)橐矂?dòng)一些元素，如圖：

刪除元素跟這個(gè)也類似，也是需要挪一挪后面的元素，只不過是往前挪。

數(shù)組的大小不能很方便地調(diào)整，需要幾個(gè)步驟，如下圖所示：

代碼我就不寫了，大概就是new，memcpy，delete這幾個(gè)步驟。

三、單向鏈表（Singly-linked List）

下圖就是最簡(jiǎn)單最一般的單向鏈表：

還有這種：

多一個(gè)Tail指針，好處就是能很方便地找到末尾，然后在末尾插入新的元素什么的。還有這種也比較常見：

留一個(gè)終始標(biāo)志，這個(gè)節(jié)點(diǎn)作為一個(gè)標(biāo)志，不用于存儲(chǔ)數(shù)據(jù)，鏈表末尾指向這個(gè)節(jié)點(diǎn)，形成一個(gè)“環(huán)形鏈表”，這樣無論在鏈表的哪里插入新的元素，操作都一致了，不必判斷頭和尾的特殊性。

數(shù)組的好處就是鏈表的壞處，數(shù)組的壞處就是鏈表的好處，請(qǐng)看：

因?yàn)樾枰獜念^開始找，沒辦法像數(shù)組那樣直接跳到那個(gè)地址。而插入元素，就比數(shù)組方便了，如果你已經(jīng)得知了要插入的地址的話，不過還要注意哦，是“后插入”（Insert After）：

有“后插入”，那就有“前插入”（Insert Before），兩者對(duì)單向鏈表來說真的不一樣，下圖描述了“前插入”：

由于指針向后不向前，我們不知道要插入位置的前一個(gè)節(jié)點(diǎn)是什么，只能從頭找，所以比較麻煩。

至于鏈表大小的重新調(diào)整，和數(shù)組相比如何呢？呃……我可沒說鏈表有大小限制吧？

（未完待續(xù)……）