Ox-Blog

• 插入新元素較快且容易
  • 一個數據結構的使用是簡單還是複雜，主要分成兩個角度，一是插入、二是移除，這方面在後續介紹各種數據結構的文章會更進一步詳細談及。但簡單而言，大部分線性數據結構在插入新元素上都會比非線性來的簡單，通常都是O(1)的時間複雜度，可以簡單理解成有一群人在排隊，你要加入這條隊的話，你只需要走到隊伍的最後即可。
    

• 節省容量空間
  • 線性數據結構裡的元素與元素之間比起非線性數據結構更加緊密，其原理很好理解，線性數據不像非線性數據需要儲存各個元素之間的連接資訊，例如a元素和b、c、d元素是否有連接等，這些都要記憶體空間來儲存，像SQL數據庫就是很好的例子，無索引的表格就是線性，而有索引的表格就是非線性，有索引的表格需要的容量空間就可多出四到五分之一。
    
    而當中的佼佼者就是最傳統的陣列(Array)，基本上不會浪費任何一點的記憶體空間。
    

• 方便於迭代
  • 如上所述，線性數據結構的特點在於元素們會以前後順序來連接彼此，因此線性數據結構能夠很好實現，從第一個最後一個逐一調用。
    

• 移除特定元素慢且複雜
  • 移除一個線性數據結構的特定元素是非常困難的事情，原因有二，一是線性數據結構對「同特徵數據」的儲存大多是容許的，而這就導致了線性數據結構在移除特定元素時很難鎖定應該被移除的目標。
    
    例如有一群人在排隊，你要移除「那位黃色衣服的大叔」，但如果這條隊伍中有多於一個「穿黃色衣服」、「符合大叔年紀」的人，那該移除誰呢? 此時大多程式語言會直接移除符合條件的所有人，但這結果未必會是設計想要的。
    
    
    
  • 原因之二為大多線性數據結構在移除特定元素時都要迭代所有已有的元素，時間複雜度通常為O(n)，也就代表比起插入元素會花n倍多的時間。
    
    大多線性數據結構在移除特定元素時，都需要透過「元素的特徵比對」來辨識需要被移除的元素。但在線性數據結構裡，要進行特徵比對就必然要迭代所有已有的元素。
    
    例如有一群人在排隊，你要移除「會說意大利語的大叔」，那你要如何一眼便分析出一個大叔是會說意大利語呢? 答案是做不到，人做不到，同樣的電腦也做不到，電腦必須要逐個人詢問並實測他們的意大利語能力，才能辨識出要被移除的目標。
    

• 搜尋特定元素緩慢
  • 正如上述所及，如果要辨識特定元素的話，線性數據結構必須要迭代每一個元素並進行比對，因此如果設計者需要取得並使用某一元素，就最少需要O(n)的時間複雜度。
    
    因此線性數據結構非常不便於完成「是否已存在」、「找出並使用」的任務。

非線性

非線性數據結構是指在一個數據集合裡，各個元素(Element)以不同且更複雜的條件連接彼此，而且每一個元素與之連接的他元素數量不一。
非線性數據結構主要分成兩種類型，分別是樹狀結構和圖狀結構，差別在於樹結構的數據會是分層式的(後續文章會詳解)，離入口越遠的層級會有越多元素。而圖狀結構則不會有層級。

像是C++裡的std::map或C#裡的SortedDictionary都是樹狀結構的數據容器，由於非線性結構比較複雜，這裡主要是簡單介紹一下，其更具體的運行邏輯會在之後的其他文章再介紹。

• 移除特定元素快且簡單
  • 和線性的數據結構相反，對線性數據結構而言，移除特定元素更容易。原因在於，如上文所及，非線性數據結構裡元素之間的連接條件通常會與元素的部分特徵有關，例如經典的二元樹( B-Tree )裡便需要辨識數字/字元是大於還是小於第一個元素，以決定新元素要放在左子樹還是右子樹。
    
    因此，通常非線性數據結構都不會接受同特徵的新元素，而且能遵循元素之間的連接方式相對快速的搜尋到有該特徵的新元素，而不需要歷遍所有的元素，辨識過程通常是O(log n)，部分專門化的非線性數據結構甚至可以達到O(1)搜尋，例如之後會介紹的雜湊表(hash table)便是插入、移除和搜尋都能夠以O(1)的速度來完成。
    

• 搜尋特定元素快速
  • 上一點也有提到，由於元素與元素之間的連接方向是以特定的特徵決定的，因此，能夠遵循其連接的方向來達成快速搜索的目的。
    

• 能滿足的目的多元
  • 非線性數據結構能以各種不同的條件來安排元素之間的連接，而且單一元素能連接的他元素數量不定，能夠透過這個特性來滿足不同的計算目的。但這部分較為複雜，會在之後的其他文章續一介紹。

• 插入新元素較慢
  • 這一點也和線性數據結構相反，對非線性數據結構而言，要加入新元素至數據容器時，元素都要完成數據特徵檢查並和部分其他元素比對，才能決定新元素該放置的位置。
    
    一樣以經典的非線性數據結構二元樹( B-Tree )為例，插入新元素時需要辨識數字/字元是大於還是小於第一個元素，以決定新元素要放在左子樹還是右子樹，而如果子樹裡已經有元素，那還要再一次和子樹裡的元素比較，再決定要前往子樹的左次子樹還是右次子樹。
    
    結果便是插入新元素時通常都需要多次的檢測，尤其是當一個容器裡已經有大量的數據時，插入的時間複雜度通常會是O(log n)。
    

• 容量空間花費大
  • 一樣與線性數據結構相反，非線性數據結構內元素之間較不緊密，部分特定非線性數據結構如雜湊表(hash table)還會預留大量空間來方便未來的新元素插入，自然需要的容量空間就會比線性來得大不小。
    

• 不方便於迭代
  • 大多數的非線性數據結構裡各個元素都不會存在前後關係，不像線性的一條人龍，非線性數據結構更像是一個無序的人群，要完成從第一個最後一個逐一調用，一般的程式語言還是會有設計預設且高度優化的迭代器，但效果必然還是會比線性結構來的慢。這部分和數據導向編程的一些概論有關，以後有機會可以進一步談。