數據結構之----邏輯結構、物理結構

目前我們常見的數據結構分別有：
數組、鏈表、棧、隊列、哈希表、樹、堆、圖
而它們可以從 邏輯結構和物理結構兩個維度進行分類。

什么是邏輯結構？

邏輯結構是指數據元素之間的邏輯關系，而邏輯結構又分為線性結構和非線性結構兩大類。

什么是線性結構？

線性結構比較直觀，指數據在邏輯關系上呈線性排列，
如：
在數組和鏈表中，數據按照順序依次排列，體現了數據之間的線性關系。

什么是非線性結構？

非線性結構則與線性結構相反，指數據在邏輯關系上呈非線性排列，
如：
在圖中，數據由節點和邊構成，反映了復雜的網絡關系。
而在樹中，數據從頂部向下按層次排列，表現出祖先與后代之間的派生關系。

而非線性數據結構又可以進一步被劃分為樹形結構和網狀結構。

• 線性結構：數組、鏈表、隊列、棧、哈希表。元素之間是一對一的順序關系。
• 樹形結構：樹、堆、哈希表。元素之間是一對多的關系。
• 網狀結構：圖。元素之間是多對多的關系。

什么是物理結構？

物理結構指的是數據在計算機內存中的存儲方式，可分為連續空間存儲（數組）和分散空間存儲（鏈表）。
它從底層決定了數據的訪問、更新、增刪等操作方法，同時在時間效率和空間效率方面呈現出互補的特點。

我們都知道所有數據結構都是基于數組、鏈表或二者的組合實現的。
如：
棧和隊列既可以使用數組實現，也可以使用鏈表實現。
而哈希表的實現可能同時包含數組和鏈表。

• 基于數組可實現：棧、隊列、哈希表、樹、堆、圖、矩陣、張量（維度 ≥ 3 的數組）等。
• 基于鏈表可實現：棧、隊列、哈希表、樹、堆、圖等。

基于數組實現的數據結構也被稱為靜態數據結構，這意味著此類數據結構在初始化后長度不可變。
相對應地，基于鏈表實現的數據結構被稱為動態數據結構，這類數據結構在初始化后，仍可以在程序運行過程中對其長度進行調整。

Q&A

為什么哈希表同時包含線性數據結構和非線性數據結構？

哈希表底層是數組，而為了解決哈希沖突，我們會使用鏈式地址：數組中每個桶指向一個鏈表，當鏈表長度超過一定閾值時，又可能被轉化為樹（通常為紅黑樹）。
從存儲的角度來看，哈希表的底層是數組，其中每一個桶槽位可能包含一個值，也可能包含一個鏈表或樹。因此，哈希表可能同時包含線性（數組、鏈表）和非線性（樹）數據結構。

基于數組實現的數據結構也被稱為“靜態數據結構”是否有歧義？因為棧也可以進行出棧和入棧等操作，這些操作都是“動態”的。

棧確實可以實現動態的數據操作，但數據結構仍然是“靜態”（長度不可變）的。盡管基于數組的數據結構可以動態地添加或刪除元素，但它們的容量是固定的。如果數據量超出了預分配的大小，就需要創建一個新的更大的數組，并將老數組的內容復制到新數組中。

在構建棧（隊列）的時候，未指定它的大小，為什么它們是“靜態數據結構”呢？

在高級編程語言中，我們無須人工指定棧（隊列）的初始容量，這個工作是由類內部自動完成的。例如，Java 的 ArrayList 的初始容量通常為 10 。另外，擴容操作也是自動實現的。