圖解數據結構（1）——大圈表示法、動態數組和單向鏈表

《數據結構》這門課是計算機專業的核心課程，但每每卻讓人頭痛，由於比較抽象，固然了，也許你足夠聰明，並不以爲它有多難，但對我而言，是有點難度，後來我仔細想了想，到底哪裏難？我得出這麼個結論：長篇大論，缺少圖表。如今的人都喜歡看電影，看電視劇，不多人還熱衷於看小說吧，密密麻麻的文字不如一些圖來得直觀。html

另外，咱們大多數人是作應用的，不是作研究的，因此咱們只須要知道2+3=5，而不須要知道a+b=c。因此我就不深刻理論，再說本身也沒那個能力。面試

好，接下去我就用最通常的例子，最通俗易懂的圖，算法和儘可能少的文字，描述某做者須要長篇大論方可完成教材。算法

1、大圈表示法數組

面試時候若是讓你寫一個算法，要求複雜度爲Ο(n)，你明白是什麼意思嗎？提及數據結構，就先提一下這個表示法吧，後面會用到。數據結構

「Ο」，其實不是英文的「O」，它是個希臘字母，發音大概是「歐麥克隆」，因此咱們通常說「圈」而不是跟英文的O同樣的發音。簡單地說，大圈表示法是一種用於表示算法複雜度數量級的方法。要精確描述這個表示法，很難，不過咱們不須要懂那麼精確，只要八九不離十就能夠了。下面我列個表，複雜度從低到高，你們就知道其意義：

另外還有個叫指數複雜度，這裏不提，由於見得實在太少，「指數級遞增」自己就是一個很誇張的形容詞，咱們也要避免這種複雜度的出現。還須要說明的一點是大圈表示法是時間遞增數量級的表示方法，注意「遞增」兩個字，因此並非說複雜度爲Ο(1)的算法消耗的時間必定比複雜度爲Ο(n)的算法少。

若是你仍是不太明白大圈表示法，不用擔憂，繼續往下看，會慢慢明白的。post

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

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

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

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

刪除元素跟這個也相似，也是須要挪一挪後面的元素，只不過是往前挪。

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

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

3、單向鏈表（Singly-linked List）指針

下圖就是最簡單最通常的單向鏈表：

還有這種：

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

留一個終始標誌，這個節點做爲一個標誌，不用於存儲數據，鏈表末尾指向這個節點，造成一個「環形鏈表」，這樣不管在鏈表的哪裏插入新的元素，操做都一致了，沒必要判斷頭和尾的特殊性。

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

由於須要從頭開始找，沒辦法像數組那樣直接跳到那個地址。而插入元素，就比數組方便了，若是你已經得知了要插入的地址的話，不過還要注意哦，是「後插入」（Insert After）：

有「後插入」，那就有「前插入」（Insert Before），二者對單向鏈表來講真的不同，下圖描述了「前插入」：

因爲指針向後不向前，咱們不知道要插入位置的前一個節點是什麼，只能從頭找，因此比較麻煩。

至於鏈表大小的從新調整，和數組相好比何呢？呃……我可沒說鏈表有大小限制吧？
做者：http://www.cppblog.com/guogangj/archive/2009/10/13/98476.htmlhtm