《數據結構》這門課是計算機專業的核心課程，但往往卻讓人頭痛，因為比較抽象，當然了，也許你足夠聰明，并不覺得它有多難，但對我而言，是有點難度，后來我仔細想了想，到底哪里難？我得出這么個結論：長篇大論，缺乏圖表。現在的人都喜歡看電影，看電視劇，很少人還熱衷于看小說吧，密密麻麻的文字不如一些圖來得直觀。

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

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

一、大圈表示法

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

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

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

如果你還是不太明白大圈表示法，不用擔心，繼續往下看，會慢慢明白的。

二、動態數組（Dynamic Array）
接下去介紹最最基本的兩種數據結構，即動態數組和單向鏈表，其它數據結構其實都可以通過這兩者衍生出來。BTW：如果算法太簡單，我就不列出代碼，只稍微描述一下。

 
這就是一個最基本的動態數組，pData記錄了數組第一個元素的位置，Unit Size記錄了每個元素的大小，（這樣可以方便地找到第N個元素了）Unit Number記錄了元素的數目。

獲取數組中第N個元素，是很簡單的，無需多說。

但已知某位置，要插入一個元素，就稍微有點難，因為要挪動一些元素，如圖：

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

數組的大小不能很方便地調整，需要幾個步驟，如下圖所示：

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

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

下圖就是最簡單最一般的單向鏈表：

還有這種：

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

留一個終始標志，這個節點作為一個標志，不用于存儲數據，鏈表末尾指向這個節點，形成一個“環形鏈表”，這樣無論在鏈表的哪里插入新的元素，操作都一致了，不必判斷頭和尾的特殊性。

數組的好處就是鏈表的壞處，數組的壞處就是鏈表的好處，請看：

因為需要從頭開始找，沒辦法像數組那樣直接跳到那個地址。而插入元素，就比數組方便了，如果你已經得知了要插入的地址的話，不過還要注意哦，是“后插入”（Insert After）：

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

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

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

（未完待續……）